Algoritmická náhodnost 2 - NTIN089
|
|
|
||
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)
|
|
||
[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/ Poslední úprava: T_KTI (27.02.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)
|