I063 Návrh algoritmů II

Fakulta informatiky
jaro 2003
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (pomocník)
Mgr. Tomáš Hanžl (pomocník)
RNDr. Lukáš Hejtmánek, Ph.D. (pomocník)
Mgr. Pavel Krčál (pomocník)
Mgr. Petr Liška (pomocník)
Mgr. Pavel Moravec (pomocník)
doc. Mgr. Adam Rogalewicz, Ph.D. (pomocník)
Mgr. Jitka Žídková (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 8:00–9:50 D1
Předpoklady
( I002 Návrh algoritmů I || IB002 Návrh algoritmů I )&&! IB108 Návrh algoritmů II &&(!NOW( IB108 Návrh algoritmů II ))
Kurz je určen studentům 5-letého magisterského studia a v jarním semestru 2002/03 se otevírá naposledy.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda.
  • Návrh a využití efektivních datových struktur. Binomiální a Fibonacciho haldy. Balancované vyhledávací stromy. Množinové datové struktury.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, hladové algoritmy, prohledávání. Teoretické základy, aplikace.
  • Metody návrhu aproximativních algoritmů -- sekvenční metody, lokální vyhledávání, linerární programování. Aplikace.
  • Metody návrhu pravděpodobnostních algoritmů -- náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Derandomizace. Aplikace.
  • Metody návrhu on-line algoritmů. Srovnávací analýza. Náhodnostní on-line algoritmy.
Literatura
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Informace učitele
http://www.fi.muni.cz/usr/cerna/NAII/i063.html
Další komentáře
Předmět je vyučován naposledy.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2002, jaro 2004.