Matemaatiline
loogika ja algoritmiteooria
Kevadsemestril
2012
Aine kood:
MTAT.05.002
Eeldusained: MTAT
05.001 Matemaatilise loogika elemendid või
Sissejuhatus matemaatilisse loogikasse MTAT.05.072/111
Aine
maht: 6 EAP.
Loengud
4 t. nädalas R.Prank
E 8.15-10 L.111
N 12.15-14 L.404
Hindamine:
eksam
Sisu lühikirjeldus
I. Rekursiooniteooria. Algoritmi mõiste
formalisatsioonid ( rekursiivsed funktsioonid, Turingi masinad),
nende samaväärsus. Rekursiivsed ja rekursiivselt
loetletavad hulgad. Aritmeetiline hierarhia.
II.
Algoritmiteooria rakendusi formaalsete keelte teoorias.
III.
Aksiomaatilised teooriad. Esimest järku teooriad, nende
lahenduvuse probleemid. Aksiomaatilised teooriad. Predikaatarvutuse
täielikkus, formaalse aritmeetika mittetäielikkus.
Töö korraldus ja hindamine
Suurem osa auditoorsest tööst on loengu vormis,
mõnedel kordadel lahendatakse auditooriumis ka ülesandeid.
Praktikumid tuletuste konstrueerimiseks aksiomaatilistes süsteemides
toimuvad arvutiklassis. Iga teema sissejuhatavad ülesanded
tehakse auditooriumis (või arvutipraktikumis), ülejäänud
tuleb lahendada iseseisvalt. Mõnede teemade kohta
(põhiliselt rekursiooniteoorias) tuleb iseseisvalt lahendada
APSTesti test (6 testi). Testides on nõutav saada vähemalt
75% tulemus.
Algoritmiteooria kohta on peatüki lõpus
kontrolltöö (test), aksiomaatiliste teooriate kohta
kontrolltöö tuletuste konstrueerimisest (arvutil).
Jooksvad testid annavad 10%, algoritmiteooria lõpptest
10%, tuletuste kontrolltöö 20% aine tulemusest ja
eksam 60% aine tulemusest.
Mõnikord antakse loengutel
koduseks individuaalseks lahendamiseks ülesandeid, mille esimene
lahendaja saab 2 lisapunkti, neli järgmist lahendajat saavad
lisapunkti 1 lisapunkti.
Loengud tabel (teemad,
ülesanded, testid)
Testide juhend,
nimekiri ja tulemuste
tabel.
Punktiülesanded (ülesannete
tabel)
Praktikumide materjale.
Rekursiooniteooria
ülesanded.
Tabel
operatsioonide kohta
Kontrolltööd
Kirjandus
Kordamisküsimused
Eksam