Sylabus
Typičnost - teorie míry, martingaly
- Kalibrace pojmu množina míry nula
- Martin-Löf testy, Schnorr testy a jejich modifikace
- Univerzální Martin-Löf test
- Základní vlastnosti ML-náhodných množin
- Relativizace Martin-Löf náhodnosti, van-Lambalgenova věta
- Martingaly, náhodnost definovaná pomocí různých tříd martingalů
Chaotičnost (incompressibilty) - Kolmogorovská složitost
- Obyčejná a prefix-free varianta Kolmogorovské složitosti,
- Chaitin-náhodnost, ekvivalence Martin-Löf náhodnosti a Chaitin náhodnosti
- Halting probability, Omega-number
- Algoritmická slabost, K-triviální množiny
Anotace
Přednáška pokrývá základy algoritmické náhodnosti a různých přístupů k jejímu studiu.