IA101 Algoritmika pro těžké problémy

Fakulta informatiky
podzim 2017
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.
Dodavatelské pracoviště: Katedra teorie programování - Fakulta informatiky
Předpoklady
Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).
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á 24 mateřských oborů, zobrazit
Cíle předmětu
Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.
Osnova
  • Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
  • Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
  • Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
  • Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.
Literatura
    doporučená literatura
  • D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
  • 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
  • CORMEN, Thomas H., Charles E. LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989. xvii, 1028. ISBN 0070131430. info
  • COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012. xiii, 228. ISBN 9780691152707. info
  • CHVÁTAL, Vašek. Linear programming. New York: W.H. Freeman, 1983. xiii, 478. ISBN 0716715872. 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/el/1433/podzim2014/IA101/index.qwarp
Další komentáře
Studijní materiály
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 podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/podzim2017/IA101

Nahoru | Aktuální datum a čas: 19. 8. 2017 09:29, 33. (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