Detail předmětu

Diskrétní matematika

FIT-IDMAk. rok: 2021/2022

Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Boolovy 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, toky v sítích.

Jazyk výuky

čeština

Počet kreditů

5

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í

  • Ohodnocení pěti písemných testů  (max 25 bodů).

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 (max. 6 bodů), vypracováním pěti písemných testů po 5 bodech, vypracováním domácího úkolu za 5 bodů  a závěrečnou zkouškou za 64 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 (na což dotyčného cvičícího upozorní). 
  • Hranice pro úspěšné složení zkoušky je získání alespoň 50 bodů z celkového maxima 100 bodů, získaných v průběhu semestru (za domácí úlohy a vnitrosemestrální zkoušky) a za závěrečnou zkoušku, podle pravidel ECTS.

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

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

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

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

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

doc. RNDr. Dana Hliněná, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
RNDr. Petr Fuchs, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Osnova

  1. Formální jazyk matematiky. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze. 
  2. Binární relace a zobrazení, jejich skládání a vlastnosti.
  3. Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
  4. Uspořádání. Hasseovské diagramy. Zobrazení
  5. Binární operace a jejich vlastnosti.
  6. Algebry s jednou operaci, zejména grupy. Kongruence a morfismy.
  7. Algebry se dvěma operacemi, svazy jako algebry. Booleovy algebry.
  8. Výroková logika. Syntaxe a sémantika. Splnitelnost a platnost. Logická ekvivalence a logický důsledek. Ekvivalentní formule. Normální formy.
  9. Predikátová logika. Jazyk predikátové logiky prvního řádu. Syntaxe, termy a formule, volné a vázané proměnné. Realizace.
  10. Predikátová logika. Sémantika, Tarského definice pravdy. Logická platnost, logický důsledek. Teorie. Ekvivalentní formule. Normální formy.
  11. Formální systém logiky. Axiomatický systém Hilbertova typu pro výrokovou a predikátovou logiku. Dokazatelnost, rozhodnutelnost, úplnost, neúplnost.
  12. Pojem grafu, základní pojmy. Isomorfismus grafů, souvislost, stromy, cesty a eulerovské grafy (jednotažky).
  13. Hledání nejkratší cesty. Dijkstrův algoritmus. Problém minimální kostry. Algoritmy Kruskala a Jarníka. Rovinné grafy.

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

26 hod., povinná

Vyučující / Lektor

Mgr. Juraj Síč
Ing. Dominik Harmim
Mgr. Gabriela Vážanová, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
Ing. Vojtěch Havlena, Ph.D.
doc. RNDr. Dana Hliněná, Ph.D.
RNDr. Petr Fuchs, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Osnova

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