Předmět: Teorie grafů a her

« Zpět
Název předmětu Teorie grafů a her
Kód předmětu NTI/TGHE
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Bakalářský
Rok studia nespecifikován
Semestr Letní
Počet ECTS kreditů 4
Vyučovací jazyk Čeština
Statut předmětu Povinný, Povinně-volitelný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
Vyučující
  • Březina Jan, doc. Mgr. Ph.D.
  • Špetlík Martin, Ing.
Obsah předmětu
Témata přednášek: Pojem graf - orientovaný, neorientovaný. Reprezentace grafu a s tím související datové struktury. 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. Klasifikace a matematické modely rozhodovacích situací, nekonfliktní rozhodovací situace, antagonistický konflikt, teorie maticových her, nekonečný antagonistický konflikt, neantagonistický konflikt dvou účastníků kooperativní a nekooperativní teorie. Rozhodování v konfliktech s p-inteligentními účastníky. 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.

Studijní aktivity a metody výuky
Monologický výklad (přednáška, prezentace, vysvětlování)
  • Účast na výuce - 56 hodin za semestr
  • Domácí příprava na výuku - 64 hodin za semestr
  • Příprava na zkoušku - 30 hodin za semestr
Výstupy z učení
Předmět bude zaměřen na širší souvislosti teorie her, aplikované teorie grafů a teorie optimálního rozhodování. První část zahrne grafová témata, která budou obsahovat i formulace některých klasických optimalizačních úloh pomocí sítí a grafů. V dalším se zaměříme na obecné i speciální případy teorie her a její aplikace. Cílem předmětu je nejenom zvládnutí základních teoretických vztahů, ale i jejich začlenění do širších souvislostí úloh operačního výzkumu.
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í.
Předpoklady
Základy programování, základy lineární algebry.

Hodnoticí metody a kritéria
Kombinovaná zkouška

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


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr