TIEA241 Automaatit ja kieliopit (5 op)
Opinnon taso:
Aineopinnot
Arviointiasteikko:
0-5
Suorituskieli:
suomi
Vastuuorganisaatio:
Informaatioteknologian tiedekunta
Opetussuunnitelmakaudet:
2017-2018, 2018-2019, 2019-2020
Kuvaus
Sisältö
Äärelliset automaatit ja säännölliset kielet, kieliopit ja kontekstittomat kielet, pinoautomaatti, rekursiivisesti etenevä jäsentäminen, kontekstiset ja rajoittamattomat kieliopit, Turingin koneet, ratkeavuus ja puoliratkeavuus.
Suoritustavat
Kirjalliset oppimistehtävät tai tentti.
Arviointiperusteet
Kurssi arvioidaan oppimistehtävien tai tentin perusteella. Läsnäolopakkoa ei ole.
Osaamistavoitteet
Opintojakson suoritettuaan opiskelija osaa selostaa seuraavien käsitteiden keskeisen sisällön ja niiden väliset erot: äärellinen automaatti, pinoautomaatti, Turingin kone; deterministinen ja epädeterministinen automaatti; säännöllinen lauseke; säännöllinen, kontekstiton, kontekstinen ja yleinen kielioppi; säännöllinen, kontekstiton, laskettava ja laskettavasti lueteltava kieli; sekä päätösongelma, puoliratkeava päätösongelma ja ratkeava päätösongelma. Lisäksi opiskelija osaa soveltaa osaa seuraavista abstraktioista ohjelmointitehtävissä: säännölliset lausekkeet, äärelliset automaatit, kontekstittomat kieliopit, pinoautomaatit. Lisäksi opiskelija osaa tulkita tietojenkäsittelyteoreettisia määritelmiä kurssin sisältöihin kuuluville käsitteille sekä laatia yksinkertaisia tietojenkäsittelyteoreettisia todistuksia.
Esitietojen kuvaus
ohjelmointitaito (esimerkiksi Ohjelmointi 1, Ohjelmointi 2 ja Algoritmit
1) sekä abstraktin matematiikan kielen ja todistustekniikoiden alkeiden
osaaminen (esimerkiksi TIEP1020 Diskreetit rakenteet tai matematiikan
aineopintoja)
1) sekä abstraktin matematiikan kielen ja todistustekniikoiden alkeiden
osaaminen (esimerkiksi TIEP1020 Diskreetit rakenteet tai matematiikan
aineopintoja)
Oppimateriaalit
Sipser: Introduction to the Theory of Computation (3nd international ed). Thompson 2006. ISBN 0-619-32764-2.
Osin myös Aho, Lam, Sethi, Ullman: Compilers – Principles, Techniques, , Tools (2nd ed). Addison Wesley 2007.
Osin myös Aho, Lam, Sethi, Ullman: Compilers – Principles, Techniques, , Tools (2nd ed). Addison Wesley 2007.
Suoritustavat
Tapa 1
Valitaan kaikki merkityt osat
Suoritustapojen osat
x
Julkaisematon arviointikohde