581336-0 Laskennan teoria (3 ov)

Opetus syksyllä 2004

Kurssikoe on korjattu. Palautetilaisuus pidetään tiistaina 4.1. kello 12-13. Voit kysyä arvostelusta myös suoraan luennoijalta.

• tulokset
• tehtävät
• malliratkaisut ja arvosteluperusteet

Kurssikyselyyn on tullut 35 vastausta (tilanne 4.1.). Kiitos vastanneille!

Luentoja pidettiin

Jyrki Kivinen 11.10.-1.12. ma 10-12, ke 12-14 CK112

Laskuharjoituksia pidettiin 18.10.- 10.12.:

1. Lauri Eronen ma 16-18 B222
2. Janne Rinta-Mänty ti 10-12 B119
3. Jyrki Kivinen ke 10-12 C221
4. Jouni Siren ke 14-16 B119
5. Janne Rinta-Mänty to 12-14 B119
6. Jouni Siren pe 12-14 B119

Kurssikoe pidettiin

to 16.12. kello 16-20 B123

Luentomateriaali ja harjoitustehtävät

(Erilliskokeet)

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:

• Pekka Orponen: Laskennan teoria. Luentomoniste, 1994.
• Michael Sipser: Introduction to the Theory of Computation. PSW Publishing 1997.

Luentomuistiinpanoja toimitetaan saataville kurssin edetessä, mutta niitä ei ole tarkoitettu itseopiskeluun ilman lisämateriaalia (esim. kurssikirja).

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