IA101 Algoritmika pro těžké problémy

Fakulta informatiky
podzim 2009
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
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.
Rozvrh
Po 14:00–15:50 D3
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory
předmět má 26 mateřských oborů, zobrazit
Cíle předmětu
Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.
Osnova
  • Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
  • Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
  • Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
  • Heuristické přístupy: simulované žíhání, genetické algoritmy.
Literatura
  • VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001. xix, 378. ISBN 3540653678. info
  • MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995. xiv, 476. ISBN 0521474655. info
  • HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001. xi, 492. ISBN 3540668608. info
Výukové metody
teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik
Metody hodnocení
Pisemna zkouska na konci semestru.
Informace učitele
https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2006%2FIA101%2Findex.qwarp
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 podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017.

Nahoru | Aktuální datum a čas: 22. 4. 2018 10:57, 16. (sudý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému