Theoretische Informatik (THI)

Verstehe die Grundlagen hinter der Informatik: Du beschäftigst dich mit logischem Denken, formalen Regeln und mathematischen Modellen, die zeigen, wie Computer Probleme lösen. Außerdem lernst du, wie Informationen verarbeitet werden, welche Aufgaben Computer lösen können und wo ihre Grenzen liegen.

Inhalte

• Die Vorlesung vermittelt eine grundlegende Einführung in zentrale Themenbereiche der theoretischen Informatik. Im Bereich der Logik werden die Grundlagen der Prädikatenlogik erster Stufe sowie darauf aufbauend das Resolutionsverfahren, die Hornklausellogik, die SLD-Resolution, die Negation as Failure und regelbasierte Systeme vorgestellt. Dabei steht ein grundlegendes Verständnis der Konzepte und ihrer Zusammenhänge im Vordergrund.Ein weiterer Teil der Vorlesung gibt eine Einführung in formale Sprachen. Hierzu werden die Chomsky-Hierarchie sowie die grundlegenden Eigenschaften regulärer und kontextfreier Sprachen behandelt. Daran anschließend werden im Bereich der Automatentheorie die grundlegenden Funktionsweisen und Einsatzgebiete endlicher Automaten und Kellerautomaten vorgestellt.Abschließend bietet die Vorlesung eine Einführung in die Berechenbarkeitstheorie und die Komplexitätstheorie. Dabei werden grundlegende Fragestellungen zur prinzipiellen Lösbarkeit von Problemen sowie zur Bewertung ihrer algorithmischen Komplexität und ihres Ressourcenbedarfs behandelt.Insgesamt dient die Vorlesung somit dazu, einen Überblick über die wesentlichen Konzepte und Zusammenhänge dieser Teilgebiete zu vermitteln, ohne einzelne Themenbereiche vertieft zu behandeln.

Lernziele/Kompetenzen

Die Studierenden sind in der Lage,

• den Prozess, von einer Problemstellung über strukturierte logische Konzepte zu einer automatisch durchführbaren Problemlösung zu gelangen, zu erläutern und zu verfolgen,
• ein gedanklichen Lösungskonzepts in eine vom Rechner verarbeitbare formale Darstellung umzusetzen,
• die syntaktischen Grundlagen von Programmiersprachen und ihre Verarbeitung auf dem Rechner zu beschreiben und
• analytisch und strukturiert zu denken mit dem Ziel, systematisch Problemlösungen entwickeln zu können.

Literatur

• R. Socher, "Theoretische Grundlagen der Informatik", 3rd ed. Munich, Germany: Carl Hanser Verlag, 2008.
• G. Vossen and K.-U. Witt, "Grundkurs Theoretische Informatik: Eine anwendungsbezogene Einführung", 6th ed. Wiesbaden, Germany: Springer Vieweg, 2016.
• J. E. Hopcroft, R. Motwani, and J. D. Ullman, "Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit", 3rd ed. Munich, Germany: Pearson Studium, 2011.
• W. Ertel, "Grundkurs Künstliche Intelligenz: Eine praxisorientierte Einführung", 6th ed. Wiesbaden, Germany: Springer Vieweg, 2025.
• D. W. Hoffmann, "Theoretische Informatik", 5th ed. Munich, Germany: Carl Hanser Verlag, 2022.
• J.-É. Pin, Ed., "Handbook of Automata Theory", vols. I–II. Berlin, Germany: EMS Press, 2021.
• P. Linz and S. H. Rodger, "An Introduction to Formal Languages and Automata", 7th ed. Burlington, MA, USA: Jones & Bartlett Learning, 2023.
• B. Barak, "Introduction to Theoretical Computer Science". Cambridge, MA, USA: self-published (open access), 2023. [Online]. Available: https://introtcs.org

Dozentinnen / Dozenten

• Prof. Dr. Lutz Strüngmann

Empfohlene Vorkenntnisse 

• keine

Daten zum Modul

Semester	2
Unterrichtssprache	Deutsch
Häufigkeit	Jedes Semester
Kreditpunkte (CP)	5
Modulverantwortlich	Prof. Dr. Lutz Strüngmann
Dauer	1 Semester
Studienleistung	Keine
Prüfungsvorleistung	Pflichtübung (PU)
Prüfungsleistung	Klausur 90 Minuten (K90)

Semesterwochenstunden (SWS) 

Vorlesung	2 SWS
Labor	2 SWS
Summe	4 SWS

Arbeitsaufwand (Workload) 

Vorlesung	30 h
Labor	30 h
Selbststudium	90 h
Summe	150 h