NDMI025 - Pravděpodobnostní algoritmy

LS 2013 - Jiří Sgall

Probraná témata

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


Úkoly a cvičení

Na zápočet je třeba polovina počtu bodů (bez bonusů), každý příklad je za dva body.

Výsledky

Pokud se v tabulce nenajdete, napište mi přezdívku.


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


Probraná témata v LS 2011

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.