PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
Rekurze - NTIN073
Anglický název: Recursion
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Antonín Kučera, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Prerekvizity : NTIN064
Je korekvizitou pro: NTIN074
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: T_KTI (20.04.2004)
Pokročilejší partie teorie rekurze. Aritmetická hierarchie tříd množin. Diagonálně nerekurzivní funkce. Aritmetický forcing. Konstrukce rekurzivně spočetných množin, prioritní metody.
Cíl předmětu -
Poslední úprava: T_KTI (23.05.2008)

Naučit základy teorie rekurze

Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)

Ústní zkouška

Literatura -
Poslední úprava: T_KTI (29.04.2015)

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, 2010

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

Požadavky ke zkoušce -
Poslední úprava: doc. RNDr. Antonín Kučera, CSc. (06.10.2017)

Zkouška sestává z ústní části. Známka ze zkoušky odpovídá hodnocení ústní části.

Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce.

Sylabus -
Poslední úprava: T_KTI (29.04.2015)

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

Vstupní požadavky
Poslední úprava: T_KTI (29.04.2015)

Znalosti na úrovni přednášky Vyčíslitelnost

 
Univerzita Karlova | Informační systém UK