NDMI025 - Pravděpodobnostní algoritmy -
Randomized Algorithms
LS 2017 - Jiří Sgall
středa 9:00 S9
Cvičení probíhají nepravidelně po přednášce v S11, vede je Dušan
Knop
Probraná látka
- 1. (1. 3.)
- úvod, příklady: karetní hra, 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)
- náhodné procházky v grafech - úvod, příklady, definice [MU
7.2, MR 6.2]
- čas pokrytí grafu a dosažení daného vrcholu (definice)
- 2. (8. 3.)
- vztah náhodných procházek k elektrickým obvodům [MR 6.4]
- odhady na čas pokrytí grafu
- 3. (15.3.)
- souvislost grafů, univerzální transversální posloupnosti [MR
6.6]
- Č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]
- 4. (22.3.)
- amplifikace chyb, vztah k deterministickým třídám [MR 1.5,
2.3]
- směrování na hyperkrychlích [MU 4.5.1, MR 4.2]
- 5. (29.3.)
- expander, definice, úvod, vlastní čísla [MR 6.7]
- vztah vlastních čísel a expanze
- 6. (5.4.)
- vyhodnocování stromů [MR 2.2]
- věta o minimaxu (von Neumann - Yao) [MR 2.1]
- 7. (12.4.)
- náhodné procházky na expanderech [MR 6.8]
- 8. (19.4.)
- 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]
- 9. (26.4.)
- permanent - přibližné počítání perfektních párování pomocí
Markovových řetězců [MU 10.2, MR 11.2]
- 10. (3.5.)
- coupling - úvod, míchání karet [MU 11.1-11.2]
- coupling - přibližné generování obarvení grafu Markovovým
řetězcem [MU 11.4-11.5]
- 11. (10.5.)
- 12. (24.5.)
Učebnice
[MR] R. Motwani, P. Raghavan: Randomized algorithms.
[MU] 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.