Algorithmic randomness.
Concepts of Kolmogorov complexity, various variants. Algorithmic randomness based
on measure theory. A connection to recursion theory.
Last update: T_KTI (29.04.2015)
Přednáška pokrývá základy algoritmické náhodnosti a různých přístupů k jejímu studiu.
Aim of the course -
Last update: doc. RNDr. Antonín Kučera, CSc. (02.11.2019)
To learn fundamentals of algorithmic randomness
Last update: doc. RNDr. Antonín Kučera, CSc. (02.11.2019)
Naučit základy algoritmické náhodnosti
Course completion requirements -
Last update: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)
Oral examination
Last update: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)
Ústní zkouška
Literature -
Last update: T_KTI (29.04.2015)
Nies, Computability and randomness, Oxford University Press, 2009
R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, 2010
Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edition, Springer, 2008
Last update: T_KTI (29.04.2015)
Nies, Computability and randomness, Oxford University Press, 2009
R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, 2010
Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edition, Springer, 2008
Requirements to the exam -
Last update: doc. RNDr. Antonín Kučera, CSc. (09.10.2017)
The course is finished by an oral examination.
Requirements at the oral examination correspond to the syllabus of the subject.
Last update: doc. RNDr. Antonín Kučera, CSc. (09.10.2017)
Zkouška sestává z ústní části. Známka ze zkoušky odpovídá hodnocení ústní části.
Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce.
Syllabus -
Last update: T_KTI (30.04.2015)
Typicalness - measure theory, martingales
Calibration of notion "sets of measure zero"
Martin-Löf tests, Schnorr tests and their modifications
Universal Martin-Löf test
Basic properties of ML-random sets
Relativization of Martin-Löf randomness, van Lambalgen theorem
Martingales, randomness defined by various classes of martingales
Incompressibility - Kolmogorov complexity
Plain and prefix-free Kolmogorov complexity
Chaitin-randomness, equivalence of Martin-Löf randomness and Chaitin randomness
Halting probability, Omega-number
Algorithmic weakness, K-trivial sets
Last update: T_KTI (29.04.2015)
Typičnost - teorie míry, martingaly
Kalibrace pojmu množina míry nula
Martin-Löf testy, Schnorr testy a jejich modifikace