Předmět Teorie her (NTI / THE)

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 / THE - Teorie 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

Ing. Josef Chudoba, Ph.D.

Vyučující

Ing. Josef Chudoba, Ph.D.Ing. Josef Chudoba, Ph.D.