581336-0 LASKENNAN TEORIA (3 ov)

Prof. Tapio Elomaa

Laskuharjoitusassistentit: Matti Kääriäinen ja Jouni Siren

Syksy 2001, 9.10.-28.11.

Luennot: ti 12-14 ja ke 10-12 A217
Laskarit: ke 12-14 (TE), 14-16 (MK ja JS) ja to 14-16 (MK ja JS)
Koe: ti 11.12. klo 16-20 Auditorio

Ajankohtaista

Itsenäisyyspäivän (to 6.12.) laskuharjoitusryhmät siirretään pidettäväksi tiistaina 4.12. klo 10-12 saleissa A319 (MK) ja A320 (JS)

Luentoviikko	Luentokalvot	Laskuharjoitukset	Mallit	Exercises	Sections in HMU
1: 9.-10.10.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	8.2
2: 16.-17.10.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	8.4 + unrestricted grammars (not in HMU)
3: 23.-24.10.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	9.1 - 9.2
4: 30.-31.10.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	9.3
5: 6.-7.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	9.3, 8.1
6: 13.-14.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF	10.1
7: 20.-21.11.	PS ja PDF	PS ja PDF	PS ja PDF	PS and PDF
8: 27.-28.11.	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 uusi kirja "Introduction to Automata Theory, Languages, and Computation" (2nd ed., Addison-Wesley, 2001). Pekka Orposen luentomoniste "Laskennan teoria" on suositeltavaa oheislukemista.

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

Rekursiivisten ja RE-kielten perusominaisuuksia

Turingin koneiden koodaus

Universaalit Turingin koneet

Pysähtymisongelma

Chomskyn kieliluokat

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

Teoreettiseen tietojenkäsittelyyn liittyviä visualisointityökaluja

elomaa@cs.helsinki.fi