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
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: not taught
• Language: Czech
• 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
• Co-requisite : NTIN088

Annotation

English

Last update: T_KTI (01.03.2007)

Algorithmic randomness, for PhD students. Calibrating randomness. K-trivials, low for random. Applications to recursion theory.

Czech

Last update: T_KTI (01.03.2007)

Předmět je určen pro doktorandské studenty se zájmem o algoritmickou náhodnost a je pokračováním předmětu Algoritmická náhodnost I (TIN088). Pokročilejší partie algoritmické náhodnosti, kalibrace různých variant. Pojmy "K-triviality", "low for random", jejich ekvivalence a význam. Aplikace v teorii rekurze.

Literature

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

English

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.

Czech

Last update: T_KTI (01.03.2007)

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

Ekvivalence různých pojmů z hlediska algoritmické náhodnosti výpočetně slabých množin.

Základní vlastnosti K-triviálních množin.

Aplikace v terorii rekurze.

Modifikace K-triviálních množin a zobecnění.