Detail předmětu
Vybrané kapitoly z algoritmů
FIT-VKDAk. rok: 2018/2019
Předmět se zaměřuje na pokročilé matody analýzy a návrhu algoritmů v oblastech dynamického programování, v oblastech pokročilých datových struktur jako B-Trees, Binomial Heaps, Fibonacci Heaps, Red-Black Trees, Skip-Lists a Splay-Tree,
Jazyk výuky
čeština, angličtina
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
- Student prokáže tvůrčí schopnosti v oblasti pokročilých algoritmů na doktorské úrovni na projektovém zadání
- Student prokáže schopnost vyspělé presentace výsledků zadaného projektu
Prerekvizity
- Znalost problematiky algorimizace na úrovni magisterského studia
Způsob a kritéria hodnocení
Úspěšná prezentace zadaného projektu
Učební cíle
Ovládnout vlastnosti vybraných pokročilých algoritmů a datových struktur. Seznámit se detailně s jejich vlastnostmi, složitostí a využitím.
Doporučená literatura
Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge
Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, London, England 1990.
Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, London, England 1990.
Zařazení předmětu ve studijních plánech
Typ (způsob) výuky
Přednáška
39 hod., nepovinná
Vyučující / Lektor
Osnova
- Rekurze: substituční metoda, iterační metoda, hlavní metoda, teorém hlavní metody.
- Četnosti a pravděpodobnost
- Dynamické programování
- Nenasytné (greedy) algoritmy
- Mediány a pořadová statistika
- Červeno-černé stromy
- Splay stromy
- Přeskakovací seznamy (Skip-lists)
- B-Stromy
- Binomické stromy
- Binomická hromada
- Fibonacciho hromada
- Polynomy a FFT