PředmětyPředměty(verze: 849)
Předmět, akademický rok 2019/2020
   Přihlásit přes CAS
Rekurze II - NTIN074
Anglický název: Recursion II
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015 do 2019
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Antonín Kučera, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN073
Anotace -
Poslední úprava: T_KTI (20.04.2004)
Pokračování přednášky Rekurze I. Další metody forcingu. Algoritmická náhodnost. Kolmogorovská složitost.
Cíl předmětu
Poslední úprava: T_KTI (23.05.2008)

Naučit další cásti z teorie rekurze

Literatura
Poslední úprava: T_KTI (20.04.2004)

Demuth O., Kryl R., Kučera A.: Teorie algoritmů I,II. SPN, 1984, 1989

Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory. North-Holland, 1989

Li M., Vitanyi P.: An introduction to Kolmogorov complexity and its applications.

Springer-Verlag, 1997

Sylabus -
Poslední úprava: T_KTI (20.04.2004)

Minimální stupně, forcing metodou perfektních rekurzivních stromů.

Algoritmická náhodnost.

Základní vlastnosti 1-náhodných množin, struktura jejich stupňů.

Kolmogorovská složitost. Martingaly.

 
Univerzita Karlova | Informační systém UK