IA101 Algoritmika pro těžké problémy

Fakulta informatiky
podzim 2007
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Mgr. Jiří Šimša (cvičí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 D2
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á 20 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
  • Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001
  • R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
  • V. Vazirani: Approximation Algorithms. Springer, 2001
Metody hodnocení
Pisemna zkouska na konci semestru. Reseni ukolu v prubehu 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 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017.

Nahoru | Aktuální datum a čas: 20. 1. 2018 07:53, 3. (lichý) 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