NDMI025 - Pravděpodobnostní algoritmy

LS 2011 - Jiří Sgall

Probraná témata

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

RP, BPP, ZPP, PP, RL(ogspace) vztahy k P, NP, PSPACE, polynomiálním obvodům

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

Markov, Čebyšev, Černov-Hoefding

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

po 2 nezávislé proměnné, definice, konstrukce
náhodné procházky na expanderech

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

MINCUT - jednoduchý alg., zlepšení iterativním procesem na čas O(n² polylog n)
MIS: paralelní algoritmus pro hledání maximální nezávislé množiny (maximální vzhledem k inkluzi, tedy ne nutně největší)
splnitelnost: algoritmy založené na náhodných procházkách pro 2SAT, 3SAT (rychlý exponenciální algoritmus)
směrování na hyperkrychlích

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í
streaming - hledání častých prvků v proudu dat

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ů, univerzální transverzální posloupnosti
coupling, použití k odhadu rychlosti konvergence
přibližné generování náhodných obarvení grafu
barvení 3-chromatických grafů 2 barvami bez monochromatických trojúhelníků

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í

redukce na náhodné vybírání
počítání splňujících ohodnocení DNF
permanent (párování v bipartitních grafech), konduktance a použití náhodných procházek

Věty o minimaxu - von Neumann, Yao, vztah k teorii her
Vyhodnocování stromů pro hry (úplné binární AND-OR stromy) - pravděpodobnostní algoritmus 3^k, dolní odhad 2.61^k
Verifikace

maticové násobení
lineární funkce
PCP věta

Distribuované algoritmy - dělení dortu s lineárním počtem řezů

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

1. (7.3.)

úvod, příklady: průměrný plat, grafový neizomorfismus, quicksort
MINCUT - začátek

2. (28.3.)

MINCUT - (skoro) kvadratický algoritmus s větvením
Čebyševova nerovnost
FastSelect - rychlé vyhledávání mediánu

3. (4.4.)

Černovovy nerovnosti
třídy pravděpodobnostních algoritmů, amplifikace

4. (4.4.)

routing na hyperkrychlích
náhodné procházky - úvod, příklady, definice
čas pokrytí grafu a dosažení daného vrcholu, odhady, příklady pro konkrétní grafy
algoritmus na 2SAT

5. (11.4.)

algoritmus na 3SAT
Markovovy řetězce, stacionární distribuce, její existence a konvergence, periodičnost

6. (18.4.)

vztah náhodných procházek k elektrickým obvodům
souvislost grafů
univerzální transversální posloupnosti

7. (18.4.)

expander, definice, úvod, vlastní čísla
vztah vlastních čísel a expanze
náhodné procházky na expanderech

8. (2.5.)

přibližné počítání
počítání splňujících ohodnocení DNF
permanent - redukce na generování perfektních a skoro perfektních párování

9. (9.5.)

permanent - dokončení
coupling - úvod, míchání karet

10. (9.5.)

barvení 3-chromatických grafů 2 barvami bez monochromatických trojúhelníků
coupling - přibližné generování obarvení grafu Markovovým řetězcem

11. (16.5.)

po dvou nezávislé proměnné
systémy hashovacích funkcí
dynamické a statické hashování
streaming

12. (23.5.)

PCP věta
vyhodnocování stromů a věta o minimaxu (von Neumann - Yao)
paralelní algoritmy pro hledání maximální nezávislé množiny
podle času cake cutting

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.