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.

With the increasing tendency to parallel calculations, the question of the formal description and analysis of the behavior of non-sequential systems also becomes more important. Petrinets provide a good graphical illustration: the points (passive components) are represented as circles, the transitions (active components) as rectangles, and the flow rela- tions as arrows between them. In the lecture, the space transition systems of C.A. Petri and their equivalent description as Verktoradditionssysteme and the automatic theoretical counterpart are presented. Decision-making questions such as accessibility and unrestrictedness are examined.

In this programming project software for the processing and visualization of formal languages is to be created, whereby the focus is on the regular languages.

The processing part involves entering and storing language descriptions (e.g., as an automaton), transferring from one description to another (e.g., automaton to regular expression), as well as applying elementary operations such as cutting two languages. [read more ...]

This is an overview of much of Theoretical Computer Science by dealing with the interrelations between the formal languages, predictability and complexity theory.

Literatur

Literature

- K.-J. Lange: Complexity and Structure in Formal Language Theory. Fundamenta Informaticae, 25(3) 327-352, 1996. Structures '93, 4070 (1993), 224-238.

Based on the foundations laid down in the lecture "Theoretical Computer Science", properties of the computability concept are treated. The content covered is:

• The sentences of Rice

• The recursion rate

• The incompleteness rate of Goedel

• The arithmetic hierarchy

• Computability and formal languages: the Greibach theorem

Literatur

Literature

H. Rogers: Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.

J. Hopcroft, J. Ullmann: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1975.

Nearly everyone who uses a computer is consciously or unconsciously using compression methods: for example, to archive files to reduce their storage requirements, unconsciously by using standard file formats that pre-define data compression. This event provides an introduction to the basics of data compression and the frequently used algorithms. [read more ...]

A basic element of the theory of formal languages is the finite description of potentially infinite sets of words, so-called formal languages. These occur as a formal description of problems, functions or other objects. [read more ...]

Although simple cutting problems, e.g. Between straight lines in the plane, are not of interest from a mathematical point of view, however, there are efficiency problems when intersecting thousands of lines, and special algorithms are required for their treatment. [read more ...]

The course gives an insight into the classical complexity theory. The concepts of resource consumption and reduction known from computer science 3 are once more motivated, repeated and deepened. [read more ...]

• Theoretische Informatik
• Seminar
• Proseminar