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

I063 Návrh algoritmů II

Fakulta informatiky
jaro 1999

Rozsah

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

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.

Předpoklady

I002 Návrh algoritmů I && M010 Kombinatorika a grafy
Podmínkou pro zápis je absolvování kursů I002 Návrh algoritmů I a M010 Kombinatorika a teorie grafů.

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. Aplikace a využití při návrhu efektivních datových struktur.
Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, greedy algoritmy. Obecná formulace, aplikace, teoretické základy.
Efektivní algoritmy -- polynomy (Fourieova trnasformace), vyhledávaní řetězů (algoritmy Knuth-Morris-Pratt, Boyer-Moore).
Metody návrhu pravděpodobnostních algoritmů -- očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Příklady.
Metody návrhu aproximativních algoritmů -- relativní aproximace a aproximativní schémy. Aplikace: pokrytí grafu, obchodní cestující, rozvrhování, pokrytí množin, vyhledávaní řetězů.
On-line algoritmy. Metody analýzy jejich složitosti -- potenciálové funkce, minimax princip. Příklady.

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ě.
Výuka probíhá každý týden.