Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

582206 Laskennan mallit (6 op), syksy 2008

Ajankohtaista

Annettava opetus

Luennot 2.9.-7.10. ja 28.10.-2.12. ti 14-16 A111 Jyrki Kivinen

Harjoitusryhmät ks. opetusohjelma.

Luennolla 9.9. pidetyn lähtötasotestin tulokset sekä tehtävät ja vastausehdotukset ovat saatavilla.

Kurssikokeet

  1. torstai 16.10. klo 9–12 salit A111 ja CK112
    • koealueena säännölliset kielet eli
      • luentokalvot 1–126 ja lisäkalvot
      • laskuharjoitukset 1–6
      • Sipser s. 1–98
    • koetehtävät PDF / PS
    • malliratkaisut PDF / PS
    • exam problems in English PDF / PS
    • tulokset
  2. torstai 11.12. klo 16–19 sali A111
    • koealueena periaatteessa kaikki luennoilla ja harjoituksissa käsitelty materiaali: kysymykset liittyvä asioihin, jotka eivät ollet 1. kokeessa, mutta kurssin alkupäästäkin voi tarvita joitain perusasioita
    • koetehtävät PDF / PS
    • Malliratkaisut PDF / PS
    • exam problems in English PDF / PS
    • tulokset

Koko kurssin tulokset.

Oppimistavoitteet (Muita yleisempiä asioita on esitelty kurssikuvauksessa.)

Oppimateriaali

Kurssi perustuu kirjaan

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

Saatavana koko kurssin luentokalvot eli sivut 1–305 PDF / PS (pienennetty).

Pumppauslemman soveltamisesta on kuusi lisäkalvoa.

Luentokalvoista korjattuja virheitä:

Suositeltavaa oheislukemista:

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.

Luentojen eteneminen

pvm aihe luentokalvot kirjan sivut (suunnilleen)
2.9. johdanto; äärellisten automaattien alkeet 1–29 1–3, 13–14 (strings), 31–37
9.9. äärellisten automaattien muodostaminen; joukko-operaatiot kielillä 30–46 37–45
16.9. säännöllisten kielten yhdiste; epädeterministiset äärelliset automaatit 47–73 45–56
23.9. epädeterministisen äärellisen automaatin muunnos deterministiseksi; säännöllisten kielten sulkeumaominaisuudet; säännölliset lausekkeet 74–93 57–69
30.9. NFA:n muuntaminen säännölliseksi lausekkeeksi; pumppauslemma 94–119 69–80
7.10. lisäesimerkkejä pumppauslemmasta; johdatus yhdeytettömiin kieliin 120–145 80–82, 101–107
28.10. kieliopin moniselitteisyys; Chomskyn normaalimuoto 146–160 107–110
4.11. CYK-algoritmi; pinoautomaatti 161–182 110–116; 266–267
11.11. pinoautomaattien ja yhteydettömien kielioppien yhteys; ei-yhteydettömiä kieliä 183–217 117–129 paitsi Lemman 2.27 todistus (s. 121–124)
18.11. Turingin koneet: perusversio, moninauhainen, epädeterministinen 218–245 (ja 246–251 nopeasti) 139–154
25.11. Churchin-Turingin teesi; universaalikieli; pysähtymisongelman ratkeamattomuus 246–272 155–161; 167; 175–183; 192–193
2.12. laskennan aikavaativuus; luokat P ja NP 273–305 183–184; pääkohdat sivuista 251–264, 266–277 ja 280

Harjoitukset

  1. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  2. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  3. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  4. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  5. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  6. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  7. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  8. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  9. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  10. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  11. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS
  12. tehtävät PDF / PS; problems in English PDF / PS; ratkaisut PDF / PS

Vapaaehtoiset lisätehtävät viimeisen luentokerran asioista PDF / PS (extra problems in English PDF / PS ); ratkaisut PDF / PS (solutions in English PDF / PS).


22. joulukuuta 2008 Jyrki Kivinen