Teoreetiline informaatika (IFI6019.DT)
Õppeaine kood
IFI6019.DT
vana ainekood
IFI6019
Õppeaine nimetus eesti k
Teoreetiline informaatika
Õppeaine nimetus inglise k
Theoretical Computer Science
Õppeaine maht EAP
5.0
Orienteeruv kontakttundide maht
56
Õpetamise semester
sügis
Kontrollivorm
eksam
2019/2020 sügissemestri õppejõud
Peeter Normak (eesti keel) tavaline kursus
2019/2020 kevadsemestri õppejõud
õppejõud on määramata
Õppeaine eesmärgid
Võimaldada üliõpilasel saada põhiteadmised teoreetilise informaatika põhistruktuuridest (lõplikud automaadid, formaalsed keeled, lahenduvus, keerukus ja parallelarvutus) ja nende põhiomadustest ning oskused neid lihtsamate probleemide lahendamisel rakendada.
Õppeaine sisu lühikirjeldus
Teoreetilise informaatika aine. Graafiteooria ja formaalsete keelte põhimõisted. Lõplikud automaadid ja nende poolt aktsepteeritavad keeled. Regulaarsed avaldised. Teoreemid regulaarsete avaldiste ja lõplike automaatide vastavusest. Pumping-lemma regulaarsete keelte jaoks. Kontekstivabad grammatikad ja nende normaalkujud. Pumping-lemma kontekstivabade grammatikate jaoks. Magasinmäluga automaadid. Turingi masinad ja piiranguteta grammatikad. Chomsky teoreem keelte hierarhiast. Lahenduvus ning algoritmide keerukus.
Iseseisev töö
Iseseisev töö: loengukonspekti läbitöötamine ning koduste ülesannete lahendamine praktikumideks valmistumiseks.
Õppeaine õpiväljundid
Teab teoreetilise informaatika ühe osa (lõplikud automaadid ja formaalsed keeled) põhimõisteid, -tulemusi ja probleeme;
Oskab lahendada lõplike automaatide ja formaalsete keeltega seonduvaid lihtsamaid ülesandeid;
Suudab lihtsamaid asjakohaseid probleeme esitada ja analüüsida kursuses käsitletud vahenditega.
Hindamismeetodid
Eksam. Eksam on kirjalik; hinne kujuneb ülesannete lahendusoskuste (42%) ning teoreetiliste teadmiste alusel (58%).


Õppejõud
prof Peeter Normak
Kohustuslik kirjandus
Peeter Normak, Teoreetiline informaatika. Loengukonspekt. TLÜ informaatika instituut 2014
Asenduskirjandus
1. Michael Sipser (1997), Introduction to the Theory of Computation, ISBN 0-534-94728-X.
2. John C. Martin (2011), Introduction to Languages and the Theory of Computation, ISBN 9780071289429.
3. John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman (2007), Introduction to automata theory, languages and computation, Addison-Wesley, (www-db.stanford.edu/~ullman/ialc.html).