Vyčíslitelnost 2 - NTIN065
Anglický název: Computability 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
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í
Garant: doc. RNDr. Antonín Kučera, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN064
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Navazující přednáška na Vyčíslitelnost I. Různé typy rekurzivně spočetných množin. Vztah k matematické logice. Relativní vyčíslitelnost. Operace skoku. Aritmetická hierarchie.
Poslední úprava: T_KTI (20.04.2004)
Cíl předmětu

Naučit další navazující teorii vyčíslitelnosti

Poslední úprava: T_KTI (23.05.2008)
Literatura -

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

Poslední úprava: T_KTI (20.04.2004)
Sylabus -

Prosté množiny

Relativní vyčíslitelnost, T-převeditelnost.

Operace skoku, její význam jako relativizovaného halting problému a její základní vlastnosti.

Věta o limitní vyčíslitelnosti.

Aritmetická hierarchie. Věta o hierarchii, souvislost s operací skoku. Aplikace teorie vyčíslitelnosti.

Poslední úprava: T_KTI (20.04.2004)