Laskennan teoria (5 op) J175221

Kurssi on kandidaatin tutkinnon 3. vuoden kurssi ja edellyttää, että johdatus tietojenkäsittelytieteeseen, ohjelmointi ja diskreetit rakenteet on joko suoritettu tai kurssien asiat on muuten omaksuttu. Kurssi on tietojenkäsittelytieteen pääaineopiskelijalle pakollinen aineopintojen kurssi. Sivuaineopiskelija voi halutessaan suorittaa kurssin aineopintoihin (pakolliset aineopintojen kurssit J175211 Tietorakenteet ja algoritmit 1 (5 op) sekä J175212 Tiedonhallinta (5 op)).

Kurssilla tarvitaan matemaattisia tietoja, joten ennen kurssia voit kerrata näitä asioita Hämäläisen Wilhelmiinan tekemästä paperista.

Kurssin yleistiedot:

• kurssiin kuuluu luentoja 32 tuntia
• harjoituksia 16 tuntia

Kurssin sisältö:

• tutustuminen kolmeen laskennan malliin (äärellinen automaatti, pinoautomaatti ja Turingin kone)
• ongelman ratkeavuuden ja vaikeuden arviointi

Kirjallisuus:

• Hämäläinen Wilhelmiina: Hauskaa ja havainnollista laskennan teoriaa, luentomoniste 1.4.2008. Hämäläisen monistetta saa ostaa Epsilonilta. Viimeisin verkkoversio 1.4.2008
• Sipser, M: Introduction of teory of computation, Addison-Wesley, 2001
• Lewis, H.R. & Papadimitriou, C.H. Elements of the Theory of Computation, Second Edition, Prentice-Hall, 1998
• Hopcroft, J.E., Motwani, R., Ulman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001
• Kinber, E. & Smith, C. Theory of Computing. A Gentle Introduction. Prentice Hall, 2001

Opetus keväällä 2010

Ilmoitaudu kurssille webOodin kautta.

Luennot: 10.3.2010 - 6.5.2010 (Pirkko Voutilainen)

• keskiviikko klo 10 - 12 sali TD106
• torstai klo 10 - 12 sali TD106

Luentojen eteneminen täällä

Harjoitukset: 15.3.2010 - 10.5.2010

• Ryhmä 1: maanantai 10 - 12 sali T/B 180
• Ryhmä 2: maanantai 12 - 14 sali T/B 179

Harjoitustehtävät:

• Demo 1
• Demo 2
• Demo 3, demot klo 10-12 ja 14-16
• Demo 4
• Demo 5
• Demo 6
• Demo 7
• Demo 8

HUOM: Vähintään puolet demoista tehneet saavat demopistehyvitystä seuraavaan loppukuulusteluun (11.6.2010).

Kurssin voi suorittaa kahden kertauskuulustelun avulla, jos tekee ainakin kolmanneksen harjoituksista. Kurssin läpäisyyn vaaditaan 50% kurssin kokonaispistemäärästä. Harjoitustehtävistä saa kertauskuulusteluun lisäpisteitä, maksimissaan 10 % kurssin maksimipistemäärästä.

Kertauskuulustelut:

1. kertauskuulustelu: ti 20.4.2010 klo 8 - 10 sali M100
2. kertauskuulustelu: ti 11.5.2010 klo 8 - 10 sali TB106 tulokset (intra)

Muuta lisätietoa

• Kreikkalaiset kirjaimet

Loppukuulustelut

• perjantai 11.6.2010 klo 12 - 16 sali M101

Päivitetty viimeksi: 12.5.2010