DMI025 - Pravděpodobnostní algoritmy

DMI025 - Pravděpodobnostní algoritmy
LS 2003

Zajišťuje: KAM
Vyučující: Jiří Sgall
Rozsah v ZS: ---
Rozsah v LS: 2/0 Zk
Třída: I

UMLUVENO: koná se ve středu 12.30 v Matematickém ústavu v Žitné ulici 25 v seminární místnosti v 3. patře přední budovy.
Budova Matematického ústavu je u křižovatky se Štěpánskou. V průjezdu vpravo je místnost podatelny, tam Vám otevřou protější vstup do budovy. Seminární místnost je ve nejvyšším patře naproti schodům.

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.

5. 4. 2002