I063 Návrh algoritmů II

Fakulta informatiky
jaro 2004
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í)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 10:00–11:50 D2
Předpoklady
SOUHLAS
.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
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
Metody hodnocení
Predmet sa otvara posledny krat a je urceny studentom, ktori mali zapisany predmet I063 semestri ja studiaro 2003, ale v tomto semestri predmet neukoncili. Vyuka sa bude konat formou indiviualneho studia.
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 2003.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2004/I063