582206 Laskennan mallit (6 op), syksy 2009

Kurssikuvaus
Oppimistavoitteet

Ajankohtaista

• Uusinta- ja erilliskokeen (22.01.2010) tulokset ovat valmistuneet.
• Kirjauslistasta (22.12.) voi tarkistaa laskuharjoitusten kirjaustilanteen. Listassa "LH" tarkoittaa perinteisiä harjoituksia (kerrat 1, 3, 5, 8, 10, 12), joista on kirjattu tehtyjen tehtävien määrä, "HT" tarkoittaa perus- ja yhteistehtäviä (kerrat 2, 4, 6, 7, 9 ja 11), joista on kirjattu läsnäolo, ja "KOE" tarkoittaa kurssikokeita, josta on kirjattu pisteet tehtävittäin: 1-3 on 1. koe ja 4-6 on 2. koe.
• Kirjauslistasta (29.10) voi tarkistaa laskuharjoitusten kirjaustilanteen. Listassa "LH" tarkoittaa perinteisiä harjoituksia (kerrat 1, 3 ja 5), joista on kirjattu tehtyjen tehtävien määrä, "HT" tarkoittaa perus- ja yhteistehtäviä (kerrat 2, 4, ja 6), joista on kirjattu läsnäolo, ja "KOE" tarkoittaa 1. kurssikoetta, josta on kirjattu pisteet tehtävittäin.
• Harjoituksista 7 alkaen harjoitusten rytmitys muuttuu siten, että parittomilla kerroilla on perus- ja yhteistehtäviä ja parilliset kerrat ovat perinteisen muotoiset laskuharjoitukset.
• Henkilökohtaista lisäohjausta 1. kurssikoetta varten on tarjolla ti 20.10. klo 12-14 salissa C220. Tule kysymään epäselväksi jääneita asioita esim. luennoilta tai laskareista.

Luennot

08.09.-13.10. ja 03.11.-08.12.
Ti 14-16 A111 Juha Kärkkäinen

Pvm	aihe	luentokalvot	kirjan sivut (suunnilleen)
08.09.	johdanto; äärellisten automaattien alkeet	1–32 [PDF] [PS](4/sivu) käsitelty s. 27 asti	1–3, 13–14 (strings), 31–40
15.09.	äärellisten automaattien muodostaminen; joukko-operaatiot kielillä, säännöllisten kielten yhdiste	25–56 (25–32 korvaa luennon 1 vastaavat sivut) [PDF] [PS](4/sivu) käsitelty s. 55 asti	41–47
22.09.	epädeterministiset äärelliset automaatit ja niiden muunnos deterministiseksi, säännöllisten kielten sulkeumaominaisuudet	57–88 [PDF] [PS](4/sivu) Käsitelty s. 85 asti. Lisätty korjaukset s. 64 ja s.82: Yhdistetyissä automaateissa oli ylimääräisiä hyväksyviä tiloja.	47–62
29.09.	säännölliset lausekkeet; säännöllisten lausekkeiden ja äärellisten automaattien ekvivalenssi	89–112 [PDF] [PS](4/sivu) Käsitelty s. 112 asti. Lisätty korjaus s. 95: Yhdiste muutettu leikkaukseksi.	63–76
06.10.	pumppauslemma; ei-säännöllisiä kieliä	113–144 [PDF] [PS](4/sivu) Käsitelty s. 131 asti.	77–82
13.10.	kertausta; johdanto yhteydettömiin kielioppeihin	Kertausta [PDF] [PS](4/sivu) 133–152 (133–144 korvaa vastaavat sivut luennolta 6.10.) [PDF] [PS](4/sivu) Käsitelty s. 151 asti. Lisätty korjaus s. 141: w muutettu u:ksi. Lisäksi jäsennyspuun määritelmää on laajennettu kattamaan myös lausejohdokset eikä vain lauseet.	101–107
03.11.	kieliopin moniselitteisyys; Chomskyn normaalimuoto	153–172 [PDF] [PS](4/sivu) Käsitelty s. 169 asti.	107–111
10.11.	CYK-algoritmi; pinoautomaatti	173–200 [PDF] [PS](4/sivu) Käsitelty s. 189 asti.	266–267, 111–116
17.11.	pinoautomaattien ja yhteydettömien kielioppien ekvivalenssi; ei-yhteydettömiä kieliä	201–224 [PDF] [PS](4/sivu) Käsitelty s. 224 asti. Lisätty korjaus s. 215: xyzuv muutettu uvxyz:ksi.	117–129 (ei Lemman 2.27 todistus, ss. 121–124)
24.11.	Turingin kone; moninauhainen Turingin kone	225–256 [PDF] [PS](4/sivu) Käsitelty s. 246 asti.	139–152
01.12.	epädeterministinen Turingin kone; Churchin-Turingin teesi; universaalikieli; pysähtymisongelman ratkeamattomuus	257–276 [PDF] [PS](4/sivu) Käsitelty s. 276 asti.	152–161, 167, 175–176, 181–184
08.12.	laskennan vaativuus; luokat P ja NP; lyhyt kertaus	277–307 [PDF] [PS](4/sivu)	251–264, 266–277, 280

Harjoitukset

08.09.-16.10. ja 02.11.-11.12.

1. Ti 16-18 B222 Antti Laaksonen
2. Ke 10-12 B222 Topi Musto
3. Ke 12-14 BK106 Topi Musto
4. Pe 14-16 CK111 Antti Laaksonen

Pvm	tehtävät	problems	ratkaisut
08.-11.09.	Tehtävät 1	Problems 1	Ratkaisut 1
15.-18.09.	Tehtävät 2	Problems 2	Ratkaisut 2
22.-25.09.	Tehtävät 3	Problems 3	Ratkaisut 3
29.09.-02.10.	Tehtävät 4	Problems 4	Ratkaisut 4
06.-09.10.	Tehtävät 5	Problems 5	Ratkaisut 5
13.-16.10.	Tehtävät 6	Problems 6	Ratkaisut 6
3.-6.11.	Tehtävät 7	Problems 7	Ratkaisut 7
10.-13.11.	Tehtävät 8	Problems 8	Ratkaisut 8
17.-20.11.	Tehtävät 9	Problems 9	Ratkaisut 9
24.-27.11.	Tehtävät 10	Problems 10	Ratkaisut 10
01.-04.12.	Tehtävät 11	Problems 11	Ratkaisut 11
08.-11.12.	Tehtävät 12	Problems 12	Ratkaisut 12
	Ylimääräisiä tehtäviä	Additional problems	Ratkaisut

Kokeet

Esitietokoe pe 04.09. klo 9-12 D122

• Korvaa puuttuvan Tietorakenteet-kurssin suorituksen.
• Vaadittavat esitiedot ks.Oppimistavoitteet

1. kurssikoe to 22.10. klo 9-12 A111

• Koealue:
  • luentokalvot 1–131 ja kertauskalvot
  • harjoitukset 1–6
  • Sipser, luvut 0 ja 1
• Henkilökohtaista lisäohjausta tarjolla ti 20.10. klo 12-14 salissa C220.
• Koetehtävät / Exam problems / Ratkaisut
• Tulokset
• Tehtävistä voi kysyä laskuharjoituksissa 3.-6.11. Oman kokeen arvosteluun voi tutustua ti 10.11. klo 13:15-14:00 salissa C220 (tai muulloin sopimuksen mukaan).

2. kurssikoe to 17.12. klo 16-19 A111

• Koealue:
  • kaikki luennoilla ja harjoituksissa käsitellyt asiat
  • kysymykset käsittelevät 1. kurssikokeen jälkeistä osuutta, mutta myös alkupään perustiedot voivat olla tarpeellisia
  • edellisvuosien kurssikokeet ovat hyvää harjoittelumateriaalia
• TKO-äly tarjoaa tukiopetusta ti 08.12. kello 16-20 luokassa CK111.
  Henkilökohtaista lisäohjausta luennoijan ja laskarinpitäjien toimesta on tarjolla ti 15.12 klo 12-14 salissa C220.
• Koetehtävät/Exam problems / Ratkaisut
• Tulokset
• Kokeen arvosteluun voi tutustua ke 20.01. klo 13:15-14:00 salissa A219 (tai muulloin sopimuksen mukaan).

Koko kurssin lopputulokset

Uusintakoe pe 22.01.2010 klo 16-20 A111

• Korvaa molemmat kurssikokeet. Laskuharjoituspisteet otetaan huomioon samoin kuin kurssikokeissa.
• Voidaan arvioida myös erilliskokeena, jolloin laskuharjoituspisteitä ei huomioida. Näiden kahden arvostelutavan antamista arvosanoista valitaan automaattisesti korkeampi.
• Koetehtävät / Ratkaisut
• Kokeen tulokset
• Arvosanat (Yht = max(KoeS+LhP+HtP, KoeS*1,25))
• Kokeen arvosteluun voi tutustua ma 22.02. klo 15:45-16:15 huoneessa B214 (tai muulloin sopimuksen mukaan).

Oppimateriaali

Kurssi perustuu kirjaan

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

Luentokalvot tulevat saataville kurssin kuluessa.

Suositeltavaa oheislukemistoa:

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

Myös kirjojen vanhemmat painokset ovat edelleen täysin käyttökelpoisia.

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

Ohjelma (alustava)

pvm	aihe
8.9.	johdanto; äärellisten automaattien alkeet
15.09.	äärellisten automaattien muodostaminen; joukko-operaatiot kielillä
22.09.	säännöllisten kielten yhdiste; epädeterministiset äärelliset automaatit
29.09.	epädeterministisen äärellisen automaatin muunnos deterministiseksi; säännöllisten kielten sulkeumaominaisuudet; säännölliset lausekkeet
06.10.	NFA:n muuntaminen säälliseksi lausekkeeksi; pumppauslemma
13.10.	lisäesimerkkejä pumppauslemmasta; johdatus yhdeytettömiin kieliin
03.11.	kieliopin moniselitteisyys; Chomskyn normaalimuoto
10.11.	CYK-algoritmi; pinoautomaatti
17.11.	pinoautomaattien ja yhteydettömien kielioppien yhteys; ei-yhteydettömiä kieliä
24.11.	Turingin koneet: perusversio, moninauhainen, epädeterministinen
01.12.	Churchin-Turingin teesi; universaalikieli; pysähtymisongelman ratkeamattomuus
08.12.	laskennan aikavaativuus; luokat P ja NP

---

Juha Kärkkäinen