Rekurze - NTIN012

• Anglický název: Recursion
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2004
• Semestr: zimní
• E-Kredity: 9
• Rozsah, examinace: zimní s.:2/1, Z [HT]; letní s.:2/1, Z+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: zrušen
• Jazyk výuky: češ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
• Korekvizity : NTIN014

Anotace

čeština

Pokročilejší partie teorie rekurze. Obsah bývá mírně modifikován podle zájmu. Aritemtická hierarchie tříd množin. Diagonálně nerekurzivní funkce. Aritmetický forcing. Konstrukce rekurzivně spočetných množin, prioritní metody. Algoritmická náhodnost. Kolmogorovská složitost.

Poslední úprava: G_I (05.06.2002)

angličtina

Classes of infinite branches of computable trees. Arithmetical hierarchy of classes of sets. Low basis theorem. Recursion theorem and selfreferential principles. Diagonally nonrecursive functions, a connection to mathematical logic. Arithmetical forcing, 1-generic sets and their properties. Minimal degrees. Algorithmic randomness. Properties of 1-random sets. Kolmogorov complexity.

Poslední úprava: G_I (05.06.2002)

Literatura

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

Li M., Vitanyi P.: An introduction to Kolmogorov complexity and its applications. Springer-Verlag, 1993

Poslední úprava: Zakouřil Pavel, RNDr., Ph.D. (05.08.2002)

Sylabus

Rekurzivní stromy. Třídy nekonečných větví rekurzivních stromů.

Aritmetická hierarchie množin a tříd množin.

Věta o nízké bazi.

Aplikace věty o rekurzi. Selfreferenční principy a jejich aplikace.

Diagonálně nerekurzivní funkce, jejich základní vlastnosti a použití. Souvislost s matematickou logikou.

Aplikace diagonálně nerekurzivních funkcí v konstrukcích r.s. množin.

Základy aritmetického forcingu metodou konečných prodloužení.

1-generické množiny a jejich základní vlastnosti.

Minimální stupně, forcing metodou perfektních rekurzivních stromů.

Algoritmická náhodnost. 1-náhodné množiny a jejich zobecnění.

Základní vlastnosti 1-náhodných množin, struktura jejich stupňů.

Poslední úprava: ()