Theory of Computation contains three central areas: automata, computability and complexity. These areas are linked by the following important question: What are the fundamental capabilities and inherent limitations of computers? This question is interpreted differently in each of these three areas and corresponding answers are shaped accordingly. In the context of computability theory, the goal is to characterize the various problems as solvable or not. In complexity theory, the goal is to categorize solvable problems into easy and difficult and the central question is: What is it that makes some problems computationally hard and some other easy? One of the most important achievements of complexity theory is an elegant system of classifying problems according to their computational hardness. Automata theory deals with the definitions and properties of mathematical models of computation. These models are used in practice in several areas of computer science. For example, finite automata are used in string searching and pattern matching, word processing, compiler and hardware design. Another model, context-free grammars, is used in programming languages and artificial intelligence. Automata theory is a particularly interesting area that allows practice with formal definitions of computation which are highly significant in the theory of computability and complexity where a precise definition of the computer is required.

Students who regularly participate in course activities and successfully complete the course:

-         have knowledge and understanding for definitions and properties of mathematical models of computation (like, for instance, finite automata, push-down automata, Turing machine) and for corresponding methods (i.e., regular expressions, grammars, algorithms) for finite representation of particular classes of problems as well as for the definition of complexity classes for languages and problems (like for example decidable and undecidable languages, recognizable languages, class P, class NP, NP-complete problems) and the identification of  problems in each class (decidability, reducibility)

• each class.; students are therefore able to keep track of current developments at the cutting edge of their field of knowledge

• are able to use knowledge and understanding they have acquired in a way that shows a professional approach to their work or profession, and appropriately skilled to use mathematical models of computation for various problems within their field

• have the ability to collect and interpret relevant data (typically within their field) to form judgments that include reflection on relevant social, scientific or ethical issues

• are able to communicate information, ideas, problems and solutions to specialized and non-specialized audience

• have developed knowledge acquisition skills necessary to further continue their studies with a high degree of autonomy

• have become familiar with computational thinking and are able to exploit its advantages in scientific, professional and practical issues

In particular, students who regularly participate in course activities and successfully complete the course:

1. have knowledge of definitions and properties of mathematical models of computation and corresponding methods for finite representation of particular classes of problems

2. understand the relation between computational hardness of problems and relevant models of compuation

3. are able to develop and apply abstraction and modelling for algorithmic and compuational problems according to their hardness (I.e., resources required for solving them)

4. analyze problems / questions in order to gain understanding of their structure and components

5. suggest solutions to these problems guided by their computational hardness

6. evaluate findings (solutions or hardness results) through analysis

7. are familiar with computational thinking