Laskennan vaativuuden opintopiiri, syksy 2007

Yleistä

Opintopiiri on tarkoitettu niille, jotka aikovat suorittaa kurssin Laskennan vaativuus erilliskokeella. Opintopiiri on suunniteltu ensisijaisesti niille, jotka haluavat valmistua maisteriksi vanhan tutkintojärjestelmän mukaisesti ja joilta puuttuu vaadittu kurssi Laskennan teoria. Tämän vanhan kurssin voi siirtymäsääntöjen mukaan korvata uudella kurssilla Laskennan vaativuus.

Opintopiiri kestää noin kaksi kuukautta syyslukukaudella 2007; tapaamisia on 20.9.–16.11.2007. Työmäärää voi arvioida sen perusteella, että kurssin Laskennan vaativuus laajuus on 4 op (2 ov).

Opintopiiriin ei tarvitse erikseen ilmoittautua. Riittää, että tulet paikalle aloitustilaisuuteen. Jos et pääse aloitustilaisuuteen, voit ottaa yhteyttä ohjaajaan sähköpostitse. Jos opintopiiristä kiinnostuneita on enemmän kuin opetustiloihin mahtuu, ensisijalla ovat vanhan tutkintojärjestelmän mukaan opiskelevat.

Opintopiirin ohjaajana toimii Jukka Suomela. Ei säännöllisiä vastaanottoaikoja; opintopiiriin liittyvissä asioissa voi ottaa yhteyttä sähköpostitse.

Työmuodot

Opintopiirin tarkoituksena on tukea ja rytmittää itseopiskelua. Opintopiiri ei ole luentokurssi eivätkä opintopiirin tapaamiset korvaa itseopiskelua. Suoritusmerkintöjä ei anneta ja mitään pisteitä ei lasketa; kaikki on vapaaehtoista.

Opintopiirin työrytmi rakentuu laskuharjoitustehtävien ympärille. Aloitamme Laskennan mallien syksyn 2006 kurssin laskuharjoitustehtävällä 9.2 (aikataulussa "lama-s06") ja tämän jälkeen käymme järjestyksessä läpi Laskennan vaativuuden kevään 2007 kurssin laskuharjoitukset (aikataulussa "lava-k07").

Aikatauluun on merkitty kunkin tapaamisen kohdalle, mitä laskuharjoitustehtäviä käsitellään. Tarkoitus on, että ennen tapaamista osallistujat ovat opiskelleet kurssimateriaalista vastaavan asian ja vähintään yrittäneet ratkaista harjoitustehtävät.

Ohjatut tapaamiset: Ohjatuissa tapaamisissa kerrataan oppimateriaalista sellaisia kohtia, jotka ovat erityisen keskeisiä, ja käydään yhdessä läpi asioista, joita on koettu vaikeiksi. Tämän jälkeen keskitytään laskuharjoituksiin. Kaikkia harjoituksia ei käydä läpi, vaan keskitytään jälleen keskeisiin tai hankaliksi koettuihin harjoituksiin; loppuihin lava-k07-harjoituksiin on saatavilla mallivastaukset, joihin kukin voi itsenäisesti tutustua. Tarvittaessa voi tapaamisen jälkeenkin vielä kysyä ohjaajalta selvennystä, ja samoihin harjoituksiin voi palata seuraavassa ei-ohjatussa tapaamisessa.

Ennen ohjattua tapaamista: Lähetä viimeistään tapaamista edeltävänä päivänä ohjaajalle sähköpostia (kirjoita postin otsikkokentän alkuun "lava"). Kerro postissa, mitä oppimateriaalin kohtia ja mitä laskuharjoitustehtäviä toivoisit käsiteltävän tapaamisessa. Voit myös toivoa selvennystä esimerkiksi oppikirjan laskuharjoituksiin tai vanhoihin tenttitehtäviin. Kaikki kommentit opiskelun etenemisestä ovat tervetulleita. Oletusarvoisesti en vastaa näihin sähköposteihin erikseen, vaan käytän niitä kootusti tapaamisessa käsiteltävien asioiden valintaan.

Ei-ohjatut tapaamiset: Ohjattujen tapaamisten välillä opintopiiri kokoontuu itsenäisesti. Aikatauluun on merkitty alustavasti muutama ei-ohjattu tapaaminen, mutta osallistujat voivat halutessaan tavata useamminkin. Ei-ohjatuissa tapaamisissa osallistujat keskustelevat keskenään niistä asioista, jotka on oppimateriaalissa ja laskuharjoituksissa koettu vaikeiksi. Aikaa voi käyttää myös seuraavassa ohjatussa tapaamisessa käsiteltävien laskuharjoitusten tekemiseen ryhmätyönä, jos osallistujat kokevat tällaisen työskentelytavan hyväksi. Jos ei-ohjatussa tapaamisessa jäivät jotkin asiat epäselväksi, yksi ryhmän jäsen voi lähettää niistä kootusti sähköpostia ohjaajalle; näihin palataan tarvittaessa seuraavassa ohjatussa tapaamisessa.

Tarpeen mukaan näille web-sivuille kootaan selvennyksiä oppimateriaalin hankaliin kohtiin.

Aikataulu

Tämä on alustava aikataulu. Kulloinkin käsiteltävä asiakokonaisuus tarkentuu opintopiirin edetessä.

Alussa aikataulu on väljempi, jotta jää aikaa tutustua huolella peruskäsitteisiin ja palauttaa mieleen esitietoja aiemmilta kursseilta. Jos asia tuntuu helpolta, saa toki edetä itse nopeamminkin; tällöin ryhmätapaamiset tarjoavat mahdollisuuden kerrata asioita ja tarkentaa epäselväksi jääneitä kohtia.

Kaikki tapaamiset pidetään torstaisin klo 16.15–18.00 salissa C220. Ei-ohjatuissa tapaamisissa pyytäkää tarvittaessa esim. vahtimestaria avaamaan salin ovi.

to 20.9.
  • Aloitustilaisuus.
to 27.9.
  • Ei-ohjattu tapaaminen.
  • Harjoitustehtävät: lama-s06, 9.2.
  • Asioita: determinististen Turingin koneiden kertausta (Sipser 3.1).
to 4.10.
  • Ohjattu tapaaminen.
  • Harjoitustehtävät: lava-k07, 1.
  • Asioita: epädeterministinen Turingin kone (Sipser 3.2); luokka P (Sipser 7.1–7.2).
to 11.10.
  • Ei-ohjattu tapaaminen.
  • Harjoitustehtävät: lava-k07, 1–2.
  • Asioita: luokka NP (Sipser 7.3).
  • Lava-k07-luentojen osa I ulottuu suunnilleen tähän asti.
to 18.10.
  • Ohjattu tapaaminen.
  • Harjoitustehtävät: lava-k07, 2.
  • Asioita: polynominen palautus, NP-täydellisyys (Sipser 7.4).
to 25.10.
  • Väliviikko.
to 1.11.
  • Ohjattu tapaaminen.
  • Harjoitustehtävät: lava-k07, 3.
  • Asioita: NP-täydellisyys (Sipser 7.4–7.5).
  • Lava-k07-luentojen osa II ulottuu suunnilleen tähän asti.
to 8.11.
  • Ohjattu tapaaminen.
  • Harjoitustehtävät: lava-k07, 4.
  • Asioita: tilavaativuusluokat PSPACE, NPSPACE, L, NL (Sipser 8).
  • Lava-k07-luentojen osat III ja IV.
to 15.11.
  • Ohjattu tapaaminen.
  • Harjoitustehtävät: lava-k07, 5.
  • Asioita: taipumattomuus (Sipser 9); luokat BPP, RP (Sipser 10.2).
  • Lava-k07-luentojen osa V ja VI.
pe 23.11.
  • Kurssin Laskennan vaativuus erilliskoe, ks. syksyn 2007 erilliskokeet. Muista ilmoittautua tenttiin ajoissa!
  • Opintopiiri päättyy. Tällä viikolla ei ole enää ohjattuja tapaamisia, mutta ohjaajaa voi lähestyä sähköpostitse.

Oppimateriaali

Seuraamme lähinnä Laskennan vaativuuden kevään 2007 kurssin oppimateriaalia ja kurssilla käytettyä Sipserin oppikirjaa. Kirjasta on yksi kappale Kumpulan tiedekirjaston lukusalissa.

Useimmilla opintopiiriin osallistuneilla lienee pohjatietoina suoritettuna vanha kurssi Ohjelmoinnin ja laskennan perusmallit. Laskennan vaativuus olettaa pohjatietoina uudelta kurssilta Laskennan mallit joitain asioita, joita ei vanhalla kurssilla käsitelty. Tämän vuoksi voi olla hyvä aluksi tutustua Turingin koneiden peruskäsitteisiin esimerkiksi seuraavista lähteistä:

Opintopiirin vihjesivulla on kommentteja laskuharjoituksesta lama-s06 9.2.

Lisämateriaalia

Aloitustapaamisessa kaivattiin myös vaihtoehtoista oppimateriaalia. Tässä joitain esimerkkejä. Mitään näistä en suosittele ainoaksi oppimateriaaliksi, mutta näistä voi löytää hiukan erilaisen selityksen asioista; jonkin vaikean asian ymmärtämistä voi helpottaa, kun lukee siitä useamman eri selityksen.

Näistä kirjoista on ohjaajalla yksi kappale; voin tuoda näytille tapaamiseen 4.10.