Automaattien teorialla on pitkä historia tieteessä. Sen synty voidaan ajoittaa 1840-luvulle ja alaa on kehitetty aktiivisesti 1930-luvulta lähtien. Aihe on keskeinen osa useimpia tietojenkäsittelytieteen koulutusohjelmia maailmalla (ja monia diskreetin matematiikan koulutusohjelmia) useistakin syistä:
- Se on hyvin yksinkertainen laskennan malli;
- Se on hyvä malli interaktiiviselle laskennalle: kone, joka reagoi ympäristöönsä ja tuottaa laskennan ympäristön mukaan;
- Se tuo esiin monien eri tosielämän prosessien iteratiiviset näkökulmat: kuvioiden tunnistaminen tekstissä tai kuvassa, lääketieteellisessä diagnostiikkaprosessissa tehdyt vaiheet, sijoituspäätökset, tekoäly (esim. videopeleissä).
Automaattien teoria on erityisen tärkeä perusta tietojenkäsittelytieteen koulutusohjelmille, koska se esittelee hyvin yksinkertaisen laskennan mallin, joka kuitenkin ottaa huomioon vaiheittaisten prosessien ja ympäristön vuorovaikutuksen keskeiset piirteet. Se on yksinkertaisimpia mutta perustavanlaatuisimpia laskennan ajattelumalleja.
Automaattien teoria on tärkeä osa matematiikan koulutusohjelmia, koska se esittelee hyvin erilaisen matematiikan osa-alueen perinteisiin matematiikan osa-alueisiin verrattuna (analyysi, algebra, geometria, topologia, lukuteoria jne.). Se käsittelee joitain konsepteja, jotka ovat ainutlaatuisia muussa diskreetissä matematiikassa, johon automaattien teorian voidaan katsoa kuuluvan. Näitä ovat esimerkiksi dynaamiset prosessit ja äärettömyys.
Tämä kurssi on johdanto automaatien teoriaan. Kurssin ensimmäisessä osassa esitellään yksi yksinkertainen matemaattinen työkalu, jonkun avulla voidaan perustella iteratiivisia laskennallisia prosesseja: rakenteellinen induktio (joka esim. mahdollistaa päättelyn automaatin onnistuneista laskelmista).
Kurssin toisessa osassa esitellään automaattien teorian keskeisimmät osat:
- äärelliset automaatit (joitain yksinkertaisimmista laskentamalleista),
- säännölliset ilmaisut (tärkeä tekstihaussa ja kuvioiden yhdistämisessä),
- säännölliset kieliopit (tärkeä ohjelmointikielten kääntäjissä).
Oppimistavoitteet
- Ymmärtää laskennan käsite vaiheittaisena tilasiirtymäjärjestelmänä.
- Ymmärtää deterministisen laskennan käsite prosessina, jolla on ainutlaatuinen seuraaja.
- Ymmärtää epädeterministisen laskennan käsite prosessina, jolla on useita mahdollisia seuraajia.
- Ymmärtää determinismi ja epädeterminismi ovat ekvivalentteja äärellisille automaateille, mutta ei yleisesti.
- Ymmärtää äärellisen automaatin käsite laskennallisena perusmallina, jolla on rajallinen muisti ja mielivaltaisen pitkä syöttö.
- Ymmärtää äärellisen automaatin käsite kuvioiden varmistusvälineenä.
- Ymmärrä säännöllisten ilmaisuiden käsite rakennekuvauksena.
- Ymmärtää säännöllisten kielioppien käsite kuvioiden generatiivisina välineinä.
