UIN1070 Kombinatorické algoritmy

Filozoficko-přírodovědecká fakulta v Opavě
zima 2015
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
Předmět navazuje a rozšiřuje znalosti získané v předmětu Teorie grafů. Ukazuje praktickou aplikaci teoretických poznatků a techniky programování a práce s grafy.
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
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 2010, zima 2011, zima 2012, zima 2013, zima 2014, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023.