Skúška

Čo treba vedieť na skúšku

1. Ochutnávka pravdepodobnostných algoritmov - pravdepodobnostné konečné automaty, testovanie násobenia matíc, hľadanie minimálneho rezu
2. Analýza pravdepodobnostných algoritmov - Markov, Čebyšev, Chernoff (aj s dôkazmi; v Chernoffovi stačí dokázať to najsilnejšie tvrdenie), vyššie momenty netreba
3. Triedenie a vyhľadávanie - s.v.p. analýza quicksortu (dôkaz); treap, skiplist - vedieť, ako fungujú a myšlienky dôkazov
4. Hľadanie mediánu - algoritmus a jeho analýza
5. Hešovanie - univerzálne rodiny hešovacích funkcií (def.), perfektné hešovanie, lineárne sondovanie (aj s dôkazom očak. zložitosti)
6. Eliminácia nepriateľa a odtlačky - online joby, Perfektné párovania - perfektné párovania, Tutteova veta (aj dôkaz), testovanie rovnosti polynómov, Schwartz-Zippelova lema (aj dôkaz)
7. Znižovanie zožitosti opakovaním a random sampling, Hľadanie minimálneho rezu - jednoduchý kontrahovací algoritmus a jeho zrýchlenia, Schöningov algoritmus a riešenie 3-SATu (aj s dôkazom zložitosti). Hľadanie najlacnejšej kostry - lineárny samplovací algoritmus pre hľadanie najlacnejšej kostry
8. Svedkovia a testovanie prvočíselnosti - Fermatov test (dôkaz Fermatovej vety, dôkaz, že ne-Carmichaelove zložené čísla majú veľa svedkov) a Miller-Rabinov test (ako funguje, že zložené čísla majú viac odmocnín z 1; dôkaz, že svedkov je veľa netreba)
9. Lineárne programovanie - Seidelov algoritmus (aj s dôkazom zložitosti), MSW a Clarksonove algoritmy vedieť ako fungujú, dôkaz netreba
10. Náhodné prechádzky - def. Markovove reťazce, prechodové matice a stacionárne distribúcie; hlavná veta MR (bez dôkazu); súvis s vlastnými číslami, súvis s elektrinou (efektívny odpor a "pendlovací čas", horný a dolný odhad pre čas pokrytia - aj s dôkazmi)
    1. Miešanie kariet - podľa Shuffling cards
11. 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 a MrBayes (myšlienka)
12. Náhodnosť a zložitosť - pravdepodobnostné triedy zložitosti (ZPP, RP, coRP, BPP a δ-BPP, PP), Adlemanova veta (BPP a boolovské obvody), Sipser-Gacsova veta (BPP a polynomiálna hierarchia)
13. 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 ⊆ Σ₂^P; MA ⊆ AM ⊆ Π₂^P
14. Interaktívne dôkazy - #P ⊆ IP ⊆ PSPACE; myšlienka IP = PSPACE
15. Pravdepodobnostne overiteľné dôkazy - NP = PCP[n³, 1] (dôkaz)
16. Derandomizácia - Schöning (informatívne, bez dôkazov), metóda podmienených pravdepodobností a Max/LargeCut, minSetBalancing (link). Derandomizácia pomocou pseudonáhodných generátorov (kap. 20.1. z Aroru); Nisan-Wigdersonov generátor (ako funguje, čo sú dizajny; dôkaz netreba)