NDMI084 - Introduction to approximation and randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů

Petr Kolman, Jiří Sgall

Fall 2017 - Monday 14:00 in S5
English section

English exercises (recitations) take place once in two weeks on Monday at 15:40 in S7 and are led by Pavel Veselý

Czech section

Česká přednáška se koná v pondělí od 9:00 v S9, přednáší Petr Kolman

Česká cvičení se konají jednou za 14 dnů v úterý od 17:20, vede je Pavel Veselý

Poznámky k přednášce [lecture notes in Czech, Dec 11, 2017]

Covered topics

Previous run of the course in 2016 [předchozí běh]

Syllabus

This course covers techniques for design and analysis of algorithms, demonstrated on concrete combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design algorithms that finds an optimal solution fast. In such a case we study approximation algorithms that work faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness in design of (approximation and other) algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable. Recommended for the 3rd year.

Sylabus [Detailed syllabus in Czech]

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:

Textbooks:

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

[MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.

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

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

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