Název: Teorie grafů a her Zkratka: TGH_K Typ: povinný Rozsah v hod.: 20K + 36E Kredity: 5 Způsob ukončení: zkouška Katedra: katedra modelování procesů FM TUL Přednášející: Prof. Ing. Miroslav Tůma, CSc.
Stručná anotace předmětu:Předmět je 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. Důraz bude kladen na aplikace teorie grafů v numerickém počítání.
Témata přednášek:
- Orientovaný a neorientovaný graf. Úvodní poznámky a definice.
- Reprezentace grafu a datové struktury.
- Sled, tah, cesta, kružnice. Vzdálenosti v grafu, poloměr a průměr grafu. Souvislost 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 více inteligentními účastníky.
- Grafy, matice a datové struktury.
- Dělení grafů.
- Grafové algoritmy pro hledání maticových permutací.
- Grafy a dekompozice řídkých symetrických a pozitivně definitních matic
- Grafy a eliminace řídkých nesymetrických matic.
Náplň cvičení:V prezenční formě se procvičují témata přednášená v minulém týdnu. V kombinované formě jsou jednotlivá témata seskupena do 4 bloků: 1. Základy teorie grafů, 2. grafové algoritmy, 3. teorie her a 4. aplikace grafů v numerických výpočtech a na cvičení probíhajícím v semestru jsou procvičeny základní úlohy, zadávány úlohy k samostudiu s možností internetových konzultací.
Literatura:[1] M. Maňas: Teorie her a její ekonomické aplikace, SNTL, Praha, 1992.
[2] A.J. Jones: Game Theory: Mathematical Models of Conflict. Wiley, New York, 1980.
[3] S. Pissanetzky: Sparse Matrix Technology, Academic Press, 1984.
[4] G. Meurant: Computer Solution of Large Linear Systems, Elsevier, 1999.
[5] J. Nešetřil: Teorie grafů, SNTL, 1979.
[6] Studijní materiály na internetu: Připravují se skripta a materiál, který se v html formě objeví i na webu Ke studiu doporučujeme i následující texty volně dostupné na webu:
- http://www.csee.usf.edu/~maurer/graphs/,
- http://www.brpreiss.com/books/opus5/html/page519.html
Prerekvizity: -Navazující: -
Organizace výuky v kombinované formě studia:V průběhu semestru bude 14 hodin přednášek, na kterých budou přednášeny úvody do každého z témat a zdůrazněny důležité body. Pro domácí studium budou ke každému z témat k dispozici na webových stránkách podrobné učební texty ve formátu pdf včetně kontrolních otázek a testů. K diskusi budou vypsány konzultační hodiny na internetu CLIX.
Cvičení budou rozdělena do 4 bloků (viz výše) a budou na nich probírány základní úlohy, zadávány úlohy pro samostudium s možností on-line nebo off-line konzultací podle dohody s posluchači. Tyto bloky budou postupně probíhat v semestru a za nimi bude následovat samostudium s podporou e-learningu, na závěr bude procvičená látka shrnuta. Student absolvuje dva kontrolní testy pro udělení zápočtu - jeden na závěr 2. bloku cvičení a druhý na závěr 4. bloku cvičení.
Datum poslední změny: 20.10.2004