NDMI025 - Pravděpodobnostní algoritmy
LS 2009
Vyučující: Jiří Sgall
Rozsah v ZS: ---
Rozsah v LS: 2/0 Zk
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
- Příklady pravděpodobnostních algoritmů a protokolů. Třídy
pravděpodobnostních
algoritmů.
- Základní nerovnosti používané při analýze pravděpodobnostních
algoritmů.
Věty o minimaxu (von Neumann, Yao).
- Techniky pro omezení počtu náhodných bitů (po dvou nezávislé
proměnné,
expandery).
- Markovovy řetězce a náhodné procházky. Testování souvislosti
grafů.
- Pravděpodobnostní algoritmy pro kombinatorické problémy.
- Hashování s konstantním časem vyhledávání.
- Pravděpodobnostní protokoly, kryptografie s veřejným klíčem (RSA,
Rabinův
systém).
- Náhodnost v on-line algoritmech.
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.
Úmluva bude v prvním týdnu semestru na KAM, v rámci hromadné úmluvy
na výběrové přednášky KAM.
Kontakt: sgall@math.cas.cz, http://www.math.cas.cz/~sgall/,
tel. 22090780.
24. 9. 2008