Teoreetiline informaatika (IFI6212.DT)
Õppeaine kood
IFI6212.DT
vana ainekood
Õppeaine nimetus eesti k
Teoreetiline informaatika
Õppeaine nimetus inglise k
Theoretical Computer Science
Õppeaine maht EAP
4.0
Orienteeruv kontakttundide maht
56
Õpetamise semester
kevad
Kontrollivorm
eksam
2019/2020 sügissemestri õppejõud
Peeter Normak (eesti keel) e-toega 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. Paralleelarvutuse mudelid ja Petri-võrgud.
Iseseisev töö
Loengukonspekti läbitöötamine ning koduste ülesannete lahendamine praktikumideks valmistumiseks.
Õppeaine õpiväljundid
Üliõpilane:
- 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
Kontrolltööd ja eksam on kirjalikud; hinne kujuneb kahe kontrolltöö (kokku 50%) ja eksamihinde (50%) alusel.
Õppejõud
Peeter Normak, PhD
Kohustuslik kirjandus
Peeter Normak, Teoreetiline informaatika. Loengukonspekt. TLÜ informaatika instituut 2010
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).