TIES5303 Models of Computation (3–5 cr)

Automaattien ja formaalien kielten peruskäsitteitä, äärelliset automaatit ja säännölliset kielet, kieliopit ja context-free kielet, pinoautomaatti, rekursiivisesti etenevä jäsentäminen, Turingin koneet ja laskettavuus, lyhyesti muista yleisistä laskennan malleista

Opintojakson suoritettuaan opiskelija osaa selittää kurssilla esitettyjen äärellisten automaattien, pinoautomaattien ja Turingin koneiden eroavaisuudet laskennan malleina ja tunnistaa niihin liittyvät rajoitteet ja mahdollisuudet sekä osaa yhdistää ne eri kieliperheisiin. Hän osaa selittää käsitteiden laskennallinen ongelma, ratkeava ongelma, osittain ratkeava ongelma ja ratkeamaton ongelma keskeisen sisällön ja niiden väliset erot. Lisäksi hän osaa selittää laskennallisten ongelmien ja kurssilla käsiteltävien laskennan mallien välisen yhteyden sekä osaa tulkita Turingin koneelle esitettyjen tulosten koskevan myös tietokoneita ja niille kirjoitettuja ohjelmia. Hän osaa selittää mitä aika- ja tilakompleksisuudella yleisesti tarkoitetaan ja mikä on niiden merkitys ongelmien ratkaisemisen kannalta. Hän osaa lisäksi soveltaa esitettyjä automaattimalleja ohjelmien suunnittelussa ja ratkaisemisessa.Hänellä on valmiudet etsiä ja omaksua tietoa muista laskennan malleista ja laskennallisesta vaativuudesta.

Matematiikan perusteet (esimerkiksi Diskreetit rakenteet tai matematiikan aineopintoja), algoritmien perusteet (esimerkiksi Algoritmit 1, Algoritmit 2) ja ohjelmoinnin perustaidot (esimerkiksi Ohjelmointi 1, Ohjelmointi 2)