582206 Laskennan mallit (6 op), syksy 2006

(Pidetyt erilliskokeet)

• Kurssikyselyyn tuli 29 vastausta; kiitos palautteesta!
• Toisesta kurssikokeesta ei pidetä erillistä palautetilaisuutta, mutta kokeesta (tai kurssista yleensä) saa mielellään tulla keskustelemaan luennoijan vastaanottoaikoina (ti, to 12.15-12.45) tai sopimalla muun ajan sähköpostitse.
• Kurssi osoittautui aiottua vaikeammaksi. Jatkossa mietitään keinoja kohdistaa opetus ja kuulustelut paremmin kurssin ydinasioihin. (Muista antaa palautetta!) Tilapäisenä korjaustoimena kurssin pisterajoja on alennettu.

Opetus syksyllä 2006

(Yleisempiä asioita on esitelty kurssikuvauksessa.)

Luennot 7.9.-12.10. ja 2.11.-7.12. to 10-12 B123 Jyrki Kivinen

• luentomateriaali (sivut 1-241) PDF, PS

Kurssikokeet

1. to 19.10. klo 16-19
   • koealueena luentojen 1-5 ja harjoitusten 1-5 asiat (luentomoniste s. 1-92; Sipser s. 31-107 ja tarvittavat osat luvusta 0).
   • tehtävät PS, PDF
   • malliratkaisut PS, PDF
2. ma 11.12. klo 16-19 B123
   • tehtävät PS, PDF
   • malliratkaisut PS, PDF
   • Tehtävät 1, 2 ja 5 arvosteli Jyrki Kivinen, tehtät 3 ja 4 Sampo Yrjänäinen.
   • kurssin lopputulokset

Harjoitusryhmät 11.9.-12.10. ja 30.10.-7.12.

1. ma 10-12 Jyrki Kivinen B119
2. ke 16-18 Sampo Yrjänäinen B119
3. to 8-10 Jyrki Kivinen B119
4. to 16-18 Sampo Yrjänäinen CK111

Harjoitustehtävät ja ratkaisut:

1. tehtävät PDF, PS; ratkaisut PDF, PS
2. tehtävät PDF, PS; ratkaisut PDF, PS
3. tehtävät PDF, PS; ratkaisut PDF, PS
4. tehtävät PDF, PS; ratkaisut PDF, PS
5. tehtävät PDF, PS; ratkaisut PDF, PS
6. tehtävät PDF, PS; ratkaisut PDF, PS
7. tehtävät PDF, PS; ratkaisut PDF, PS
8. tehtävät PDF, PS; ratkaisut PDF, PS
9. tehtävät PDF, PS; ratkaisut PDF, PS
10. tehtävät PDF, PS; ratkaisut PDF, PS
11. tehtävät PDF, PS; ratkaisut PDF, PS

Dana Angluinin ohje tärkeimmistä todistustekniikoista

Alustava aikataulu

Alla oleva kalvojen jako eri tiedostoihin ei tällä hetkellä täysin osu yhteen pidettyjen luentojen eikä ilmoitettujen kurssikirjan sivujen kanssa.

• Viikko 36
  • luento 1: hallintoa, yleiskatsaus kurssin alueeseen, esitietojen kertaus; äärellisten automaattien perusteet [Sipser s. 31-43]; kalvot PDF, PS
  • ei harjoituksia
• Viikko 37
  • luento 2: säännöllisten kielten yhdiste, epädeterministiset automaatit [Sipser s. 44-54; kalvot PDF, PS]; determinististen ja epädeterminististen automaattien ekvivalenssi [Sipser s. 54-58; kalvot PDF, PS];
  • harjoitus 1: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 38
  • luento 3: säännöllisten kielten sulkeumaominaisuudet, säännölliset lausekkeet [Sipser s. 58-66]; kalvot PDF, PS
  • harjoitus 2: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 39
  • luento 4: säännöllisten lausekkeiden ja äärellisten automaattien ekvivalenssi [Sipser s. 66-76]; kalvot PDF, PS
  • harjoitus 3: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 40
  • luento 5: ei-säännöllisiä kieliä [Sipser s. 77-82]; kalvot PDF, PS
  • harjoitus 4: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 41
  • luento 6: yhteydettömät (eli kontekstittomat) kieliopit, niiden moniselitteisyys ja normaalimuodot [Sipser s. 101-111]; kalvot PDF, PS
  • harjoitus 5: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 42:
  • 1. kurssikoe torstaina 19.10 kello 16-19: tehtävät PS, PDF; malliratkaisut PS, PDF
• Viikko 43: väliviikko, ei opetusta
• Viikko 44
  • luento 7: jäsentäminen ja pinoautomaatit (kalvot PDF, PS); pinoautomaattien ekvivalenssi yhteydettömien kielioppien kanssa (I) (kalvot PDF, PS) [Sipser s. 111-120]
  • harjoitus 6: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 45
  • luento 8: pinoautomaattien ja yhteydettömien kielioppien ekvivalenssi (II); yhteydettömien kielioppien rajoitukset (kalvot PDF, PS); [Sipser s. 121-129]
  • harjoitus 7: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 46
  • luento 9: Turingin kone ja sen muunnelmat (I) (kalvot PDF, PS); [Sipser s. 139-152]
  • harjoitus 8: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 47
  • luento 10: Turingin koneen muunnelmat (II); algoritmikäsitteen formalisointi ja ratkeavuus; esimerkkejä kieliteoriasta (kalvot PDF, PS); [Sipser s. 152-161, 167-174]
  • harjoitus 9: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 48
  • luento 11: ratkeamattomuus, erityisesti pysähtymisongelma (kalvot PDF, PS); [Sipser s. 175-184]
  • harjoitus 10: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 49
  • luento 12: lisää ratkeamattomia ongelmia (kalvot PDF, PS); [Sipser s. 191-214 osittain]; yhteenveto (kalvot PDF, PS);
  • harjoitus 11: tehtävät PDF, PS; ratkaisut PDF, PS
• Viikko 50: 2. kurssikoe maanantaina 11.12. kello 16-19

---

1. maaliskuuta 2007 Jyrki Kivinen