PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Vyčíslitelnost - NTIN064
Anglický název: Computability
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015 do 2021
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [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.
RNDr. Petr Kučera, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Teoretická informatika
Je korekvizitou pro: NTIN065
Je neslučitelnost pro: NTIN090, NTIX090
Je prerekvizitou pro: NTIN073
Ve slož. záměnnosti pro: NTIN090, NTIX090
Anotace -
Poslední úprava: T_KTI (29.04.2015)
Přednáška pokrývá základy teorie algoritmů, relativní vyčíslitelnosti a aritmetické hierarchie.
Cíl předmětu -
Poslední úprava: T_KTI (23.05.2008)

Naučit základy vyčíslitelnosti

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jan Hric (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

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

Požadavky ke zkoušce -
Poslední úprava: doc. RNDr. Antonín Kučera, CSc. (09.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)

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

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

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

 
Univerzita Karlova | Informační systém UK