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

Petr Kolman, Jiří Sgall

Fall 2016 - Tuesday 14:00 in S4 

Česká cvičení se konají jednou za 14 dnů v pondělí od 14:00, vede je Martin Böhm.

English classes (recitations) take place once in two weeks on Monday at 2 pm and are led by Martin Böhm.

The first half of the course was given by Petr Kolman

Předchozí běh přednášky v r. 2015 [previous year]

Poznámky k přednášce [lecture notes in Czech, Jan 18, 2016 - not much new in the new version]

Covered topics

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.