Prednášky a poznámky

Literatúra:

• Motwani, Raghavan - Randomized Algorithms
• Mitzenmacher, Upfal - Probability and Computing

1. 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:
     • Condon - Bounded error probabilistic finite state automata (prehľadová kapitola o PKA; na prednáške bola sekcia 3)
       • Kargerov kontrahovací algoritmus na hľadanie minimálneho rezu (pekné obrázky)
2. 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)
     • Motwani, kap. 3.2, 4.1, Mitzenmacher, kap. 3.1-3.3, 4.1-4.2
     • ďalšie materiály:
       • Odhady chvostov (zopár grafov pre ilustráciu)
       • Dubhashi, Panconesi - Concentration of Measure for the Analysis of Randomised Algorithms (na prednáške sme si hovorili iba čosi z kapitoly 1, ale keby niekoho zaujímalo, ako sa dá dokazovať koncentrácia náhodnej premennej...)
     • Díaz, Petit, Serna - A guide to concentration bounds
     • Raab, Steger - "Balls into Bins" - A Simple and Tight Analysis
3. Triedenie a vyhľadávanie
   • quicksort a analýza s.v.p.
   • treap
   • skiplist
   • poznámky
   • ďalšie materiály:
     • pohrajte sa vizualizáciami treapu a skiplistu; (prípadne ďalšie dátové štruktúry, ktoré vás zaujmú)
     • poznámky jeffa ericksona: matice a skrutky, treapy a skiplisty, s.v.p. odhady chvostov a analýza treapov
     • Aragon, Seidel - Randomized Search Trees
       • Kozenova kniha - treapy
       • Pugh - Skip Lists: A Probabilistic Alternative to Balanced Trees, Pugh - A Skip List Cookbook (aj s implementáciou)
       • matice a skrutky - keby niekoho zaujímalo, ako sa dá úloha riešiť deterministicky v O(nlog n), tak takto - ale je to zložité
4. Hľadanie mediánu
   • poznámky
     • Motwani kap. 3.3, Mitzenmacher kap. 3.4
     • ďalšie materiály:
       • Floyd, Rivest - Expected Time Bounds for Selection - pôvodný článok
       • Floyd, Rivest - Algorithm 489 - implementácia a nejaké namerané dáta
       • spider factory - ak by niekoho zaujímalo, ako sa dá nájsť medián deterministicky na 3n porovnaní, tento článok je veľmi pekne napísaný
5. 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
     • Motwani kap. 8.4, 8.5, Mitzenmacher kap. 13.3, Erik Demaine - Hashing (video)
     • ďalšie materiály:
       • Perfect hashing (z knihy Introduction to Algorithms)
       • perfektné hešovanie [Fredman, Komlos, Szemeredi '84] staticky, [Dietzfelbinger et al. '90] dynamicky
       • lineárne sondovanie: [Pagh, Pagh, Ruzic '07] (5-nezávislosť stačí), [Patrascu, Thorup '10] (4-nezávislosť nestačí)
6. 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:
     • Kozen - Probabilistic tests with polynomials
     • Ivan, Virza, Yuen - Algebraic Algorithms for Matching
     • Harvey - Algebraic algorithms for matching and matroid problems
   • Hľadanie najkratších ciest
   • Seidelov algoritmus
   • slidy
   • Motwani kap. 10.1
     • ďalšie materiály:
     • Seidel - On the all-pairs-shortest-path problem in unweighted undirected graphs
       • Zwick - All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms (čo robiť s orientovanými grafmi)
       • pekný prehľadový článok - čo sa vie: Zwick - Exact and approximate distances in graphs—a survey
       • spannery: Thorup, Zwick - Approximate distance oracles
   • Intermezzo:
     • matice a grafy: pekný graf - ako postupne klesal exponent omega v zložitosti násobenia matíc
     • vlastné čísla: Fibonacci, Tribonacci, matice a vlastné čísla + dokončenie; pythonovský kód generujúci 3D pohľad na Tribonacciho čísla
7. 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:
     • Kargerov kontrahovací algoritmus na hľadanie minimálneho rezu (pekné obrázky)
     • Karger, Stein - A new approach to the minimum cut problem
     • Karger - Random sampling in cut, flow, and network design problems
     • Benczur, Karger - Randomized approximation schemes for cuts and flows in capacitated graphs
     • Spielman, Srivastava - Graph sparsification by effective resistances
   • Problém splniteľnosti
     • Schöningov algoritmus na riešenie 3-SATu
   • slidy
     • ďalšie materiály:
       • Satisfiability Solvers - prehľadová kapitola o rôznych metódach riešenia SATu
       • [Ravi '12] - iný prehľadový článok
       • Hertli - 3-SAT Faster and Simpler - v súčasnosti najrýchlejší algoritmus pre 3-SAT, beží v Õ(1.308ⁿ)
   • 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:
     • Borůvka - 0 jistém problému minimálním, Borůvka - Příspěvek k řešení otázky ekonomické stavby elektrovodných sítí - brať skôr ako historický artefakt, nie študijný materiál :-)
     • Katriel, Sanders, Träff - A practical minimum spanning tree algorithm using the cycle property
     • Karger, Klein, Tarjan - A randomized linear-time algorithm to find minimum spanning trees
     • Chan - Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees
     • King - A simpler minimum spanning tree verification algorithm
     • Martin Mareš - The Saga of Minimum Spanning Trees
8. Metódy - metóda svedkov a testovanie prvočíselnosti
   • Fermatov a Miller-Rabinov test
   • poznámky, slidy, slidy DP
     • Testovanie prvočíselnosti I., Testovanie prvočíselnosti II. (tieto poznámky som spísal kedysi dávno a mali by byť na úrovni strednej školy)
   • ďalšie materiály:
     • Kozen - Miller's primality test
     • Crandall, Pomerance - Prime numbers: A Computational Perspective (úryvok z knihy; obsahuje oba testy, poriadnejšiu analýzu Miller-Rabina a dôkaz, že prvočísla majú krátke certifikáty)
       • Stay - PRIMES is in P, slowly (ak by niekoho zaujímal deterministický algoritmus na testovanie prvočíselnosti - AKS)
9. Lineárne programovanie
   • Seidelov, MSW a Clarksonove algoritmy
   • randomizované inkrementálne algoritmy a samplovanie
   • poznámky
     • Motwani kap. 9.10
     • ďalšie materiály:
       • [Seidel '91] [Clarkson '95] [Matoušek, Sharir, Welzl '96]
10. Náhodné prechádzky
    • Markovove reťazce, prechodová matica a stacionárna distribúcia
    • súvis s vlastnými číslami
    • slidy, slidy (2. časť)
    • Motwani kap. 6.1-6.5, Mitzenmacher, kap. 7.3-7.4
    • ďalšie materiály:
    • Doyle, Snell - Random walks and electric networks
    • Markov Chains and Mixing Times
    • The $25,000,000,000 eigenvector: The linear algebra behind Google
      • bakalárka Ondra Mikuláša - PageRank algoritmus
11. Miešanie kariet
    • miešanie (variačná vzdialenosť), silne uniformné časy zastavenia
    • top-to-random a riffle shuffle
    • ďalšie materiály:
      • Shuffling cards - úryvok z prekrásnej knihy Proofs from the Book, čo je zbierka najkrajších matematických dôkazov - veľmi odporúčam
    • Aldous, Diaconis - Shuffling cards and stopping times
    • Bayer, Diaconis - Trailing the dovetail shuffle to its lair
      • Gardner - Playing cards - čo sa môže stať, ak nemiešate poriadne
12. 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
      • ďalšie materiály:
        • The Evolution of MCMC Methods - o MCMC, dačo o histórii tohto algoritmu, aplikácie vo fyzike, rekonštrukcia obrázkov
      • The MCMC revolution
      • An Introduction to MCMC for Machine Learning
        • David MacKay - Information Theory, Inference, and Learning Algoritms (kap. 29)
        • MrBayes - pekne spísaná kapitola o tom, ako sa robí fylogenetická analýza a ako funguje MrBayes
13. 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
      • ďalšie materiály:
        • asi najlepšia knižka o výpočtovej zložitosti je od Sanjeeva Aroru a Boaza Baraka - Computational Complexity: A Modern Approach; voľne dostupná draft verzia je tu; pozrite si kapitolu o náhodnosti a zložitosti; prípadne o boolovských obvodoch a polynomiálnej hierarchii
        • poznámky od Jonathana Katza
14. 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
    • bonus: ak by bol grafový izomorfizmus NP-ťažký problém, skolabuje PH
    • poznámky
      • ďalšie materiály:
        • Arora, Barak - kapitola o interaktívnych dôkazoch
      • [Goldwasser, Sipser '86]
15. Interaktívne dôkazy
    • #P ⊆ IP
    • myšlienka IP = PSPACE
    • slidy
      • ďalšie materiály:
        • Arora, Barak - kapitola o interaktívnych dôkazoch
        • dosť podrobné vysvetlenie celého dôkazu IP = PSPACE
        • poznámky od Jonathana Katza
        • [Shamir '92] - pôvodný článok dokazujúci IP = PSPACE
16. Pravdepodobnostne overiteľné dôkazy
    • NP = PCP[n³, 1]
    • Arora, Barak - kapitola o PCP - odprednášaná bola sekcia 11.5
    • ďalšie materiály:
      • Rasťo Královič - Aproximačné algoritmy - kap. 4 je o tom, ako PCP veta súvisí s nemožnosťou aproximácie niektorých problémov
      • poznámky od Jonathana Katza: PCP a neaproximovateľnosť, dôkaz PCP vety
      • ak by mal niekto chuť na celú PCP vetu a veľa ďalších vecí, môžete si pozrieť Arorovu dizertačku alebo nový, vraj jednoduchší dôkaz z knihy od Aroru a Baraka
      • Håstadove optimálne výsledky o neaproximovateľnosti viacerých problémov - len pre silné žalúdky
      • pekne a zaujímavo spísaná história PCP vety a výsledkov, ktoré jej predchádzali
17. 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