This course covers three traditionally central areas of the theory of computation: automata, computability and complexity. It aims to provide the students with an understanding to what are the computation models and to explain what each one can/cannot do, how quickly, and with how much memory. The formal languages and their computation models in the Chomsky hierarchy are introduced. Turing machines are defined and their variants are introduced. Time and space complexity classes are also defined and covered.

Regular, context free, and context sensitive languages and their computation models; turing machine and their variants, the definition of algorithm, decidability and undecidability; time and space classes and their relatlions to each other; approximation algorithms and probabilistic algorithms