NDMI025 - Pravděpodobnostní algoritmy

LS 2013 - 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 [MR 1.5, 2.3]

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

Markov, Čebyšev, Černov-Hoefding [MU 3.1-3.3, 4.2-4.3, MR 3.2, 4.1]

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

po 2 nezávislé proměnné, definice, konstrukce [MU 13.1, MR 8.4]
náhodné procházky na expanderech [MR 6.8]

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

MINCUT - jednoduchý alg., zlepšení iterativním procesem na čas O(n² polylog n) [MR 1.1, 10.2]
MIS: paralelní algoritmus pro hledání maximální nezávislé množiny (maximální vzhledem k inkluzi, tedy ne nutně největší) [MR 12.3]
splnitelnost: algoritmy založené na náhodných procházkách pro 2SAT, 3SAT (rychlý exponenciální algoritmus) [MU 7.1]
směrování na hyperkrychlích [MU 4.5.1]
FastSelect - rychlé vyhledávání mediánu pomocí samplování [MU 3.4, MR 3.3]

Hashování

definice univerzálních systémů hashovacích funkcí, jejich konstrukce [MU 13.3, MR 8.4]
dynamické hashování s průměrným konstantním časem vyhledávání. [MU 5.5.1, MR 8.5]
statické hashování s nejhorším konstantním časem vyhledávání [MU 13.3, MR 8.5]
Bloomovy filtry (bez důkazu) [MU 5.5.3]
streaming - hledání častých prvků v proudu dat [MU 13.4]

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

stacionární distribuce, její existence a konvergence, periodičnost [MU 7.2, MR 6.2]
čas pokrytí grafu a dosažení daného vrcholu, odhady, příklady pro konkrétní grafy [MU 7.4, MR 6.3, 6.5]
vztah k elektrickým obvodům [MR 6.4]
testování souvislosti grafů, univerzální transverzální posloupnosti [MR 6.6]
coupling, použití k odhadu rychlosti konvergence [MU 11.1-11.2]
přibližné generování náhodných obarvení grafu [MU 11.4-11.5]

Expandery [MR 6.7-6.8]

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í [MU 10.1, MR 11.1]
počítání splňujících ohodnocení DNF [MU 10.2, MR 11.2]
permanent (párování v bipartitních grafech), konduktance a použití náhodných procházek [MR 11.3]

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

neizomorfismus grafů [MR 7.7.1]
maticové násobení [MR 7.1-7.2, MU 1.3]
lineární funkce a PCP věta [MR 7.8, http://iuuk.mff.cuni.cz/~sgall/pcp/]

[MR] R. Motwani, P. Raghavan: Randomized algorithms.
[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Úkoly a cvičení

Na zápočet je třeba polovina počtu bodů (bez bonusů), každý příklad je za dva body.

1. série úkolů (termín 5. 3. před přednáškou)
V úloze 3 předpokládejte, že algoritmus s kontrakcemi z n vrcholů do t vrcholů je implementovaný v O(n^2) bez ohledu na t a počet hran. (To je možné, pokud předpokládáme aritmetické operace jednotkové ceny.)
Cvičení k tomuto úkolu budou 6. března
2. série úkolů (termín 26. 3. před přednáškou)
Cvičení k tomuto úkolu budou 27. března
3. série úkolů (termín 16. 4. před přednáškou)
Cvičení k tomuto úkolu budou 17. dubna
4. série úkolů (termín 21. 5. před přednáškou)
Cvičení k tomuto úkolu budou 22. května

Výsledky

Pokud se v tabulce nenajdete, napište mi přezdívku.

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

1. (26. 2.)

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

2. (5. 3.)

Markovova a Čebyševova nerovnost
Černovovy nerovnosti
třídy pravděpodobnostních algoritmů, amplifikace

3. (19. 3.)

FastSelect - rychlé vyhledávání mediánu pomocí samplování
směrování na hyperkrychlích

4. (20. 3.)

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. (26. 3.)

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

6. (2. 4.)

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

7. (3. 4.)

expander, definice, úvod, vlastní čísla
vztah vlastních čísel a expanze

8. (9. 4.)

náhodné procházky na expanderech
přibližné počítání, metoda Monte Carlo
počítání splňujících ohodnocení DNF

9. (16. 4.)

coupling - úvod, míchání karet
coupling - přibližné generování obarvení grafu Markovovým řetězcem

10. (23. 4.)

permanent - přibližné počítání perfektních párování pomocí Markovových řetězců

11. (24. 4.)

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

12. (30. 4.)

paralelní algoritmus pro hledání maximální nezávislé množiny, jeho derandomizace
Bloomovy filtry (bez důkazu)
streaming - hledání častých prvků v proudu dat

13. (21. 5.)

PCP věta
vyhodnocování stromů a věta o minimaxu (von Neumann - Yao)

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.