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

Petr Kolman, Jiří Sgall

Fall 2019 - Monday 10:40 v S3

Česká cvičení se konají jednou za 14 dnů ve středu od 15:40, vede je Michal Berg.

English exercises (recitations) take place once in two weeks on Wednesday at 3:40 pm and are led by Michal Berg.

The first half of the course will be given by Petr Kolman

Czech lecture notes - poznámky k přednášce (verze 8. 1. 2020)

Covered topics

Previous run of the course in Czech - předchozí běh přednášky v r. 2018

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.

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: