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:
 
  • 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
Literatura referenční:
 
  • 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