Matemaatiline
loogika ja algoritmiteooria
Kevadsemestril
2013
Aine kood:
MTAT.05.002
Eeldusained:
Sissejuhatus matemaatilisse loogikasse MTAT.05.072/111
Aine
maht: 6 EAP.
Loengud
4 t. nädalas R.Prank
T 10.15-12 L.404
K 16.15-18 L.403
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
Praktikumide
materjale.
Rekursiooniteooria
ülesanded.
Tabel
operatsioonide kohta
Kontrolltööd
Kirjandus
Kordamisküsimused
Eksam