Automaatit I (TIETS02)

Julkaistu

Automaatit I on TIM-maisteriohjelman syventäviä jaksoja. Kelpaa myös matematiikan syventäväksi (ks. tarkemmin matematiikan opinto-oppaasta).

Sisältö

Laskennan teoria jaetaan perinteisesti kolmeen osaan: automaatit-, laskettavuus- ja vaativuusteoria.

Automaatit I kurssi käsittelee abstrakteja automaatteja, jotka toimivat laskennan matemaattisina malleina.

Automaatit II kurssi käsittelee kahta jälkimmäistä osa-aluetta nimittäin laskettavuutta ja vaativuusteoriaa.

Avainsanoja:

  • Äärellinen automaatti,
  • Formaali kieli,
  • Chomskyn kielihierarkia,
  • Kontekstittomat kieliopit,
  • Pinoautomaatti,
  • Turingin kone.

TIETS02 kurssilla määritellään diskreettejä matemaattisia olioita. Esim. yllä olevassa kuvassa on äärellinen automaatti
A = (Q, \Sigma, \delta, q_0, F), \text{ missä } Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7 \}, \Sigma = \{ a,u,t,o,m,i \}, {\delta: Q \times \Sigma \rightarrow Q}, \delta = \{((q_0,a),q_1),((q_1,u),q_2),((q_2,t),q_3),((q_3,o),q_4),((q_4,m),q_5),((q_5,a),q_5),((q_5,t),q_6),((q_6,t),q_6),((q_6,i),q_7) \} \cup \{x\mid x = ((q,s),q_r) \text{ on tilasiirtymä, joka ei näy kuvassa,} q \in Q, s \in \Sigma, q_r \text{ on hylkytila}\}, {q_0 \in Q} \text{ ja } {F = \{q_7\} \subseteq Q.}

Varsinainen täsmällinen määritelmä äärelliselle automaatille annetaan kurssin alkupuolella. Esitietoina suositellaan kertaamaan seuraavat käsitteet ja niihin liittyvät määritelmät: joukko, relaatio, kuvaus (funktio), puu ja graafi (verkko).

Katso esim. kirjan Johdatus diskreettiin matematiikkaan kappaleet 3, 4 ja 5 (myös kappaleiden 1-2 kertaamista suositellaan, ja innokkaimmat voivat vilkaista kappaletta 8).

Yllä olevassa kuvassa emuloidaan 6502 prosessorilla suoritettavaa ohjelmaa, joka simuloi äärellistä automaattia kahden ensimmäisen tilan osalta. Vaikka Automaatit I kurssin teoriat mahdollistavat erilaiset sovellukset, kuten ohjelmointikielten kääntäjät ja konkreettiset tietokoneet, emme kuitenkaan kurssin aikana juuri ehdi toteuttamaan sovelluksia.

Kyseiset sovellukset vaatisivat työmäärään suhteen omat kurssinsa, ja koska kyseessä on teoreettisen tietojenkäsittelyn kurssi, painopiste on luonnollisesti teoriassa ja käsitteiden täsmällisessä kuvaamisessa. Kurssin aikana saa toki toteuttaa (ohjelmoida) esim. algoritmeja, ja toteutuksista on mahdollista tienata ylimääräisiä pisteitä tenttiä varten.

Opetus

Jakso järjestetään syksyllä 2018 II-periodissa. Opetusajat ja paikat ilmoitetaan opetusohjelmassa.

Kurssilla on Moodle-alue, joka toimii kurssin pääasiallisena foorumina.

Moodle-alueen osoite on https://learning2.uta.fi/course/view.php?id=14184

Muutoin tätä sivua ei tulla päivittämään.

Materiaalit

Kirjallisuutta: J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Second Edition. Addison-Wesley, 2001.

Vastuuopettaja

Syksyn 2018 jaksolla opettajana toimii Jonne Iso-Tuisku.