SubjectsSubjects(version: 920)
Course, academic year 2022/2023
   Login via CAS
Algorithmic Randomness 2 - NTIN089
Title: Algoritmická náhodnost 2
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
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: not taught
Language: Czech
Teaching methods: full-time
Guarantor: doc. RNDr. Antonín Kučera, CSc.
Class: DS, teoretická informatika
Classification: Informatics > Theoretical Computer Science
Co-requisite : NTIN088
Annotation -
Last update: T_KTI (01.03.2007)
Algorithmic randomness, for PhD students. Calibrating randomness. K-trivials, low for random. Applications to recursion theory.
Literature - Czech
Last update: T_KTI (27.02.2007)

[1] Ming Li, Paul Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997.

[2] R. Downey, D. Hirschfeldt: Algorithmic randomness and complexity, draft of book at

Syllabus -
Last update: T_KTI (01.03.2007)

Concepts ?low for random", ?K-trivial".

Computationally weak sets from the point of view of algorithmic randomness

and their equivalence.

Basic properties of K-trivial sets.

Applications to recursion theory.

Modifications and generalizations of K-trivial sets.

Charles University | Information system of Charles University |