PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
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 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: 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 -
Poslední úprava: T_KTI (20.04.2004)
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.
Cíl předmětu
Poslední úprava: T_KTI (23.05.2008)

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

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

Sylabus -
Poslední úprava: T_KTI (20.04.2004)

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.

 
Univerzita Karlova | Informační systém UK