Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen.

Lehrinhalt:
Es gibt wichtige Probleme, deren Lösung sich zwar klar definieren läßt, aber die man niemals wird systematisch berechnen können. Andere Probleme lassen sich "vermutlich" nur durch systematisches Ausprobieren lösen. Andere Themen dieser Vorlesungen legen die Grundlagen für Schaltkreisentwurf, Compilerbau, uvam. Die meisten Ergebnisse dieser Vorlesung werden rigoros bewiesen. Die dabei erlernten Beweistechniken sind wichtig für die Spezifikation von Systemen der Informatik und für den systematischen Entwurf von Programmen und Algorithmen.
Das Modul gibt einen vertieften Einblick in die Grundlagen und Methoden der Theoretischen Informatik. Insbesondere wird dabei eingegangen auf grundlegende Eigenschaften Formaler Sprachen als Grundlagen von Programmiersprachen und Kommunikationsprotokollen (regulär, kontextfrei, Chomsky-Hierarchie), Maschinenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen, Nichtdeterminismus, Bezug zu Familien formaler Sprachen), Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (Halteproblem,...), Gödels Unvollständigkeitssatz und Einführung in die Komplexitätstheorie (NP-vollständige Probleme und polynomiale Reduktionen).

Lernziele:
Der/die Studierende besitzt einen vertieften Einblick in die Grundlagen der Theoretischen Informatik und hat grundlegende Kenntnis in den Bereichen Berechenbarkeitstheorie, Komplexitätstheorie, formale Sprachen und Informationstheorie. Er/sie kann die Beziehungen dieser Gebiete erörtern und in einen Gesamtzusammenhang bringen. Außerdem kennt er/sie die fundamentalen Definitionen und Aussagen aus diesen Bereichen und ist in der Lage geführte Beweise zu verstehen sowie Wissen über erlangte Beweistechniken auf ähnliche Probleme anzuwenden.

Er/sie versteht die Grenzen und Möglichkeiten der Informatik in Bezug auf die Lösung von definierbaren aber nur bedingt berechenbare Probleme. Hierzu beherrscht er verschiedene Berechnungsmodelle, wie die der Turingmaschine, des Kellerautomaten und des endlichen

Automaten. Er/sie kann deterministische von nicht-deterministischen Modellen unterscheiden und deren Mächtigkeit gegeneinander abschätzen. Der/die Studierende kann die Äquivalenz aller hinreichend mächtigen Berechnungsmodelle (Churchsche These), Nichtberechenbarkeit wichtiger Funktionen (z.B. Halteproblem) und Gödels Unvollständigkeitssatz erläutern.

Er/sie besitzt einen Überblick über die wichtigsten Klassen der Komplexitätstheorie. Darüber hinaus kann er/sie ausgewählte Probleme mittels formaler Beweisführung in die ihm/ihr bekannten Komplexitätsklassen zuordnen. Insbesondere kennt er/sie die Komplexitätsklassen P und NP sowie das Konzept NP-vollständiger Probleme (polynomielle Reduktion). Er/sie kann erste grundlegende Techniken anwenden, um NP-schwere Probleme zu analysieren. Diese

Techniken umfassen unter anderem polynomielle Näherungsverfahren (Approximationsalgorithmen mit absoluter/relativer Güte, Approximationsschemata) als auch exakte Verfahren (Ganzzahlige Programme).

Im Bereich der formalen Sprachen ist es ihm/ihr möglich, Sprachen als Grammatiken zu formulieren und diese in die Chomsky-Hierarchie einzuordnen. Somit besitzt er/sie erste Kenntnisse im Compilerbau. Zudem kann er/sie die ihm/ihr bekannten Berechnungsmodelle den einzelnen Typen der Chomsky-Hierarchie zuordnen, so dass er/sie die Zusammenhänge zwischen formalen Sprachen und Berechnungstheorie identifizieren kann.

Der/die Studierende besitzt einen grundlegenden Überblick über die Informationstheorie und kennt damit Entropie, Kodierungsschemata sowie eine formale Definition für Information. Er/sie besitzt zudem die Fähigkeit, dieses Wissen anzuwenden.

Arbeitsaufwand:
Vorlesung mit 3 SWS + 1 SWS Übung. 6 LP entspricht ca. 180 Stunden

ca. 45 Std. Vorlesungsbesuch
ca. 15 Std. Übungsbesuch
ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter
ca. 30 Std. Prüfungsvorbereitung

Erfolgskontrolle:
Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung nach § 4 Abs. 2 Nr. 1 SPO. Es besteht die Möglichkeit, einen Übungsschein (Erfolgskontrolle anderer Art nach §4 Abs. 2 Nr. 3 SPO) zu erwerben. Für diesen werden Bonuspunkte vergeben, die auf eine bestandene Klausur angerechnet werden. Die Modulnote ist die Note der Klausur.

Weiterführende Literatur

• Uwe Schöning: Theoretische Informatik - kurz gefasst. Sprektrum (2001).
• Ingo Wegener: Theoretische Informatik. Teubner (1999)
• Ingo Wegener: Kompedium theoretische Informatik. Teubner (1996).

Genaue Informationen zu den Vorlesungs-, Übungsterminen finden sich auf https://act.iti.kit.edu/teaching/24wise/tgi