IB108 Návrh algoritmů II

Fakulta informatiky
jaro 2006
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Bc. Tomáš Richter (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 12:00–13:50 D3
Předpoklady
( I002 Návrh algoritmů I || IB002 Návrh algoritmů I )&&! I063 Návrh algoritmů II
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
předmět má 11 mateřských oborů, zobrazit
Cíle předmětu
Kurz navazuje na úvodní kurz Návrh algoritmů I. Prezentuje algoritmické koncepty a konstrukty bez jejich přímé návaznosti na jakýkoliv programovací jazyk a bez požadavků na jejich praktickou programovou realizaci. Cílem je naučit studenta konstruovat a analyzovat algoritmy v kontextu pseudokódů, což umožní studentovi rozlišit mezi obecnými koncepty a specifikami konkrétních programovacích jazyků. Kurz uvádí pokročilé techniky analýzy algoritmů. Rozšiřuje seznam algoritmických strategií a charakterizuje typ problémů, pro které jsou jednotlivé strategie vhodné. Nové datové struktury jsou prezentovány spolu s příklady algoritmů, které je využívají, přičemž důraz je kladen na propojenost návrhu algoritmu a návrhu datové struktury.
Osnova
  • Techniky návrhu a analýzy algoritmů: dynamické programování, hladové strategie, backtracking, lokální vyhledávání. Amortizovaná analýza složitosti.
  • Datové struktury: binomiální a Fibonacciho haldy, datové struktury pro reprezentaci disjunktních množin.
  • Grafové algoritmy: kostry v grafech, problém nejkratších cest, toky v sítích, párování.
  • Algoritmy pro práci s řetězci: přímý algoritmus, Rabin-Karpův algoritmus, užití konečných automatů.
  • Algoritmy pro NP-těžké problémy: aproximativní algoritmy. Problém pokrytí množin a problém obchodního cestujícího.
  • Náhodnostní algoritmy: náhodnostní třídění, problém maximální nezávislé množiny. Náhodnost v datových strukturách.
Literatura
  • 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, 1989, xvii, 1028. ISBN 0070131430. info
Záložky
https://is.muni.cz/ln/tag/FI:IB108!
Metody hodnocení
Informace na webové stránce předmětu http://www.fi.muni.cz/usr/cerna/NAII/ib108.html
Informace učitele
http://www.fi.muni.cz/usr/cerna/NAII/ib108.html
Informace na webové stránce předmětu http://www.fi.muni.cz/usr/cerna/NAII/ib108.html
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2003, jaro 2004, jaro 2005, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013.