Vyčíslitelnost - NTIN064

• Anglický název: Computability
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní 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.; RNDr. Petr Kučera, Ph.D.
• Vyučující: doc. RNDr. Antonín Kučera, CSc.
• Třída: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Teoretická informatika
• Prerekvizity : NTIN090
• Je korekvizitou pro: NTIN065
• Je neslučitelnost pro: NTIX090
• Je prerekvizitou pro: NTIN073
• Ve slož. záměnnosti pro: NTIN090, NTIX090

Anotace

čeština

Přednáška pokrývá základy teorie algoritmů, relativní vyčíslitelnosti a aritmetické hierarchie.

Poslední úprava: T_KTI (29.04.2015)

angličtina

An introductory course on computability, relative computability, and arithmetical hierarchy

Poslední úprava: T_KTI (30.04.2015)

Cíl předmětu

čeština

Naučit základy vyčíslitelnosti

Poslední úprava: T_KTI (23.05.2008)

angličtina

To learn fundamentals of computability

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

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

čeština

Ústní zkouška

Poslední úprava: Hric Jan, RNDr. (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

Soare R. I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory. North-Holland, 1989

S.B. Cooper. Computability Theory Chapman Hall, 2003

Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009

R. Downey, D. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010

A. Shen, N. Vereshchagin. Computable functions, Student Mathematical Library, vol. 19, AMS, 2003

Poslední úprava: T_KTI (29.04.2015)

angličtina

Soare R. I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory. North-Holland, 1989

S.B. Cooper. Computability Theory Chapman Hall, 2003

Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009

R. Downey, D. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010

A. Shen, N. Vereshchagin. Computable functions, Student Mathematical Library, vol. 19, AMS, 2003

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. (09.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

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úplnosti

Relativní 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

Poslední úprava: T_KTI (29.04.2015)

angličtina

Introduction to computability

• Algorithmically computable functions, numbering, the s-m-n theorem.

• Basic properties of computable and computably enumerable sets.

• Recursion theorems and their applications.

• Productive and creative sets and their properties.

• Effectively inseparable sets, Gödel incompletness theorems.

Relative computability

• Relative computability, Turing functionals, T-reducibility.

• Degrees of undecidability, jump operation, relativized halting problem.

• Limit computability.

• Arithmetical hierarchy, basic properties. Hierarchy theorem.

• Applications of computability theory.

Poslední úprava: T_KTI (30.04.2015)

Vstupní požadavky

čeština

Znalosti na úrovni přednášky Základy složitosti a vyčíslitelnosti

Poslední úprava: T_KTI (29.04.2015)

angličtina

A basic knowledge of computability equivalent to course NTIN090 (or NTIX090)

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