581336-0 LASKENNAN TEORIA (3 ov)

Leht. Tapio Elomaa

Laskuharjoitusassistentit: Matti Kääriäinen ja Taneli Mielikäinen

Kevät 2000, 1.3.-27.4.

Luennot: ke, to 10-12 Auditorio
Laskarit: ke 8-10 (TM) ja 12-14 (TE), to 8-10 (MK), 12-14 (MK) ja 14-16 (TM)
Välikoe: pe 12.5. klo 16-20 Porthania PI

koetehtävät; osallistui 81 (kurssilla osanottajia 137, ilmoittautuneita 198)

mallivastauksia ja arvosteluperusteita: teht. 1, teht. 2, teht. 3, teht. 4.

Ajankohtaista

Koealue: Kaikki kurssilla käsitellyt asiat; s.o. luvut 4-7 Orposen monisteesta sekä RAM-kone

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

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.

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.

Laskuharjoitus 1 (8.-9. 3.): tehtävät 81, 82, 85 ja 86 Orposen monisteesta.
Laskuharjoitus 2 (15.-16. 3.): tehtävät 88, 89, 90, 93 ja 94 Orposen monisteesta.
Laskuharjoitus 3 (22.-23.3.) vastauksia
Laskuharjoitus 4 (29.-30. 3.): tehtävät 95, 97, 101, 102, 104 ja 106 Orposen monisteesta.
Laskuharjoitus 5 (5.-6. 4.): tehtävät 107-110 Orposen monisteesta.
Laskuharjoitus 6 (12.-13. 4.): tehtävät 112, 114-117 Orposen monisteesta.
Laskuharjoitus 7 (19. ja 27. 4.): tehtävät 118-122, 124 Orposen monisteesta.
Laskuharjoitus 8 (3. ja 4. 5.): tehtävät 126, 128, 129 ja 131 Orposen monisteesta ja kurssikysely.

Sisältö

1. Laskennan universaaleja malleja

Turingin koneet

Turingin koneiden laajennuksia

RAM-koneet

2. Kieliopeista

Rajoittamattomat kieliopit

Kontekstiset kieliopit

Chomskyn kielihierarkia

3. Laskettavuusteoriaa

Rekursiivisten ja RE-kielten perusominaisuuksia

Turingin koneiden koodaus

Universaalit Turingin koneet

Pysähtymisongelma

Chomskyn kieliluokat

Ratkeamattomuustuloksia

Rekursiiviset funktiot

Rekursiiviset palautukset

4. 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