581336-0 Laskennan teoria (3 ov)

Prof. Tapio Elomaa (Matti Kääriäinen viikolla 48: 26.-27. 11.)

Laskuharjoitusassistentit: Matti Luukkainen, Mikko Rauhala ja Jouni Siren

Syksy 2002, 15.10.-4.12.

Luennot: ti 12-14 ja ke 10-12 A217
Laskarit: Katso ryhmien ajat opetusohjelmasta
Koe: ti 17.12. klo 16-20 Auditorio, tammikuun erilliskoe 17.1.2003 14-18 Aud. (siirretty)

Ajankohtaista

Tentin 10.6.2003 tulokset (Intranet)

Tentin 21.3.2003 tulokset (Intranet)

Tentin 17.1.2003 tulokset (Intranet)

Kurssin tulokset (Intranet)

Kurssikokeen arvosteluperusteita:
Tehtävä 1
Tehtävä 2
Tehtävä 3
Tehtävä 4

Luentoviikko	Luentokalvot	Laskuharjoitukset	Mallit	Exercises	Sections in HMU
1: 15.-16.10.	PS ja PDF	PS ja PDF		PS and PDF	8.2
2: 22.-23.10.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	8.3-8.5
3: 29.-30.10.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	9.1-9.2
4: 5.-6.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF
5: 12.-13.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF
6: 19.-20.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF
7: 26.-27.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF
8: 3.-4.12.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF

Yleistä

Laudaturin pakollinen kurssi pääaineopiskelijoille. 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.

Kurssikirja on Hopcroftin, Motwanin ja Ullmanin kirja Introduction to Automata Theory, Languages, and Computation (2nd ed., Addison-Wesley, 2001).

Esitiedot

Kurssi Ohjelmoinnin ja laskennan perusmallit. Matemaattiset perusvalmiudet (algebra, diskreetti matematiikka).

Muodot

Luennot, laskuharjoitukset sekä kurssikoe.

Laskuharjoitukset

Kurssin laskuharjoitukset ovat pakolliset. Ne ovat olennainen osa kurssia. Laskuharjoitusten pakollisuus tarkoittaa, että on oltava läsnä vähintään 4 kertaa. Läsnäolo puolestaan tarkoittaa, että on tehnyt vähintään puolet tehtävistä (esim. 5/2=2). On suositeltavaa osallistua laskuharjoituksiin joka kerta.

Laskuharjoituslisäpisteitä saa vasta kun on tehnyt vähintään puolet kaikista laskuharjoitustehtävistä.

Sisältö

1. Laskennan universaaleja malleja

Turingin koneet

Rajoittamattomat kieliopit

2. Laskettavuusteoriaa

Rekursiiviset ja rekursiivisesti lueteltavat kielet

Turingin koneiden koodaus

Universaalit Turingin koneet

Pysähtymisongelma

Ratkeamattomuustuloksia

Rekursiiviset funktiot

Rekursiiviset palautukset

3. Laskennan vaativuusteoriaa

Turingin koneiden aika- ja tilavaativuus

Vaativuusfunktioiden kertaluokat

Vaativuusluokat

Epädeterministiset vaativuusluokat

Luokan NP ongelmia

Polynomiset palautukset

Kirjallisuutta

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

Pekka Orponen: Laskennan teoria. Luentomoniste, 1994.

Linkkejä

Ohjelmoinnin ja laskennan perusmallit

Algoritmien suunnittelu ja analyysi

Laskettavuuden teoria, matematiikan laudatur-kurssi

Teoreettiseen tietojenkäsittelyyn liittyviä visualisointityökaluja

Algoritmien erikoistumislinja

elomaa@cs.helsinki.fi