Discrete Structures

Zkratka předmětu KMI/DSA
Název předmětu Discrete Structures
Akademický rok 2020/2021
Pracoviště / Zkratka KMI/DSA
Název Discrete Structures
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 2 HOD/TYD Cvičení 2 HOD/TYD
Vyučovací jazyk angličtina
Nahrazovaný předmět
Vyloučené předměty
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í
Stáhnout jako PDF
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