OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Prof. Tapio Elomaa, Asst.prof. Henri Hansen, Asst. Timo Aho

Fall 2011, periods I ja II

Lectures:

• P I Aug. 30 - Oct. 13: Tue 14-16 and Thu 14-16 TB220
• P II Oct. 25 - Dec. 8: Tue 14-16 and Thu 14-16 TB220

Weekly exercises: M.Sc. Teemu Heinimäki, Fri 10-12 TC210

Course exam: Thu Dec. 15, 2011, 9 - 12 AM

News

• The remaining lectures will be given by Ph.D. Henri Hansen.

General Information

Course main page.

Mandatory prerequisites are a course on discrete mathematics (MAT-20600 Diskreetti matematiikka) and a course on algorithm analysis (OHJ-2150 Algoritmien analyysi).

The course can be included in post-graduate studies. It is compulsory course in the advanced studies within computer science.

The course offers an introduction to the fundamental possibilities of programming and computation - which problems can be solved in principle by computing and, additionally, which problems can be solved efficiently. What can be done if the problem needing solution cannot be solved efficiently using computers.

Lectures

The lectures of Fall 2011 are based on the book

• Michael Sipser: Introduction to the Theory of Computation, Second (International) ed., Thomson, 2006.

Course exams are based on lectures and not solely on the lecture slides.

Week	Dates	Slides	Exercises	Chapters in the Book
1	Aug. 31	1 - 11	n/a	Course Organization
2	Sept. 6 & 8	12 - 35	n/a	0, 1.1
3	Sept. 13 & 15	36 - 73	Sept. 23	1.2-1.3
4	Sept. 20 & 22	74 - 104	Sept. 30	1.4-2.1
5	Sept. 27 & 29	105 - 135	Oct. 10	2.2-3.2
6	Oct. 4	136 - 151	Oct. 14	3.3 + unrestricted grammars
7	Oct. 11 & 13	152 - 184	Oct. 28	4 + universal TMs
8	Oct. 25 & 27	185 - 218	Nov. 4	5.1, 5.3
9	Nov. 1 & 3	219 - 242	Nov. 11	5.3, 6.4
10	Nov. 8 & 10	243 - 269	Nov. 18	7.1-7.2
11	Nov. 15 & 17	270 - 297	Nov. 26	7.3-7.5
12	Nov. 22 & 24	298 - 323	Dec. 2	8
13	Nov. 29 & Dec. 1	324 - 370	--	10.1-10.2

Weekly Exercises

• Weekly exercises yield extra points.
• Attending the weekly exercises and solving the exercises independently is an almost necessary prerequisite for passing the course.
• For the exercise questions see above, the Lectures section.

Contents

0. Introduction
   
   • Computational Problems
   • Reppresentations
   • Decision Problems
   • Decidability of Computational Problems
1. Recap
   • Finite Automata
   • Minimizing Automata
   • Nondeterministic Finite Automata
   • Regular Expressions
   • Restrictions of Regular Languages
2. Context-Free Grammars
   
   • Ambiguity
   • Chomsky Normal Form
   • Pushdown Automata
3. Universal Models of Computation
   • Turinging Machines
     Variants: Multitape TMs, Nondeterministic TMs
   • Grammars
   • Algorithms
4. Computability Theory
   • Basic Properties of Decidable and Turing-Recognizable Languages
   • Coding Turing Machines
   • Decidable Problems
   • Infinite Sets
   • Universal Turing Machines
   • The Halting Problem
   • Chomsky Hierarchy
5. Reducibility
   
   • TMs Recognizing an Empty Language
   • TMs Recognizing a Regular Language
   • Rice's Theorem
   • Linear Bounded Automata
   • Mapping Reducibility
6. Advanced Topics in Computability Theory
   
   • A Definition of Information
   • Kolmogorov Complexity
   • Optimality of the Definition
   • Incompressible Strings and Randomness
7. Time Complexity
   • Asymptotic Analysis
   • The Class P
   • The Class NP
   • NP-completeness
8. Space Complexity
   • Savitch's Theorem
   • PSPACE-completeness
   • The Classes L and NL
9. Approximation
10. Randomized Algorithms

Literature

• Eitan M. Gurari: An Introduction to the Theory of Computation, Computer Science Press, 1989
• John E. Hopcroft, Rajeev Motwani & Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second ed., Addison-Wesley, 2001
• Efim Kinber & Carl Smith: Theory of Computing, A Gentle Introduction, Prentice Hall, 2001
• Harry R. Lewis & Christos H. Papadimitriou: Elements of the Theory of Computation, Second ed., Prentice-Hall, 1998
• J. Martin: Introduction to Languages and the Theory of Computation, Third ed., McGraw-Hill, 2003
• B. Moret: The Theory of Computation, Addison-Wesley, 1998
• Michael Sipser: Introduction to the Theory of Computation, Second (International) ed., Thomson, 2006

Links