Laskettavuuden Teoria

Kevät 2009

Yleistä

Keväällä 2009 opetettava kurssi on kaksiosainen: kurssin alkuosa Laskettavuuden teoria A on matematiikan syventävä erikoiskurssi, jonka laajuus on 6 op.  Tällä alkuosalla voi myös korvata tietojenkäsittelyopin opintojakson
Automaatit.  Vastaavasti Laskettavuuden teoria A:n voi korvata kurssin Automaatit suorituksella. Kurssin loppuosa Laskettavuuden teoria B on matematiikan syventävä erikoiskurssi, jonka laajuus on 4 op.

Huom:  Kursseilla Laskettavuuden teoria A+B voi yhdessä korvata opintojakson Joukko-oppi suorituksen.

Luennot ja harjoitukset

Luennot:

            ma   14-16   C8  päätalo
            to     14-16  A4  päätalo

Viikkoharjoitukset:

            to     10-12  A5073   vain kurssin A osan aikana
            to     12-14  A5073 

Ensimmäinen luento on torstaina  15.1. ja ensimmäiset viikkoharjoitukset torstaina  29.1.

Huom:  Maanantain 4.5. luento siirretään tiistaille 5.5. klo 12-14 saliin A 3112.

Luennoija:  Prof. Lauri Hella (lauri.hella@uta.fi), tavattavissa luentojen yhteydessä sekä vastaanotolla  (ma 13-14).
Harjoitusryhmää ohjaa  FM Jonni Virtema.

Kurssien suorittaminen

Kurssin molemmat osat suoritetaan loppukokeella, ja aktiivisella harjoituksiin osallistumisella. Loppukokeesta voi saada 0-24 pistettä, ja harjoituksista tehtyjen tehtävien mukaan 0-6 pistettä.  Läpipääsyyn riittää 15 pistettä.

Loppukoeajat ja -paikat

Laskettavuuden teoria A:n loppukoe:

            to  26.3.  klo  14-16  A4  päätalo 

Laskettavuuden teoria B:n loppukoe:

            ma  11.5.  klo  14-16  C8  päätalo 

Kurssien sisältö

Kurssin A-osassa käydään läpi säännölliset kielet, äärelliset automaatit, muodolliset kieliopit, Chomskyn kielihierarkia, kontekstittomat kielet, pinoautomaatit ja Turingin kone. Kurssin B-osassa tarkastellaan yleistä laskettavuuden käsitettä Turingin koneen pohjalta, sekä tutustutaan vaativuusluokkiin P, NP, LOG, NLOG, PSPACE.

Kurssilla ei ole varsinaista luentomonistetta, mutta suurin osa sen sisällöstä löytyy Erkki Mäkisen Automaatit kurssin monisteesta. Toinen hyvä aihepiirin esittely on Keijo Ruohosen  TTY:llä pitämän kurssin monisteessa.

Varsin kattava aiheen esittely löytyy kirjasta Hopcroft-Motwani-Ullman: Introduction to Automata Theory, Languages and Computation.

Viikkoharjoitustehtävät

Tehtävät annetaan edellisen viikon torstaina: pdf-tiedostot tulevat tähän kurssin kotisivulle.

Laskettavuuden teoria A:

    Harj 1      Harj 2      Harj 3      Harj 4      Harj 5      Harj 6      Harj 7     


Laskettavuuden teoria B:
 
    Harj 1      Harj 2      Harj 3      Harj 4      Harj 5      Harj 6