Teoreetiline informaatika (IFI6019.DT)
space
Õ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
Kontrollivorm
eksam
2023/2024 kevadsemestri õppejõud
Ei ole õpetamiseks avatud. Vt all õppekava lingi kaudu peaeriala all nominaaljaotuse ajakava.
2024/2025 sügissemestri õppejõud
Ei ole õpetamiseks avatud. Vt all õppekava lingi kaudu peaeriala all nominaaljaotuse ajakava.
Õ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.
Õppeaine õpiväljundid
Õppeaine edukal läbimisel ü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.
Õppejõud
prof Peeter Normak
space