TIEA241 Automaatit ja kieliopit (5 op)

Avaa opintojakson esite Sisussa
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)

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.

Suoritustavat

Tapa 1

Valitaan kaikki merkityt osat
Suoritustapojen osat
x

Osallistuminen opetukseen (5 op)

Tyyppi:
Osallistuminen opetukseen
Arviointiasteikko:
0-5
Suorituskieli:
suomi

Opetus