581336-0 Laskennan teoria (3 ov)

Opetus keväällä 2006

Kurssikoe pidettin torstaina 4.5. kello 9.00-12.00 salissa B123:

• tehtävät (PS, PDF)
• malliratkaisut (päivitetty 12.5.): PS, PDF
• tulokset

Kurssikyselyyn tuli (12.7. mennessä) 40 vastausta. Kiitos osallistuneille!

Luentoja pidettiin seuraavasti:

Jyrki Kivinen 18.1.-24.2. ja 15.3.-21.4. ke 16-18, pe 12-13 salissa B123

Laskuharjoituksia pidettiin 23.1.-28.4.:

1. Janne Rinta-Mänty ti 10-12 B119
2. Janne Rinta-Mänty ke 12-14 CK111
3. Janne Rinta-Mänty ke 14-16 BK106
4. Jyrki Kivinen ke 18-20 C222
5. Jyrki Kivinen pe 10-12 BK106

(Erilliskokeet)

Kurssimateriaali

Reunahuomautus: Luennolla nousi esiin kysymys, ovatko kaikki ei-rekursiiviset kielet NP-kovia. Oheinen konstruktio osoittaa, että on olemassa ei-rekursiivisia kieliä, jotka eivät myöskään ole NP-kovia. (Tämä ei kuulu kurssin koealueeseen!)

Luentomuistiinpanot

Kaikki luentokalvot (sivut 1-270):

• PostScript 4 sivua/arkki tulostettavaksi
• PDF ruudulla katseltavaksi.

Näitä ei ole tarkoitettu itseopiskeluun ilman lisämateriaalia (esim. kurssikirja) vaan helpottamaan luentojen etenemisen seuraamista.

Laskuharjoitukset

1. harjoitus (24.-27.1.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
2. harjoitus (31.1.-3.2.) tehtävät (PS, PDF), ratkaisut (vain PS)
3. harjoitus (7.-10.2.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   Tehtävässä 4(c) on virhe: kieli A pitää lisäksi olettaa äärettömäksi.
4. harjoitus (14.-17.2.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   
5. harjoitus (21.-24.2.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   
6. harjoitus (14.-17.3.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   
7. harjoitus (21.-24.3.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   
8. harjoitus (28.-31.3.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   
9. harjoitus (4.-7.4.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
   
10. harjoitus (11.-21.4.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
    
11. harjoitus (25.-28.4.) tehtävät (PS, PDF), ratkaisut (PS, PDF)
    

Yleistä

Kurssi laajentaa ja syventää Ohjelmoinnin ja laskennan perusmallit -kurssin antamaa tietojenkäsittelytieteen teoreettisten perusteiden tuntemusta. Erityisesti tarkastellaan Turingin koneita, laskennallisten ongelmien ratkeavuutta sekä laskennan vaativuusteoriaa.

Asema opetuksessa

Laudaturin pakollinen kurssi tietojenkäsittelyn, opettajan sekä bioinformatiikan ja laskennallisen biologian suuntautumisvaihtoehdossa.

Opiskelijoilta edellytetään kurssien Ohjelmoinnin ja laskennan perusmallit ja Tietorakenteet tiedot sekä kohtuulliset matemaattiset perusvalmiudet (esim. kursseilta Logiikka I tai Diskreetti matematiikka I).

Aihepiiriin liittyviä jatkokursseja ovat mm. Algoritmien suunnittelu ja analyysi ja useat algoritmien erikoistumislinjan erikoiskurssit sekä Laskettavuuden teoria ja osittain muutkin matemaattisen logiikan kurssit.

Suoritusmuodot

Luentokurssi koostuu luennoista, laskuharjoituksista ja kurssikokeesta. Vaihtoehtoisesti kurssin voi myös suorittaa erilliskokeella.

Laskuharjoitukset ovat pakollisia suoritettaessa kurssi kurssikokeella. Laskuharjoituksista voi tällöin saada myös lisäpisteitä. Tarkemmista yksityiskohdista tiedotetaan erikseen.

Kirjallisuutta

Kurssikirja:

• Hopcroft J. E., Motwani R., Ullman J. D.: Introduction to Automata Theory, Languages, and Computation (2nd ed.). Addison-Wesley, 2001

Suositeltavaa oheislukemista:

• Michael Sipser: Introduction to the Theory of Computation. PSW Publishing 1997.
• Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of computation. Prentice Hall 1998 (second edition).
• Pekka Orponen: Laskennan teoria. Luentomoniste, 1994. (Nykyistä Laskennan teoriaa edeltäneen kurssin luentomoniste; edelleen käyttökelpoinen jos sen sattuu saamaan käsiinsä.)

Sisältö

1. Johdanto
• Laskennalliset ongelmat
• Pysähtymisongelman ratkeamattomuus
2. Universaaleja laskennan malleja
• Turingin koneet
• Rajoittamattomat kieliopit
• Churchin-Turingin teesi
3. Laskettavuusteoriaa
• Rekursiiviset ja rekursiivisesti lueteltavat kielet
• Rekursiiviset funktiot ja palautukset
• Universaalit Turingin koneet
• Ratkeamattomuustuloksia
4. Vaativuusteoriaa
• aika- ja tilavaativuus
• deterministiset ja epädeterministiset vaativuusluokat
• polynomiset palautukset
• luokka NP; NP-täydellisyys
• SAT ja muita NP-täydellisiä ongelmia