Course Catalog 2013-2014
Postgraduate

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2013-2014

MAT-73006 Theoretical Computer Science, 7 cr

Additional information

Suitable for postgraduate studies

Person responsible

Henri Hansen, 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


 
MAT-73006 2013-01 Tuesday 14 - 16, TB222
Thursday 14 - 16, TB219

Requirements

Examination.
Completion parts must belong to the same implementation

Learning Outcomes

The student knows the classical fundamental results in theoretical computer science.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Regular expressions. Deterministic and nondeterministic finite automata.     
2. Backus-Naur format. Context-free grammars. Push-down automata.     
3. Turing machines and their relation to computers and programming languages.     
4. Undecidability. Rice's theorem.     
5. NP-completeness. A glimpse to other complexity classes.     

Study material

Type Name Author ISBN URL Edition, availability, ... Examination material Language
Book   Introduction to the Theory of Computation   Michael Sipser         Yes    English  

Prerequisites

Course Mandatory/Advisable Description
MAT-02650 Algoritmimatematiikka Mandatory    
MAT-71000 Tieto ja laskenta Advisable    
TIE-02200 Ohjelmoinnin peruskurssi Mandatory    

Prerequisite relations (Requires logging in to POP)



Correspondence of content

Course Corresponds course  Description 
MAT-73006 Theoretical Computer Science, 7 cr OHJ-2306 Introduction to Theoretical Computer Science, 6 cr  

More precise information per implementation

Implementation Description Methods of instruction Implementation
MAT-73006 2013-01        

Last modified03.05.2013