Laskennan mallit

582206
8
Algorithms and machine learning
Intermediate studies
Laskentaongelmien matemaattinen määrittely. Automaatit, formaalit kielet ja kieliopit. Algoritmikäsitteen formalisointi. Ratkeavuus. Esitiedot: Tietorakenteet-kurssin suoritus (tai esitietokoe). Huom: Kurssin harjoitukset alkavat jo ensimmäisellä luentoviikolla. Kurssikirja: Sipser M.: Introduction to the Theory of Computation (2nd ed.), Thomson Course Technology, 2006.

Exam

18.10.2012 09.00 A111
14.12.2012 16.00 A111
Year Semester Date Period Language In charge
2012 autumn 03.09-03.12. 1-2 Finnish Tomi Pasanen

Lectures

Time Room Lecturer Date
Mon 10-12 A111 Tomi Pasanen 03.09.2012-08.10.2012
Mon 10-12 A111 Tomi Pasanen 29.10.2012-03.12.2012

Exercise groups

Group: 1
Time Room Instructor Date Observe
Tue 10-12 B119 Tomi Pasanen 03.09.2012—12.10.2012 In English, if needed.
Tue 10-12 B119 Tomi Pasanen 29.10.2012—07.12.2012 In English, if needed.
Group: 2
Time Room Instructor Date Observe
Tue 16-18 B222 Jani Rahkola 03.09.2012—12.10.2012
Tue 16-18 B222 Jani Rahkola 29.10.2012—07.12.2012
Group: 3
Time Room Instructor Date Observe
Wed 10-12 B119 Tomi Pasanen 03.09.2012—12.10.2012
Wed 10-12 B119 Tomi Pasanen 29.10.2012—07.12.2012
Group: 4
Time Room Instructor Date Observe
Wed 16-18 B119 Juhana Laurinharju 03.09.2012—12.10.2012
Wed 16-18 D122 Juhana Laurinharju 29.10.2012—07.12.2012
Group: 5
Time Room Instructor Date Observe
Thu 14-16 B222 Juhana Laurinharju 03.09.2012—12.10.2012
Thu 14-16 B222 Juhana Laurinharju 29.10.2012—07.12.2012

Harjoitukset alkavat jo ensimmäisellä luentoviikolla. Esitietokoe perjantaina 31.8. klo 9-12 B222.

Non finnish students, contact the lecturer Tomi Pasanen before hand.

Completing the course

Kurssin voi suorittaa joko yhdellä erilliskokeella tai kahdella välikokeella (kurssikokeilla).

  • Erilliskokeessa arvosana perustuu suoraan kokeessa pärjäämiseen.
  • Välikoejärjestelyssä arvosanaan vaikuttaa huomattavasti kurssin aikana tehtyjen laskuharjoituksien määrä. Tehtyjen laskuharjoituksien määrä jaetaan kahdella ja tämä yhdistetään välikokeissa saatuihin pisteisiin (max 36 p.), minkä perusteella lasketaan lopulliset arvosana-asteikot. Välikoearvostelussa on käytössä myös ns. kurssikoeleikkuri, joka määrittää pistemäärän, mikä täytyy ainakin saada jos haluaa läpäistä kurssin. Leikkurin pistemäärä ilmoitetaan myöhemmin.

Kurssikoe

Koetulosten ja laskuharjoituspisteiden tarkistuslista täällä.

Tässä toisen koekeen jälkeen tulokset ja arvosanat.

Literature and material

 Opiskelijoilla oletetaan olevan käytössään kurssikirja

  • Sipser M.: Introduction to the Theory of Computation (2nd ed.), Thomson Course Technology, 2006.

Jyrki Kivisen erinomainen materiaali vuodelta 2011 on saatavana kokonaan eli sivut 1-302  (PDF / PS (4 kalvoa/arkki)).

Pohdintaa lauseesta, millä käsittellään merkkijonon toistuvuusominaisuutta eli pumppautuvuutta: viite 1 ja 2.

Pumppauslemmaopas (A5-versio). Oppaaseen liittyen järjestetään paja tiistaina 16.10. kello 12:00 - 16:00 luokassa B222.

Luennot

Periodi I

  • Kappale 1
  • Kappale 2
    • luentokalvot 1-42 (Jyrkin kalvot 130-178 ja 201-216; ei Lauseen 2.12 todistusta, pages in the course book 101-116 and 125-129; proof of Theorem 2.9 skipped)
    • luentokalvot 43-71 (Jyrkin kalvot 179-200; pages in the course book 117-124)

Periodi II

  • Kappale 3
  • Kappale 4
    • luentokalvot (Jyrkin kalvot 254-272;pages in the course book 167-184) 
  • Kappale 5
    • luentokalvot (Jyrkin kalvot 254-272;pages in the course book 191-196) 
  • Kappale 7 (ei koealuetta, not for an exam)
    • luentokalvot (Jyrkin kalvot 273-302;pages in the course book 251-287) 

 

Harjoitustehtävät

Periodi I

Periodi II