Detail předmětu
Grafové algoritmy (v angličtině)
GALe Ak. rok 2024/2025 zimní semestr 5 kreditů
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ů, hledání komponent grafu a silně souvislých komponent, 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í principu jejich fungování a na studium složitosti navržených algoritmů.
Odkazy
- E-learning/Moodle website of GALe for WS 2024/25
Garant předmětu
Koordinátor předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 13 hod. projekty
Bodové hodnocení
- 60 bodů závěrečná zkouška (písemná část)
- 15 bodů půlsemestrální test (písemná část)
- 25 bodů projekty
Zajišťuje ústav
Přednášející
Cvičící
Cíle předmětu
Úvod do teorie grafů se zaměřením na reprezentace grafů, grafové algoritmy a jejich složitosti.
Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.
Požadované prerekvizitní znalosti a dovednosti
Základní znalost diskrétní matematiky a schopnost algoritmického myšlení.
Literatura studijní
- J. Demel, Grafy, SNTL Praha, 1988.
- J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize)
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, Kruskalův algoritmus a Primův algoritmus.
- Nejkratší cesty z jednoho vrcholu do všech ostatních vrcholů, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
- Dijkstrův algoritmus. Nejkratší cesty ze všech do 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ů.
- Eulerovské grafy a tahy, Hamiltonovské grafy a kružnice.
Osnova ostatní - projekty, práce
- Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).
Průběžná kontrola studia
Bodové hodnocení výsledků půlsemestrální zkoušky (max. 15 bodů) a vypracovaných projektů (max. 25 bodů).
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.
Rozvrh
Den | Typ | Týdny | Místn. | Od | Do | Kapacita | PSK | Skup | Info |
---|---|---|---|---|---|---|---|---|---|
Út | přednáška | výuky | L314 | 09:00 | 11:50 | 30 | 1EIT 2EIT INTE | xx | Křivka |
Zařazení předmětu ve studijních plánech
- Program MIT-EN (anglicky), libovolný ročník, povinně volitelný skupina B