Detail předmětu
Grafové algoritmy
FIT-GALAk. rok: 2021/2022
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 v elektronické podobě. (CS)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 3. vydání, 1312 s., 2009.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3. vydání, 1312 s., 2009. (CS)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition. MIT Press, 2009. (EN)
J. Demel, Grafy, SNTL Praha, 1988.
J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize) (CS)
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.
K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Discributed). Springer, 2018.
Způsob a kritéria hodnocení
- Půlsemestrální písemná zkouška (max. 15 bodů)
- Hodnocený projekt (max. 25 bod)
- Závěrečná písemná zkouška (max. 60 bodů)
- 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.
Jazyk výuky
čeština, angličtina
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
Pokud v průběhu semestru student onemocní nebo se vyskytne jiná překážka ve studiu, je třeba tuto překážku řádně ohlásit a doložit. Pak k ní lze přihlédnout a přizpůsobit jí hodnocení:
- U projektu může student požádat příslušného učitele o přiměřené prodloužení termínu pro odevzdání.
- Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může přednášejícího požádat, aby body za půlsemestrální zkoušku byly odvozeny od bodového zisku u prvního termínu zkoušky, kterého se zúčastní.
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 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ý - Program MITAI magisterský navazující
specializace NBIO , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NISD , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NISY , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NISY do 2020/21 , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NIDE , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NCPS , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NSEC , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NMAT , libovolný ročník, zimní semestr, 5 kreditů, povinný
specializace NGRI , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NNET , libovolný ročník, zimní semestr, 5 kreditů, povinný
specializace NVIZ , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NSEN , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NMAL , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NHPC , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NVER , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NEMB , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NADE , libovolný ročník, zimní semestr, 5 kreditů, volitelný
specializace NSPE , libovolný ročník, zimní semestr, 5 kreditů, volitelný - Program IT-MGR-2 magisterský navazující
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í.
- Barvení grafů, chromatický polynom.
- Eulerovské grafy a tahy, problém čínského pošťáka, Hamiltonovské kružnice a cykly.
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).