Detail předmětu

Vybrané kapitoly z algoritmů

FIT-VKDAk. rok: 2019/2020

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,

Výsledky učení 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

Prerekvizity

  • Znalost problematiky algorimizace na úrovni magisterského studia

Doporučená nebo povinná literatura

Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, London, England 1990.

Způsob a kritéria hodnocení

Úspěšná prezentace zadaného projektu

Jazyk výuky

čeština

Cíl

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.

Zařazení předmětu ve studijních plánech

  • Program VTI-DR-4 doktorský

    obor DVI4 , libovolný ročník, letní semestr, 0 kreditů, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , libovolný ročník, letní semestr, 0 kreditů, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , libovolný ročník, letní semestr, 0 kreditů, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , libovolný ročník, letní semestr, 0 kreditů, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

Osnova


  • 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