SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Algorithmic Randomness II - NTIN089
Title in English: Algoritmická náhodnost II
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2015 to 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
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

http://www.mcs.vuw.ac.nz/~downey/

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 | http://www.cuni.cz/UKEN-329.html