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.
| Dienstag, 25. November 2025 (7. Woche, KW 48) |
|
| Montag, 24. November 2025 (7. Woche, KW 48) |
Übung: wir haben den Aufgabenkomplex 1 besprochen. Eindeutigkeit der Darstellung als GF(2)-Polynom. Dann Darstellung einer booleschen Funktion $f: \{-1,1\}^n \rightarrow \{-1,1\}$ als multilineares Polynom über $\R$ und Eindeutigkeit der Darstellung. |
| Dienstag, 18. November 2025 (6. Woche, KW 47) |
Padding und warum P=NP dann auch EXP=NEXP impliziert. Unäre Sprachen und Bermans Theorem. |
| Montag, 17. November 2025 (6. Woche, KW 47) |
Effizient lösbare Sonderfälle von SAT: 2-SAT und Horn-SAT. Algorithmen für diese zwei Probleme (Resolution und deren Vollständigkeit) und warum es keine "Gadget-Reduktionen" von 3-SAT auf 2-SAT geben kann: der Majority-Polymorphismus. |
| Dienstag, 11. November 2025 (5. Woche, KW 46) |
Reduktion von 3-SAT auf 3-Colorability. Netz aus Reduktionen. Übung: Reduktion von SAT auf verschiedene Spezialfälle (Monoton, jede Variable nur 3 mal etc.) |
| Montag, 10. November 2025 (5. Woche, KW 46) |
Die Klassen P und NP. Reduktionen und NP-Vollständigkeit: alles reduziert auf Circuit SAT und somit auf SAT. Reduktion von SAT auf Independent Set. |
| Dienstag, 4. November 2025 (4. Woche, KW 45) |
Weiterhin Übung zu Kapitel 1: SAT als Modellierungssprache |
| Montag, 3. November 2025 (4. Woche, KW 45) |
Übung zu Kapitel 1: SAT als Modellierungssprache |
| Dienstag, 28. Oktober 2025 (3. Woche, KW 44) |
SAT und SAT als Modellierungssprache |
| Montag, 27. Oktober 2025 (3. Woche, KW 44) |
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. |