Laskennan mallit

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.

Exam

16.12.2010 16.00 A111
Year Semester Date Period Language In charge
2010 autumn 07.09-07.12. 1-2 Finnish

Lectures

Time Room Lecturer Date
Tue 14-16 A111 Jyrki Kivinen 07.09.2010-12.10.2010
Tue 14-16 A111 Jyrki Kivinen 02.11.2010-07.12.2010

Exercise groups

Group: 1
Time Room Instructor Date Observe
Mon 12-14 CK111 Juha Kärkkäinen 06.09.2010—15.10.2010
Mon 12-14 CK111 Juha Kärkkäinen 01.11.2010—10.12.2010
Group: 2
Time Room Instructor Date Observe
Wed 14-16 BK107 Jyrki Kivinen 06.09.2010—15.10.2010
Wed 14-16 BK107 Jyrki Kivinen 01.11.2010—10.12.2010
Group: 3
Time Room Instructor Date Observe
Thu 10-12 C222 Esa Junttila 06.09.2010—15.10.2010
Thu 10-12 B119 Esa Junttila 01.11.2010—10.12.2010
Group: 4
Time Room Instructor Date Observe
Thu 14-16 B222 Jyrki Kivinen 06.09.2010—15.10.2010
Thu 14-16 B222 Jyrki Kivinen 01.11.2010—10.12.2010
Group: 5
Time Room Instructor Date Observe
Thu 16-18 C220 Jyrki Kivinen 06.09.2010—15.10.2010 in English
Wed 16-18 C220 Jyrki Kivinen 01.11.2010—10.12.2010 in English

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

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

Information for international students

The meeting time for the English-speaking exercise group has been changed to Wednesdays at 16:15-18:00 in room C220.

General

Jyrki Kivinen will be away from the department for about three weeks beginning 3 November.  During his absence, Patrik Floréen will be the lecturer of the course.

Completing the course

First course exam:

The feedback session is Wed 10 November at 13.00-14.00 in room A307.

Literature and material

Lecture notes about the game version of pumping lemma.

Students are expected to have the text book

  • Michael Sipser: Introduction to the Theory of Computation. Second edition (international), Thomson Course Technology 2006.

The older edition of the text book is mostly sufficient, but there may be some problems as the new edition includes e.g. new problems and example solutions.

Lectures

The lecture notes are available only in Finnish.

The lectures so far have covered roughly the following parts of the textbook:

  1. lecture on 7 September: pages 1–41 (introduction, mathematical background of which a large part is assumed as prerequisite, finite automata)
  2. lecture on 14 September: pages 41–47 (constructing finite automata, union of regular languages)
  3. lecture on 21 September: pages 47–63 (nondeterministic finite automata, equivalence of DFAs and NFAs, closure under regular operations)
  4. lecture on 28 September: pages 63–76 (regular expressions, equivalence of regular expressions and finite automata)
  5. lecture on 5 October: pages 77–82 and some extra material (nonregular languages)
  6. lecture on 12 October: pages 101–107 (context-free grammars)
  7. lecture on 3 November: pages 107–109 ambiguity, Chomsky normal form
  8. lecture on 9 November: pages 109–125 (not Lemma 2.27; i.e., pages 121–124 upper part) Chomsky normal form, CYK algorithm (p. 266–267), pushdown automata
  9. lecture on 16 November: pages 125–147 Pumping lemma for context-free languages, Turing machines (first part)
  10. lecture on 23 November: pages 147–159 end of Turing machines, (not Chapter 4.1), pages 175–184 halting problem
  11. lecture on 30 November: Chapter 7

 

 

Homework problems

Additional readings

There are several other good books that cover the topics of the course. If you wish to have some supplementary readings, for example the following are recommended.

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2007 (3rd ed.).
  • Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall 1998 (2nd ed.).
  • Thomas A. Sudkamp: Languages and Machines: An Introduction to the Theory of Computer Science. Pearson 2006 (3rd ed.).
  • Efim Kinber, Carl Smith: Theory of Computing: A Gentle Introduction. Prentice-Hall 2001.