Modul

siehe Teilleistung

Der/die Studierende

• besitzt einen vertieften Einblick in die Grundlagen der Theoretischen Informatik und beherrscht deren Berechnungsmodelle und Beweistechniken,
• versteht die Grenzen und Möglichkeiten der Informatik in Bezug auf die Lösung von definierbaren aber nur bedingt berechenbaren Problemen,
• abstrahiert grundlegende Aspekte der Informatik von konkreten Gegebenheiten wie konkreten Rechnern oder Programmiersprachen und formuliert darüber allgemeingültige Aussagen über die Lösbarkeit von Problemen,
• ist in der Lage, die erlernten Beweistechniken bei der Spezifikation von Systemen der Informatik und für den systematischen Entwurf von Programmen und Algorithmen anzuwenden.

s. Teilleistung

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. Weitere Themen des Moduls legen die Grundlagen für Schaltkreisentwurf, Compilerbau, uvam. Die meisten Ergebnisse 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 polynomielle Reduktionen).

Der Gesamtarbeitsaufwand für dieses Modul beträgt ca. 180 Stunden (6 Credits). Die Gesamtstundenzahl ergibt sich dabei aus dem Aufwand für den Besuch der Vorlesungen und Übungen, sowie den Prüfungszeiten und dem zeitlichen Aufwand, der zur Erreichung der Lernziele des Moduls für einen durchschnittlichen Studenten für eine durchschnittliche Leistung erforderlich ist.