OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Prof. Tapio Elomaa

Fall 2009, periods I ja II

Lectures:

• P I Sept. 7 - Oct. 18: Tue 14-16 TC103 and Thu 14-16 TC133
• P II Oct. 26 - Dec. 12: Tue 14-16 TB219 and Thu 12-14 TB224

Weekly exercises: Ph.D. Jussi Kujala

• P I Thu 10-12 TC128
• P II Tue 12-14 TC210

Course exam: Tue Dec. 15, 2009, 9 - 12 AM

News

• Course exam: Tue Dec. 15, 2009, 9 - 12 AM
• Exercise counts

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. Lisäksi pyritään vetämään näiden tulosten yhteyksiä käytännön ohjelmistotyöhön.

Lectures

The lectures of Fall 2009 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	Sept. 8 & 10	PDF	--	0, 1.1
2	Sept. 15 & 17	PDF	Sept. 24	1.1-1.2
3	Sept. 22 & 24	PDF	Oct. 1	1.3-1.4
4	Sept. 29 & Oct. 1	PDF	Oct. 8	2.1
5	Oct. 6 & 8	PDF	Oct. 15	2.2, 3.1-3.2
6	Oct. 13 & 15	PDF	Oct. 27	3.3 + unrestricted grammars
7	Oct. 27 & 29	PDF	Nov. 3	4 + universal TMs
8	Nov. 3 & 5	PDF	Nov. 10	5.1, 5.3
9	Nov. 10 & 12	PDF	Nov. 17	7.1-7.2
10	Nov. 17 & 19	PDF	Nov. 24	7.3-7.5
11	Nov. 24 & 26	PDF	Dec. 1	8
12	Dec. 1 & 3	PDF		10.1

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.

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. Time Complexity
   • Asymptotic Analysis
   • The Class P
   • The Class NP
   • NP-completeness
7. Space Complexity
   • Savitch's Theorem
   • PSPACE-completeness
   • The Classes L and NL
8. Approximation
9. 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