Detail předmětu

Grafové algoritmy (v angličtině)

FIT-GALeAk. rok: 2019/2020

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

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

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

Doporučená nebo povinná literatura

Text přednášek.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (http://www.introductiontoalgorithms.com), McGraw-Hill, 2002.
A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
J. Demel, Grafy, SNTL Praha, 1988.
J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize (http://kix.fsv.cvut.cz/~demel/grafy/))
R. Diestel, Graph Theory, Third Edition (http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/), 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.

Způsob a kritéria hodnocení

Bodové hodnocení výsledků půlsemestrální zkoušky (max. 15 bodů) a vypracovaných projektů (max. 25 bodů).

Jazyk výuky

angličtina

Cíl

Úvod do teorie grafů se zaměřením na reprezentace grafů, grafové algoritmy a jejich složitosti.

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.

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

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

    obor MGMe , libovolný ročník, zimní semestr, 5 kreditů, 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, 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

prof. RNDr. Alexandr Meduna, CSc.

Osnova

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