Models of Computation

Main themes and learning objectives »
This course requires prerequisites »
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.
Year Semester Date Period Language In charge
2011 autumn 05.09-05.12. 1-2 Finnish

Lectures

Time Room Lecturer Date
Mon 10-12 A111 Jyrki Kivinen 05.09.2011-10.10.2011
Mon 10-12 A111 Jyrki Kivinen 31.10.2011-05.12.2011

Exercise groups

Group: 1
Time Room Instructor Date Observe
Tue 10-12 C220 Jyrki Kivinen 05.09.2011—14.10.2011 in English
Tue 10-12 C220 Jyrki Kivinen 31.10.2011—09.12.2011 in English
Group: 2
Time Room Instructor Date Observe
Tue 16-18 B119 Antti Laaksonen 05.09.2011—14.10.2011
Tue 16-18 B119 Antti Laaksonen 31.10.2011—09.12.2011
Group: 3
Time Room Instructor Date Observe
Wed 10-12 B119 Jyrki Kivinen 05.09.2011—14.10.2011
Wed 10-12 B119 Jyrki Kivinen 31.10.2011—09.12.2011
Group: 4
Time Room Instructor Date Observe
Thu 16-18 B119 Antti Laaksonen 05.09.2011—14.10.2011
Thu 16-18 B119 Antti Laaksonen 31.10.2011—09.12.2011
Group: 5
Time Room Instructor Date Observe
Fri 14-16 B222 Antti Laaksonen 05.09.2011—14.10.2011
Fri 14-16 B222 Antti Laaksonen 31.10.2011—09.12.2011

Harjoitukset alkavat jo ensimmäisellä luentoviikolla. Esitietokoe perjantaina 2.9. klo 9-12 D122.

Non finnish students, contact the lecturer Jyrki Kivinen before hand.

Information for international students

 

 

Completing the course

The first course exam (20 October) covered the topics of Homeworks 1–6, which in practice means regular languages (Sipser pp. 1–98).

  • You can discuss the grading of your exam on Thursday, 10 November, at 11:15–12:00 in room A217.
  • Check list with exam results and home work credits for period 1.

The course consists of homework exercises and course exams.

The maximum score is 60 points.  The requirement for passing is about 30 points and for the highest grade about 50 points.

Homework gives a maximum of 12 points, which requires completing about 80% of homework.

There are two course exams. each giving 24 points.

Literature and material

Students are expected to have the text book

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

Lecture material

The lecture material is available only in Finnish.  Pages 1–38 (PDF / PS (4 slides/page))

Homework problems

  1. homework (6.–9.9.): problems
  2. homework (13.–16.9.): problems
  3. homework (20.–23.9.): problems
  4. homework (27.–30.9.): problems
  5. homework (4.–7.10.): problems
  6. homework (11.–14.10.): problems
  7. homework (1.–4.11.): problems
  8. homework (8.–11.11.): problems
  9. homework (15.–18.11.): problems
  10. homework (22.–25.11.): problems
  11. homework (29.11.–2.12.): problems
  12. homework (7.–9.12.): problems