Fakulta informačních technologií VUT v Brně

Detail předmětu

Grafové algoritmy

GAL Ak. rok 2010/2011 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

Jazyk výuky

česky

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)
Zemek Petr, Ing. (UIFS FIT VUT)

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

Požadované prerekvizitní znalosti a dovednosti

Algoritmické myšlení.

Literatura studijní

  • Text přednášek.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.

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 algorithmus.
  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. Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly.
  13. Barvení grafů.

Osnova ostatní - projekty, práce

  1. Implementace 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ů).

Kontrolovaná výuka

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.

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

Nahoru