Detail předmětu

Grafové algoritmy

GAL Ak. rok 2019/2020 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ů, 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

Zástupce garanta předmětu

Jazyk výuky

český

Zakončení

zkouška (písemná)

Rozsah

39 hod. přednášky, 13 hod. projekty

Bodové hodnocení

60 zkouška, 15 půlsemestrální test, 25 projekty

Zajišťuje ústav

Přednášející

Cvičící

Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Tomko Martin, Ing. (UIFS FIT VUT)

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.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 3. vydání, 1312 s., 2009.

Literatura referenční

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

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

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Čtzkouška2020-01-02 E104 10:0012:50 1MIT 2MIT řádná
Čtzkouška2020-02-06 G108 13:0015:50 1MIT 2MIT 2. oprava
Čtzkouška2020-01-23 G202 15:0017:50 1MIT 2MIT 1. oprava
přednáškavýuky A112 08:0010:50 1MIT 2MIT MMM MSK xx

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

Nahoru