Název: Kombinatorické metody Zkratka: KOM Typ: povinný Rozsah: 14 týdnů, týdně 2 hodiny přednášek + 2 hodiny seminárních cvičení Kredity: 5 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 následujícími tématickými okruhy. Úvod do matematické logiky, vybrané partie z kombinatoriky a teorie grafů, základní kombinatorické a grafové algoritmy.
Témata přednášek:Základy matematické logiky. Výroková logika, syntax, sémantika, Postova věta, CNF a DNF. Predikátová logika, syntax, sémantika, prenexní tvar. Věta o úplnosti.
Kombinatorika - kombinatorika rozkladů, Stirlingova a Bellova čísla, Burnsidovo lemma, Pólyova formule. Möbiova funkce, Möbiova inverze a jejich aplikace v kombinatorice.
Vytvořující funkce (obyčejné a exponenciální), základní operace (konvoluce, derivace, integrál). Rekurentní vztahy (homogenní i nehomogenní) a jejich řešení. Čísla Fibonacciho, Lucasova, Catalanova, Bernoulliho, Ramseyova. Aplikace při řešení kombinatorických úloh.
Grafy a jejich základní typy, grafové operace. Reprezentace grafů, implementace. Cesty v grafech, vzdálenost, eulerovské grafy. Rovinné grafy. Hamiltonovské grafy, problém obchodního cestujícího. Souvislost grafu.
Kombinatorické a grafové algoritmy. Generování permutací a kombinací v lexikografickém i náhodném pořadí. Minimální, maximální kostra, Jarníkův - Primův algoritmus, hladový algoritmus (Kruskal-Edmonds). Párování, nejkratší cesty, Dijkstrův algoritmus. Toky v sítích, Ford-Fulkersonův a Dinicův algoritmus.
Náplň cvičení:Procvičuje se látka vyložená na předchozích přednáškách. Důraz je kladen na schopnost samostatné aplikace získaných poznatků při řešení různých typů úloh a na schopnost implementovat uvedené algoritmy s využitím vhodných datových struktur (pole, záznam, zásobník, fronta, spojové seznamy, kořenové stromy a uspořádané kořenové stromy).
Literatura:Demel J.: Grafy. SNTL, Praha 1989.
Kolář J., Štěpánková D., Chytil M.: Logika, algebra a grafy. Praha, SNTL 1959.
Kučera L.: Kombinatorické algoritmy. Praha, SNTL, 1989
Nešetřil J., Matoušek J.: Kapitoly z diskrétní matematiky. Praha, Karolinum, 2000.
Prerekvizity: -Navazující: -
Datum poslední změny: 5. 12. 2001