A4.1: Theoretische Grundlagen der Informatik (Informatik IV)

Bedeutung

Die universitären Informatikstudiengänge sind grundlagen‑ und methodenorientierte Studiengänge, so dass eine intensive Beschäftigung mit den Grundlagen der Informatik, insbesondere den theoretischen Grundlagen, ein fester Bestandteil des Studiums ist.

Lernziele

Die Studentinnen und Studenten sollen mathematisch präzise Antworten auf die folgenden Fragen kennenlernen: Was können Computer berechnen und was nicht? Wie klassifiziert und vergleicht man Berechnungsprobleme gemäß des zu ihrer Lösung notwendigen Aufwands? Wie definiert man die Syntax von textuellen Objekten (wie zum Beispiel Suchmuster oder Programmiersprachen)? Und wie ihre Semantik? Was bedeutet Korrektheit? Und wie weist man sie nach?

Stoff

Behandelt werden die Grundzüge der Rekursionstheorie,Komplexitätstheorie, Theorie der formalen Sprachen, Automatentheorie und Korrektheitstheorie. Zentrale Begriffe sind Berechenbarkeit, (Semi‑)Entscheidbarkeit, Reduzierbarkeit, Komplexitätsklassen, Vollständigkeit, Schwere, Automaten, Grammatiken, Ausdrücke, Korrektheitsaussagen, Kalküle und (relative) Vollständigkeit.

Voraussetzungen

Module G1.1, G1.2, G1.4, G2.1, G2.2, A3.4

Unterrichtssprache

Deutsch

Zuordnung zu den Curricula

Modul A4.1 des Bachelor‑ und des Diplomstudiengangs Informatik

Lehrform

4-stündige Vorlesung, 2-stündige Übung

ECTS-Punkte

8

Studien‑ und Prüfungsleistungen

Teilnahme an den Übungen und schriftliche Abschlussprüfung

Medienformen

Tafelanschrieb in der Vorlesung, Diskussion in der Kleingruppe in der Übung

Literatur

Michael Sipser, Introduction to the Theory of Computation, 2nd Ed., Boston: PWS, 2005.