Themen und Termine
Termine
Alle Vorträge finden in E1.3 HS 001 statt.
- Mo, 14.3.: Folienvorträge
10:00 - 12:30 Uhr
Reihenfolge: Kuhn, Röhl, Wu, Kananizadeh, Lohse - Di, 15.3: Tafelvorträge
9:00 - 10:30 Kuhn
10:45 - 12:15 Röhl
13:30 - 15:00 Wu - Mi, 16.3: Tafelvorträge
9:00 - 10:30 Kananizadeh
10:45 - 12:15 Lohse
Die Startzeiten an jedem Tag sind fix. Die weiteren Zeiten richten sich dann nach der tatsächlichen Dauer der Vorträge.
Themen
Kozen, Automata and Computatbility:
- Kapitel 17 und 18: 2DFAs (Iona Kuhn)
- Kapitel J: Beyond Undecidability - Arithmetic Hierarchy (s. auch ToC Kapitel 35, 36)
Kozen, Theory of Computation:
- Kapitel 1: Untere Schranken durch Crossing-Sequenzen
- Kapitel 32: Gap Theorems
Schöning & Pruim, Gems of Theoretical Computer Science:
(elektronischer Zugang anscheinend nur über die MPI-Domain. Melden Sie sich bitte, wenn Sie Zugang brauchen.)
- Kapitel 1: Post's Problem (s. auch Kozen ToC, 37 & 38)
- Kapitel 2: Hilbert's 10th Problem (Lisa Röhl)
- Kapitel 3: The Equivalence Problem for LOOP(1) and LOOP(2) Programs
- Kapitel 8 und 9 (Auswahl): Kolmogorov-Komplexität
- Kapitel 23: Superconcentrators and the Marriage Theorem (Alexander Ikonomou)
Schöning, Theoretische Informatik - kurzgefasst
(gibt es nur gedruckt; sie können hier auch das TI-Skript verwenden)
- Kapitel 2.4 Primitiv- und mu-rekursive Funktionen (Hongroi Wu)
- Kapitel 2.5 Ackermann-Funktion (Yunus Kananizadeh)
- Kapitel 2.9 Der Gödelsche Satz (Janine Lohse)