I. Korec: Úvod do teórie algoritmov, skriptá MFF UK, Bratislava, 1981.
A. Maľcev: Algoritmy i rekursivnyje funkcii, Moskva, 1965.
H. Rogers: Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.
D. E. Cohen: Computability and Logic, Ellis Horwood, Chichester, 1987.
2-INF-121 Teória vypočítateľnosti
| Odporúčaný ročník: | 1. |
| Semester: | letný |
| Rozsah: | K4 |
| Hodnotenie: | 20/80 |
| Počet kreditov: | 6 |
| Vyučujúci: | prednáša RNDr. Michal Forišek PhD. |
| www stránka: | http://foja.dcs.fmph.uniba.sk/tvyp/ |
Cieľ:
Formalizovať pojmy algoritmickej riešiteľnosti problémov a vypočítateľnosti funkcií a uviesť aplikácie takýchto formalizmov v informatike, logike apod. Pôjde pritom o štandardný klasický výklad pojmov teórie vypočítateľnosti, ktorý bude vedený formou teoretickej prednášky doplnenej teoretickými cvičeniami.
Sylabus:
- Induktívne budovanie pojmov teórie vypočítateľnosti nezávisle od konkrétneho výpočtového modelu: klony (čiastočných) funkcií, primitívne rekurzívne, rekurzívne a čiastočne rekurzívne funkcie, množiny a predikáty, univerzálne (čiastočné) funkcie.
- Výpočtové modely: najmä registrové a Turingove stroje, výpočty a ekvivalencia vypočítateľnosti na jednotlivých modeloch (Gödelizácia), Churchova téza. Pôjde o teoretické modely, ktoré nebudú programovo realizované na skutočných počítačoch.
- Aplikácie teórie vypočítateľnosti: kódovanie nečíselných oborov, (ne)rozhodnuteľnosť problémov, indexácia, redukcie a hierarchie problémov.
Literatúra: