Diskrétní struktury

Zkratka předmětu KMI/KDS
Název předmětu Diskrétní struktury
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/KDS
Název Diskrétní struktury
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 18 HOD/SEM
Vyučovací jazyk čeština
Nahrazovaný předmět
Vyloučené předměty KMI/DSA
Podmiňující
Způsob zakončení Zkouška
Forma zakončení Kombinovaná
Zápočet před zkouškou Ano
Vyučovaný semestr Zimní
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í.

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 prezentovat 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.

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.

Garanti a vyučující
  • Garanti: Mgr. Tomáš Roskovec, Ph.D.
  • Přednášející: Mgr. Tomáš Roskovec, Ph.D., RNDr. Filip Soudský, Ph.D.
  • Cvičící: RNDr. Filip Soudský, 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