Předmět Algoritmy (KMI / PGSAL)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / PGSAL - Algoritmy, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).

Materiál	Typ	Datum	Počet stažení

Obsah

Obsahem předmětu jsou vybrané partie z algoritmů. Důraz je kladen na aspekty, které jsou nad rámec látky z bakalářského a magisterského studia.- Přehled vybraných teoretických modelů výpočtu a odpovídajících pojmů složitosti, vzájemné vztahy.- Růst funkcí, "Big O" notace, základní vztahy, základní funkce pro analýzu algoritmů, rekurence, master theorem.- Pravděpodobnostní analýza a randomizace.- Analýza složitosti vybraných algoritmů, analýza v nejhorším a v průměrném případě.- Pokročilé stromové struktury: B-stromy, R-stromy, M-stromy, prefixové stromy.- Sumy, rekurence, celočíselné funkce, generující funkce, asymptotické metody.- Pokročilé techniky návrhu a analýzy algoritmů: dynamické programování, žravé algoritmy, amortizovaná analýza.- Optimalizační problémy a aproximační algoritmy (NP-obtížnost, třídy složitosti, redukce, příklady problémů a aproximačních algoritmů).

Získané způsobilosti

2. PorozuměníPopsat a důkladně pochopit principy a metody algoritmů a jejich návrhu.

Literatura

Hromkovič J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd Edition. Springer, 2003. ISBN 3540441344.Sedgewick R., Flajolet P. An Introduction to the Analysis of Algorithms. 2nd Printing. Addison-Wesley, 2001. Ausiello G. et al. Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin, 1999. ISBN 3540654313.Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics. A Foundation for Computer Science. Second Edition. Addison-Wesley, 1994. ISBN 0201558025.Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. Second Edition. MIT Press, 2001. ISBN 0-262-53196-8.Levitin A. Introduction to the Design and Analysis of Algorithms. Addison Wesley, 2003. ISBN 321-21076-X.Skiena S. S. The Algorithms Design Manual. Springer, New York, 1998. ISBN 0-387-94860-0.

Požadavky

Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.

Garant

prof. RNDr. Radim Bělohlávek, Ph.D., DSc.

Vyučující

prof. RNDr. Radim Bělohlávek, Ph.D., DSc.