Datum | Aufzeichnungen | Inhaltsverzeichnis |
---|---|---|
Mi. 19.10.2016 | Vorlesung 1 | §0 Vorbereitung: O-Notation |
Fr. 21.10.2016 | Vorlesung 2 | Teil A: Logik und Berechenbarkeit Kapitel 1 Aussagenlogik §1 Syntax der Aussagenlogik §2 Semantik der Aussagenlogik |
Mi. 26.10.2016 | Vorlesung 3 | §3 Äquivalenz und Normalformen |
Fr. 28.10.2016 | Vorlesung 4 | §4 "Schnelle", randomisierte Algorithmen für das Erfüllbarkeitsproblem von k-KNF-Formeln |
Mi. 2.11.2016 | Vorlesung 5 | §5 Resolution |
Fr. 4.11.2016 | Vorlesung 6 | |
Mi. 9.11.2016 | Vorlesung 7 | Kapitel 2 Prädikatenlogik §1 Syntax der Prädikatenlogik §2 Semantik der Prädikatenlogik |
Fr. 11.11.2016 | Vorlesung 8 LEGO Turing Machine | Kapitel 3 Berechenbarkeit §1 Turingmaschine und Church-Turing These |
Mi. 16.11.2016 | Vorlesung 9 | |
Fr. 18.11.2016 | Vorlesung 10 | §2 Unentscheidbarkeit |
Mi. 23.11.2016 | Vorlesung 11 | |
Fr. 25.11.2016 | Vorlesung 12 | |
Mi. 30.11.2016 | Vorlesung 13 | |
Fr. 2.12.2016 | Vorlesung 14 | Teil B: Komplexitätstheorie Kapitel 4 NP-Vollständigkeitstheorie §1 Die Klassen P und NP |
Mi. 7.12.2016 | Vorlesung 15 | §2 Das Cook-Levin Theorem |
Fr. 9.12.2016 | Vorlesung 16 | §3 Die 21 NP-vollständigen Probleme von Karp und weitere |
Mi. 14.12.2016 | Vorlesung 17 | |
Fr. 16.12.2016 | Vorlesung 18 | §4 Such- und Entscheidungsprobleme §5 NP-unvollständige Probleme |
Mi. 21.12.2016 | Vorlesung 19 | Kapitel 5 Weitere Komplexitätsklassen §1 Randomisierte Berechnung |
Mi. 11.1.2017 | Vorlesung 20 | §2 Die Polynomielle Hierarchie |
Fr. 13.1.2017 | Vorlesung 21 | |
Mi. 18.1.2017 | Vorlesung 22 | §3 Interaktive Beweise |
Fr. 20.1.2017 | Vorlesung 23 | |
Mi. 25.1.2017 | Vorlesung 24 | |
Fr. 27.1.2017 | Vorlesung 25 | |
Mi. 1.2.2017 | Vorlesung 26 | §4 Das PCP Theorem und seine Konsequenzen |
Mi. 3.2.2017 | Vorlesung 27 |