Detail předmětu

Grafové algoritmy

GAL Ak. rok 2021/2022 zimní semestr 5 kreditů

Aktuální akademický rok

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

Koordinátor předmětu

Jazyk výuky

česky, anglicky

Zakončení

zkouška (písemná)

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í

Stránky předmětu

Získané dovednosti, znalosti a kompetence z předmětu

Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.

Cíle předmětu

Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.

Proč je předmět vyučován

Student si v první části přednášek zopakuje důležité algoritmy na systematické prohledávání grafů včetně ukázek toho, jak se u algoritmů dokazuje korektnost. Dále se postupuje k náročnějším algoritmům na hledání nejkratších cest a dalších pokročilejších vlastností zadaného grafu. Vždy je kladen důraz na pochopení principu algoritmu a detailní diskuzi případné implementace (včetně vhodný datových struktur a jejich časově/prostorových složitostí). Kromě samotných grafových algoritmů se student zlepší ve schopnosti formálně popisovat algoritmy a odhadovat jejich složitost. V rámci projektu si vyzkouší modifikaci, implementaci a experimentování s některými vybranými grafovými algoritmy.

Požadované prerekvizitní znalosti a dovednosti

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

Literatura studijní

  • Text přednášek v elektronické podobě.
  • 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.
  • 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.
  • K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Discributed). Springer, 2018.

Osnova přednášek

  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, algoritmy Kruskala a Prima.
  7. Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
  8. Dijkstrův algoritmus. Nejkratší cesty ze 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ů, chromatický polynom.
  13. Eulerovské grafy a tahy, problém čínského pošťáka, Hamiltonovské kružnice a cykly.

Osnova ostatní - projekty, práce

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

Průběžná kontrola studia

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

Kontrolovaná výuka

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

Nahoru