Detail předmětu
Grafové algoritmy
FIT-GALAk. rok: 2018/2019
Předmět diskutuje různé reprezentace grafů v počítači a grafové algoritmy pro problémy typu prohledávání grafů (do hloubky, do šířky), topologické uspořádání grafů, komponenty grafů a silně souvislé komponenty, stromy a minimální kostry, nejkratší cesty z jednoho vrcholu do všech ostatních či ze všech vrcholů do všech ostatních, maximální tok a minimální řez, maximální párování v bipartitních grafech, Eulerovské grafy a barvení grafů. U všech algoritmů je kladen důraz na pochopení principů a na studium složitosti navržených algoritmů.
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.
Prerekvizity
Základní znalost diskrétní matematiky a schopnost algoritmického myšlení.
Doporučená nebo povinná literatura
- Text přednášek.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
- J. Demel, Grafy, SNTL Praha, 1988.
- J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize)
- R. Diestel, Graph Theory, Third Edition, Springer-Verlag, Heidelberg, 2000.
- J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
- J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008.
- J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005.
- J.L. Gross, J. Yellen: Handbook of Graph Theory (Discrete Mathematics and Its Applications), CRC Press, 2003.
Způsob a kritéria hodnocení
Bodové hodnocení výsledků půlsemestrální zkoušky (max. 15 bodů) a vypracovaných projektů (max. 25 bodů).
Jazyk výuky
čeština, angličtina
Osnovy výuky
- Osnova přednášek:
- Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu.
- Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů.
- Topologické uspořádání vrcholů a hran, test acykličnosti grafu.
- Komponenty grafu, silně souvislé komponenty, příklady.
- Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus.
- Růst minimální kostry, algoritmy Kruskala a Prima.
- Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
- Dijkstrův algoritmus. Nejkratší cesty ze všech vrcholů.
- Nejkratší cesty a násobení matic, Floyd-Warshallův algoritmus.
- Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus.
- Párování v bipartitních grafech, maximální párování.
- Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly.
- Barvení grafů.
- Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).
Osnova ostatní - projekty, práce:
Cíl
Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů, závěrečná semestrální zkouška. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MBS , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MBI , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MIS , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MIN , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MMI , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MMM , libovolný ročník, zimní semestr, 5 kreditů, povinný
obor MGM , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MPV , libovolný ročník, zimní semestr, 5 kreditů, volitelný
obor MSK , 1. ročník, zimní semestr, 5 kreditů, povinný
Typ (způsob) výuky
Přednáška
39 hod., nepovinná
Vyučující / Lektor
Osnova
- Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu.
- Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů.
- Topologické uspořádání vrcholů a hran, test acykličnosti grafu.
- Komponenty grafu, silně souvislé komponenty, příklady.
- Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus.
- Růst minimální kostry, algoritmy Kruskala a Prima.
- Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
- Dijkstrův algoritmus. Nejkratší cesty ze všech vrcholů.
- Nejkratší cesty a násobení matic, Floyd-Warshallův algoritmus.
- Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus.
- Párování v bipartitních grafech, maximální párování.
- Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly.
- Barvení grafů.
Projekt
13 hod., povinná
Vyučující / Lektor
Osnova
- Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).