581330-2 Ohjelmoinnin ja laskennan perusmallit (2 ov)

Prof. Tapio Elomaa

Kevät 2001, 4. - 30. 5., kaikki tilaisuudet salissa A217

pe 4.5. luennot 15.00-17.30 (3 h), la 5.5. luennot 10.15-13.30 (4 h)
pe 11/18.5. luennot 15.00-17.30 (3 h), harjoitukset 17.45-19.15 (2 h)
la 12/19.5. luennot 10.15-13.30 (4 h)
pe 25.5. luennot 15.00-17.30 (3 h), harjoitukset 17.45-19.15 (2 h)
ke 30.5. harjoitukset 16.15-17.45 (2 h)

Koe pe 8. 6. klo 14-18 PI

Ajankohtaista

Vastauksia laskuharjoitusten 4 tehtäviin sama PDF muodossa
Vastauksia laskuharjoitusten 3 tehtäviin sama PDF muodossa

Viikon 4 luentokalvot sama PDF muodossa (25. 5.)
Viikon 3 luentokalvot sama PDF muodossa (18.-19. 5.)
Viikon 2 luentokalvot sama PDF muodossa (11.-12. 5.)
Viikon 1 luentokalvot sama PDF muodossa (4.-5. 5.)

Myös jonotuslistalla olevat opiskelijat saavat näillä näkymin osallistua kurssille.

Yleistä

Kurssilla on neljät laskuharjoitukset (6 tehtävää kussakin). Laskuharjoituksia tekemällä voi saada korkeintaan 10 lisäpistettä (11 tehtyä tehtävää = 1 piste, 12 tehtävää = 2 pistettä, ..., 20 tehtävää = 10 pistettä). Kokeen maksimipistemäärä on 50.

Tämä luentokurssi on tarkoitettu muuntokoulutettaville. He saavat kurssilla etusijan kaikissa asioissa.

Esitiedot

Riittävät matemaattiset valmiudet. Mitään tiettyä osa-aluetta ei erityisesti vaadita, mutta kurssilla käsitellään formaaleja asioita. Hyvä koulumatematiikan osaaminen riittää.

Muodot

Laskuharjoitukset

Laskuharjoitus 1 sama PDF muodossa (11. 5.)
Laskuharjoitus 2 sama PDF muodossa (18. 5.)
Laskuharjoitus 3 sama PDF muodossa (25. 5.)
Laskuharjoitus 4 sama PDF muodossa (30. 5.)

Sisältö

1. Automaatit

2. Laskennalliset ongelmat

laskennalliset ongelmat

tapaukset

merkkijonot

kielet ja ratkeavuus

3. Äärelliset automaatit ja säännölliset kielet

automaatin käsitteen formalisointi

automaattien minimointi

epädeterministiset automaatit

säännölliset lausekkeet

pumppauslemma

4. Kielioppien jäsentäminen

merkkijonojen tuottaminen

kontekstittomat kieliopit

rekursiivisesti etenevä jäsentäminen

CYK-algoritmi

pinoautomaatit

5. Laskennan universaaleista malleista: RAM-koneet

Kirjallisuutta

Kurssi perustuu oleellisesti Pekka Orposen luentomonisteen "Laskennan teoria" alkuosaan (ss. 1-60). Monisteessa käsiteltyjen asioiden lisäksi kurssilla käsitellään muitakin asioita. Monistetta ei enää ole saatavissa monistemyynnistä.

John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001 (kurssikirjahyllyssä)

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

elomaa@cs.helsinki.fi