Předměty

Váš prohlížeč nepodporuje JavaScript nebo je jeho podpora vypnutá. Některé funkce nemusejí být dostupné.

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