582206 Laskennan mallit (6 op)
Kurssi luennoidaan syksyllä 2008.
Kurssi on aiemmin luennoitu
- syksyllä 2006 (kommentoitu tiivistelmä opiskelijapalautteesta)
- syksyllä 2007.
Yleistä
Kurssilla luodaan peruskatsaus laskennallisten ongelmien ja niiden ratkaisemiseksi käytettävien laskentamekanismien matemaattisiin malleihin. Perustavoitteena on nähdä, miten näistä asioista voidaan esittää täsmällisiä määritelmiä ja päätelmiä. Samalla tutustutaan tietojenkäsittelyteorian perustuloksiin ja niiden vaikutuksiin tietojenkäsittelytieteen eri osa-alueilla.
Kurssilla käsitellään ensin säännöllisiä ja kontekstittomia kieliä ja niiden tunnistamiseen kykeneviä automaatteja, joilla on sovelluksia esim. ohjelmointikielissä. Lopuksi tarkastellaan kysymystä siitä, mitkä ongelmat on ylipäänsä mahdollista ratkaista algoritmisesti. Tässä käytetään Turingin konetta formalisoimaan, mitä "algoritmilla" oikeastaan tarkoitetaan.
Asema opetuksessa
Kurssi on tietojenkäsittelytieteen pääaineopiskelijoille pakollinen aineopintokurssi.
Kurssi korvaa vanhan kurssin Ohjelmoinnin ja laskennan perusmallit; näitä kahta ei voi sisällyttää samaan tutkintoon.
Esitietovaatimuksena on kurssi Tietorakenteet. Kurssilla ei tarvitse tuntea mitään monimutkaisia tietorakenteita tai algoritmeja, mutta ainakin puiden ja verkkojen peruskäsitteiden ja verkon läpikäyntialgoritmien olisi hyvä olla muistissa.
Matematiikan osalta esitiedoiksi riittää Johdatus diskreettiin matematiikkaan. Koska kurssin lähestymistapa on matemaattinen, laajemmistakin matematiikan opinnoista on apua asioiden omaksumisessa.
Aihepiiristä kiinnostuneet voivat jatkaa algoritmeihin liittyvillä syventävillä kursseilla kuten Algoritmien suunnittelu ja analyysi. Myös Matemaattinen logiikka ja muut saman aihealueen kurssit ovat keskeisiä tietojenkäsittelyteorian ymmärtämiselle.
Suoritusmuodot
Kurssi suoritetaan luentokurssina tai vaihtoehtoisesti erilliskokeella.
Luentokurssi koostuu luennoista, laskuharjoituksista ja kahdesta kurssikokeesta. Kurssi luennoidaan joka syksy koko lukukauden mittaisena (periodit I ja II; 2 tuntia luentoja ja 2 tuntia harjoituksia viikossa).
Laskuharjoitukset ovat pakollisia suoritettaessa kurssi kurssikokeella. Laskuharjoituksista voi tällöin saada myös lisäpisteitä. Tarkemmista yksityiskohdista tiedotetaan luentokurssin yhteydessä.
Kurssikirja
Kurssi perustuu kirjaan
Michael Sipser: Introduction to the Theory of Computation. Second edition (international), Thomson Course Technology 2006.Kirjasta käsitellään suunnilleen luvut 0-4 ja osia luvusta 5. Kurssikokeisssa kuulusteltavat asiat rajataan tarkemmin luennoilla. Erilliskokeissa koealue on sama kuin edellisellä luentokurssilla.
Sisältö ja tavoitteet
- Johdanto: yleistä, matematiikan pikakertaus [Sipser luku 0]
- Säännölliset kielet: äärelliset automaatit, säännölliset lausekkeet, ei-säännölliset kielet [Sipser luku 1]
- Kontekstittomat kielet: kontekstittomat kieliopit, pinoautomaatit, ei-kontekstittomat kielet [Sipser luku 2]
- Laskettavuuden teoria: algoritmit ja Turingin koneet, ratkeavuus, ratkeamattomat ongelmat [Sipser luvut 3-5]
Oppimistavoitteet taulukkomuodossa
Suositeltavaa oheislukemista
Koska tämäntyyppinen kurssin on hyvin monen yliopiston opetusohjelmassa, myös oppikirjoja on tarjolla runsaasti. Seuraava on samantyylinen kuin kurssikirja:
Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation. Second edition, Prentice Hall 1998.Kurssilla Laskennan teoria käytettiin seuraavaa kirjaa, jonka esitystavasta jotkut opiskelijat pitävät:
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Third edition, Addison-Wesley 2006.Seuraava kirja sisältää huomattavasti enemmän asiaa, kuin kurssilla käsitellään:
Thomas A. Sudkamp: Languages and Machines: An Introduction to the Theory of Computer Science. Third edition, Addison-Wesley 2006.Seuraava on tarkoitettu "pehmeäksi laskuksi" tietojenkäsittelyteoriaan eikä käsittele kaikkia aiheita kurssin edellyttämässä laajuudessa:
Efim Kinber, Carl Smith: Theory of Computation: A Gentle Introduction. Prentice-Hall 2001.Pekka Orposen vanha luentomoniste kurssille Laskennan teoria (tai vastaava TKK:n moniste) on edelleen käyttökelpoinen, jos sen sattuu saamaan käsiinsä.
23. syyskuuta 2008 Jyrki Kivinen