582206 Laskennan mallit (6 op), syksy 2008

Ajankohtaista

• Tätä verkkosivua ei enää (luultavasti) päivitetä 22.12.2008 jälkeen. Jos sinulla on kysyttävä kurssista, ota yhteyttä luennoijaan. Jos olet valmistautumassa erilliskokeeseen, katso myös vanhoja erilliskokeita.
• Malliratkaisuihin (PDF / PS) on lisätty puutuneita arvosteluperusteita.
• Tämän syksyn laskuharjoituspisteet ovat voimassa seuraavassa Laskennan mallien erilliskokeessa ti 13.1. klo 16-20 A111, ja vain siinä.
• Toisen kokeen tehtäväkohtainen tuloslista, johon on korjattu palautetilaisuudessa ilmenneet virheet.
• Koko kurssin tulokset, joihin on korjattu palautetilaisuudessa ilmenneet virheet.
• Myös kirjauslistaan on korjattu palautetilaisuuteen mennessä ilmenneet virheet. Kirjausteknisistä syistä parillisnumeroiset laskuharjoituskerrat ovat erikseen kohdassa "HT". Kohdassa "LH 2" on toisella luennolla pidetystä lähtötasomittauksesta annetut lisäpisteet ja kohdassa "LH 4" ajankäytön seurannasta saadut lisäpisteet (5–9 palautettua lomaketta 1 piste, 10–15 lomaketta 2 pistettä).
• Vielä ehtii antaa kurssista palautetta! Tähaän mennessä (19.12.) vastanneita on 18, kiitos heille! Kaikki palaute otetaan kiitollisuudella vastaan ja luetaan huolellisesti, ja sitä käytetään opetuksen kehittämisessä, vaikka kaikkia ehdotuksia ei voida toteuttaa.

Annettava opetus

Luennot 2.9.-7.10. ja 28.10.-2.12. ti 14-16 A111 Jyrki Kivinen

Harjoitusryhmät ks. opetusohjelma.

Luennolla 9.9. pidetyn lähtötasotestin tulokset sekä tehtävät ja vastausehdotukset ovat saatavilla.

Kurssikokeet

1. torstai 16.10. klo 9–12 salit A111 ja CK112
   • koealueena säännölliset kielet eli
     • luentokalvot 1–126 ja lisäkalvot
     • laskuharjoitukset 1–6
     • Sipser s. 1–98
   • koetehtävät PDF / PS
   • malliratkaisut PDF / PS
   • exam problems in English PDF / PS
   • tulokset
2. torstai 11.12. klo 16–19 sali A111
   • koealueena periaatteessa kaikki luennoilla ja harjoituksissa käsitelty materiaali: kysymykset liittyvä asioihin, jotka eivät ollet 1. kokeessa, mutta kurssin alkupäästäkin voi tarvita joitain perusasioita
   • koetehtävät PDF / PS
   • Malliratkaisut PDF / PS
   • exam problems in English PDF / PS
   • tulokset

Koko kurssin tulokset.

Oppimistavoitteet (Muita yleisempiä asioita on esitelty kurssikuvauksessa.)

Oppimateriaali

Kurssi perustuu kirjaan

Michael Sipser: Introduction to the Theory of Computation. Second edition (international), Thomson Course Technology 2006.

Saatavana koko kurssin luentokalvot eli sivut 1–305 PDF / PS (pienennetty).

Pumppauslemman soveltamisesta on kuusi lisäkalvoa.

Luentokalvoista korjattuja virheitä:

• s. 71 viimeinen kappale: δ(r,a) oli virheellisesti δ(s,a)
• s. 80: N(...) oli virheellisesti N₁(...)
• s. 90: otsikossa piti olla säännölliset lausekkeet, ei säännölliset kielet
• s. 91: "abc"-automaatissa oli yksi hyväksyvä tila liikaa ja "b*"-automaatissa yksi liian vähän
• s. 208 s=a^pb^pc^p oli virheellisesti s=a^pb^bc^b
• s. 242 viimeisellä rivillä ''yksinauhaisella'' oli virheellisesti ''moninauhaisella''
• s. 281 lisätty puuttunut sulkumerkki
• s. 282 "Turigin" piti tietysti olla "Turingin"
• s. 288 algoritmin kohtaan 3 lisätty puuttunut testi

Suositeltavaa oheislukemista:

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2007 (3rd ed.).
• Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall 1998 (2nd ed.).
• Thomas A. Sudkamp: Languages and Machines: An Introduction to the Theory of Computer Science. Pearson 2006 (3rd ed.).
• Efim Kinber, Carl Smith: Theory of Computing: A Gentle Introduction. Prentice-Hall 2001.

Matemaattisten pohjatietojen kertaamiseen voi käyttää Heikki Junnilan materiaalia kurssille Johdatus diskreettiin matematiikkaan.

Luentojen eteneminen

pvm	aihe	luentokalvot	kirjan sivut (suunnilleen)
2.9.	johdanto; äärellisten automaattien alkeet	1–29	1–3, 13–14 (strings), 31–37
9.9.	äärellisten automaattien muodostaminen; joukko-operaatiot kielillä	30–46	37–45
16.9.	säännöllisten kielten yhdiste; epädeterministiset äärelliset automaatit	47–73	45–56
23.9.	epädeterministisen äärellisen automaatin muunnos deterministiseksi; säännöllisten kielten sulkeumaominaisuudet; säännölliset lausekkeet	74–93	57–69
30.9.	NFA:n muuntaminen säännölliseksi lausekkeeksi; pumppauslemma	94–119	69–80
7.10.	lisäesimerkkejä pumppauslemmasta; johdatus yhdeytettömiin kieliin	120–145	80–82, 101–107
28.10.	kieliopin moniselitteisyys; Chomskyn normaalimuoto	146–160	107–110
4.11.	CYK-algoritmi; pinoautomaatti	161–182	110–116; 266–267
11.11.	pinoautomaattien ja yhteydettömien kielioppien yhteys; ei-yhteydettömiä kieliä	183–217	117–129 paitsi Lemman 2.27 todistus (s. 121–124)
18.11.	Turingin koneet: perusversio, moninauhainen, epädeterministinen	218–245 (ja 246–251 nopeasti)	139–154
25.11.	Churchin-Turingin teesi; universaalikieli; pysähtymisongelman ratkeamattomuus	246–272	155–161; 167; 175–183; 192–193
2.12.	laskennan aikavaativuus; luokat P ja NP	273–305	183–184; pääkohdat sivuista 251–264, 266–277 ja 280

Harjoitukset

1. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
2. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
3. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
4. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
5. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
6. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
7. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
8. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
9. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
10. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
11. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
12. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS

Vapaaehtoiset lisätehtävät viimeisen luentokerran asioista PDF / PS (extra problems in English PDF / PS ); ratkaisut PDF / PS (solutions in English PDF / PS).

22. joulukuuta 2008 Jyrki Kivinen