NDMI025 - Pravděpodobnostní algoritmy - Randomized Algorithms

LS 2019 - Jiří Sgall
pondělí 10:40 v S4

Probraná látka

• 1. (25. 2.)
• úvod, příklady: grafový neizomorfismus, 2-obarvení 3-obarvitelných grafů bez monochromatických trojúhelníků
• Markovovy řetězce, stacionární distribuce, její existence a konvergence, periodičnost (opakování z pravděpodobnostních technik, viz poznámky o stacionární distribuci)
  
• náhodné procházky v grafech - úvod, příklady, definice [MU 7.2, MR 6.2]
• odhady na čas dosažení vrcholu
  
• 2. (4. 3.)
• vztah náhodných procházek k elektrickým obvodům [MR 6.4]
• odhady na čas pokrytí grafu
• souvislost grafů, univerzální transversální posloupnosti [MR 6.6]
• 3. (11. 3.)
• Černovovy nerovnosti (opakování z pravděpodobnostních technik) [MU 4.2-4.3, MR 4.1] (viz přehled odhadů)
• třídy pravděpodobnostních algoritmů: RP, BPP, PP, ZPP [MR 1.5]
• amplifikace chyb, vztah k deterministickým třídám [MR 1.5, 2.3]
• expander, definice, úvod, vlastní čísla [MR 6.7]
• 4. (18. 3.)
  
• vztah vlastních čísel a expanze
• náhodné procházky na expanderech [MR 6.8]
• 5. (25. 3.)
• přibližné počítání, metoda Monte Carlo [MU 10.1, MR 11.1]
• počítání splňujících ohodnocení DNF [MU 10.2, MR 11.2]
• permanent - přibližné počítání perfektních párování pomocí Markovových řetězců [MU 10.2, MR 11.2]
• 6. (1. 4.)
• permanent - přibližné počítání perfektních párování pomocí Markovových řetězců - dokončení [MU 10.2, MR 11.2]
• coupling - úvod, míchání karet [MU 11.1-11.2]
• 7. (8. 4.)
  
• coupling - přibližné generování obarvení grafu Markovovým řetězcem [MU 11.4-11.5]
  
• vyhodnocování stromů [MR 2.2]
• 8. (15. 4.)
  
• vyhodnocování stromů - dolní odhad, dokončení [MR 2.2, M. Tarsi: Optimal Search on Some Game Trees. J. ACM 30(3): 389-396 (1983)]
• věta o minimaxu (von Neumann - Yao) [MR 2.1]
• PCP věta - definice, úvod
• 9. (29. 4.)
• PCP věta - důkaz slabé verze, testování linearity [MR 7.8, http://iuuk.mff.cuni.cz/~sgall/pcp/]
• 10. (6. 5.)
• algoritmy s proudy dat
  
• úvod, hledání častých prvků [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, kap. 1 a 4]
• 11. (13. 5.)
• algoritmy s proudy dat
  
• počítání různých prvků [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, kap. 2 a 3]
• 12. (20. 5.)
• algoritmy s proudy dat
  
• počítání momentů [http://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf, kap. 5 a 6]
• distribuované algortimy - Byzantine agreement [MR 12.6]
  

Učebnice

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

Předchozí běh přednášky v LS 2017

Další informace

Přednáška se nekoná každý rok, předpokládám její opakování za 2 roky.