[ITH] - [de] - [Einführung in die Theoretische Informatik]

Einführung in die Theoretische Informatik [2026 SoSe]
Code
ITH		 Name
Einführung in die Theoretische Informatik
LP
8		 Dauer
ein Semester		 Angebotsturnus
jedes Sommersemester
Format
Vorlesung 4 SWS + Übung 2 SWS		 Arbeitsaufwand
240 h; davon
90 h Präsenzstudium
15 h Prüfungsvorbereitung
135 h Selbststudium und Bearbeitung der Übungsaufgaben (eventuell in Gruppen)		 Verwendbarkeit
B.Sc. Informatik
B.Sc. Mathematik
Sprache
Deutsch		 Lehrende
Felix Joos, Wolfgang Merkle		 Prüfungsschema
1+1
Lernziele Die Studierenden
- sind mit grundlegenden Aspekten des Berechenbarkeitsbegriffs vertraut, insbesondere mit dessen anschaulicher Bedeutung, der Formalisierung durch Turingmaschinen und der Church-Turing-These,
- wissen um die Grenzen der Berechenbarkeit, können die Unentscheidbarkeit des Halteproblems nachweisen und durch die Reduktionsmethode auf weitere Probleme übertragen,
- sind vertraut mit universellen Maschinen und weiteren Konzepten und Herangehensweisen der Berechenbarkeitstheorie,
- kennen wichtige Sätze wie das Rekursionstheorem und den Satz von Rice und können diese selbstständig anwenden,
- sind vertraut mit regulären Sprachen, insbesondere deren Charakterisierung durch endliche Automaten und mit dazu verwandten Konzepten wie L-Äquivalenz und Pumping-Lemma,
- können kontextfreie, kontextsensitive und allgemeine Chomsky-Sprachen in die Chomsky-Hierarchie einordnen,
- können die Stufen der Chomsky-Hierarchie durch generative Grammatiken charakterisieren und haben einen Überblick über die dazugehörigen Automatenmodelle,
- können Probleme hinsichtlich deren Zeit- und Platzkomplexität beschreiben und erhalten durch die Hierarchiesätze einen Einblick in die Auswirkungen unterschiedlicher Zeit- und Platzschranken,
- kennen die Bedeutung der Klassen P und NP, das P-NP-Problem, die NP-Vollständigkeit des Erfüllbarkeitsproblems und können diese durch die Reduktionsmethode auf weitere Probleme übertragen.
Lerninhalte Die Vorlesung gibt eine Einführung in drei zentrale Gebiete der Theoretischen Informatik: in die Berechenbarkeitstheorie, die Theorie Formaler Sprachen und die Komplexitätstheorie.
Teilnahme-
voraus-
setzungen		 empfohlen sind: Grundkenntnisse aus Mathematik (wie in einführenden Mathematikvorlesungen vermittelt) und Informatik
Vergabe der LP und Modulendnote Das Modul wird mit einer benoteten Klausur abgeschlossen. Die Modulendnote wird durch die Note der Klausur festgelegt. Für die Vergabe der LP gilt die Regelung aus dem Kapitel Prüfungsmodalitäten.
Nützliche Literatur Wird vom Lehrenden bekannt gegeben.