Grundlagen der Theoretischen Informatik

Technische Universität Dresden Institut für Theoretische Informatik Lehrstuhl für Automatentheorie

Lehrveranstaltungsbeschreibung

Postscript

Studiengang

• Studiengang Informatik
• Studiengang Medieninformatik
• Ergänzungsstudiengang Softwaretechnik

Art der Lehrveranstaltung

Pflichtfach im Grundstudium (2/1/0)

Erwünschte Vorkenntnisse

• Algorithmen und Datenstrukturen
• Logik I

Zielstellung

In der Vorlesung Grundlagen der Theoretischen Informatik I werden Automaten und Grammatiken vorgestellt, die formale Sprachen - d.h. Mengen von Wörtern - erkennen bzw. erzeugen. Je nach Typ des Automaten oder der Grammatik erhält man verschieden starke Ausdrucksmittel zur Beschreibung von Klassen formaler Sprachen. Die wichtigsten dieser Klassen sind in der sogenannten Chomsky-Hierarchie zusammengefaßt. Insbesondere die regulären und die kontextfreien Sprachen sind wichtige Hilfsmittel bei der Beschreibung syntaktischer Strukturen z.B. von Programmen. Ihre formale Untersuchung bildet daher die Grundlage für die Übersetzung von Programmiersprachen und die Konstruktion zahlreicher Software-Werkzeuge.

Neben der Vermittlung von Wissen über formale Sprachen, Grammatiken und Automaten ist ein weiteres Ziel der Vorlesung, die Studierenden mit der Arbeitsweise in der Theoretischen Informatik vertraut zu machen.

In der Vorlesung Grundlagen der Theoretischen Informatik II werden formale Berechnungsmodelle eingeführt, die es ermöglichen, den intuitiven Begriff der "berechenbaren Funktion" formal zu definieren. Dies ist insbesondere wichtig, wenn man zeigen will, daß es nicht-berechenbare Funktionen gibt. In der Vorlesung werden Turing-Maschinen, While-Programme und µ-rekursive Funktionen als derartige Berechnungsmodelle eingeführt und es wird gezeigt, daß diese Modelle äquivalent sind, d.h. dieselbe Klasse von Funktionen berechnen. Diese Äquivalenz stützt die These von Church, welche besagt, daß die Turing-berechenbaren Funktionen genau die intuitiv berechenbaren Funktionen sind.

Auch wenn eine Funktion im Prinzip berechenbar ist, kann der Aufwand für ihre Berechnung so hoch sein, daß das Berechnungsverfahren in der Praxis nicht einsetzbar ist. Im zweiten Teil der Vorlesung wird daher ein formaler Rahmen eingeführt, mit dessen Hilfe man die Berechnungskomplexität von Funktionen abschätzen kann. Insbesondere erlaubt dies die Lokalisierung von harten Berechnungsproblemen, d.h. Problemen die (wahrscheinlich) nicht in polynomieller Zeit gelöst werden können.

Gliederung

Teil 1: Endliche Automaten

0. Einführung
1. Nichtdeterministische endliche Automaten
2. Deterministische endliche Automaten
3. Nachweis der Nichterkennbarkeit
4. Abschlußeigenschaften und Entscheidungsprobleme
5. Reguläre Ausdrücke und Sprachen

Teil 2: Grammatiken, kontextfreie Sprachen und Kellerautomaten

6. Die Chomsky-Hierarchie
7. Rechtslineare Grammatiken und reguläre Sprachen
8. Normalformen kontextfreier Grammatiken
9. Abschlußeigenschaften kontextfreier Sprachen
10. Kellerautomaten

Teil 3: Berechenbarkeit

11. Turingmaschinen
12. Zusammenhang zwischen Turingmaschinen und Grammatiken
13. Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit und Zusammenhänge
14. Primitiv rekursive Funktionen und LOOP-Programme
15. µ-rekursive Funktionen und WHILE-Programme
16. Universelle Turingmaschinen und unentscheidbare Probleme
17. Weitere unentscheidbare Probleme

Teil 4: Komplexität

Literatur

• Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993
• Uwe Schöning, Theoretische Informatik - kurzgefaßt, Spektrum Akademischer Verlag, 1999

Form des Abschlusses

Prüfung (Klausur) nach dem 3. Semester

Fortsetzungsmöglichkeiten der Lehrveranstaltung

• Vorlesungen des Fachgebietes »Theorie der Programmierung« (Hauptstudium)

Lehrbeauftragter

Prof. Dr.-Ing. Franz Baader, Institut für Theoretische Informatik