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

Jiří Sgall

ZS 2020 - Pondělí 10:40 v S3 / zoom

Cvičení se konají jednou za 14 dnů ve čtvrtek od 14:00 v S11, vede je Matej Lieskovský

Distanční výuka proběhne formou online přednášek přes zoom. Adresa je https://cesnet.zoom.us/my/[moje příjmení] . První přednáška se koná 5. 10. 2020. Budu rád, pokud se přednášky zúčastníte interaktivně, se zapnutým videem alespoň na diskusní části, a s plným jménem.

Konzultace nabízím na stejném zoomu většinou v pondělí nebo v úterý odpoledne, případně i jindy po dohodě.

Poznámky k přednášce (verze 8. 1. 2020)

Záznamy přednášek jsou k dispozici v SISu pro zapsané studenty

English section

Zkoušky

Zkouška je ústní s písemnou přípravou. Po zadání otázky se většina studentů připravuje cca 10-20 minut. Poté následuje diskuse nad přípravou, doplňující otázky apod. Podobně bude probíhat i distanční zkouška.

Termíny prezenčních zkoušek jsou vypsané v SISu na pondělí dopoledne. Mají malou kapacitu, abychom mohli dodržovat potřebné odstupy. Pokud se naplní kapacita a jste ve frontě, můžete počítat s tím, že Vás v daný den vyzkouším. Pokud by se místo neuvolnilo, tak se domluvíme na čase buď dříve anebo odpoledne.

Pokud nemůžete nebo nepovažujete za bezpečné přijet na prezenční zkoušku, vyzkouším Vás distančně přes zoom. Tyto termíny dohodneme individuálně mailem. Je potřeba minimálně funkční mikrofon a kamera. Rád bych také viděl Vaše poznámky z přípravy, např. naskenované či vyfocené, v nejhorším aspoň přes kameru. Ideální by bylo psát na sdílenou obrazovku např. na tabletu, pokud máte tu možnost.

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

Probraná látka podle přednášek v r. 2018

Předchozí běh přednášky v r. 2019 (anglicky)

Literatura

[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.

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: