Laskennan teoria (5 op/3 ov)

Ajankohtaista

Luentomonisteen korjatut sivut löytyvät täältä (mukana myös viereinen sivu, jotta korjaussivu on helppo liittää monisteeseen). Korjauslistasta selviää, mitä vikaa vanhoissa sivuissa oli.
s. 38-40 (samalla asia on selostettu hieman havainnollisemmin);
s. 74;
s. 163;
s. 181;
s. 218;
s. 239.
Seuraava loppukoe pe 3.8. klo 12-16 M2. Ilmoittautuminen weboodissa.
Kurssi on nyt arvosteltu! Toisen välikokeen arvostelukriteerit. Palautetilaisuus ke 30.5. 14.00-14.30 B179. Kurssin lopputulokset (sisältää koepisteet sekä harjoituspisteet). Jos jotain harjoituspisteitä tuntuu puuttuvan, otathan yhteyttä Mikkoon.
2. välikoe on pe 11.5. klo 12.00-15.00 2D106. Koealue kattaa kurssin loppuosan (CYK-algoritmista ja Chomskyn normaalimuodosta ratkeamattomiin ongelmiin). Hämäläisen monisteessa luvut 5.7-8.2, paitsi *:llä merkitty extra-aines. Jokainen saa laatia yhden a4:n henkilökohtaisen lunttilapun, joka palautetaan kokeen päätteeksi. Lunttilapun tulee olla itse laadittu!
1. välikoe on nyt arvosteltu. Saat tutustua kokeeseesi luennolla ti 8.5. ja harjoituksissa 9.-10.5. arvostelukriteerit. Koska koe meni aika huonosti (oli työläs?), jokainen yli 0p saanut saa työläyshyvitystä +5p! Parhaalle tulee siis yli maksimipisteet!
Kurssin työmäärän analyysi: kirjaathan ylös vappuviikolla 30.4.-6.5. Late-kurssiin käyttämäsi työajan. Kokonaissumma lähetetään lomakkeella viikon lopuksi. Tiistain luento jää pois, mutta meillä ei ole ollut oikein "normaaleja" viikkoja (lisäkommenteissa voit arvioida, miten luennon puute vaikutti loppusummaan). Tarkemmat ohjeet löytyvät lomakkeen alusta. Kiitos!
Extraharjoituspisteitä tarjolla! Pidetään bugien korjaustalkoot: jokaisesta monisteesta löytämästäsi uudesta pikkuvirheestä saat 1/2 p ja isommasta 1p. Tarkista ensin korjauslistasta, onko virhe jo huomattu. Pisteen saa virheen ekana keksinyt. Huom! Kirjoitusvirheistä pisteitä vain, jos muuttavat asian merkityksen.
Korjaus! Harj. 21 kissakielioppia ei saa LL(1):een (on LL(2)-kieli), ellemme muuta sääntöä U->Uu|epsilon muotoon U->Uu|u. Kiitos + extrapiste tarkkasilmäiselle opiskelijalle!
C-kielen syntaksi tekstitiedostona ja pdf:nä (sama kuin luennolla jaettu).
Vielä kerran korjattu sivu 74. Nyt tilasiirtymätaulukko oli oikein, mutta kuva ei vastannut sitä! Extrapiste keksijälle!
Kertausmateriaalia:
Kertauskalvot. Miumau-kielen kielioppi ja pinoautomaatti. Huom! Taulun pinoautomaatista puuttui "au"-osan käsittely! 5. harjoituskerran vastaukset.
Korjattu sivu 163. Jäsentimen funktiossa F, säännön F->(E) kohdalla yli yksi ylimääräinen next=getnext. Ohessa vielä jäsentimen simulaatio syötteellä "(3+2)*4-7". Kannattaa simuloida jäsennintä muillakin syötteillä, jotta opit rekursiivisen jäsennyksen idean!
1. välikoe on ma 23.4. klo 14.00-17.00 salissa 2D106. Koealue Hämäläisen monisteessa luvut 1-5.6 (rekursiivinen jäsennys on viimeinen kokeeseen tuleva asia) sekä näihin liittyvät harjoitustehtävät. Jokainen saa laatia yhden a4:n henkilökohtaisen lunttilapun, joka palautetaan kokeen päätteeksi. Lunttilapun tulee olla itse laadittu!
korjattu sivu 74. (Determinisoinnissa oli huolimattomuusvirhe, joka kostautui minimoinnissa! Jos teillä sattuu kokeessa samaa, ei se haittaa, vaan riittää, että jokainen askel on lähtökohtansa pohjalta oikein.)
Luennolla otetun C:n liukulukuautomaatin determinisointi ja minimointi.
Korjaus- ja täydennyslista luentomateriaaleihin. Jos huomaat materiaaleissa virheitä tai tarkennettavia asioita, kerrothan niistä! Lisään niitä listaan sitä mukaan. Samoin kaikki uudet hyvät esimerkit ovat tervetulleita!
Luentomonisteen saa ostaa Epsilonin kopilta, Metrian bunkkerista, sen aukioloaikoina (varmimmin ma, ti, ke 12.00-12.15).
Teethän lähtötasotestin! Se antaa sekä itsellesi että luennoijallesi hyvää palautetta, mitä kannattaa erityisesti kerrata. Jotta testistä olisi hyötyä, se tulee tehdä itsenäisesti. Tuloksella ei ole mitään vaikutusta arvosanaasi. Sen sijaan jokainen testin omalla nimellään tehnyt saa 2 laskuharjoituspistettä! Tee testi viimeistään 12.3. jos haluat pisteet!
Yhteenveto lähtätasotestin tuloksista

Luennot 6.3.-10.5. 2007

ti 16-18 ja to 14-16 2D106
Luennoija: Wilhelmiina Hämäläinen (ilman skandeja etunimi.sukunimi@cs.joensuu.fi)

Välikokeet

ma 23.4. 14.00-17.00 ja pe 11.5. 12.00-15.00

Laskuharjoitukset 14.3.->

Mikko Vinni
Ryhmä 1 ke 14-16 B180
Ryhmä 2 to 12-14 B180

Kaikki tehtävät löytyvät sekä luentomonisteesta että ohesta pdf:inä:

Harjoituksia johdantomateriaalista (luvut 2.8 (Kertaustehtäviä matematiikasta) ja 3.5 (Tehtäviä laskennallisista ongelmista))
Harjoituksia säännöllisistä kielistä (luku 4.9)
Harjoituksia kontekstittomista kielistä (luku 5.13)
Harjoituksia Turingin koneista (Luku "6.5" - lukunumero puuttuu monisteesta!)
Harjoituksia ratkeavuudesta ja ratkeamattomuudesta (Luku 7.10)

Viikko	Tehtävät
1 (14.-15.3.)	Luku 2.8: teht. 2 ja 4; Luku 3.5: teht. 1 ja 3; Luku 4.9: teht. 1
	(Viimeinen tehtävä ei edellyttä kotitöitä, vain aktiivista osallistumista itse session aikana.)
2 (21.-22.3.)	Luku 4.9: tehtävät 2,3,4,7,9,11
3 (28.-29.3.)	Luku 4.9: tehtävät 17,20,21,23,25,26
	Teht. 20c) on hieman hankala, mutta onnistuu helposti, kun luet luvun 4.6 Säännöllisten kielten sulkeumaominaisuuksista.
4 (4.4. ja 12.4.)	Luku 4.9: teht. 35, 38; Luku 5.13: teht. 1, 2, 3, 5
	Extratehtävä Luku 4.9 teht. 27 tuottaa 2 extrapistettä! Palauta ohjelmakoodi ja esimerkkitulosteita 12.4. mennessä
5 (18.-19.4.)	Luku 5.13: teht. 9, 11, 12, 15, 16, 20
6 (25.-26.4.)	Luku 5.13: teht. 21, 22, 23, 25, 28
	Lisätehtävä: Anna palautetta luentomonisteesta tähän mennessä.Kysymykset ohessa. 1 harjoituspiste vastaajille
7 (2.-3.5.)	Luku 5.13: teht. 30, 31, 32; Luku "6.5": 4, 5, 14
8 (9.-10.5.)	Luku 7.10: teht. 2, 7, 13, 15, 16, 19
	Lisätehtäviä (kukin 1 harjoituspiste): Täytä kurssikyselypalaute! Anna palautetta luentomonisteen loppuosasta. Huom! Piste edellyttää myös omaa esimerkkiä tms. Kysymykset ohessa. Analysoi kurssilla vaadittavat esitiedot. Kysymykset ohessa.

Esitiedot

Kurssilla tarvitaan matematiikan ja ohjelmoinnin perustaitoja. Matematiikan taitojesi riittävyydestä saat hyvän käsityksen suorittamalla alkutestin. 2005 aloittaneille Diskreetit rakenteet on pakollinen kurssi ja sen tulee olla suoritettuna ennen osallistumista Laskennan teoriaan. Aiemmin aloittaneillekin DR on suositeltava, mutta ei pakollinen. Mikäli et ole suorittanut Diskreetit rakenteet -kurssia, sinun on syytä kerrata tarvittavaa matematiikkaa ennen Laskennan teorian alkua oheisesta materiaalista (sama ps:nä).
Myös ohjelmointitaitoja tarvitaan jonkin verran. Harjoituksissa on jonkin verran ohjelmointitehtäviä ja tietysti sinun tulee ymmärtää materiaalin esimerkkitoteutukset. Erityisesti rekursio-käsitteen ymmärtäminen on tarpeellista monissa tehtävissä. Jokaisella tulee olla pakolliset Ohjelmointi-kurssit suoritettuna ennen Laskennan teoriaan osallistumista.

Kuvaus

Laskennanteoria jaetaan perinteisesti kahteen osaan:

Laskettavuuden teoria (Theory of computability), jossa tutkitaan ongelmien ratkeavuutta ja arvioidaan niiden vaikeutta ennen ratkaisualgoritmin laatimista.
Laskennan vaativuusteoria (Theory of computational complexity), jossa arvioidaan ongelman laskennallista tila- ja aikavaativuutta.

Tällä kurssilla käsittelemme vain laskettavuuden teoriaa, mutta kurssin päätteeksi voit tehdä vapaaehtoisen harjoitustyön laskennan vaativuusteoriasta.

Kurssilla saat hyvät eväät arvioida mitä tahansa ongelmia:

Onko ongelma luonteeltaan laskennallinen? Ts. voisiko sen edes periaatteessa ratkaista tietokoneella?
Jos ongelma on laskennallinen, niin onko se ratkeava? Ts. voiko sille laatia ratkaisuohjelman, joka pysähtyy aina kaikilla syötteillä?
Jos ongelma on ratkeava, niin kuinka vaikea se on? Ennen ratkaisualgoritmin laatimista voimme jo erottaa helpot ja nopeasti ratkaistavat ongelmat työläämmistä. Tällä kurssilla jaamme ongelmat Chomskyn hierakian mukaan kolmeen vaikeusluokkaan, joita vastaavat säännölliset kielet, kontekstittomat kielet ja rajoittamattomat kielet.
Jos ongelma on ratkeava ja sen vaikeus tunnetaan, niin miten se kannattaa ratkaista? Tämä kysymys menee osittain kurssin aihepiirin ulkopuolelle, mutta tulet oppimaan näppäriä ja tehokkaita menetelmiä tietyn tyyppisiin ongelmiin.

Ekskursioina kurssi esittelee myös joukon kiinnostavia käytännön sovelluksia formaaleille työkaluille, joihin tutustutaan (esim. hahmontunnistus, kääntäjät, kasvikieliopit). Laskennan teoria antaa myös hyvät eväät filosofisille pohdinnoille tietokoneiden luomasta maailmasta sekä ihmisen ja koneen kilpajuoksusta.

Kurssin suoritus

Opiskelijoiden toiveesta kurssi pidetään tänä vuonna perinteiseen tapaan! Kurssin suoritus koostuu laskuharjoituksista saatavista pisteistä ja välikoeiden pisteistä. Laskuharjoituksista voi saada maksimissaan 25% kokonaispisteistä.

Arvioitu työmäärä:
Viikottain 6 h kontaktiopetusta, yht. 48h
Harjoitustehtävien ratkaisu 6 h/vk, yht. 48 h
Teorian opiskelu 2h/vk, yht. 16 h
Kokeet + niihin valmistautuminen 10-20h
Yht. 122-132h
(5 op kurssin keskimääräisen työmäärän tulisi olla 5*26=130 h.)

Alustava ohjelma

Kerta	Pvm	Aihe
1	to 8.3.	Kurssin esittely. Mitä on laskennan teoria?
2	ti 13.3.	Äärelliset automaatit. Automaatin ohjelmatoteutus.
3	to 15.3.	Automaatin minimointi. Epädeterministiset automaatit.
4	ti 20.3.	Säännölliset lausekkeet, epsilon-automaatti.
5	to 22.3.	Automaatit <-> säännölliset lausekkeet.
6	ti 27.3.	Säännöllisten kielten rajoitukset, Pumppauslemma
7	to 29.3.	Kontekstittomat kielet ja kieliopit
8	ti 3.4.	Pinoautomaatit
-	to 5.4. ja ti 10.4.	PÄÄSIÄISLOMA
9	to 12.4.	Jäsennys
10	ti 17.4.	Rekursiiviset jäsentäjät
11	to 19.4.	Kertausluento
-	ma 23.4.	1. VÄLIKOE
12	ti 24.4.	Chomskyn normaalimuoto. CYK-algoritmi.
13	to 26.4.	Turingin koneet
-	ti 1.5.	VAPPULOMA
14	to 3.5.	Ratkeavuus; Universaalikieli ja -koneet
15	ti 8.5.	Ratkeamattomuus
16	to 10.5.	Kertausluento
-	pe 11.5.	2. VÄLIKOE

Kurssin lopuksi voit suorittaa vapaaehtoisen projektityön laskennan vaativuusteoriasta (2 op).

Kirjallisuus

Luentomoniste Hämäläinen, W.: Hauskaa ja havainnollista laskennanteoriaa. Rekursiosta. Tai Orponen, Pekka: Automaatit ja kieliopit. Tilauslista täytetään 1. luennolla!

Kurssilla ei ole yhtä virallista kurssikirjaa, mutta sen sijaan joukko suositeltavaa kirjallisuutta (ks. alla). Luentomoniste kattaa koko kurssin sisällön, mutta saattaa olla paikoin tiivis, joten kannattaa ehdottomasti käyttää tukena kirjoja. Luentomoniste sopii hyvin myös omien kattavien muistiinpanojesi rungoksi.

Sipser, M. Introduction to the Theory of Computation. (Hauskalukuinen, mielenkiintoisia esimerkkejä ja tehtäviä, mutta paikoin liian suppea.)
Hopcroft, J.E., Motwani, R., Ulman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001. (Varsin perusteellinen, mutta asioita selitetty turhankin pitkästi. Hopcroftin ja Ullmanin vanha painos on tiiviimpi, tosin hieman matemaattisempi.)
Kinber, E. & Smith, C. Theory of Computing. A Gentle Introduction. Prentice Hall, 2001. (Hyvin havainnollinen, kiltti johdatus aiheeseen :)
Lewis, H.R. & Papadimitriou, C.H. Elements of the Theory of Computation, Second Edition, Prentice-Hall, 1998. (Klassikko, pätevä ja perusteellinen, mutta ainakin 1. painos aika matemaattinen.)
Wood, D. Theory of Computation, Harper & Row, 1987.
Sudkamp, T.A. Languages and Machines. An Introduction to the Theory of Computer Science. (Hyvä käsikirja jos haluat tietää enemmän etkä pelkää matematiikkaa. Varsinkin rekursiiviset ja rekursiivisesti numeroituvat kielet selitetty hyvin, vaatimattomammat kielet löytyvät kauniimmin muista lähteistä.)