ÚVOD / Studijní obory / Sylaby / Pokročilá algoritmizace

Pokročilá algoritmizace

Cílem předmětu je poskytnout studentům komplexní přehled a vysvětlení metodik řešení složitějších programovacích úloh. V rámci kurzu budou probírány jednak problematiky základních algoritmů databázového typu, jako jsou vyhledávání a řazení, jednak metodiky deterministického řešení rozhodovacích a rozvrhovacích úloh prezentovaných platformou grafových algoritmů a bude také podán jemný úvod do přístupů nedeterministických.

Sylabus předmětu

Předmět má dva tematické algoritmické bloky - obecný a grafově orientovaný. Na obecném bloku se popisují principy, které se posléze předvádí na příkladu grafových algoritmů.
Obecně algoritmický blok:
  1. Algoritmická složitost - popis problematiky algoritmické složitosti jednak časové, tak i prostorové, metody jejího vyjádření a efektivní porovnání algoritmů pomocí těchto metrik, ukázky složitosti na základních grafových operacích.
  2. Pokročilejší metodiky programování - popis pokročilejších metodik programování jako jsou rekurze či dynamické programování, využití pro prohledávání grafů.
  3. Pokročilé metody třídění a vyhledávání - popis pokročilých metod pro problematiku třídění a vyhledávání (např. merge sort, quicksort, BB(α) strom, B-strom, vyhledávání v textu Boyer-Mooreovým algoritmem, apod.)
  4. Standardní datové algoritmy - popis různých metod standardních algoritmů na řazení a vyhledávání včetně odpovídajících vlastností algoritmů, snížení složitosti zacházení s grafy zavedením efektivnějších metod správy dat.
  5. Heuristické řešení problémů - hladové algoritmy a zavedení heuristik, představení jednoduchosti hladových algoritmů na jednoduchém případě minimální kostry grafu.
  6. Třídy složitosti - zavedení tříd složitosti P a NP, jejich rozdíl a potenciální vztah, NP-úplné problémy, předvedení problému barvení jako NP-úplného problému.
  7. Aproximační a přibližné algoritmy - uvedení do problematiky přibližných a aproximačních algoritmů, ukázka metod řešení problému barevnosti polynomiálními algoritmy.
Grafově algoritmický blok:
  1. Graf a jeho uložení v počítači - problematika reprezentace reálných problémů grafem a jeho efektivní uložení v počítači s uvážením řešeného problému, orientované grafy, využití obecných definic algoritmické složitosti 
  2. Průchody grafem - základní metody průchodu grafem do hloubky a šířky a jejich využití pro charakterizaci grafu a realizaci reálných úloh, využití prohledávání pro algoritmus nejkratší cesty. Využití pokročilých metodik algoritmů jako rekurze či dynamické programování.
  3. Stromy - Charakterizace stromů, jejich kódování a tím umožněné efektivní uložení v paměti, související problém isomorfismu stromů. 
  4. Problém minimální kostry - Problém hledání kostry a její minimalizace, složitost celého přístupu a jednoduchý hladový algoritmus na řešení, využívá znalostí z obecných heuristických metod.
  5. Problém barvení - Problém barvení grafu, využití pro plánovací algoritmy, složitost tohoto problému a jeho NP-úplnost, souvislost s obecnou definicí tříd složitosti.
  6. Přibližné algoritmy na barvení grafů - algoritmy na přibližné barvení grafů, přístupy na řešení složitých algoritmů polynomiálně s určitou mírou nepřesnosti, souvisí s obecnou definicí aproximačních a přibližných algoritmů.

Doporučená literatura

Základní učební texty a pomůcky

  1. MAREŠ, M., VALLA, T. : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, dostupné onlin:http://pruvodce.ucw.cz/ 
  2. CORMEN, T., LEISERSON, Ch., RIVEST, R., STEIN, C.: Introduction To Algorithms, The MIT Press, 2009
  3. MATOUŠEK, J., NEŠETŘIL, J.: Kapitoly z diskrétní matematiky, čtvrté vydání, Karolinum, 2010.
  4. DIESTEL, R.: Graph Theory, 5th edition, Springer, 2017.

Doplňující a rozšiřující učební texty

  1. MAŘÍK, V., ŠTĚPÁNKOVÁ, O., LAŽANSKÝ, J. A KOLEKTIV.: Umělá inteligence 1-6, Academia Praha, 1993, 1997, 1999, 2003, 2007, 2013.
  2. JONES, T. J.: Artificial Intelligence: A Systems Approach. Jones & Bartlett Learning, 2008.
  3. SKIENA, S. S. The Algorithm Design Manual. Springer, 2. vydání, 2008. 
  4. BOLLOBÁS, B.: Modern Graph Theory, Corrected Edition, Springer, 2013.