Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time
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

Opinion survey results Examination dates SS schedule Noticeboard

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