SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   Login via CAS
Algorithmic Randomness - NTIN088
Title: Algoritmická náhodnost
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. RNDr. Antonín Kučera, CSc.
Class: DS, teoretická informatika
Classification: Informatics > Theoretical Computer Science
Is co-requisite for: NTIN089
Annotation -
Last update: T_KTI (29.04.2015)
Algorithmic randomness. Concepts of Kolmogorov complexity, various variants. Algorithmic randomness based on measure theory. A connection to recursion theory.
Aim of the course -
Last update: doc. RNDr. Antonín Kučera, CSc. (02.11.2019)

To learn fundamentals of algorithmic randomness

Course completion requirements -
Last update: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)

Oral examination

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

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.

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

Entry requirements - Czech
Last update: T_KTI (29.04.2015)

Znalosti na úrovni přednášky Rekurze

Charles University | Information system of Charles University |