Der Stundenplan dient als Tagebuch, um festzuhalten, was wir tatsächlich in den Vorlesungen gemacht haben. Hier kündige ich auch an, welche Übungsaufgaben Sie bis zum nächsten Termin anschauen sollten.
| Montag, 27. Oktober 2025 (2. Woche, KW 43) |
Definition von Laufzeit. Das Speedup-Theorem, allerdings recht informell. Das Cook-Levin-Theorem: wie man für eine feste Input-Größe $n$ eine Turingmaschine mit Laufzeit $t(n)$ in einen effizienten Schaltkreis ($O(t^2)$ Gatter) umwandelt. |
| Dienstag, 21. Oktober 2025 (2. Woche, KW 43) |
Wie man nichtdeterministische Turingmaschinen deterministisch simulieren kann.
Nichtdeterministische Turingmaschinen als Maschinen mit einem Eingabeband und einem zusätzlichen
Zertifikatband.
Übung, zum Großteil nochmals zum Thema Schaltkreise. |
| Montag, 20. Oktober 2025 (2. Woche, KW 43) |
Turingmaschinen. Wir haben eine Turingmaschine für die Sprache $\{wcw \ | \ w \in \{0,1\}^* \}$ gebaut. Mehrband-Turingmaschinen und wie man die simulieren kann. Nichtdeterministische Maschinen. Übergangsrelation statt -funktion. |
| Dienstag, 14. Oktober 2025 (1. Woche, KW 42) |
Übung zum Thema Schaltkreise. |
| Montag, 13. Oktober 2025 (1. Woche, KW 42) |
Schaltkreise im Schnelldurchgang. Wahrheitstabelle, DNF, CNF, Top-Down-Konstruktion einer Formel. Warum man jede Funktion als DNF mit maximal $2^{n-1}$ Termen schreiben kann; warum es für Parity nicht besser geht. |