Předmět Rekurze (NTIN073)
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 NTIN073 - Rekurze, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit základy teorie rekurze
Sylabus
Přednáška z teorie rekurze, která pokrývá základní typy forcingu a základní typy konstrukcí v teorii rekurze. Základy aritmetického forcingu, 1-generické a n-generické množiny Vlastnosti 1-generických množin Aritmetická hierarchie tříd množin Třídy nekonečných větví rekurzivních stromů Věta o nízké bázi Diagonálně nerekurzivní funkce Stupně kompletních rozšíření Peanovy aritmetiky Prioritní metody konstrukcí rekurzivně spočetných množin
Literatura
Demuth O., Kryl R., Kučera A.: Teorie algoritmů I,II. SPN, 1984, 1989 Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009.R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, 2010P. Odifreddi: Classical recursion theory. North-Holland, 1989 R.I. Soare: Recursively enumerable sets and degrees. Springer-Verlag, 1987 M. Li, P. Vitanyi: An introduction to Kolmogorov complexity and its applications. Springer-Verlag, 1997
Garant
doc. RNDr. Antonín Kučera, CSc.