ALGORITMITEOORIA
Rakendusinformaatika. Kevad 2001
Numbrid nurksulgudes viitavad kirjanduse nimekirjale
I. ALGORITMITEOORIA
1. Algoritmid matemaatikas enne algoritmiteooriat. Algoritmide üldised
omadused. Algoritmilist lahendust oodanud probleemid. Vajadus algoritmi
mõiste formaliseerimiseks.
2. Lihtrekursiivse funktsiooni mõiste. Näiteid. LRF
omadusi. [1,5]
3. Lihtrekursiivsed hulgad. [1,5]
4. Lihtrekursiivsed predikaadid. [1,5]
5. Osaliselt rekursiivse funktsiooni mõiste. [1,5]
6. Turingi masin. Turingi mõttes arvutatavad funktsioonid.
[1,4,6]
7. TM kompositsion ja hargnemine. [1,4,6]
8. Rekursiivsete funktsioonide arvutatavus. [1,6]
9. Turingi mõttes arvutatavate funktsioonide rekursiivsus
(ülevaade, ilma detailse tõestuseta). Situatsioonide numeratsioon.
Algsituatsiooni number ja numbri muutumine arvutuse jooksul. Resultatiivsuse
tingimuste rekursiivsus. [1,6]
10. Turingi masinate ja rekursiivsete funktsioonide numeratsioon.
Universaalne funktsioon. S-m-n-teoreem. [3,5,7]
11. Peatumise probleem. Mittejätkatavad funktsioonid. [3,5,7]
12. Rekursiivsed ja rekursiivselt loetletavad hulgad. [3,5,7]
14. Mitmedimensionaalsed hulgad. Projektsiooniteoreemid. [3,5,7]
15. Püsipunkti teoreem. Rice’i teoreem. Järeldused
programmeerimisteoorias. [3,5,7]
KIRJANDUS
1. R.Prank. Matemaatiline loogika ja diskreetne matemaatika I.
TÜ rotaprint, 1978.
2. -
3. R.Prank. Rekursiooniteooria konspekt. 17 lk.
4. R.Prank. Matemaatilise loogika elementide konspekt. 74 lk.
5. V.A.Uspenski. Lekcii o wychislimyh funkcijax.
6. S.C.Kleene. Introduction to Metamathematics. (ka vene keeles)
7. H.Rogers. Theory of Recursive Functions and Effective Computability.
(ka vene keeles)