Předmět Vyčíslitelnost (NTIN064)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN064 - Vyčíslitelnost, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).

Materiál	Typ	Datum	Počet stažení

Cíl

Naučit základy vyčíslitelnosti

Sylabus

Základy vyčíslitelnosti Algoritmicky vyčíslitelné funkce, numerace, s-m-n věta Základní vlastnosti rekurzivních a rekurzivně spočetných množin - shrnutí Věty o rekurzi a jejich aplikace Produktivní a kreativní množiny a jejich vlastnosti Efektivně neoddělitelné dvojice množin, Gödelovy věty o neúplnostiRelativní vyčíslitelnost Relativní vyčíslitelnost, částečně rekurzivní funkcionály, Turingovská převeditelnost Stupně nerozhodnutelnosti, operace skoku, relativizovaný halting problém Limitní vyčíslitelnost Aritmetická hierarchie, věta o hierarchii Aplikace teorie vyčíslitelnosti

Literatura

Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989Soare R. I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987Odifreddi P.: Classical recursion theory. North-Holland, 1989S.B. Cooper. Computability Theory Chapman Hall, 2003Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009R. Downey, D. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010A. Shen, N. Vereshchagin. Computable functions, Student Mathematical Library, vol. 19, AMS, 2003

Garant

doc. RNDr. Antonín Kučera, CSc.RNDr. Petr Kučera, Ph.D.