Detail předmětu

Teorie grafů a grafové algoritmy

FSI-VTGAk. rok: 2019/2020

Předmět je úvodem do teorie grafů a seznamuje studenty s jeho základními pojmy. 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, Voronoiovy diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Zajišťuje ústav

Ústav automatizace a informatiky (ÚAI)

Výsledky učení předmětu

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í osvojených algoritmů.

Prerekvizity

Ke studiu teorie grafů postačují základní znalosti z teorie množin, kombinatoriky a operačního výzkumu.

Plánované vzdělávací činnosti a výukové metody

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. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách.

Způsob a kritéria hodnocení

Podmínkou pro zápočet je implementace netriviálního grafového algoritmu na počítači ve vyšším programovacím jazyku (např. C++, Java, Python, ...)
Zkouška má písemnou formu. Studenti v ní prokazují znalosti pojmů a základních algoritmů.

Učební cíle

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Protože cvičení jsou povinná, bude na nich vyučující pravidelně kontrolovat účast. V případě omluvené nepřítomnosti student obdrží příklady k samostatnému vypracování tak, aby mohl zameškanou látku zvládnout.

Základní literatura

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

Doporučená literatura

Demel, J.: Grafy a jejich aplikace. ACADEMIA, Praha, 2002.
Chartrand, G. and Oellermann, O.R. : Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
Kolář, J.: Theoretical Computer Science. ČVUT FEL, Praha, 1998.

Zařazení předmětu ve studijních plánech

  • Program M2I-P magisterský navazující

    obor M-AIŘ , 2 ročník, zimní semestr, povinný
    obor M-AIŘ , 2 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Osnova

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.

Cvičení s počítačovou podporou

26 hod., povinná

Vyučující / Lektor

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Osnova

Cvičení jsou orientována na implementaci grafových algoritmů na počítači a vyhledávání a testování softwaru na Internetu z oblasti teorie grafů.