Informatik 3

Die Informatik 3 gibt eine Einführung in die Themen der theoretischen Informatik.

Die theoretische Informatik befasst sich mit den mathematischen Grundlagen der Informatik. Die zentralen Themen der Vorlesung sind formale Sprachen, Berechenbarkeit und Komplexitätstheorie.

Formale Sprachen sind das Thema der Vorlesung. Sie dienen der mathematisch präzisen Formulierung der auftretenden Probleme und Fragestellungen. Im Themengebiet formale Sprachen wird untersucht, wie sich formale Sprachen beschreiben und auch erkennen lassen. Dazu werden Grammatiken eingeführt und verschiedene Automatenmodelle zum Erkennen von formalen Sprachen eingeführt. Ein Beispiel für formale Sprachen sind Programmiersprachen. Es wird gezeigt, wie sich einerseits gültige Programme beschreiben lassen und auch andererseits, wie entschieden werden kann, ob ein Quelltext ein gültiges Programm ist.

Im Gebiet der Berechenbarkeit wird der Begriff des Algorithmus mathematisch präzise definiert. Es werden verschiedene Möglichkeiten aufgezeigt, allgemeine Berechnungsmodelle zu definieren. Des weiteren wird untersucht, inwiefern Problemstellungen algorithmisch lösbar sind.

In der Komplexitätstheorie wird untersucht, wie effizient oder schnell sich Probleme durch Algorithmen lösen lassen. es wird der begriff der Laufzeit eines Algorithmus definiert und Probleme auf ihre Schwierigkeit hin untersucht.

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.

In der Komplexitätstheorie wird untersucht, wie effizient oder schnell sich Probleme durch Algorithmen lösen lassen. es wird der begriff der Laufzeit eines Algorithmus definiert und Probleme auf ihre Schwierigkeit hin untersucht.