Course Catalog 2009-2010
International

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2009-2010

OHJ-2306 Introduction to Theoretical Computer Science, 6 cr

Person responsible

Tapio Elomaa, Antti Valmari

Implementations

  Lecture times and places Target group recommended to
Implementation 1


Per 1 :
Tuesday 14 - 16, TC103
Thursday 14 - 16, TC133
Per 2 :
Tuesday 14 - 16, TB219
Thursday 12 - 14, TB224

 
 


Requirements

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

Learning outcomes

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.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Universal models of computation  Turing machines  Variants of Turing machines 
2. Computability theory  Decidability  Reducibility 
3. Complexity theory  Intractability  Time and space complexity 


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   A course on the analysis of algorithms.
MAT-20600 Discrete Mathematics Mandatory   A course on discrete mathematics, or the old requirement 8100500 Ohjelmistotekniikan matemaattiset menetelmät.

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  

More precise information per implementation

  Description Methods of instruction Implementation
Implementation 1   Lectures
Excercises
   
Contact teaching: 50 %
Distance learning: 0 %
Self-directed learning: 50 %  


Last modified15.10.2009
ModifierTapio Elomaa