Předmět Algoritmika pro těžké problémy (IA101)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IA101 - Algoritmika pro těžké problémy, Fakulta informatiky, Masarykova univerzita (MU).

Materiál	Typ	Datum	Počet stažení

Cíl

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 protěž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á literaturaD. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001. xix, 378 s. ISBN 3-540-65367-8. infoMOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: University Press, 1995. xiv, 476 s. ISBN 0-521-47465-5. infoHROMKOVIČ, Juraj 1958-. Algorithmics for hard problems :introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001. xi, 492 s. ISBN 3-540-66860-8. infoCORMEN, Thomas H., Charles E. LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990. xi, 1028 s. ISBN 0-262-03141-8. infoIn pursuit of the traveling salesman :mathematics at the limits of computation. ISBN 9780691152707. infoCHVÁTAL, Vašek. Linear programming. New York: W.H. Freeman, 1983. xiii, 478. ISBN 0-7167-1587-2. info

Požadavky

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

Garant

prof. RNDr. Mojmír Křetínský, CSc.

Vyučující

prof. RNDr. Ivana Černá, CSc.