Detail předmětu

Grafové algoritmy

FIT-GALAk. rok: 2014/2015

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

Jazyk výuky

čeština, angličtina

Počet kreditů

Garant předmětu

prof. RNDr. Alexandr Meduna, CSc.

Zajišťuje ústav

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

Výsledky učení předmětu

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

Prerekvizity

Algoritmické myšlení.

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Osnovy výuky

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

    Osnova ostatní - projekty, práce:
    1. Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).

Učební cíle

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

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

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.

Základní literatura

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.

Doporučená literatura

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

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

  • Program IT-MGR-2 magisterský navazující

    obor MBI , 0 ročník, zimní semestr, volitelný
    obor MBS , 0 ročník, zimní semestr, volitelný
    obor MIN , 0 ročník, zimní semestr, volitelný
    obor MIS , 0 ročník, zimní semestr, volitelný
    obor MMI , 0 ročník, zimní semestr, volitelný
    obor MMM , 0 ročník, zimní semestr, povinný
    obor MPV , 0 ročník, zimní semestr, volitelný
    obor MSK , 1 ročník, zimní semestr, povinný
    obor MGM , 0 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.

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

Projekt

13 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.