Předmět Teorie grafů a her (NTI / TGH)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTI / TGH - Teorie grafů a her, Fakulta mechatroniky a MIS, Technická univerzita v Liberci (TUL).

Materiál	Typ	Datum	Počet stažení

Obsah

Přednášky:1. Program vs. algoritmus, časová a paměťová složitost; nejhorší, průměrná amortizovaná složitost, správnost algoritmu2. Motivační problémy a jejich grafová reprezentace, datové struktury pro ukládání grafů a analýza základních operací na nich3. Typy grafů, základní pojmy, stromy, věta o stromech.4. Průchod grafem do hloubky, vlastnosti, klasifikace hran orientovaného grafu, topologické třídění, CPM5. Hledání maximálních souvislých komponent, Eulerovská cesta a kružnice; průchod do šířky, hledání nejkratší cesty v neohodnoceném grafu.6. Halda, prioritní fronta, disjunktní množiny (UNION, FIND)7. Hledání nejkratší cesty v ohodnoceném grafu, Dijkstrův algoritmus, Floyd-Warshallův algoritmus.8. Minimální kostra grafu.9. NP úplné a horší problémy, aproximační algoritmy.10. Toky v sítích.11. Barvení grafů.12. Partitioning grafů nebo maximální párování, geometrické algoritmy.13. Teorie her, úvod, Nashovo ekvilibrium, klasické příklady maticových her.14. Základní věta o maticových hrách, aplikace lineárního programování.Cvičení:1. O(n) notace, výpočet složitostí algoritmů, algoritmizace.2. Metoda rozděl a panuj, master theorem a jeho aplikace (quick sort, medián, násobení čísel).3. Grafová reprezentace praktických problémů, nakreslený vs. zapsaný graf, izomorfismus.4. Uložení grafu, převody reprezentací, transpozice grafu, mocnina grafu.5. Průchody grafem a jejich aplikace.6. Průchody grafem a jejich aplikace.7. Průchody grafem a jejich aplikace.8. Halda, disjunktní množiny; příklady použití.9. Hledání nejkratší cesty a její modifikace.10. Minimální kostra, Primův a Kruskalův algoritmus a jejich použití na příbuzné úlohy.11. Toky v sítích.12. Barvení grafů.13. Hledání optimální smíšené strategie pomocí lineárního programování.14. Zápočtová písemka.

Získané způsobilosti

Student získá teoretické poznatky z teorie grafů a dalších probíraných témat i z její aplikace na praktické problémy. Uvědomí si důležitost struktury nejenom v řešení praktických problémů, ale například i v teorii a praxi programování.

Literatura

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein C. Introduction to Algorithms. MIT Press, 1990. J. Matoušek, J. Nešetřil. Kapitoly z diskrétní matematiky, Karolinum, 2009. J. Nešetřil:. Teorie grafů. SNTL Praha, 1979. M. Maňas:. Teorie her a její ekonomické aplikace. SNTL, Praha, 1992. J. Černý. Základní grafové algoritmy, on-line: http://kam.mff.cuni.cz/~kuba/ka/.

Požadavky

Podmínkou zápočtu je aktivní účast na cvičeních a úspěšné absolvování testů. Ke zkoušce je třeba vyřešit jednu ze zadaných semestrálních úloh - implementace grafového algoritmu ve zvoleném jazyce. Zkouška má část písemnou a část ústní se zaměřením na odevzdanou práci.

Garant

Mgr. Jan Březina, Ph.D.

Vyučující

Mgr. Jan Březina, Ph.D.Ing. Josef Chudoba, Ph.D.Mgr. Kateřina JurkováMgr. Jan Březina, Ph.D.Ing. Josef Chudoba, Ph.D.Mgr. Kateřina JurkováIng. Dana Rosická