Matemaatiline loogika ja
algoritmiteooria
Loengud
2011
|
|
Loengu sisu (järg konspektis) |
Ülesanded ( 2/1 p.) |
|
1. |
12.II |
Sissejuhatus. Algoritmi mõiste formaliseerimisest. |
|
|
2. |
13.II |
LRF definitsioon. Lihtsamad omadused. LRF näited. Lihtrekursiivsed hulgad (algus) |
|
AT01 |
3. |
19.II |
Lihtrekursiivsed hulgad. Lihtrekursiivsed predikaadid – tõkestatud kvantoriteni. |
1. Näidata, et [x/y] on LRF (kui määrata väärtused y=0 jaoks) |
|
4. |
20.II |
Lihtrekursiivsed predikaadid. Universaalne funktsioon, (Ackermanni funktsioon- iseseisvalt lugeda). |
2. Tõkestatud suurima lahendi leidmise operaatori lihtrekursiivsus. |
AT02 |
5. |
26.II |
ORF definitsioon. Täisrekursiivse programmeerimiskeele olemasolu probleem. Ülesanded lihtrekursiivsuse tõestamise kohta. ORF arvutatavus (baaslemma ). |
|
|
6. |
27.II |
ORF arvutatavus (tõestuse lõpp). Arvutatavate funktsioonide rekursiivsus (situatsioonide numeratsioon, algseisundi number) |
|
|
7. |
5.III |
Arvutatavate f-nide rekursiivsus. ORF numeratsioon. Universaalne funktsioon. s-m-n-teoreem. |
|
|
8. |
6.III |
Esimesed mittearvutatavuse teoreemid. Rekursiivsed ja rekursiivselt loetletavad hulgad (teor.7-9) |
|
AT03* |
9. |
12.III |
Rekursiivsed ja
rekursiivselt loetletavad hulgad (teor.10-13). |
|
|
10. |
13.III |
Projektsiooniteoreemid. Püsipunkti teoreem. Rice“i teoreem. |
3. Uurida, kas naturaalarvu järgi temale vastava paari komponentide leidmise funktsioonid π on lihtrekursiivsed. |
|
11. |
19.III |
Ülesanded (hulkade/predikaatide omaduste säilimine operatsioonidel). |
4. Tuua näide, kus kolõpliku hulga originaal täisrekursiivse funktsiooniga kujutamisel pole lihtrekursiivne. |
|
12. |
20.III |
Ülesanded (hulkade/predikaatide omaduste säilimine operatsioonidel) |
5. Tuua näide, kus A on kolõplik (näiteks N), f on LRF ja f(A) pole rekursiivne. |
AT05, AT06 |
13. |
26.III |
Ülesanded. Rice-Shapiro teoreem. Lahenduvad ja loetletavad programmide omadused. |
|
AT04 |
14. |
27.III |
Kordamine: predikaatloogika mudeliteooria. Interpretatsioonid. Struktuuri I järku teooria. |
|
|
15. |
2.IV |
Samaselt tõesus, kehtestatavus, samaväärsus. Lõpliku kandjaga struktuurid. |
|
|
16. |
3.IV |
Bethi tabelid |
|
|
17. |
9.IV |
1.
Kontrolltöö (test klassis 003). |
|
|
18. |
10.IV |
Reaalarvude järjestuse elementaarteooria.Järeldumine. |
|
|
19. |
16.IV |
Aksiomaatilised teooriad. Aks. teooriate algoritmiteoreetilised omadused (teor 1). |
|
|
20. |
17.IV |
Aks. teooriate algoritmiteoreetilised omadused (lõpp). Lausearvutus. Predikaatarvutus. Võrdusega predikaatarvutus. |
|
|
|
|
|
|
|
21. |
23.IV |
Praktikum (klass 003): Puhas predikaatarvutus.Võrdusega predikaatarvutus: ülesannete kogu M:\Loogika\ML&AT\EQ\EQ.TSK (välja arvatud üles. 16). Tudengifail saata kirjaga 2 nädala jooksul. |
Üles 16. |
|
22. |
24.IV |
Võrdusega predikaatarvutus. Esimest järku aksiomaatilised teooriad. Rühmateooria aksioomid ja Peano aritmeetika aksioomid. |
|
|
23. |
30.IV |
Teooria laiendamine, mudeli ahendamine. |
|
|
24. |
7.V |
Praktikum
(klass 003): Tuletamine aritmeetikas.
|
|
|
25. |
8.V |
Kanooniline mudel. Laiendamine Henkini teooriaks. Laiendamine süntaktiliselt täielikuks. |
|
|
26. |
14.V |
Praktikum (klass 003): Tuletamine aritmeetikas. |
|
|
|
|
|
|
|
27. |
15.V |
Teoreem mudelist. Predikaatloogika täielikkus. PA mudelid. Formaalse aritmeetika mittetäielikkus. Aritmeetika mittevasturääkivuse probleem. |
|
|
28. |
21.V |
Kontrolltöö (003): tuletamine (võrdusega pred.-arvutus ja formaalne aritmeetika). |
|
|
29. |
22.V |
Genereerivad grammatikad. Loetletavate sõnahulkade esitamine grammatika abil. |
|
|
30. |
28.V |
Sõnade ekvivalentsi probleem. Thue poolsüsteemid. |
|
|
31. |
29.V |
|
|
|