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

I063 Návrh algoritmů II

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

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

• Informatika (program FI, B-IN)
• Informatika (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Výpočetní technika (program FI, B-IN)

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

• Statistika zápisu (léto 1998, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/leto1998/I063