Opinto-opas 2003-2004

73117 THEORY OF AUTOMATA, THEORY OF AUTOMATA, 3 ov

Lecturer info
Professor STEPHAN FOLDES

Lectures and exercises:
Lecture hours total 42 h. Exercise hours total 28 h.

Weekly teaching / period

A1

A2

S1

S2

Summer

Lectures (h):

3+

3

-

-

-

Exercises (h):

2+

2

-

-

-

Content of the course
Strings of symbols, languages and mathematical machines. Deterministic and non-deterministic computations. Turing machines, algorithms, decidability. Oracles and reducibility. Complexity of computation.

Requirements
Final exam plus activity points and class tests, particulars to be announced during first lecture.

Literature
Sipser, M.: Introduction to the Theory of Computation. PWS Publ. Co., Boston 1996

Prerequisites

Number

Name

OV

P/S

73116

Mathematics for Algorithms

3

Obl.

Notes
Lectures in English. The course is given biannually. It is not given in the academic year 2003-2004.