Empfehlenswerte Bücher
- Introduction to the Theory of Computation. 2. Auflage, PWS 2005 Auf diesem Buch basiert die Lehrveranstaltung. Es ist nach unserer Ansicht der beste Einführungstext in die theoretische Informatik. Leider ist es in Deutschlang recht teuer, aber vielleicht gebraucht zu bekommen (die erste Auflage von 1997 ist übrigens fast identisch).
-
Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
4. Auflage,
Oldenbourg Verlag
2000
Dieses Buch basiert auf der 1979er Ausgabe des englischsprachigen
Originals. Es ist etwas detaillierter als das Buch von Sipser, dafür
fehlen einige modernere Ergebnisse. Im Handel ist es nicht mehr
erhältlich, aber gebraucht günstig zu bekommen und in vielen
Bibliotheken vorrätig.
Achtung: Es gibt ein gleichnamiges Buch von Hopcroft, Ullman und Motwani, das 2002 bei Pearson erschienen ist. Dies ist jedoch ein völlig anderes Buch und aus unserer Sicht nur bedingt zu empfehlen. Dafür ist es recht günstig. - Introduction to Languages and the Theory of Computation. 3. Auflage, McGraw-Hill 2002 Ein gutes Buch, das alle Standardthemen abdeckt.
- Theoretische Informatik - kurzgefasst. 4. Auflage, Spektrum Akademischer Verlag 2001 Eine knappe, aber angenehm zu lesende Einführung in die theoretische Informatik.
Folien und weitere Materialien zur Vorlesung
- Automatendiagramme zu Kapitel 3
- Die Unentscheidbarkeit extensionaler Eigenschaften von Turingmaschinen — der Satz von Rice Ein Einführungstext zur funktionalen Reduktion von Sprachen und zum Satz von Rice.
- Folien zur Vorlesung 12: Klasse BPP, Primzahltest, Branching Programme
Referenzen zum Lambda-Kalkül
Im Folgenden finden Sie einige von uns empfohlene Referenzen zu diesem Thema:
- Introduction to Functional Programming (John Harrison) Ein sehr guter Kurs zur funktionalen Programmierung, der auch eine Einführung in den Lambda-Kalkül umfasst. Für die Vorlesung sind die Kapitel 2 (Lambda calculus) und 3 (Lambda calculus as a programming language) relevant.
- Einführung in den Lambda-Kalkül (André Metzner) Ein guter Einführungstext in den Lambda-Kalkül, der alle Themen behandelt, die Sie über den Lambda-Kalkül wissen sollten (und noch etwas mehr). Für die Vorlesung spielt nur der Abschnitt über untypisierte Lambda-Kalküle eine Rolle.
- Das gefürchtete Lambda-Kalkül (Fabian Nilius) Eine Einführung in den Lambda-Kalkül in Form eines Vortrags. Der Y-Kombinator wird recht gut erklärt. Allerdings enthält der Text ein paar kleinere Fehler und einige Details kommen etwas zu kurz.
- Funktionale und logische Programme (Christoph Kreitz) Die Folien zum Lambda-Kalkül aus der Vorlesung Theoretische Informatik II von Professor Kreitz. Diese Vorlesung ist auch als Video verfügbar (erfordert allerdings den Real Player). Der zweite Teil zur arithmetischen Repräsentation spiel für die Vorlesung keine Rolle.
- Der Lambda-Kalkül (Christoph Kreitz) Die Folien zum Lambda-Kalkül aus der Vorlesung Automatisierte Logik und Programmierung von Professor Kreitz. Das zugehörige Skript enthält eine recht detaillierte Darstellung des Lambda-Kalküls und seiner Eigenschaften. Die behandelten Themen gehen allerdings um Einiges über das hinaus, was für unsere Vorlesung erforderlich ist.
