Název:

Vybrané kapitoly z algoritmů

Zkratka:VKD
Ak.rok:2012/2013
Semestr:letní
Studijní plán:
ProgramOborRočníkPovinnost
VTI-DR-4DVI4-volitelný
Vyučovací jazyk:čeština
Ukončení:zkouška (ústní)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:390000
 zkouškatestycvičenílaboratořeostatní
Body:00000
Garant:Honzík Jan M., prof. Ing., CSc., UIFS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav informačních systémů FIT VUT v Brně
 
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.
Anotace:
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,
Požadované prerekvizitní znalosti a dovednosti:
  • Znalost problematiky algorimizace na úrovni magisterského studia
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í
Dovednosti, znalosti a kompetence obecné:
  • Student prokáže schopnost vyspělé presentace výsledků zadaného projektu
Osnova přednášek:
  1. Rekurze: substituční metoda, iterační metoda, hlavní metoda, teorém hlavní metody.
  2. Četnosti a pravděpodobnost
  3. Dynamické programování
  4. Nenasytné (greedy) algoritmy
  5. Mediány a pořadová statistika
  6. Červeno-černé stromy
  7. Splay stromy
  8. Přeskakovací seznamy (Skip-lists)
  9. B-Stromy
  10. Binomické stromy
  11. Binomická hromada
  12. Fibonacciho hromada
  13. Polynomy a FFT
Literatura referenční:
  1. Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, London, England 1990.
Literatura studijní:
Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge
Podmínky zápočtu:
Úspěšná prezentace zadaného projektu