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

Guarantor:	doc. RNDr. Antonín Kučera, CSc.
Teacher(s):	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 Noticeboard

Annotation -

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)

Aim of the course -

To learn fundamentals of algorithmic randomness

Last update: Kučera Antonín, doc. RNDr., CSc. (02.11.2019)

Course completion requirements -

Oral examination

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

Literature -

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)

Requirements to the exam -

The course is finished by an oral examination.

Requirements at the oral examination correspond to the syllabus of the subject.

Last update: Kučera Antonín, doc. RNDr., CSc. (09.10.2017)

Syllabus -

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 (30.04.2015)

Entry requirements - Czech

Znalosti na úrovni přednášky Rekurze

Last update: T_KTI (29.04.2015)