581330-2 Ohjelmoinnin ja laskennan perusmallit, kevät 2005
If you don't understand Finnish, please visit the English homepage.
Sivua muutettu viimeksi Jun 10, 2005
Uutta
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.
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 (alustava) sisältö
-
Johdanto
- Kurssin esittely
- Laskennalliset ongelmat ja ratkeavuus
-
Säännölliset kielet ja äärelliset automaatit
- Deterministiset äärelliset automaatit
- Äärellisen automaatin minimointi
- Epädeterministinen äärellinen automaatti
- Automaatin determinisointi
- Säännölliset lausekkeet ja kielet
- Säännöllisten kielten rajoituksista: pumppauslemma
-
Kontekstittomat kielet ja pinoautomaatit
- Kontekstittomat kieliopit ja kielet
- Kieliopin jäsennysongelma
- Rekursiivisesti etenevä jäsentäminen
- CYK-jäsennys algoritmi
- Pinoautomaatit
- Kontekstittomien kielten rajoituksista
-
Johdanto laskennan teoriaan
- Rajoittamattomat kieliopit
- Turingin koneet
- Laskennallisten ongelmien ratkeavuus
Luennot 18.01.-24.02. ti, to 10-12 A111
Laskuharjoitukset
Kurssilla pidetään kuudet laskuharjoitukset ajalla 24.1.- 4.3. Tehtävät ilmestyvät tänne kurssin edistyessä. Katso ryhmien ajat opetusohjelmasta.
- Laskuharjoitus 1: tehtävät: ps pdf, mallivastaukset: ps pdf
- Laskuharjoitus 2: tehtävät: ps pdf, mallivastaukset: ps pdf
- Laskuharjoitus 3: tehtävät: ps pdf, mallivastaukset: ps pdf
- Laskuharjoitus 4: tehtävät: ps pdf, mallivastaukset: ps pdf
- Laskuharjoitus 5: tehtävät: ps pdf, mallivastaukset: ps pdf
- Laskuharjoitus 6: tehtävät: ps pdf, mallivastaukset: ps pdf
Kurssin suorittaminen
Kurssin suoritus koostuu kahdesta osasta: kurssikokeesta ja pakollisista harjoitustehtävistä (vähintään 1/3 tehtävistä tai 2/3 laskarikerroista läsnä):
- Kurssikoe enint. 54 p
- Laskuharjoitukset enint. 6 p
Kurssikoe järjestetään pe 11.3. klo 14-18 A111 ja B123 (Exactum).
Kurssin sisällön voi myös opiskella itsenäisesti ja osallistua erilliskokeeseen. Tällöin arvostelu perustuu pelkästään koepistemäärään.
Kirjallisuutta
Kurssi perustuu pääasiallisesti Pekka Orposen luentomonisteen "Laskennan teoria" alkuosaan (sivut 1-60). Monistetta saa laitoksen monistemyynnistä.
Kirjoja:
- John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001 (kirjaston kurssikirjahyllyssä, Laskennan teorian kurssikirja)
- Harry R. Lewis & Christos H. Papadimitriou: Elements of the Theory of Computation, Second Edition, Prentice-Hall, 1998 (kurssikirjahyllyssä, saa luettavaksi pyytämällä lainaamosta)
- Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997 (kurssikirjahyllyssä)
- Efim Kinber & Carl Smith: Theory of Computing. A Gentle Introduction. Prentice Hall, 2001 (kurssikirjahyllyssä)