Grundlagen der theoretischen Informatik
Die Klausurergebnisse zur Nachklausur finden Sie hier
Übungen
- Nachklausur
- Hauptklausur
- Probeklausur
- Blatt 1
- Blatt 2
- Blatt 3
- Blatt 4
- Blatt 5
- Blatt 6
- Blatt 7
- Blatt 8
- Blatt 9
- Blatt 10
- Blatt 11
Lösungen
- Lösungen zur Nachklausur
- Lösungen zur Hauptklausur
- Lösungen zur Probeklausur
- Lösungen zu Blatt 1
- Lösungen zu Blatt 2
- Lösungen zu Blatt 3
- Lösungen zu Blatt 4
- Lösungen zu Blatt 5
- Lösungen zu Blatt 6
- Lösungen zu Blatt 7
- Lösungsskizze zu Blatt 8
- Lösungsskizze zu Blatt 9
- Lösungsskizze zu Blatt 10
- Lösungsskizze zu Blatt 11
Unterlagen
- Komplette Folien für Teil 1
- Folien (09.04.2013)
- Folien (11.04.2013) (Update: 12.04.2013)
- Folien (16.04.2013)
- Folien (18.04.2013)
- Folien (23.04.2013)
- Folien (30.04.2013)
- Folien (02.05.2013)
- Folien (07.05.2013)
- Folien (07.05.2013, Teil 2)
- Folien (14.05.2013)
- Folien (16.05.2013)
- Folien (23.05.2013)
- Folien (28.05.2013)
- Folien (04.06.2013)
- Index für Teil 1 (Update: 13.08.2013)
- Folien zur Berechenbarkeit (Update: 10.06.2013)
- Folien zu Turingmaschinen (Update: 13.06.2013)
- Folien zur universellen Turingmaschine (Update: 13.06.2013)
- Folien zu While- und Loop-Programmen (Update: 19.06.2013)
- Folien zu rekursiven Funktionen (Update: 03.07.2013)
- Folien zu Äquivalenzen der Berechenbarkeitsmodelle (Update: 03.07.2013)
- Folien zu Entscheidungsproblemen und dem Halteproblem (Update: 10.07.2013)
- Folien zu Komplexität (Update: 22.07.2013)
- Interaktive Beispiele zu Turingmaschinen
Literatur
Harry R. Lewis, Christos H. Papadimitriou: Elements of the theory of computation, Prentice Hall
Der Stoff der Vorlesung orientiert sich hauptsächlich an diesem Buch, vor allem die verwendeten Notationen und Begriffe.
Alexander Asteroth, Christel Baier: Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen, Pearson Studium
Das Buch beginnt zwar mit Berechenbarkeit, soll es aber auch ermöglichen, zuerst die Kapitel über formale Sprachen zu lesen.
John E. Hopcroft, Jeffrey D. Ullmann: Introduction to automata theory, languages, and computation, Addison Wesley
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann: Introduction to automata theory, languages, and computation, Pearson, Addison Wesley
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullmann: Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit, Pearson Studium
Eine deutsche Übersetzung, von der eher abzuraten ist.
Uwe Schöning: Theoretische Informatik - kurz gefasst (5. Edition), Spektrum Akademischer Verlag, 2008, ISBN 3827418240, 9783827418241