I387 - Pravděpodobnostní algoritmy

I387,M734 - Pravděpodobnostní algoritmy
LS 1999

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

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ředpoklady

Základní pojmy z teorie pravděpodobnosti (např. I129) a teorie algoritmů (např. I148 nebo I404).

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-3 roky.

Úmluva pro letní semestr 1999 bude v prvním týdnu semestru v rámci hromadné úmluvy na KAM (MFF Malá Strana, 3.patro). Termín bude upřesněn.

Kontakt

sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 22090724

Probraná témata

Třídy pravděpodobnostních algoritmů.

RP, BPP, ZPP, PP, RLOGSPACE vztahy k P, NP, PSPACE, polynomiálním obvodům
aproximační alg., aproximace v průměru vs. s velkou pravděp., (F)PRAS, vztah k #P

Základní nerovnosti používané při analýze pravděpodobnostních algoritmů.

Markov, Chernoff-Hoefding

Pravděpodobnostní algoritmy pro kombinatorické problémy.

MINCUT - jednoduchý alg., zlepšení iterativním procesem na čas O(n² polylog n)
MAXCUT - jednoduchý 2-aproximační alg., derandomizace

Techniky pro omezení počtu náhodných bitů

po k nezávislé proměnné

definice, odhady na velikost pravděpodobnostních prostorů
konstrukce - lineární funkce, resp. polynomy, Sylvestrova matice

náhodné procházky na expanderech

Hashování

definice univerzálních systémů hashovacích funkcí, jejich konstrukce
dynamické hashování s průměrným konstantním časem vyhledávání.
statické hashování s nejhorším konstantním časem vyhledávání

Věty o minimaxu

von Neumann, Yao, vztah k teorii her

Vyhodnocování stromů pro hry (úplné binární AND-OR stromy)

deterministický dolní odhad 2^2k
pravděpodobnostní algoritmus 3^k, dolní odhad 2.61^k

Markovovy řetězce a náhodné procházky.

stacionární distribuce, její existence a konvergence, periodičnost
čas pokrytí grafu a dosažení daného vrcholu, odhady, příklady pro konkrétní grafy
vztah k elektrickým obvodům
testování souvislosti grafů

Expandery

definice, konstrukce explicitní a pravděpodobnostní
vztah vlastních čísel a expanze
náhodné procházky na expanderech, rychlá konvergence, použití k derandomizaci

Přibližné počítání

odhady pomocí náhodných vzorků z většího univerza (tzv. Monte-Carlo)
generování přibližně náhodných vzorků pomocí náhodných procházek
iterované použití pro výpočet permanentu hustých 0-1 matic
konduktance, metoda kanonických cest pro permanent

Náhodnost v on-line algoritmech

kompetitivní poměr
cachování s k stránkami rychlé paměti (pravděpodobnostně O(log k) kompetitivní vs. k deterministicky)
rozvrhování, dva modely: v reálném čase a s posloupností požadavků

hladový algoritmus, jeho (téměř) optimalita v modelu v reálném čase
rozvrhování pro 2 počítače s posloupností požadavků - 3/2 deterministicky vs. 4/3 pravděpodobnostně

Číselně teoretické algoritmy

kvadratická rezidua a odmocniny
testování prvočíselnosti
kryptografie s veřejným klíčem (RSA, Rabinův systém)

I387,M734 - Pravděpodobnostní algoritmy LS 1999