Detail předmětu
Vybrané kapitoly z algoritmů
VKD Ak. rok 2015/2016 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í
Rozsah
- 39 hod. přednášky
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 přednášek
- 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.
Zařazení předmětu ve studijních plánech