[TU Dresden]

Grundlagen der Theoretischen Informatik

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


Lehrveranstaltungsbeschreibung

Postscript

Studiengang

Art der Lehrveranstaltung

Pflichtfach im Grundstudium (2/1/0)

Erwünschte Vorkenntnisse

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

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

Teil 2: Grammatiken, kontextfreie Sprachen und Kellerautomaten

  1. Die Chomsky-Hierarchie
  2. Rechtslineare Grammatiken und reguläre Sprachen
  3. Normalformen kontextfreier Grammatiken
  4. Abschlußeigenschaften kontextfreier Sprachen
  5. Kellerautomaten

Teil 3: Berechenbarkeit

  1. Turingmaschinen
  2. Zusammenhang zwischen Turingmaschinen und Grammatiken
  3. Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit und Zusammenhänge
  4. Primitiv rekursive Funktionen und LOOP-Programme
  5. µ-rekursive Funktionen und WHILE-Programme
  6. Universelle Turingmaschinen und unentscheidbare Probleme
  7. Weitere unentscheidbare Probleme

Teil 4: Komplexität

Literatur

Form des Abschlusses

Prüfung (Klausur) nach dem 3. Semester

Fortsetzungsmöglichkeiten der Lehrveranstaltung

Lehrbeauftragter

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