Literatúra:
- Ochutnávka pravdepodobnostných algoritmov
- pravdepodobnostné konečné automaty
- testovanie násobenia matíc
- hľadanie minimálneho rezu
- poznámky
- Motwani, kap. 1.1., 7.1
- ďalšie materiály:
- Analýza pravdepodobnostných algoritmov
- opakovanie pravdepodobnosti
- odhady chvostov distribúcií - Markov, Čebyšev, Chernoff
- poznámky (sekcie hešovanie ani martingaly sa neprednášali)
- Triedenie a vyhľadávanie
- quicksort a analýza s.v.p.
- treap
- skiplist
- poznámky
- ďalšie materiály:
- Hľadanie mediánu
- poznámky
- Motwani kap. 3.3, Mitzenmacher kap. 3.4
- ďalšie materiály:
- Hešovanie
- univerzálne rodiny hešovacích funkcií
- perfektné hešovanie (O(1) vyhľadávanie pre statický slovník)
- lineárne sondovanie
- poznámky
- Metódy - eliminácia nepriateľa, odtlačky
- on-line joby (tu)
- perfektné párovania
- testovanie rovnosti polynómov
- izolačná lema
- poznámky, slidy
- Motwani kap. 7.2-7.3, 12.4
- ďalšie materiály:
- Hľadanie najkratších ciest
- Seidelov algoritmus
- slidy
- Motwani kap. 10.1
- Intermezzo:
- Metódy - znižovanie zložitosti opakovaním a random sampling
- Hľadanie minimálneho rezu
- jednoduchý kontrahovací algoritmus a jeho zrýchlenia
- sparsifikátory
- poznámky
- Motwani kap. 10.2
- ďalšie materiály:
- Problém splniteľnosti
- Schöningov algoritmus na riešenie 3-SATu
- slidy
- Hľadanie najlacnejšej kostry
- lineárny samplovací algoritmus pre hľadanie najlacnejšej kostry
- matice a grafy
- poznámky
- Motwani kap. 10.3
- ďalšie materiály:
- Metódy - metóda svedkov a testovanie prvočíselnosti
- Lineárne programovanie
- Seidelov, MSW a Clarksonove algoritmy
- randomizované inkrementálne algoritmy a samplovanie
- poznámky
- Motwani kap. 9.10
- ďalšie materiály:
- Náhodné prechádzky
- Miešanie kariet
- Markov Chain Monte Carlo (MCMC)
- samplovanie pomocou náhodných prechádzok (náhodné grafy s predpísanými stupňami, náhodné riešenia knapsacku)
- reverzibilné MR a Metropolisov-Hastingsov algoritmus (ako vyrobiť MR s danou stacionárnou distribúciou)
- bayesovská inferencia, MrBayes
- slidy
- Náhodnosť a zložitosť
- pravdepodobnostné triedy zložitosti (ZPP, RP, coRP, BPP, PP)
- BPP a δ-BPP (poznamky DP)
- Adlemanova veta (BPP a boolovské obvody), Sipser-Gacsova veta (BPP a polynomiálna hierarchia)
- poznámky
- Arturove Merlinove hry
- triedy MA a AM
- protokol pre grafový neizomorfizmus so súkromnou a verejnou mincou (t.j. GNI je v IP[2] aj v AM)
- protokoly v MA a AM sa dajú upraviť tak, aby mali perfektnú úplnosť
- zosilnenie Sipser-Gacsovej vety: MA ⊆ Σ2P; MA ⊆ AM ⊆ Π2P
- bonus: ak by bol grafový izomorfizmus NP-ťažký problém, skolabuje PH
- poznámky
- Interaktívne dôkazy
- #P ⊆ IP
- myšlienka IP = PSPACE
- slidy
- Pravdepodobnostne overiteľné dôkazy
- NP = PCP[n3, 1]
- Arora, Barak - kapitola o PCP - odprednášaná bola sekcia 11.5
- ďalšie materiály:
- Derandomizácia
- derandomizácia Schöningovho bez dôkazov [Dantsin et al. '02]
- metóda podmienených pravdepodobností - Max/LargeCut, minSetBalancing [Naor]
- derandomizácia pomocou pseudonáhodných generátorov
- Nisan-Wigdersonov generátor
- Arora, Barak - kapitola o derandomizácii
- poznámky od Jonathana Katza o derandomizácii
Zhrnutie link