UINA170 Combinatorial algorithms

Filozoficko-přírodovědecká fakulta v Opavě
zima 2018
Rozsah
2/2/0. 4 kr. Ukončení: zk.
Garance
RNDr. Miroslav Langer, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
The course follows and extends knowledge obtain in the Graph theory course. It focuses on the practical applications of the theoretical knowledge and on the programming techniques and on the working with graphs.
Osnova
  • 1. Připomenutí základních pojmů z teorie grafů.
    2. Reprezentace grafů v počítači, vhodnost reprezentací.
    3. Základní metody průchodů grafů, prohledávání grafů do hloubky a do šířky.
    4. Dostupnost v grafu, hranová a vrcholová souvislosta komponenty grafu.
    5. Délka cesty v grafu
    6. Kostry grafu
    7. Hledání eulerovských cest a cyklů, eulerovské grafy, hledání hamiltonovské cesty a cyklu.
    8. Toky v sítích
    9. Párování v bipartitních a obecných grafech
    10. Klikovost grafu, hledání nezávislé množiny vrcholů, barvení grafů
Literatura
    doporučená literatura
  • Večerka. Grafy a grafové algoritmy. PřF UP Olmouc, 2007. info
  • Fronček. Úvod do teorie grafů. SLU Opava, 1999. info
  • Kučera. Kombinatorické algoritmy. SNTL Praha, 1991. info
  • Demel. Grafy. Praha, 1989. info
Výukové metody
Přednáška s aktivizací
Přednáška s analýzou videozáznamu
Metody hodnocení
Zkouška
Vyučovací jazyk
Angličtina
Informace učitele
Vytvořit aplikaci řešící vybrané grafové algoritmy
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2017, zima 2019, zima 2020.