581336-0 LASKENNAN TEORIA (3 ov)

Prof. Tapio Elomaa

Laskuharjoitusassistentti: Matti Kääriäinen

Syksy 2000, 19.9.-15.11.

Luennot: ti 12-14 ja ke 10-12 A217
Laskarit: ke 8-10 (MK), 12-14 (TE) ja 14-16 (MK), B453
Koe: pe 1.12. 14-18 Aud. vastauksia koekysymyksiin

Ajankohtaista

Kurssin koe on nyt arvosteltu ja tulokset ovat taululla nähtävissä.

Laskuharjoitukset:
lh1 (27. 9.): 81-85 Orposen monisteesta
lh2 (4. 10.): 87-89, 93, 94 Orposen monisteesta ja yksi RAM-kone tehtävä
lh3 (18. 10.): kolme RAM-kone tehtävää ja 95 sekä 96 Orposen monisteesta
lh4 (25. 10.): 104-108 Orposen monisteesta
lh5 (1. 11.): kolme uutta tehtävää ja 109-111 Orposen monisteesta
lh6 (8. 11.): Lauseen 6.15 todistus ja 114-117 Orposen monisteesta
lh7 (15. 11.): 119, 121, 122, 125 ja 126 Orposen monisteesta
lh8 (22. 11.): kurssikysely ja tehtävät 128 - 131 Orposen monisteesta

Luentokalvot: : vko 1, vko 2, vko 3, vko 4, vko 5, vko 6, vko 7, vko 8

Syksyn luennot perustuvat vielä oleellisesti Pekka Orposen luentomonisteeseen "Laskennan teoria".

Yleistä

Laudaturin pakollinen kurssi pääaineopiskelijoille. Korvaa yhdessä kurssin ohjelmoinnin ja laskennan perusmallit kanssa vanhan laskennan teoria (4 ov) kurssin.

Esitiedot

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

Muodot

Luennot, laskuharjoitukset sekä välikoe. Vaihtoehtoisesti loppukoe.

Syksyn 2000 kurssin arvostelussa laskuharjoitustehtävien tekemisestä saa lisäpisteitä enintään 10 ja kokeen maksipisteet ovat 50. Yhteispistemäärä siis on 50+10=60.

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

RAM-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

Polynomiset palautukset

NP-täydellisyys

Kirjallisuutta

Harry R. Lewis & Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1998.

Bernard M. Moret: The Theory of Computation. Addison-Wesley, 1998.

Pekka Orponen: Laskennan teoria. Luentomoniste, 1994.

Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994

John E. Savage: Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1998.

Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Derick Wood: Theory of Computation, Harper & Row, 1987 (kurssikirjahyllyssä)

Linkkejä

Teoreettiseen tietojenkäsittelyyn liittyviä visualisointityökaluja

elomaa@cs.helsinki.fi