Rekurze 2 - NTIN074

• Anglický název: Recursion 2
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• 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: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika
• Korekvizity : NTIN073

Anotace

čeština

Poslední úprava: T_KTI (20.04.2004)

Pokračování přednášky Rekurze I. Další metody forcingu. Algoritmická náhodnost. Kolmogorovská složitost.

angličtina

Poslední úprava: T_KTI (20.04.2004)

A continuation of Recursion Theory I. Other forcing techniques. Algorithmic randomness. Kolmogorov complexity.

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

čeština

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.

angličtina

Poslední úprava: T_KTI (20.04.2004)

Minimal degrees.

Algorithmic randomness. Properties of 1-random sets and their degrees.

Kolmogorov complexity. Martingales.