Computer Science 3 gives an introduction to the topics of theoretical computer science.

Theoretical computer science deals with the mathematical fundamentals of computer science. The main topics of the lecture are formal languages, calculability and complexity theory.

Formal languages are the topic of the lecture. They serve the mathematically precise formulation of the problems and questions that arise. In the subject area formal languages, it will be inspected how formal languages can be described and also recognized. For this, grammars are introduced and various machine models for the recognition of formal languages are introduced. Examples of formal languages are programming languages. It shows how valid programs can be described on the one hand, and, on the other hand, how to decide whether a source text is a valid program.

In the domain of predictability the term of the algorithm is defined mathematically precisely. There are several ways to define general calculation models. Furthermore, we examine the extent to which problems can be solved by algorithms.

In the theory of complexity, we investigate how efficiently or quickly problems can be solved by algorithms. The concept of the runtime of an algorithm is defined and problems are examined for their difficulty.