Detail předmětu

Grafové algoritmy (v angličtině)

FIT-GALeAk. rok: 2024/2025

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

Jazyk výuky

angličtina

Počet kreditů

Garant předmětu

prof. RNDr. Alexandr Meduna, CSc.

Zajišťuje ústav

Ústav informačních systémů (UIFS)

Nabízen zahraničním studentům

Všech fakult

Vstupní znalosti

Základní znalost diskrétní matematiky a schopnost algoritmického myšlení.

Pravidla hodnocení a ukončení předmětu

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.

Učební cíle

Ú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.

Doporučená literatura

Electronic copy of lectures. (EN)
J. Demel, Grafy, SNTL Praha, 1988. (CS)
J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize) (CS)
J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990. (EN)
K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Distributed). Springer, 2018. (EN)
A. Mitina: Applied Combinatorics with Graph Theory. NEIU, 2019. (EN)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition. MIT Press, 2009. (EN)

Elearning

eLearning: aktuální otevřený kurz

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

  • Program IT-MGR-1H magisterský navazující

    specializace MGH , 0 ročník, zimní semestr, doporučený kurs

  • Program MIT-EN magisterský navazující 0 ročník, zimní semestr, povinně volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

Ing. Zbyněk Křivka, Ph.D.

Osnova

  1. Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu.
  2. Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů.
  3. Topologické uspořádání vrcholů a hran, test acykličnosti grafu.
  4. Komponenty grafu, silně souvislé komponenty, příklady.
  5. Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus.
  6. Růst minimální kostry, Kruskalův algoritmus a Primův algoritmus.
  7. 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.
  8. Dijkstrův algoritmus. Nejkratší cesty ze všech do všech vrcholů.
  9. Nejkratší cesty a násobení matic, Floyd-Warshallův algoritmus.
  10. Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus.
  11. Párování v bipartitních grafech, maximální párování.
  12. Barvení grafů.
  13. Eulerovské grafy a tahy, Hamiltonovské grafy a kružnice.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Zbyněk Křivka, Ph.D.

Osnova

  1. Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).

Elearning

eLearning: aktuální otevřený kurz