Formale Grundlagen der Informatik 1



Im Modul FGI1 werden wir grundlegende Themen und Ideen der theoretischen Informatik behandeln, die in vielen Bereichen der Informatik Anwendung finden. Die Veranstaltung ist dabei in zwei Teile gegliedert, den Automatenteil und den Logikteil.

Im Automatenteil werden wir verschiedene abstrakte Konzepte wie Automaten und Grammatiken kennenlernen. Diese findet man oft als Modellierungswerkzeug in den unterschiedlichsten Bereichen der Informatik oder sie dienen als Ideengeber für den Entwurf effizienter Algorithmen und Datenstrukturen.

Im Logikteil wollen wir zwei Logiken betrachten, die Aussagenlogik und die Prädikatenlogik. Die Aussagenlogik ist eine ganz grundlegende Logik, die sozusagen als Teillogik in vielen weiteren Logiken enthalten ist. Die Prädikatenlogik erweitert die Konzepte der Prädikatenlogik deutlich und erlaubt mit ihren Quantoren Aussagen über alle oder einzelne Elemente einer Grundmenge. Logiken finden ebenfalls in vielen Bereichen der Informatik Anwendung wie bspw. in der Spezifikation und in der KI-Forschung zudem hilft ein Verständnis der Logik bei grundlegenden Programmieraufgaben und beim Verstehen von Beweisen.

Auch wenn wir die beiden Teile in dieser Veranstaltung überwiegend getrennt voneinander behandeln werden, so bestehen doch zwischen Automaten und Logiken viele Verbindungen. Beispielsweise spielen in der Hardware- und Software-Verifikation, also bei der Herstellung korrekt arbeitender IT-Systeme, Automaten und Logiken eine herausragende Rolle. Wir werden hierauf nur am Rand eingehen, weiterführende Veranstaltungen im Studium gehen hierauf näher ein.

Neben diesen inhaltlichen Schwerpunkten liegt ein Schwerpunkt der Vorlesung insbesondere auch auf der formalen Herangehensweise. Wie beschreibt man die Modelle mathematisch und wie können dann formal korrekte Aussagen getroffen werden? Die dabei gewonnene Fähigkeit, sehr strikt vorzugehen, wird einem auch an vielen Stellen im Studium und in der Arbeitswelt hilfreich sein.