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.
Poslední úprava: T_KTI (01.03.2007)
Algorithmic randomness, for PhD students.
Calibrating randomness. K-trivials, low for random.
Applications to recursion theory.
Literatura
Poslední úprava: 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/
Sylabus -
Poslední úprava: 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í.
Poslední úprava: 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.