Laskennan mallit
Exam
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
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 |
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 |
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 |
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 |
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.
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:
- lecture on 7 September: pages 1–41 (introduction, mathematical background of which a large part is assumed as prerequisite, finite automata)
- lecture on 14 September: pages 41–47 (constructing finite automata, union of regular languages)
- lecture on 21 September: pages 47–63 (nondeterministic finite automata, equivalence of DFAs and NFAs, closure under regular operations)
- lecture on 28 September: pages 63–76 (regular expressions, equivalence of regular expressions and finite automata)
- lecture on 5 October: pages 77–82 and some extra material (nonregular languages)
- lecture on 12 October: pages 101–107 (context-free grammars)
- lecture on 3 November: pages 107–109 ambiguity, Chomsky normal form
- 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
- lecture on 16 November: pages 125–147 Pumping lemma for context-free languages, Turing machines (first part)
- lecture on 23 November: pages 147–159 end of Turing machines, (not Chapter 4.1), pages 175–184 halting problem
- lecture on 30 November: Chapter 7
Homework problems
- Homework 1 (6–10 September): problems; example solutions are available only in Finnish
- Homework 2 (13–17 September): problems
- Homework 3 (20–24 September): problems
- Homework 4 (27–30 September): problems
- Homework 5 (4–7 October): problems
- Homework 6 (11–14 October): problems
- Homework 7 (1–4 November): problems
- Homework 8 (8–11 November): problems
- Homework 9 (15–18 November): problems
- Homework 10 (22–25 November): problems
- Homework 11 (29 November–2 December): problems
- Homework 12 (7–9 December): 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.