Detail předmětu

Diskrétní matematika

FIT-IDMAk. rok: 2022/2023

Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Booleovy algebry. Výroková a predikátová logika. Základní pojmy teorie grafů. Souvislost grafů. Podgrafy a morfismy grafů. Problém rovinnosti. Stromy a jejich vlastnosti. Základní grafové algoritmy. Orientované grafy.

Jazyk výuky

čeština

Počet kreditů

4

Garant předmětu

doc. RNDr. Dana Hliněná, Ph.D.

Zajišťuje ústav

Ústav matematiky (UMAT)

Výsledky učení předmětu

Studenti získají schopnost orientace v základních diskrétních matematických strukturách a schopnost porozumět logické struktuře matematického textu. Budou schopni vysvětlit matematické struktury a budou umět přesně formulovat vlastní tvrzení a jejich důkazy.

Prerekvizity

Středoškolská matematika.

Způsob a kritéria hodnocení

Písemné testy během semestru (pět 4bodových testů).

Učební cíle

Předmět poskytuje základní znalosti z matematiky potřebné pro řadu navazujících předmětů. Studenti se seznámí s elementárními poznatky z  algebry a diskrétní matematiky, s důrazem na matematické struktury, které jsou potřebné pro pozdější aplikace v informatice.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

  • Znalosti studentů jsou ověřovány na cvičeních vypracováním pěti písemných testů po 4 bodech a závěrečnou zkouškou za 80 bodů.
  • Pokud se student nemůže cvičení z vážného důvodu (například pro nemoc) zúčastnit a tento důvod doloží v souladu s Článkem 55 Studijního a zkušebního řádu VUT, může se cvičení se stejným tématem zúčastnit s jinou skupinou (pokud s tím cvičící souhlasí).

Zařazení předmětu ve studijních plánech

  • Program BIT bakalářský 1 ročník, zimní semestr, povinný
  • Program BIT bakalářský 1 ročník, zimní semestr, povinný

  • Program IT-BC-3 bakalářský

    obor BIT , 1 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., povinná

Vyučující / Lektor

doc. RNDr. Dana Hliněná, Ph.D.

Osnova

  1. Formální jazyk matematiky. Základní formalismy - věta, důkaz, výroková a predikátová logika.
  2. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze.
  3. Důkazové techniky.
  4. Binární relace, jejich vlastnosti a skládání.
  5. Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
  6. Relace uspořádání, svazy. Hasseovské diagramy. Zobrazení.
  7. Pojem grafu, základní pojmy. Isomorfismus grafů, stromy, cesty a eulerovské grafy.
  8. Grafové algoritmy pro hledání nejkratší cesty a minimální kostry. Rovinné grafy.
  9. Orientované grafy.
  10. Binární operace a jejich vlastnosti.
  11. Algebry s jednou operaci, grupy.
  12. Kongruence a morfismy.
  13. Algebry se dvěma operacemi, svazy jako algebry. Booleovy algebry.

Cvičení s počítačovou podporou

26 hod., povinná

Vyučující / Lektor

RNDr. Petr Fuchs, Ph.D.
doc. RNDr. Dana Hliněná, Ph.D.
Mgr. Martin Tůma, Ph.D.

Osnova

Příklady probírané na cvičeních jsou voleny tak, aby vhodným způsobem doplňovaly přednášky.