Grundbegriffe der theoretischen Informatik

Aktuelles

Die Vorlesung beginnt voraussichtlich am 9.4.2024.

Bitte beachten Sie: genauere Informationen zum Ablauf der Veranstaltung erhalten Sie im Moodle-Arbeitsraum.

Inhalt

Die Vorlesung "Grundbegriffe der Theoretischen Informatik" besteht aus zwei Teilen.

Der erste Teil beschäftigt sich mit formalen Sprachen. Im Mittelpunkt stehen die regulären und kontextfreien Sprachen. Beide Sprachklassen sind fundamental für die Syntax von Programmiersprachen. Grob gesagt, korrespondieren reguläre Sprachen zum Scannen eines Programmtextes, also der Zerlegung des Zeichenstroms in einzelne Strings. Die kontextfreien Sprachen entsprechen dem Parsen, also der strukturellen Analyse des Programmtextes.

Reguläre Sprachen lassen sich durch reguläre Ausdrücke spezifizieren (grep!), diese können in Algorithmen transformiert werden, die sich (außer einem Positionszeiger) nur konstant viel Information merken müssen: endliche Automaten. Die Bedeutung von regulären Sprachen und insbesondere von endlichen Automaten reicht jedoch sehr viel weiter. Endliche Automaten spielen beispielsweise in der Hardware- und Software-Verifikation eine große Rolle, oft unter dem Namen "Transitionssysteme".

Kontextfreie Sprachen können durch kontextfreie Grammatiken (oder auch Backus-Naur-Formen) spezifiziert werden und haben ebenfalls ein grundlegendes korrespondierendes Automatenmodell, die Automaten mit einem Pushdown-Speicher.

Die Vorlesung gibt eine Einführung in die verschiedenen, jeweils äquivalenten Arten zur Beschreibung regulärer und kontextfreier Sprachen, untersucht Algorithmen zum Umgang mit solchen Sprachen, stellt ihre wichtigsten Eigenschaften dar, und betrachtet Anwendungen.


Der zweite Teil der Vorlesung beschäftigt sich mit den wesentlichen Resultaten der Theorie von Algorithmen: dabei geht es vor allem um die beiden Fragen "was ist überhaupt algorithmisch berechenbar?" und "was ist "effizient algorithmisch berechenbar?". Die erste Frage führt zur Berechenbarkeitstheorie, die zweite zur Komplexitätstheorie.

In der Berechenbarkeitstheorie wird zunächst der Begriff des "algorithmisch berechenbaren" geklärt. Sodann wird gezeigt, dass konkrete algorithmische Probleme, wie z.B.: "haben zwei gegebene Programme bei jeder Eingabe dieselbe Ausgabe?" nicht algorithmisch lösbar sind.

Die Komplexitätstheorie klassifiziert die algorithmisch lösbaren Probleme nach ihrem Ressourcenverbrauch, insbesondere hinsichtlich Laufzeit und Speicherbedarf. Die berühmteste offene Frage (der theoretischen und vielleicht der gesamten Informatik) ist die nach dem
Verhältnis der Probleme, die in polynomieller Zeit gelöst werden können (z.B.: testen, ob ein gegebener Graph zusammenhängend ist) und denen, für die ein Lösungskandidat in polynomieller Zeit überprüft werden kann (wie z.B. ob eine gegebene Menge von Jobs auf einer gegebenen Menge von Prozessoren in einer gegebenen Zeit bearbeitet werden kann).

Die bisher unbewiesene Vermutung ist, dass es Probleme der zweiten Art gibt, die nicht zugleich von der ersten Art sind, also keine polynomielle Lösung haben (also: zu testen, ob eine Zuordnung von
Jobs zu Prozessoren korrekt ist, ist einfach, aber selbst eine zu finden, ist schwierig).

Typisch für die theoretische Informatik ist, dass sie Phänomene aus der Informatik mathematisch modelliert und sich dadurch die Möglichkeit schafft, Aussagen (über die Modelle) zu beweisen. Ein Beweis liefert (idealerweise) mindestens zweierlei: die Sicherheit, dass die Aussage gilt und eine präzise Erklärung, warum sie gilt. Neben der reinen Darstellung von Fakten, soll in der Vorlesung insbesondere auch diese Denkweise vermittelt werden.

Literatur

Die Vorlesung richtet sich im Wesentlichen nach den folgenden Büchern:

• E. Hopcroft, R. Motwani, J.D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson. 2002.
• I. Wegener. Theoretische Informatik - eine algorithmenorientierte Einführung. 2. Auflage. 1999. Teubner.
• I. Wegener. Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. 2003. Springer.
• U. Schöning. Theoretische Informatik - kurz gefasst. Spektrum. 2008.

Im folgenden Buch werden wichtige Ideen der Vorlesung auf eine informellere Weise dargestellt, was für das Verständnis hilfreich sein kann, aber nicht den Inhalt der Vorlesung vollständig abdeckt.

• I. Wegener. Kompendium der Theoretischen Informatik - eine Ideensammlung. Teubner. 1996.

Weitere Literaturhinweise erfolgen in der Vorlesung.