Detail předmětu

Vybrané kapitoly z algoritmů

FIT-VKDAk. rok: 2017/2018

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,

Jazyk výuky

čeština, angličtina

Garant předmětu

prof. Ing. Jan M. Honzík, CSc.

Zajišťuje ústav

Ústav informačních systémů (UIFS)

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

Způsob a kritéria hodnocení

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

Osnovy výuky

    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

Učební cíle

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Výuka není kontrolována.

Základní literatura

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

Doporučená literatura

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

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

  • Program VTI-DR-4 doktorský

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