NDMI025 - Pravděpodobnostní algoritmy

LS 2011 - Jiří Sgall

Probraná témata


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

1. (7.3.)

2. (28.3.)
3. (4.4.)
4. (4.4.)
5. (11.4.)
6. (18.4.)
7. (18.4.)
8. (2.5.)
9. (9.5.)
10. (9.5.)
11. (16.5.)
12. (23.5.)

Anotace

Přenáška o použití náhodnosti v algoritmech a protokolech. Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně. Probereme základní techniky pro návrh a analýzu takových algoritmů a protokolů, ilustrované na konkrétních problémech. Předpokládá se znalost základních pojmů z teorie pravděpodobnosti (např. STP064) a teorie algoritmů (např. DMI026).

Osnova

Literatura

R. Motwani, P. Raghavan: Randomized algorithms.
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Další informace

Přednáška se nekoná každý rok, předpokládám její opakování za 2 roky.