581330-2
OHJELMOINNIN JA LASKENNAN PERUSMALLIT (2 ov)

Leht. Tapio Elomaa

Kevät 2000, 19.1.-24.2.

Luennot: ke, to 10-12 Auditorio
Laskarit: katso opetusohjelmasta harjoitusryhmien ajat.
Koe: ke 8. 3. 2000 klo 16-20:

A-M: Päärakennus, sali I (suuri luentosali)

N-S: Porthania, PII (S alkuiset valitsevat Porthanian ja Metsätalon välillä)

S-Ö: Metsätalo, sali 1 (S alkuiset valitsevat Porthanian ja Metsätalon välillä)

Koealue: kurssin kaikki asiat, laskuharjoituksissa käsitellyistä asioista voi tulla kysymyksiä (Orponen, luvut 1-3.7)

koetehtävät, osallistui 331 (kurssilla osanottajia 434, ilmoittautuneita 563).

Mallivastauksia ja arvosteluperusteita: teht. 1, teht. 2, teht. 3, teht. 4, teht. 5

Ajankohtaista

Kokeet on arvosteltu, pisteet ovat nähtävissä cum laude approbatur -ilmoitustaululla (5.4.2000).

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

Yleistä

Cum laude approbaturin pakollinen kurssi pääaineopiskelijoille ja valinnainen sivuaineopiskelijoille. Korvaa yhdessä kurssin laskennan teoria (3 ov) kanssa vanhojen tutkintovaatimusten mukaisen kurssin laskennan teoria (4 ov).

Kurssimateriaalina käytetään Pekka Orposen luentomonistetta Laskennan teoria, jota myy monistemyynti.

Esitiedot

Matematiikkaa on syytä osata.

Muodot

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

Laskuharjoitukset

Laskuharjoitukset ovat oleellinen osa kurssia. Ne ovat pakolliset. Tehtävien tekemisestä saa lisäpisteitä seuraavasti: 18 tehtyä tehtävää = 1 lisäpiste, 20 teht. = 2 p., 22 teht. = 3 p., 24 teht. = 4 p., 26 teht. = 5 p. ja 28 teht. = 6 p. Pakollisuus tarkoittaa, että vähintään joka toisella kerralla on oltava läsnä, joka puolestaan tarkoittaa sitä, että ainakin puolet tehtävistä on tehty (5/2=2).

Laskuharjoitus 1 (24.-28.1.): Tehtävät 2, 3(a), 4(a), 5, 6(b) ja 8 Orposen monisteesta. Exercises in english
Laskuharjoitus 2 (1.-4.2.): Tehtävät 10, 11, 15, 16, 18 ja 20 Orposen onisteesta. Exercises in english
Laskuharjoitus 3 (7.-11.2.): Tehtävät 22, 24, 27, 29, 31 ja 33 Orposen monisteesta. Exercises in english
Laskuharjoitus 4 (14.-18.2.): Tehtävät 34, 36, 38, 41, 43 ja 46 Orposen monisteesta. Exercises in english
Laskuharjoitus 5 (21.-25.2.): Tehtävät 48, 52, 55, 57, 59 ja 61 Orposen monisteesta. Exercises in english are available upon request from the lecturer
Laskuharjoitus 6 (28.2.-3.3.): Tehtävä 1: kurssikysely sekä lisäksi tehtävät 68, 71, 72, 75 ja 78 Orposen monisteesta.

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

attribuuttikieliopit

CYK-algoritmi

pinoautomaatit

5. Turingin kone

Kirjallisuutta

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

Pekka Orponen: Laskennan teoria. Luentomoniste, 1994.

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

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

Linkkejä

58133-2 Laskennan teoria

elomaa@cs.helsinki.fi