Course Catalog 2010-2011
International

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2010-2011

OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Person responsible

Tapio Elomaa, Antti Valmari

Lessons

Study type P1 P2 P3 P4 Summer Implementations Lecture times and places
Lectures
Excercises
 4 h/week
 2 h/week
+4 h/week
+2 h/week


 


 


 
OHJ-2306 2010-01 Tuesday 14 - 16, TB220
Thursday 14 - 16, TB220

Requirements

Weekly exercises and exam
Completion parts must belong to the same implementation

Learning outcomes

After completing the course the student will have a clear understanding that different computing devices have different computation power and that all formal models of computing have their limitations. The student will learn that different formulations of computation lead to same computing power. In particular, the student can give automaton and grammar implementations for formal languages belonging to classes of regular, context-free, and Turing-recognizable languages. The student is also able to prove basic results concerning computability and decidability. The student can also explain the dependency of time and space complexity of problems on the model of computation.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Automata and languages, Regular languages  Nonregular languages, Context-free languages, Push-down automata  Chomsky normal form 
2. Universal models of computation, Turing machines  Variants of Turing machines, Unrestricted grammars  Encoding Turing machines 
3. Computability theory, Decidability  Reducibility  Completeness 
4. Complexity theory, Intractability  Time and space complexity, Classes P and NP  Sunlinear space complexity 

Evaluation criteria for the course

The course grade will be based on the course exam. Active participation to weekly exercises yields extra points. If the student demonstrates thorough understanding of the core content, s/he may pass the course with grade 3. In order to achieve grade 4, the student must also demonstrate competency in complementary knowledge. The student may achieve grade 5, if s/he also demonstrates good command of specialist knowledge. If there are minor shortcomings regarding the core content, the student may receive the grade 1 or 2, depending on the number of flaws. If there are significant shortcomings regarding core content, the student will not pass the course.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

Type Name Author ISBN URL Edition, availability, ... Examination material Language
Book   Introduction to the Theory of Computation   Michael Sipser   0-619-21764-2     Second, International Edition      English  

Prerequisites

Course Mandatory/Advisable Description
OHJ-2156 Analysis of Algorithms Mandatory    

Prerequisite relations (Requires logging in to POP)



Correspondence of content

Course Corresponds course  Description 
OHJ-2306 Introduction to Theoretical Computer Science, 6 cr OHJ-2300 Introduction to Theoretical Computer Science, 6 cr  

Additional information

Suitable for postgraduate studies

More precise information per implementation

Implementation Description Methods of instruction Implementation
OHJ-2306 2010-01 Autumn 2010   Lectures
Excercises
   
Contact teaching: 50 %
Distance learning: 0 %
Self-directed learning: 50 %  

Last modified19.08.2010