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.
Lecture room and time
TUESDAY 17 - 19, TB222,
WEDNESDAY 13 - 14, K2106,
Weekly teaching / period |
|
|
|
|
|
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 |
|
|
73116 |
3 |
Recomm. |
Notes
Lectures in English. The course is given biannually. It is given in the academic year 2002-2003.