I063 Návrh algoritmů II

Fakulta informatiky
jaro 2000
Rozsah
2/0. 2 kr. (plus ukončení). 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
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
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í. Obecná formulace, aplikace, teoretické zá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ů.
  • 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: vyhledávací stromy, nezávislé množiny.
  • Metody návrhu on-line algoritmů. Srovnávací analýza on-line algoritmů. Náhodnostní on-line algoritmy. Aplikace: stránkování, obsluha procesorů
Literatura
  • BRASSARD, Gilles a Paul BRATLEY. Fundamentals of algorithmics. London: Prentice-Hall International, 1996, xix, 524 s. ISBN 0-13-073487-X. info
  • MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
  • KOZEN, Dexter C. The Design and Analysis of Algorithms. New York: Springer-Verlag, 1992, 320 s. ISBN 0387976876. info
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
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.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2001, jaro 2002, jaro 2003, jaro 2004.