Zum Inhalt

Grundbegriffe der theoretischen Informatik

Veranstaltungsnummer 040125
Titel Logik
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation  
  • Pflichtvorlesung im Bachelorstudiengang Informatik
  • Pflichtvorlesung im Diplomstudiengang Informatik
  • Diese Vorlesung und ihre Übungen ersetzen die Elemente "Theoretische Informatik für Studierende der Angewandten Informatik" und "Übungen zu Theoretische Informatik für Studierende der Angewandten Informatik" in den Modulen INF-BSc-112: "Theoretische Informatik für Studierende der Angewandten Informatik" und INF-BL-105: "Theoretische Informatik für BK (TIfBK)".
 
Semester Sommersemester 2022
SWS 6 (4V+2Ü)
Kreditpunkte 8 (im Bachelorstudiengang Informatik)
Ort und Zeit Dienstags, 10:15 - 12:00 Uhr, HG II, HS 3

Donnerstags, 12:15 - 14:00 Uhr, HG II, HS 3
Querverbindungen DAP II, Logik
Voraussetzungen Kenntnisse aus RS, DAP I und DAP II
Materialien Im Moodle-Arbeitsraum (Anmeldung über LSF)
Übungsleiter tba

Aktuelles

Die Vorlesung beginnt voraussichtlich am 7.4.2022.

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.


Anfahrt & Lageplan

Der Campus der Technischen Universität Dortmund liegt in der Nähe des Autobahnkreuzes Dortmund West, wo die Sauerlandlinie A45 den Ruhrschnellweg B1/A40 kreuzt. Die Abfahrt Dortmund-Eichlinghofen auf der A45 führt zum Campus Süd, die Abfahrt Dortmund-Dorstfeld auf der A40 zum Campus-Nord. An beiden Ausfahrten ist die Universität ausgeschildert.

Direkt auf dem Campus Nord befindet sich die S-Bahn-Station „Dortmund Universität“. Von dort fährt die S-Bahn-Linie S1 im 15- oder 30-Minuten-Takt zum Hauptbahnhof Dortmund und in der Gegenrichtung zum Hauptbahnhof Düsseldorf über Bochum, Essen und Duisburg. Außerdem ist die Universität mit den Buslinien 445, 447 und 462 zu erreichen. Eine Fahrplanauskunft findet sich auf der Homepage des Verkehrsverbundes Rhein-Ruhr, außerdem bieten die DSW21 einen interaktiven Liniennetzplan an.
 

Zu den Wahrzeichen der TU Dortmund gehört die H-Bahn. Linie 1 verkehrt im 10-Minuten-Takt zwischen Dortmund Eichlinghofen und dem Technologiezentrum über Campus Süd und Dortmund Universität S, Linie 2 pendelt im 5-Minuten-Takt zwischen Campus Nord und Campus Süd. Diese Strecke legt sie in zwei Minuten zurück.

Vom Flughafen Dortmund aus gelangt man mit dem AirportExpress innerhalb von gut 20 Minuten zum Dortmunder Hauptbahnhof und von dort mit der S-Bahn zur Universität. Ein größeres Angebot an internationalen Flugverbindungen bietet der etwa 60 Kilometer entfernte Flughafen Düsseldorf, der direkt mit der S-Bahn vom Bahnhof der Universität zu erreichen ist.