Vorlesung Einführung in die Theoretische Informatik SS04

Prof. Dr. B. Möller


Vorlesungsskriptum
Kapitel 0 Organisatorisches 1:1 2:1 4:1
Kapitel 1 Formale Sprachen 1:1 2:1 4:1
Kapitel 2 Relationen 1:1 2:1 4:1
Kapitel 3 Ordnungen 1:1 2:1 4:1
Kapitel 4 Ordnungsdiagramme 1:1 2:1 4:1
Kapitel 5 Schranken und Extrema 1:1 2:1 4:1
Kapitel 6 Ordnungen auf Tupeln 1:1 2:1 4:1
Kapitel 7 Verbände 1:1 2:1 4:1
Kapitel 8 Rekursion und Iteration 1:1 2:1 4:1
Kapitel 9 Terminierende Fixpunktiteration 1:1 2:1 4:1
Kapitel 10 Regelsysteme 1:1 2:1 4:1
Kapitel 11 Normalformen 1:1 2:1 4:1
Kapitel 12 Chomsky-Grammatiken 1:1 2:1 4:1
Kapitel 13 Kontextfreie Strukturen 1:1 2:1 4:1
Kapitel 14 Endliche Automaten 1:1 2:1 4:1
Kapitel 15 Reguläre Sprachen 1:1 2:1 4:1
Kapitel 16 Normalisierung kontextfreier Grammatiken 1:1 2:1 4:1
Kapitel 17 Kellerautomaten 1:1 2:1 4:1
Kapitel 18 Turingmaschinen 1:1 2:1 4:1
Kapitel 19 Berechenbarkeit und Entscheidbarkeit 1:1 2:1 4:1
Übersichtsfolie Die Chomsky-Hierarchie 1:1


Programmbeispiele
  • Kapitel 1
  • Kapitel 2
    • Aktualisiert 10.5.04: Relationen in Haskell: rel.hs

Literatur

Als Begleitliteratur kann teilweise folgendes Buch dienen:

Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage. Spektrum Akademischer Verlag 2001 ISBN: 3827410991

Software: Hugs
  1. Eine Kurzanleitung zu Haskell gibt's hier.
  2. Die neueste Hugs-Version erhält man über
  3. Für Nutzer älterer Windows-Versionen: Das Programm, das Dateien mit der Extension .msi bearbeiten kann, erhält man über Die Datei instmsia.exe etwa nach \temp laden und dort ausführen - damit installiert sich der Installierer selbst.
  4. Nach Installation von Hugs bindet man dann am besten noch einen komfortablen Editor ein durch das Kommando
    • :set -E<Editor-Pfad>
    Dann läßt sich die jeweils zuletzt geladene Dateimit :e edieren.
    Achtung: Dabei nicht das abschließende Semikolon vergessen (sonst wird der aktuelle Suchpfad überschrieben statt verlängert)!
  5. Hat man sich aus Versehen doch den Pfad "zerschossen", läßt sich Hugs nicht mehr direkt starten, da die Datei prelude.hs nicht mehr gefunden wird. Abhilfe: Ein DOS-Fenster öffnen, zum Hugs-Verzeichnis navigieren und dort Hugs starten mit dem Aufruf
    • hugs -P<Hugs>\lib
    Anschließend können die Pfade wieder mit :set restauriert werden.
Bernhard Möller
Last update: 25.5.04