Course Catalog 2009-2010 Basic
Basic	Pori	International	Postgraduate	Open University
\|Degrees\| \|Study blocks\| \|Courses\|

Course Catalog 2009-2010

MAT-41176 Theory of Automata, 5 cr

Person responsible

Stephane Foldes

Implementations

No implementations

Requirements

Final exam plus activity points, particulars to be announced during first lecture.

Principles and baselines related to teaching and learning

Content

Content Core content Complementary knowledge Specialist knowledge

1. Strings of symbols, languages and mathematical machines.

2. Deterministic and non-deterministic computations. Turing machines, algorithms, decidability.

3. Oracles and reducibility. Complexity of computation.

4. COURSE NOT GIVEN IN 2009-2010

Study material

Type Name Author ISBN URL Edition, availability, ... Examination material Language

Book Introduction to the Theory of Computation Sipser, M. PWS Publ. Co., Boston 1996 English

Prerequisites

Course	Mandatory/Advisable	Description
MAT-21160 Algoritmimatematiikka	Mandatory

Prerequisite relations (Requires logging in to POP)

Correspondence of content

Course	Corresponds course	Description
MAT-41176 Theory of Automata, 5 cr	73117 Theory of Automata, 3 cu

Last modified 24.06.2009

Modifier Stephane Foldes

Content	Core content	Complementary knowledge	Specialist knowledge
1.	Strings of symbols, languages and mathematical machines.
2.	Deterministic and non-deterministic computations. Turing machines, algorithms, decidability.
3.	Oracles and reducibility. Complexity of computation.
4.	COURSE NOT GIVEN IN 2009-2010

Type	Name	Author	ISBN	URL	Edition, availability, ...	Examination material	Language
Book	Introduction to the Theory of Computation	Sipser, M.			PWS Publ. Co., Boston 1996		English

Course Catalog 2009-2010 Basic

Course Catalog 2009-2010