Yliopiston etusivulle Suomeksi Inte på svenska No english version available
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

582206 Laskennan mallit (6 op), syksy 2007

Ajankohtaista:

  • Seuraava Laskennan mallien erilliskoe on jo 11.1. ja toimii samalla tämän luentokurssin uusintakuulusteluna: syksyn laskuharjoituspisteet ovat voimassa tässä ja vain tässä erilliskokeessa (mikäli parantavat arvosanaa). (21.12.2007)
  • Toisen kokeen palautetilaisuus pidetään pe 11.1. klo 12.00-13.00 salissa A218. (21.12.2007)
  • Kurssipalautetta ehtii vielä antaa. Tähän mennessä vastauksia on tullut 35; kiitos vastanneille! (20.12.2007)
  • Kurssin lopputulokset löytyvät laitoksen intranetistä opiskelijanumeron mukaan.
  • Toinen kurssikoe on tarkastettu. Malliratkaisuihin (PS/PDF) on lisätty lyhyt selvitys arvosteluperusteista. Palautetilaisuus pidetään 11.1.2008 klo 12.00-13.00 myöhemmin ilmoitettavassa salissa. (20.12.2007)
  • Tarkastuslistaan on kirjattu myös esitietotesti ("LH 7", maksimi 4 pistettä) ja osallistuminen työajanseurantaan ("LH 8", maksimi 2 pistettä). (18.12.2007)
  • Isto Havun pro gradu -tutkielma, jossa tarkasteltiin tämän kurssin opiskelijoiden ajankättöä, on valmistunut: tiivistelmä, koko gradu (11.12.2007)
  • Toinen kurssikoe: tehtävät PS/PDF, in English PS/PDF; ratkaisuja PS/PDF (10.12.2007)
  • Voit katsoa tarkastuslistasta laskuharjoituskirjauksesi. Tässä vaiheessa kaikki varsinaiset laskuharjoitukset pitäisi olla kirjattuna. Lähipäivinä kirjataan myös esitietotestistä ja työaikaseurannasta tulevat lisäsuoritukset. Lukuohje: LH 1-6 on yksilölaskareissa (1, 3, 5, ..., 11) merkatut tehtävät ja HT 1-6 osallistumiset ryhmälaskareihin (2, 4, 6, ..., 12). Kurssikyselyyn vastaaminen on kirjattu sarakkeeseen "LH 6", josta maksimi siis on 5 tehtävää. (7.12.2007)
  • Saatavana kaikki luentokalvot eli sivut 1-294: PDF / PS (neljä sivua arkilla) (3.12.2007)

(Yleisempiä asioita on esitelty kurssikuvauksessa.)

Luennot 4.9.-9.10. ja 30.10.-4.12. ti 14-16 A111 Jyrki Kivinen

Harjoitusryhmät 3.9.-12.10. ja 29.10.-7.12.

  1. ti 12-14 B119 Jouni Siren
  2. ti 16-18 B222 Jyrki Kivinen
  3. ke 16-18 CK111 Jouni Siren
  4. pe 12-14 CK107 Jyrki Kivinen

Kurssikokeet:

  1. to 18.10. klo 9-12 A111
  2. ma 10.12. klo 9-12 B123

Harjoitustehtävät:

  1. harjoitus (4.-7.9.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  2. harjoitus (11.-14.9.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  3. harjoitus (18.-21.9.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  4. harjoitus (25.-28.9.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  5. harjoitus (2.-5.10.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  6. harjoitus (9.-12.10.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  7. harjoitus (30.10.-2.11.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  8. harjoitus (6.-9.11.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  9. harjoitus (13.-16.11.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  10. harjoitus (20.-23.11.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  11. harjoitus (27.-30.11.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)
  12. harjoitus (4.-7.12.): tehtävät PDF, PS, ratkaisut PDF, PS (in English: problems PDF, PS)

Opetuksen kehittämistä varten pyritään mm. muodostamaan kuva kurssin todellisesta kuormittavuudesta seuraamalla opiskelijoiden ajankäyttöä. Tätä varten pyydämme ystävällisesti, että pidät kirjaa työajastasi ja palautat viikoittain seurantalomakkeen paperilla laskuharjoitustilaisuudessa (jolloin saat uuden tyhjän lomakkeen) tai sähköpostitse suoraan Nina Aremolle. Merkitse lomakkeeseen myös, minkä viikon tiedot siinä on (esim. 24.-30.9. on viikko 39). Osallistumisesta ajankäytön seurantaan koko kurssin ajan hyvitetään kahden laskuharjoitustehtävän verran.

Luennoilla esitettävät kalvot tulevat tänne nähtäville, mutta ne on tarkoitettu vain helpottamaan luentojen seuraamista eivätkä korvaa kurssikirjaa. Kalvot ilmestyvät viimeistään päivää ennen luentoja, mutta niihin saattaa toisinaan tulla muutoksia ja korjauksia vielä vähän ennen luentoa. Luennon jälkeen tehdyistä korjauksista tulee tieto tälle sivulle.

Kalvoista saatavilla sivut 1-294: PDF / PS (neljä sivua arkilla).

Kalvoihin tulleita korjauksia:

  • sivulla 26 kaava δ(ri,wi+1) oli virheellisesti q(...) [korjattu 14.9.]
  • sivun 96 esimerkkiautomaatista puuttui siirtymä tilasta qst tilaan qacc [korjattu 4.10.]
  • sivulla 103 algoritmin oletuksessa oli virheellisesti ''M=(G,...)'', kun piti olla ''G=(Q,...)'' [korjattu 4.10.]
  • sivulla 109 algoritmin kohdassa 1 oli virheellisesti ''k2 tilaa'', kun pitää olla ''k+2 tilaa'' [korjattu 4.10.]
  • sivun 152 pseudokoodista korjattu luennolla havaittu virhe [korjattu 6.11.]
  • sivun 184 pinon sisällöstä korjattu luennolla havaittu virhe [korjattu 14.11.]
  • sivulla 224 oli viittaus vääräälle sivulle [korjattu 21.11.]
  • sivulla 266 kielen D määritelmässä oli virheellisiä merkintöjä [korjattu 28.11.]

Luentojen eteneminen (viittaukset kirjan sivuihin ohjeellisia):

4.9. kalvot 1-22; Sipser s. 1-3, 13-14, 31-34
11.9. kalvot 23-36; Sipser s. 35-43
18.9. kalvot 37-65; Sipser s. 44-54
25.9. kalvot 66-88; Sipser s. 54-66
2.10. kalvot 89-110; Sipser s. 66-77
9.10. kalvot 111-124; Sipser s. 77-82
30.10. kalvot 125-148; Sipser s. 101-108
6.11. kalvot 149-173; Sipser s. 108-111, 266-267 (''Proof idea'' ja ''Proof'', joissa on esitetty CYK-algoritmi)
13.11. kalvot 174-189, 201-208 (kalvoista 190-200 vain varsinainen tulos eli lemma 2.28); Sipser s. 111-121, 124-129 (ei Lemman 2.27 todistusta)
20.11. kalvot 209-239; Sipser s. 125-129, 139-152
27.11. kalvot 240-245, 249-269; Sipser s. 152-154, 155-161, 167, 175-183, 192-193
4.12. kalvot 270-294; Sipser s. 183-184, 168-175

Kurssi perustuu kirjaan

Michael Sipser: Introduction to the Theory of Computation. Second edition (international), Thomson Course Technology 2006.
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.
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.

21. joulukuuta 2007 Jyrki Kivinen

 
Palaute laitokselle | Tiedekunnan etusivulle | Yliopiston etusivulle