Skočit na navigaci

Informační systém Masarykovy univerzity

Informace o předmětu

IS MU > Katalog předmětů

česky | in English

IA101 Algoritmika pro těžké problémy

Fakulta informatiky
podzim 2014

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

Rozvrh

Po 12:00–13:50 D2

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á 23 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