Název:	Základy diskrétní matematiky
Zkratka:	ZDM
Typ:	povinný
Rozsah:	14 týdnů, týdně 2 hodiny přednášek + 1 hodina seminárního cvičení
Způsob ukončení:	zkouška
Katedra:	katedra aplikované matematiky FP TUL
Přednášející:	RNDr. Miroslav Koucký, CSc.

 
Stručná anotace předmětu:

Předmět seznamuje studenty s úvodními partiemi diskrétní matematiky, které zahrnují elementární úvod do teorie množin a relací, klasickou kombinatoriku (variace, permutace, kombinace) a na ni navazující základy teorie pravděpodobnosti (omezené na diskrétní případy), booleovské funkce a základy matematické logiky, základy teorie grafů a principy jejích aplikací a teorii algoritmů (Turingovy stroje, Markovovy algoritmy).

 
Témata přednášek:

Pojem množiny, množinové operace, sjednocení, průnik, rozdíl, kartézský součin. Relace na množinách jakožto podmnožiny kartézských součinů, především relace ekvivalence, uspořádání, zobrazení.

Variace bez opakování a s opakováním, permutace, kombinace bez opakování i s opakováním.

Pojem pravděpodobnosti, kombinatorická pravděpodobnost, podmíněná pravděpodobnost, Bayesův vzorec. Diskrétní rozložení pravděpodobnosti.

Základní logické spojky. Booleovské vektory. Booleovské funkce. Přehled všech booleovských funkcí dvou proměnných. Vyjádření booleovské funkce pomocí disjunktivní formy, použití krychlí k tomuto účelu. Minimalizace booleovských funkcí. Základy predikátové logiky, kvantifikátory. Reléové sítě.

Pojem neorientovaného grafu. Incidenční matice, matice sousednosti. Sled, tah, cesta, kružnice. Vzdálenosti v grafu, poloměr a průměr grafu. Souvislost grafu, stromy, kostra grafu. Základní pojmy teorie orientovaných grafů. Čínský problém listonoše, toky v sítích, síťová analýza, Borůvkův problém minimální kostry. Rovinné grafy, Kuratowského věta.

Obecný pojem algoritmu, příklady algoritmů. Turingův stroj. Markovův algoritmus.

 
Náplň cvičení:

Řešení úloh z kombinatoriky, teorie pravděpodobnosti booleovských funkcí. Příklady různých objektů z teorie grafů a teorie algoritmů.

 
Literatura:

Kolář J., Štěpánková D., Chytil M.: Logika, algebra a grafy. Praha, SNTL 1959.

Nešetřil J.: Teorie grafů. Praha, SNTL, 1979.

Nešetřil J., Matoušek J.: Kapitoly z diskrétní matematiky. Praha, Karolinum, 2000.

Vild J., Šedý J.: Matematika II (Algoritmy a logika). VŠST, Liberec 1978.

 
Prerekvizity: -

Navazující:    -

 
Datum poslední změny: 15.1.2002