DMI025 - Pravděpodobnostní algoritmy
LS 2005
Zajišťuje: KAM
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.
Základní lit.
R. Motwani, P. Raghavan: Randomized algorithms.
Doplň.popis
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.
23. 3. 2004