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.
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í.
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