Algoritmická náhodnost 2 - NTIN089

• Anglický název: Algorithmic Randomness 2
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: doc. RNDr. Antonín Kučera, CSc.
• Třída: DS, teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika
• Korekvizity : NTIN088

Anotace

čeština

Poslední úprava: 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.

angličtina

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

čeština

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í.

angličtina

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.