Theory of Computability and Complexity

This course provides parts of the theoretical background for computer science. The course includes formal languages, finite automata, Turing machines, computability, polynomical reduction and complexity-classes with examples. The course is given every second year, next time fall 2012.

After completing the course, the student should be able to recognize, understand and apply concepts from the theoretical basis for computer science, as specified under "Academic content". The student should be familiar with the mathematical approach to complexity computations which is important in connection with programming and information technology.

Lectures and exercises. Retake of examination may be given as an oral examination.