This is an introductory course on theoretical computer science. Subjects covered are: basic automata theory, basics of formal languages and of the theory of computability, the theoretical limits of computers.

General Information

• Registration by TOPI. You should register both to the lectures and to a tutorial group. One of the tutorial groups (Wed 15-16) will be held in English and the rest in Finnish. The registeration to groups will be opened after the first lecture.
• Lectures by Rauno Heinonen, on Tuesdays, 17-19, hall A.
• Tutorials

  Day	Time	Location
  Tue	12-13	Y228
  	13-14	Y228
  Wed	12-13	Y228
  	13-14	Y228
  	14-15	Y427B
  	15-16	Y427B	English
  Thu	16-17	U358
  	17-18	U358
  Fri	8-9	T2
  	9-10	T2
  	12-13	Y405
  	13-14	Y405
  	14-15	Y427A
  	15-16	Y427A

• The course consists of
  • lectures (2 h a week) held in Finnish
  • tutorials (1 hour a week)
  • an examination (next one on 9 May 2001, 9-12ABC)

  This year we experiment by awarding points from tutorial exercises. Tutorials have two kinds of exercises:

  • normal
  • demonstration
  If you do normal exercises and attend a tutorial session, you receive extra points for the examination. Demonstration exercises give no points but they contain larger examples and cover the course material more thoroughly than the normal exercises.

  There are a total of 33 normal exercises on the course (3 each week). The examination points are awarded using the following table:

  Exercise points	Bonus exam points
  5	1
  10	2
  15	3
  20	4
  25	5
  30	6

  However, it is not possible to change the grade from 0 to 1 with bonus points, so you have to get enough normal exam points to pass the course.

  Tutorial exercises(The papers are also available from a rack outside room TB336):

  • 1. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 2. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 3. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 4. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 5. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 6. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 7. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 8. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 9. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 10. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)
  • 11. tehtävät (pdf) ratkaisut (pdf) exercises (pdf) solutions (pdf)

  Tutorial results.

• Newsgroup: opinnot.tik.tkt

Material

• Textbook: H. Lewis and C. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1998, 351 p. The first edition of the book (1981) can also be used but second edition is significally better on some subjects.
• Lecture Notes (opetusmonisteet)
  • Questions from tutorials and answers to the demonstration exercises.
  • Slides for the lectures
  • Lecture notes can be ordered from Otatieto (opetusmonisteet).
  • Some of the material will be available also on this web page. Please avoid unnecessary printing of this material to save printers, paper and thus nature !!!
• Other:
  • A short introduction to set theory and relations (pdf) (in Finnish) that covers the chapters 1.1--1.6 of the course book.
  • An example on determinising a finite-state automatom (pdf). (in Finnish)
• Examination requirements (suomeksi)
• Mallitentti (pdf) vastaukset (pdf) A sample examination (pdf) solutions