Koti Yhteystiedot Laitos Henkilöt Opiskelu Hakeminen Tutkimus Uutiset ja tapahtumat

581330-2 Ohjelmoinnin ja laskennan perusmallit (2 ov)

Toukokuu 2004

Kurssin tulokset

Yleistä

OLPE-kurssi on tietojenkäsittelytieteen pääaineopiskelijoille pakollinen cum laude approbatur -kurssi ja sivuaineopiskelijoille valinnainen cum laude approbatur -kurssi. Kurssilla tutustutaan laskennallisten ongelmien abstraktin mallintamisen perusteisiin.

Tämä luentokurssi on tarkoitettu ensisijaisesti muuntokoulutettaville. He saavat kurssilla etusijan kaikissa asioissa.

Esitiedot

Riittävät matemaattiset valmiudet. Mitään tiettyä osa-aluetta ei erityisesti vaadita, mutta kurssilla käsitellään matemaattistyyppisiä asioita. Mikäli haluat virkistää muistiasi siitä, mitä ovat esimerkiksi funktiot ja relaatiot, joukot, numeroituvuus tai induktiotodistus, kannattaa ehdottomasti osallistua ensimmäiselle luennolle. Kurssin suoritusta tukevat kurssit Diskreetti matematiikka I ja Tietorakenteet.

Kurssin sisältö

1. Johdanto
   • Kurssin esittely
   • Laskennalliset ongelmat ja ratkeavuus
2. Säännölliset kielet ja äärelliset automaatit
   • Säännölliset lausekkeet ja kielet
   • Deterministiset äärelliset automaatit
   • Äärellisen automaatin minimointi
   • Epädeterministinen äärellinen automaatti
   • Automaatin determinisointi
   • Säännöllisten kielten rajoituksista: pumppauslemma
3. Kontekstittomat kielet ja pinoautomaatit
   • Kontekstittomat kieliopit ja kielet
   • Kieliopin jäsennysongelma
   • Rekursiivisesti etenevä jäsentäminen
   • CYK-jäsennys algoritmi
   • Pinoautomaatit
   • Kontekstittomien kielten rajoituksista
4. Johdanto laskennan vaativuusteoriaan
   • Rajoittamattomat kieliopit
   • Turingin koneet
   • Laskennallisten ongelmien ratkeavuus

Opetus (luennot ja laskarit)

• ma 3.5 16-20 A414 (luento, kalvot 1-29)
  
• ke 5.5 16-20 A414 (luento, kalvot 30-57)
  
• pe 7.5 16-19 A414 (laskari, tehtävät 5, 6, 7, 8, 10, 11, 12 ja 13
• pe 7.5 19-20 A414 (luento, kertausta)

• ma 10.5 16-20 A414 (luento, kalvot 58-82)
  
• ke 12.5 16-18 A414 (laskari, tehtävät 16, 17, 19, 20, 21 ja 22)
• ke 12.5 18-20 A414 (luento, kalvot 83-92)
  
• to 13.5 16-20 A414 (luento, kalvot 93-123)

• ma 17.5 16-19 A414 (laskari, tehtävät 24, 25, 26, 28, 30, 31 ja 38)
• ma 17.5 19-20 A414 (luento, kalvot 130-135)

• ma 24.5 16-20 A414 (luento, kalvot 136-177)
  
• ke 26.5 16-20 A414 (laskari, tehtävät 32, 33, 34, 35, 36, 37, 39, 40 ja 41)
• to 27.5 16-20 A414 (kertausta)

  luentokalvojen alkuosa postscriptina (pdf)
  luentokalvojen loppuosa postscriptina (pdf)

  laskaritehtäviä postscriptina (pdf)

• HUOM: monisteen sivut 125-129 eivät kuulu koealueeseen!

• kertauskalvot (pdf)
• 27.5. käsiteltävät kertaustehtävät (pdf)