NDMI084 - Úvod do aproximačních a pravděpodobnostních algoritmů

ZS 2014 - Jiří Sgall

Přednáška se koná v úterý od 14:00 v S5, cvičení se konají nepravidelně po přednášce od 15:40 také v S5

Úkoly a cvičení

Cvičení budou formou domácích úkolů a jejich řešení na cvičeních cca 1x za 3-4 týdny.

Data cvičení jsou 21. 10., 25. 11. a poslední buď 16. 12. nebo 6. 1.

Výsledky

Předchozí běh přednášky v r. 2013

Poznámky k přednášce (verze 21. 10.)

Probraná látka podle přednášek

Sylabus

Přednáška probírá středně pokročilé techniky pro návrh a analýzu algoritmů a ilustruje je na konkrétních kombinatorických problémech. Pro mnohé optimalizační problémy je obtížné navrhonout algoritmy, které je vyřeší optimálně a zároveň rychle (např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Často pro návrh algoritmů (aproximačních i jiných) používáme náhodnost, což umožňuje řešit některé úlohy efektivněji nebo řešit úlohy jinak neřešitelné. Doporučeno pro 3. ročník bakalářského studia.

Probírané techniky:

Probírané problémy a algoritmy:

Literatura

[KT] J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.

[WS] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.

[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.

[MR] R. Motwani, P. Raghavan: Randomized algorithms.

[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis.