Detail předmětu
Vybrané kapitoly z algoritmů
VKD Ak. rok 2008/2009 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
Přednášející
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
Metody vyučování
Metody vyučování závisí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.
Kontrolovaná výuka
Výuka není kontrolována.