|
T-79.148 Introduction to Theoretical Computer Science (2 cr)
Autumn 2004
This introductory course on the theory of computation covers
the basic aspects of finite automata and regular languages,
context-free grammars and pushdown automata, Turing machines
and computability theory.
[Current]
[General]
[Lectures]
[Tutorials]
[Exams]
[Material]
[Feedback]
[Links]
Previous years:
[Spring 2004]
[Autumn 2003]
[Spring 2003]
[Autumn 2002]
[Spring 2002]
[Spring 2001]
[Spring 2000]
[Spring 1999]
[Spring 1998]
-
Please provide feedback on the course via the DCSE department's
course feedback system. Filling in the feedback form is
rewarded by one bonus exam point, used to increase any passing
grade earned from the course.
The feedback system is open from 1 Dec to 22 Dec.
-
An additional review lecture for the course will be organised
on Tuesday, 7 December, from 8-10 a.m. in Lecture Hall T1.
-
Due to technical problems in the Regis system,
the bonus deadline for the computerised assignments has been moved
forward by a week. The new deadline is thus Friday, 26 November (11:59 p.m.)
-
The fourth and final set of compulsory computerised assignments was
generated on Fri 5 November. All problems in these four problem sets
must be correctly solved before the exam. By solving the problems
within the early deadline of 19 November, you earn two bonus exam points.
(For further information, see the computerised assignments
info page.)
- Recommended reading for Finnish students:
Ajankäyttötutkimuksen satoa eli miten saan ystäviä,
menestystä ja hyvän arvosanan tietojenkäsittelyteorian
perusteista by Harri Haanpää
(a statistical analysis of factors affecting course
performance in Spring 2004, in Finnish).
- The course consists of:
- lectures (2 h per week, in Finnish)
- tutorials (1 h per week, one group in English)
- an examination
- Registration for the course is by
TOPI.
You must register in
order to take the course, even if you were
not intending to attend the lectures or the
tutorials. (Registrations are needed for bookkeeping
purposes, specifically for generating your set of
computerised home assignments; see below.)
One of the tutorial groups (indicated below)
will be given in English and the rest in Finnish.
Registration for the tutorials opens
Mon 13 Sep at 9:00 and closes Fri 1 Oct at 16:00.
- In order to pass the course you have to:
- complete four compulsory sets of home assignments, and
- get a passing grade on the exam, as augmented by
credit earned from the tutorials.
The compulsory assignments are individually computer-generated
for each student, and are submitted over the network.
Completing these assignments is a
mandatory prerequisite
for participating in the exam.
For more details, see the computerised assignments
info page.
- Newsgroup:
opinnot.tik.tkt
Lectures by
Pekka Orponen
Thursdays 12 noon - 2 p.m. in Lecture Hall T1 of the Computer Science
building. First lecture on Thu 16 Sep.
The lectures are in Finnish, and the slides will appear here
after each lecture.
The contents will likely be very close to those from previous years,
e.g. Spring 2004.
English translations of the lecture slides from Spring 2004 are
available here.
Lecture schedule (tentative):
Week | Date | Topic |
Sipser | Lewis-Papadimitriou |
Lecture slides (in Finnish) |
38. | Sep 16 |
Administration. Review of basic math (functions, relations, induction). |
Pp. 1-13, 23-25 | 1.1-1.3, 1.5 |
PostScript PDF |
39. | Sep 23 |
Alphabets, strings and languages. Countable and uncountable sets. |
Pp. 13-14, 16, 161-164 | 1.4, 1.7 |
PostScript PDF |
40. | Sep 30 |
Finite automata. |
Pp. 31-43 | 2.1 |
PostScript PDF |
41. | Oct 7 |
Automata minimisation. Nondetermistic finite automata. |
Pp. 47-58, 275 | 2.2, 2.5 |
PostScript PDF |
42. | Oct 14 |
Regular expressions and finite automata. |
Pp. 58-76 | 1.8, 2.3 |
PostScript PDF |
43. | Oct 21 |
Nonregular languages and the "pumping lemma".
Context-free grammars and languages. |
Pp. 77-97 | 2.4, 3.1 |
PostScript PDF |
44. | Oct 28 |
Regular grammars. Parse trees and derivations.
Recursive-descent parsing of LL(1) grammars. |
Pp. 97-98 | 3.2, 3.7 (partly) |
PostScript PDF |
45. | Nov 4 |
Chomsky normal form and the
CYK parsing algorithm.
Pushdown automata. |
Pp. 98-114, 240-241 | 3.3, 3.4, 3.6 |
PostScript PDF |
46. | Nov 11 |
The context-free pumping ("uvwxy") lemma.
Turing machines. |
Pp. 115-135 | 3.5, 4.1 |
PostScript PDF |
47. | Nov 18 |
Multitrack and multitape Turing machines.
Nondeterministic Turing machines. |
Pp. 136-140 | 4.3, 4.5 |
PostScript PDF |
48. | Nov 25 |
Recursive and recursively enumerable languages.
Turing machine encoding and universal Turing machines. |
Pp. 142-145, 159-168 | 4.2, 5.1, 5.2, 5.7 |
PostScript PDF |
49. | Dec 2 |
The halting problem. Undecidability. Rice's theorem.
General and context-sensitive grammars.
Linear bounded automata. The Chomsky hierarchy. |
Pp. 171-174, 196 | 5.3, 5.4, 4.6 p. 271 |
PostScript PDF |
50. | Dec 7 |
Review and discussion of the course material.
Exam requirements.
Note exceptional time: Tue 8-10
(Lecture Hall T1).
|
Tutorials
The tutorials start the week after the first lecture. The last tutorials are on 7-8 Dec.
The Tuesday 16-17 tutorial is in English, the others are in Finnish.
Day | Time |
Location | Assistant |
Tue | 12-13 | Y228 | Emilia Oikarinen |
| 13-14 | Y228 | Emilia Oikarinen |
| 16-17 | Y405 | Tommi Syrjänen
in English |
| 17-18 | Y405 | Tommi Syrjänen |
Wed | 12-13 | Y313 | Antti Hyvärinen |
| 13-14 | Y313 | Antti Hyvärinen |
| 14-15 | U264 | Matti Järvisalo |
| 15-16 | U264 | Matti Järvisalo |
TOPI registration
for the tutorials opens
Mon 13 Sep at 9:00 and closes Fri 1 Oct at 16:00.
You must register in order to
take the course, even if you were not intending to
physically attend the tutorials. (Registrations are
needed for bookkeeping purposes, specifically for
generating your set of computerised home assignments;
see below.)
In the tutorials, there will be three home assignments and
two or three demonstration problems each week. The tutorials
are not compulsory, but bonus exam points (max 6) will be awarded
for doing the home assignments and marking them as done at the
tutorial sessions. The grading scheme for the home assignments
is as follows:
Problems solved | Bonus points |
5 | 1 |
10 | 2 |
15 | 3 |
20 | 4 |
25 | 5 |
30 | 6 |
The demonstration problems are likely to be 90% the same as
in the previous instalment of the course,
and are discussed at the tutorials to the extent that time permits.
In addition to the voluntary tutorials there are
four compulsory computer-generated "Regis" problem sets.
(See the info page.)
Tutorial problems: Electronic copies downloadable here
each week. Paper copies available at the
lectures, and from the rack outside the theory lab office
(TB336).
Solutions for the demonstration problems are provided here
as the course progresses.
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
- tehtävät (pdf)
ratkaisut (pdf)
problems (pdf)
solutions (pdf)
Tutorial
scores.
Validity of tutorial and Regis problems and their bonus points.
In general, exams for the course are scheduled for February,
May, August, October, and December of each year. As long as that
schedule holds:
-
The Regis problems generated in a given autumn / spring semester
will be valid until the Feb / Oct exam in the following semester.
-
Fully completed Regis assignments, and any bonus points earned
in a given autumn / spring semester will
be valid until the Oct / Feb exam in the following year.
Examinations and Grading
In general, exams for the course are scheduled for February,
May, August, October, and December of each year.
The main course exam in Autumn 2004 is
scheduled for Monday 20 December.
There is also an exam scheduled for Saturday 23 October,
intended mainly for students from previous instantiations
of the course.
To participate in an exam, you must first complete your
personal computer-aided Regis exercises. See the
exam requirements.
Remember also to register
for the exam.
Grading: Exam max 60 points, tutorials max 6 points.
Min passing grade approx. 30 points (tolerance 4 p),
highest grade (5) approx. 54 points.
In the case of "close call" failures (at most 2 points
below passing) despite serious study effort
(at least 4 tutorial bonus points), there is a possibility
of getting a passing grade by solving additional tutorial
problems. To discuss this option, please contact the
lecturer after the exam has been graded.
Bonus points earned from the tutorials are added directly
to the exam points, and may help to change the exam grade
from failing to passing. Bonus points earned from Regis
assignments completed on time (see the
info page) are
only added afterwards to a passing exam grade,
and may thus help to increase the grade, but not pass the
course. Note that the Regis assignments must
in any case be completed before the exam, and extra points
are awarded only for completion by the bonus deadline, which
in Autumn 2004 is 19 November.
Material
- Lecture Notes:
Typeset lecture notes (in Finnish) distributed by Edita.
- Textbook(s):
The recommended English textbook for the course is
M. Sipser, Introduction to the Theory of Computation
(PWS Publishing 1997).
The former recommended
text, H. Lewis and C. Papadimitriou,
Elements of the Theory of Computation
(Prentice Hall 1998) is being phased out.
Finnish students do not need to purchase the textbook,
since the course follows closely the lecture notes.
However the Sipser book is very reader-friendly
yet insightful, so reading it on the side will help
in following the course.
- Supporting material:
- Demonstration problems and their solutions from the tutorials.
Material from Spring 2004 is bundled together with the
lecture notes; updates available as the course progresses.
- Some of the material will be available also via this web page.
Please avoid unnecessary printing of this material
to save printers, paper and thus nature !!!
- A short introduction to set theory and relations
(by Tommi Syrjänen, in Finnish, ps/
pdf).
- An example on determinising a finite-state automaton
(by Heikki Tauriainen, in Finnish, ps/
pdf).
- An introduction to pumping lemmata and their uses
(by Tommi Syrjänen, in Finnish, ps/
pdf).
- Solutions for one old examination (25.10.2003), in Finnish,
ps/
pdf
- Examination requirements are available.
- Mallitentti vm 2001
(ps/
pdf),
vastaukset
(ps/
pdf).
A sample examination from 2001
(ps/
pdf).
- Tentti/exam 11.2.2002:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 8.5.2002:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 12.8.2002:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 28.10.2002:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 17.12.2002:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 3.2.2003:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 7.5.2003:
tehtävät
(pdf),
problems
(pdf),
tulokset/results.
- Tentti/exam 18.8.2003:
tehtävät
(pdf),
problems
(pdf).
tulokset/results.
- Tentti/exam 25.10.2003:
tehtävät
(pdf),
problems
(pdf).
tulokset/results
ratkaisut
(pdf).
- Tentti/exam 19.12.2003:
tehtävät
(pdf),
problems
(pdf).
tulokset/results.
- Tentti/exam 16.2.2004:
tehtävät
(pdf),
problems
(pdf).
tulokset/results.
- Tentti/exam 13.5.2004:
tehtävät (pdf),
problems (pdf).
tulokset/results.
- Tentti/exam 23.8.2004:
tehtävät (pdf),
problems (pdf).
tulokset/results.
- Tentti/exam 23.10.2004:
tehtävät (pdf),
problems (pdf).
tulokset/results.
- Tentti/exam 20.12.2004:
tehtävät (pdf),
problems (pdf).
tulokset/results.
Feedback
Please provide feedback on the course via the DCSE department's
course feedback system. Filling in the feedback form is
rewarded by one bonus exam point, used to increase any passing
grade earned from the course.
The feedback system is open from 1 Dec to 22 Dec.
Summaries of feedback from previous courses:
Autumn 2003
Spring 2003
Autumn 2002,
Spring 2002.
Links
Some fun links that are related to the course contents, but
not part of the official course material.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 07 January 2005.
Pekka Orponen
|