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

J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize) (CS)
J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Discributed). Springer, 2018.
A. Mitina: Applied Combinatorics with Graph Theory. NEIU, 2019.
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)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition. MIT Press, 2009. (EN)

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