Laskettavuuden Teoria

Syksy 2006

Luennot ja harjoitukset

Luennot:

            ti   14-16  C8  päätalo
            to  12-14  C8  päätalo

Viikkoharjoitukset:

            to   14-16  A2a  päätalo

Ensimmäinen luento on torstaina  7.9. ja ensimmäiset viikkoharjoitukset torstaina  21.9.

Luennoitsija:  Prof. Lauri Hella (lauri.hella@uta.fi), tavattavissa luentojen yhteydessä sekä vastaanotolla  (ma 13-14).
Harjoitusryhmää ohjaa  M.Sc. Antti Kuusisto.

Kurssin suorittaminen

Laskettavuuden teoria on matematiikan syventävä erikoiskurssi, jonka laajuus on 5 ov (10 op).  Kurssilla pidetään kaksi välikoetta, joista voi saada yhteensä 2x24 = 48 pistettä. Harjoitusaktiivisuus palkitaan lisäpisteillä, joita saa tehtyjen tehtävien mukaan  0-8.  Arvosteluasteikko perustuu kuitenkin 48 pisteen maksimiin, jolloin läpipääsyyn riittää n. 24 pistettä. Molemmista välikokeista pitää kuitenkin saada vähintään 6 pistettä.

Välikoeajat, -paikat

Välikokeita on kaksi:

             1. välikoe    ti  7.11.     14-16   C8   päätalo
             2. välikoe    ti  12.12.   14-16   C8   päätalo

Kurssin sisältö

Kurssilla käydään läpi laskettavuuden teorian perusasiat matemaattisesta näkökulmasta. Laskennan mallina käytetään n.s. URM konetta (unlimited register machine), jonka lisäksi perehdytään myös rekursiivisten funktioiden määritelmään sekä lyhyesti myös Turingin koneen määritelmään.

Kurssi ei edellytä erityisiä pohjatietoja; matematiikan perusopintokurssien sisältö riittää hyvin. Kurssin asioiden omaksuminen vaatii kuitenkin riittävää matemaattista kypsyyttä, joten sitä suositellaan vasta aineopintojen jälkeen suoritettavaksi.

Luennot pohjautuvat suureksi osaksi oppikirjaan

N.J. Cutland: Computability,  Cambridge University Press 1980.
Kirjaa ei kuitenkaan tarvitse hankkia; kurssin aikaisemmat luentomuistiinpanot ovat saatavilla kopiointia varten.

Viikkoharjoitustehtävät

Tehtävät jaetaan monistettuna torstain luennoilla, jolloin ne löytyvät myös laitoksen lokerikosta.