Detail předmětu
Vybrané kapitoly z algoritmů
VKD Ak. rok 2014/2015 letní semestr
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,
Garant předmětu
Jazyk výuky
Zakončení
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z 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
Cíle předmětu
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.
Požadované prerekvizitní znalosti a dovednosti
- Znalost problematiky algorimizace na úrovni magisterského studia
Literatura studijní
- Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge
Literatura referenční
- Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, London, England 1990.
Osnova seminářů
- 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
Průběžná kontrola studia
Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.
Úspěšná prezentace zadaného projektu
Kontrolovaná výuka
Výuka není kontrolována.