FI:I063 Návrh algoritmů II - Informace o předmětu

I063 Návrh algoritmů II

Fakulta informatiky
jaro 2002

Rozsah

2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

Garance

Rozvrh

St 10:00–11:50 D2

Předpoklady

I002 Návrh algoritmů I && M010 Kombinatorika a grafy

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/i063.html

Další komentáře

Předmět je vyučován každoročně.