Grafové algoritmy (FSI-9GRA)

Akademický rok 2019/2020

Garant:	prof. RNDr. Ing. Miloš Šeda, Ph.D.
Garantující pracoviště:	ÚAI	všechny předměty garantované tímto pracovištěm
Jazyk výuky:	čeština či angličtina
Cíle předmětu:
Cílem předmětu je seznámit studenty s teorií grafů a jejími algoritmy, které rozšiřují znalosti získané v předmětech se zaměřením na umělou inteligenci, operační výzkum, projektové řízení a počítačové sítě, a mají aplikace v technických i jiných oblastech.
Výstupy studia a kompetence:
Studenti získají základní znalosti z teorie grafů a grafových algoritmů. Budou tak schopni modelovat pomocí grafů různé problémy z praxe a ty pak řešit pomocí grafových algoritmů.
Prerekvizity:
Ke studiu grafových algoritmů postačují základní znalosti z teorie množin, kombinatoriky a operačního výzkumu.
Obsah předmětu (anotace):
Předmět se zaměřuje na teorii grafů a seznamuje studenty s jejími základními pojmy a algoritmy. Zabývá se následujícími tématy: Reprezentace grafu v počítači. Časová složitost algoritmů. Datové struktury pro grafové algoritmy (binární halda, disjunktní množiny, ...). Eulerovské tahy, hamiltonovské cesty. Prohledávání grafů (do šířky, do hloubky), backtracking, metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty. Síťové grafy. Stromy a kostry. Steinerovy stromy. Základy počítačové geometrie - grafy viditelnosti, Voroného diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.
Metody vyučování:
Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny.
Způsob a kritéria hodnocení:
Podmínkou pro absolvování předmětu je textové zpracování nebo implementace netriviálního grafového algoritmu na počítači. Zkouška má písemnou formu. Studenti v ní prokazují znalosti pojmů a základních algoritmů.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:

Typ (způsob) výuky:
Přednáška	10 × 2 hod.	nepovinná
Osnova:
Přednáška	1. Definice grafu a základní pojmy. 2. Reprezentace grafu v počítači. 3. Časová a paměťová složitost algoritmů. 4. Prohledávání grafů, backtracking, metoda větví a mezí. 5. Aplikace úloh o cestách, nejkratší cesty, síťové grafy. 6. Eulerovské tahy, hamiltonovské cesty a kružnice. 7. Komponenty souvislosti, stromy a kostry. 8. Steinerovy stromy. 9. Voronoiovy diagramy, Delaunayho triangulace. 10. Barvení grafů, kliky. 11.-12. Toky v sítích. 13. Párování grafech.

Literatura - základní:
1. Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
2. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001.
3. Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004.
4. Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998.
Literatura - doporučená:
5. Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
6. Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.
7. Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002.