Detail předmětu

Grafové algoritmy

FIT-GALAk. rok: 2023/2024

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

Počet kreditů

5

Garant předmětu

prof. RNDr. Alexandr Meduna, CSc.

Zajišťuje ústav

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

Vstupní znalosti

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

Pravidla hodnocení a ukončení předmětu

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

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

Učební cíle

Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.
Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.

Doporučená literatura

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition. MIT Press, 2009. (EN)
J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
Text přednášek v elektronické podobě. (CS)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3. vydání, 1312 s., 2009. (CS)
J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize) (CS)
K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Discributed). Springer, 2018.
A. Mitina: Applied Combinatorics with Graph Theory. NEIU, 2019.

Elearning

eLearning: aktuální otevřený kurz

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

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

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

  • Program MITAI magisterský navazující

    specializace NSPE , 0 ročník, zimní semestr, volitelný
    specializace NBIO , 0 ročník, zimní semestr, volitelný
    specializace NSEN , 0 ročník, zimní semestr, volitelný
    specializace NVIZ , 0 ročník, zimní semestr, volitelný
    specializace NGRI , 0 ročník, zimní semestr, volitelný
    specializace NADE , 0 ročník, zimní semestr, volitelný
    specializace NISD , 0 ročník, zimní semestr, volitelný
    specializace NMAT , 0 ročník, zimní semestr, povinný
    specializace NSEC , 0 ročník, zimní semestr, volitelný
    specializace NISY do 2020/21 , 0 ročník, zimní semestr, volitelný
    specializace NCPS , 0 ročník, zimní semestr, volitelný
    specializace NHPC , 0 ročník, zimní semestr, volitelný
    specializace NNET , 0 ročník, zimní semestr, povinný
    specializace NMAL , 0 ročník, zimní semestr, volitelný
    specializace NVER , 0 ročník, zimní semestr, volitelný
    specializace NIDE , 0 ročník, zimní semestr, volitelný
    specializace NEMB , 0 ročník, zimní semestr, volitelný
    specializace NISY , 0 ročník, zimní semestr, volitelný
    specializace NEMB do 2021/22 , 0 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

Ing. Zbyněk Křivka, Ph.D.

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. Barvení grafů, chromatický polynom.
  13. Eulerovské grafy a tahy, problém čínského pošťáka, Hamiltonovské kružnice a cykly.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Tomáš Kožár
Ing. Zbyněk Křivka, Ph.D.

Osnova

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

Elearning

eLearning: aktuální otevřený kurz