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, angličtina

Počet kreditů

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.