582208 LASKENNAN VAATIVUUS, 2. periodi, kevät 2007

Sivua muutettu viimeksi 1.3. 2007

Yleistä

Laskennan vaativuus on aineopintojen ja syventävien opintojen välimaastoon sijoittuva 4 op:n (2 ov:n) valinnainen kurssi, joka on on pakollinen niille, jotka valitsevat algoritmilinjan erikoistumissuunnakseen. Toisaalta se on myös hyödyllinen kaikille, jotka joutuvat opinnoissaan tai työssään käsittelemään vaativia algoritmisia ongelmia.

Esitietoina oletetaan kurssit Tietorakenteet ja Laskennan mallit.

Luennot ja harjoitukset

Luentoajat 14.3. - 27.4. 2007 ke, pe 10-12 CK112. Luennoitsija Timo Karvi.

Kurssi suoritetaan osallistumalla kurssikokeeseen ja harjoituksiin. Harjoituksista saatavat lisäpisteet riippuvat kurssin osanottajamäärästä. Jos osallistujia ei ole kovin paljon, harjoitukset jätetään kirjallisina harjoitusassistentille, joka tarkastaa vastaukset ja pisteyttää ne. Tässä tapauksessa harjoituksista voi saada puolet kaikista pisteistä (30/60, kokeesta maksimissaan samat 30). Mikäli taas osanottajia on niin paljon, ettei harjoitusten kattava tarkastaminen ole mahdollista, harjoituksista saa 10 pistettä ja kokeesta 50. Maksimipisteet harjoituksista saa ratkaisemalla 80 prosenttia kaikista tehtävistä. Tässä vaiheessa näyttää siltä, että noudatetaan tätä jälkimmäistä periaatetta.

Kurssiin liittyviä erilliskokeita järjestetään yksi kesällä, kaksi syksyllä ja vielä yksi seuraavan kevään alkupuolella. Näissä ei harjoituksia oteta huomioon.

Materiaali

Luentokalvot ovat saatavissa verkosta tältä sivulta. Tavoitteena on, että luennot ovat saatavissa hyvissä ajoin ennen luentoa.

Oppikirjana on Michael Sipser: Introduction to the Theory of Computation, Second (International) Edition, Thomson Course Technology, 2006.

Kirjasta käydään läpi seuraavat luvut:

• 3.2. Nondeterministic Turing Machines
• 7. Time Complexity
• 8. Space Complexity (ainakin 8.1., 8.2, 8.3)
• Mahdollisesti 9. Intractability ja
• 10.2. Probabilistic Algorithms.

Tavoitteena on,että kurssi seuraisi oppikirjaa melko tarkasti. Pieniä eroja saattaa tulla joissakin todistusten kohdissa. Tällöin opiskelija voi ratkaista, kummasta esityksestä, kirjan vai luentojen, asia parhaiten selviää.

• Luentokalvot, osa I, pdf-muodossa.
• Luentokalvot, osa II, pdf-muodossa.
• Luentokalvot, osa III, pdf-muodossa, uusi versio.
• Luentokalvot, osa IV, pdf-muodossa, uusi versio.
• Luentokalvot, osa V, pdf-muodossa, uusi versio.
• Luentokalvot, osa VI, pdf-muodossa, uusi versio.

Huomattakoon, että kalvot kannattaa tulostaa siten, että kaksi kalvoa tulee samalle sivulle. Tämä onnistuu helposti ainakin laitoksen Linuxissa Acrobat-ohjelmiston avulla (tulostuksessa optio Page Scaling = Multiple pages per sheet).

Ajankohtaista

• Yhteenvetokalvot, joista näkyy kokeeseen tuleva asia ja pisteytys.

• Toivomuksena on ollut, että harjoitusten selityssessio pidetään kuitenkin. Tämän johdosta harjoitustilaisuuksia jatketaan siten, että ensi viikolla 3.4. harjoitustilaisuus pidetään normaalin suunnitelman mukaan, mutta harjoituksissa käsitellään edellisellä viikolla jätetyt ja arvostellut harjoitukset. Edelleen siis harjoitukset jätetään kirjallisena ja ne arvostellaan. Selitystilaisuuteen ei ole pakko tulla.

• Koska osanottajamäärä ei ole kovin suuri, harjoitukset jätetään kirjallisena, joko sähköpostitse Harri Forsgrenille keskiviikkoon mennessä tai tuomalla keskiviikon luennolle. Harjoitusten tehtävät arvostellaan skaalalla 0-6 ja harjoituksista voi saada lisäpisteitä maksimissaan 25. Arvostellut harjoitukset voi noutaa luennoilta, harjoitustilaisuuksia ei ole.

• Pääsiäisloma 5.4.-11.4., jolloin ei ole luentoja eikä harjoituksia.

Korjauksia luentoihin ja harjoituksiin

1. Luentomateriaalit III, IV, V, VI on korjattu ja korjatut versiot on laitettu tälle kotisivulle. Korjaukset näkyvät alla.
2. (26.4.2007) Luentomateriaalissa VI on korjattu seuraavaa:
   • s.18: Kiinalainen jäännöslause on muotoiltu uudelleen.
   • s.20: Kohta 4: rs --> qr, s --> q.
   • s.21: Kohta 5: d1t mod t --> d1t mod p
   • s.29: Kohta 2: Sigman alaindeksi muutettu (aidoksi) piiksi.
   • s.29: Kohta 3: Sulkumerkki lisätty.

3. (26.4.2007) Luentomateriaalissa V on korjattu seuraavaa:
   • s.11: Viimeinen kohta: Perustelua on laajennettu.

4. (26.4.2007) Luentomateriaalissa IV on korjattu seuraavaa:
   • s.1: kieletn --> kielten
   • s.3: nolia --> nollia
   • s.5: konen --> koneen
   • s.7: Kohta 2: Lause on muotoiltu uudelleen.
   • s.16: Kohta 2: NP-täydellinen --> NL-täydellinen
   • s.16: Kohta 4: myöhenmmin --> myöhemmin
   • s.17: Kohta 2: arvtaan --> arvataan
   • s.17: Viimeinen kohta: positivinen --> positiivinen

5. (26.4.2007) Luentomateriaalissa III on korjattu seuraavaa:
   • s.11: Lisätty määritelmään "polynomisessa ajassa".
   • s.13: Kaavan phi kvanttorien yhteyteen lisätty x ja y.
   • s.19: Lause: Formula-Game on PSPACE-täydellinen.

6. (4.4.2007) Luentomateriaalissa II on korjattu seuraavat paino- ym virheet:
   • s.4: Polynomisen palautuksen merkinälle on esitelty vaihtoehtoinen merkintä.
   • s.22: G1:n kaavaan jälkimmäiseen osaan on lisätty ehdoksi k'/=k.
   • s.27: Kaavassa G'6 termi h[t,j] on muutettu muotoon h[t,i].
   • s.34: Määritelmässä literaalit a on muutettu alfoiksi.
   • s.36: Jälkimmäisessä G6''':n kaavassa konjunktiot on vaihdettu disjunktioiksi. Kaavoja on myös yksinkertaistettu merkinnällisesti.
   • s.37: Kaavoja on yksinkertaistettu merkinnällisesti.
   • s.38: Todistuksen toisessa kohdassa palautetaan tietysti CSAT 3SAT:iin, ei NP:tä.
   • s.39: Sivun lopussa tj:n ehtoa on muutettu.
   • s.40: Toisen kohdan perustelua on kirjoitettu selkeämpään muotoon.
   • s.46: Puhutaan särmistä eikä kaarista.
   • s.62: Sivun ensimmäinen jos-sana on jätetty pois.
   • s.64: Puhutaan tekijöistä eikä termeistä.

   Uuden version materiaalista II saa tästä. Siinä on myös sivuja yhdistetty.

7. Luentomateriaali, osa I, s. 15; toinen kappale pitäisi olla muodossa: Yksinauhaisella koneella ei tulosta voi enää parantaa. Itse asiassa voidaan osoittaa, että mikä tahansa kieli, joka voidaan tunnistaa yksinauhaisella Turingin koneella ajassa o(n log n), on säännöllinen.

   (Siis ison O:n tilalla pieni o; f(n)=o(g(n)), jos on olemassa sellainen vakio c, että f(n) on aidosti pienempi kuin c g(n) jostakin n:n arvosta alkaen. )

8. Luentomateriaali, osa I, s. 34: Viimeisessä kappaleessa y:n pitäisi olla b.

Harjoitukset

1. Harjoitus 1, 20.3.2007, ps- ja pdf-muodossa. Ratkaisut.
2. Harjoitus 2, 27.3.2007, pdf-muodossa. Ratkaisut.
3. Harjoitus 3, 13.4.2007, pdf-muodossa. Ratkaisut.
4. Harjoitus 4, 20.4.2007, pdf-muodossa. Ratkaisut.
5. Harjoitus 5, 30.4.2007, pdf-muodossa. Ratkaisut.

Harjoitusryhmät

Löytyvät laitoksen opetusohjelmasta.