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, 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: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Garant: doc. RNDr. Antonín Kučera, CSc.
• Vyučující: 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

Anotace

čeština

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.

Poslední úprava: T_KTI (20.04.2004)

angličtina

Advanced course on computability theory. Arithmetical hierarchy of classes of sets. Diagonally nonrecursive functions. Arithmetical forcing. Computably enumerable sets, priority methods.

Poslední úprava: T_KTI (20.04.2004)

Cíl předmětu

čeština

Naučit základy teorie rekurze

Poslední úprava: T_KTI (23.05.2008)

angličtina

To learn fundamentals of recursion theory

Poslední úprava: Hric Jan, RNDr. (07.06.2019)

Podmínky zakončení předmětu

čeština

Ústní zkouška

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (07.06.2019)

angličtina

Oral examination

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (07.06.2019)

Literatura

čeština

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

Poslední úprava: T_KTI (29.04.2015)

angličtina

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

Poslední úprava: T_KTI (29.04.2015)

Požadavky ke zkoušce

čeština

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.

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (06.10.2017)

angličtina

The course is finished by an oral examination.

Requirements at the oral examination correspond to the syllabus of the subject.

Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (09.10.2017)

Sylabus

čeština

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

Poslední úprava: T_KTI (29.04.2015)

angličtina

• Arithmetical forcing, 1-generic and n-generic sets and their properties.

• Arithmetical hierarchy of classes of sets.

• Classes of infinite branches of computable trees.

• Low basis theorem.

• Diagonally noncomputable functions.

• Degrees of complete extensions of Peano arithmetic

• Priority methods of constructions of computably enumerable sets.

Poslední úprava: T_KTI (30.04.2015)

Vstupní požadavky

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

Poslední úprava: T_KTI (29.04.2015)