Cíle předmětu (anotace)
Předmět je zaměřen na algoritmy na diskrétních strukturách se zdůrazněním výpočetní náročnosti a praktických aplikací. Předmět probíhá v anglickém jazyce.
Požadavky na studenta
Vypracování 5 krátkodobých úkolů (naprogramování řešení úloh využívajících některé z probraných algoritmů). Aktivní účast na cvičení. Závěrečná ústní zkouška (algoritmizace vybraného problému). Místo závěrečné zkoušky lze naprogramovat projekt (komplexnější program vybavený dokumentací, který se bude presentovat ostatním).
Obsah
Tematické celky:
1. Úvod, motivační problémy, paměťová a časová složitost algoritmů.
2. Vyhledávání a třídění (přímé a nepřímé metody a jejich složitost).
3. Datové struktury (binární stromy, haldy, heapsort).
4. Základní grafové algoritmy (representace grafů, prohledávání do šířky a hloubky).
5. Hledání nejkratší cesty (Dijksrtův algoritmus, Floydův-Warschalův algoritmus, ...).
6. Problém minimální kostry (Borůvkův, Kruskalův a Jarníkův algoritmus).
7. Binární vyhledávací stromy (vkládání, vyvažování a další operace).
8. Metoda rozděl a panuj (několik metod využívajících rekurzivní techniky)
9. Vyhledávání v textu.
10. Toky v sítích (problém maximálního toku, řezy, Hallova věta)
11. Toky v sítích (Fordův-Fulkersonův algoritmus)
12. Složitost úloh, P a NP úplné problémy.
13. Diskrétní Fourierova transformace.
Viz https://moodle.ef.jcu.cz/course/view.php?id=1827
Předpoklady - další informace k podmíněnosti studia předmětu
Základní znalosti diskrétní matematiky a teorie algoritmů.
Získané způsobilosti
Schopnost algoritmizace pro vybranou třídu úloh z praxe. Využití výpočetní techniky pro řešení úloh s diskrétní strukturou. Student je schopen komunikovat v anglickém jazyce.
Garanti a vyučující
Garanti: Mgr. Tomáš Roskovec, Ph.D.
Přednášející: Mgr. Tomáš Roskovec, Ph.D.
Cvičící: Mgr. Tomáš Roskovec, Ph.D.
Literatura
Mareš M., Valla T. Průvodce labyrintem algoritmů. Praha, 2017. ISBN 978-80-88168-22-5.
Topfer, P. Algoritmy a programovací techniky. Praha, 2010. ISBN 978-80-7196-350-9.
KREHER, L. D. Combinatorial Algorithms. New York, 1999.
GAREZ, M. R. a D. S. JOHNSON. Computers and Intractibility. New York, 1979.
KUČERA, L. Kombinatorické algoritmy. Praha, 1983.
Vyučovací metody
Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming)
Hodnotící metody
Analýza výkonů studenta, Kombinovaná zkouška
Stáhnout jako PDF