Vyčíslitelnost - NTIN064
| Anglický název: |
Computability |
| Podoba výuky: |
přednáška |
| Zajišťuje: |
Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Fakulta: |
Matematicko-fyzikální fakulta |
| Platnost: |
od 2022 |
| Počet semestrů výuky: |
1 |
| Semestr: |
letní |
| E-Kredity: |
3 |
| Rozsah, examinace: |
letní s.:2/0, Zk [HT] |
| Počet míst: |
neomezen |
| Maximální kapacita předmětu: |
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 |
| Forma uskutečňování: |
prezenční |
| Možnost opakovaného zápisu: |
2 / 2 / 2 / 2 |
|
|
| Anotace -
| |
|
Přednáška pokrývá základy teorie algoritmů, relativní vyčíslitelnosti a aritmetické hierarchie.
Poslední úprava: T_KTI (29.04.2015)
An introductory course on computability, relative computability, and arithmetical hierarchy
Poslední úprava: T_KTI (30.04.2015)
|
| Cíl předmětu -
| |
|
Naučit základy vyčíslitelnosti
Poslední úprava: T_KTI (23.05.2008)
To learn fundamentals of computability
Poslední úprava: Hric Jan, RNDr. (07.06.2019)
|
| Podmínky zakončení předmětu -
| |
|
Ústní zkouška
Poslední úprava: Hric Jan, RNDr. (07.06.2019)
Oral examination
Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (07.06.2019)
|
| 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
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)
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)
|
| Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení -
| |
|
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)
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 -
| |
|
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
- Aritmetická hierarchie, věta o hierarchii
- Aplikace teorie vyčíslitelnosti
Poslední úprava: T_KTI (29.04.2015)
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.
- Arithmetical hierarchy, basic properties. Hierarchy theorem.
- Applications of computability theory.
Poslední úprava: T_KTI (30.04.2015)
|
| Podmínky zápisu předmětu -
| |
|
Znalosti na úrovni přednášky Základy složitosti a vyčíslitelnosti
Poslední úprava: T_KTI (29.04.2015)
A basic knowledge of computability equivalent to course NTIN090 (or NTIX090)
Poslední úprava: Kučera Antonín, doc. RNDr., CSc. (14.02.2022)
|
|
