Opinto-opas

Osaamistavoitteet

Tietojenkäsittelyteorian alkeiden hallinta. Säännöllisten kielten ja kontekstittomien kielten kuvaamisessa ja käsittelemisessä tarvittavien välineiden ja tekniikoiden hallinta. Käsitys laskettavuuden ja ratkeavuuden perusteista, Churchin-Turingin teesistä ja näiden keskeisistä perusteluista ja seurauksista.

Sisältö

Tietojenkäsittelyongelmien ja niiden ratkaisukeinojen teoreettinen mallintaminen rajoittuen käytännön ohjelmistotyössä sovellettaviin kuvausmenetelmiin ja syötteiden käsittelytekniikoihin (alkioanalyysi ja jäsennys): Äärelliset automaatit ja säännölliset kielet, pinoautomaatit ja kontekstittomat kielet.

Esitietovaatimukset

Johdatus tietojenkäsittelytieteeseen, Tietorakenteet ja algoritmit I, Diskreetit rakenteet (ja näiden kurssien esitiedot)

Oppimateriaalit

Luentomuistiinpanot, sopivia kirjoja: Sipser M.: Introduction to the Theory of Computation. Hopcroft J.E., Motwani R., Ullman J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd Ed. Pearson, 2003. Lewis H.R., Papadimitriou C.H.: Elements of the Theory of Computation, 2nd Ed., Prentice Hall, 1998.

Lisätiedot

Itä-Suomen yliopiston Tietojenkäsittelytieteen laitoksen toteuttama opintojakso

Esitietovaatimukset

Johdatus tietojenkäsittelytieteeseen, Tietorakenteet ja algoritmit I, Diskreetit rakenteet (ja näiden kurssien esitiedot)