Vorlesung

DatumAufzeichnungenInhaltsverzeichnis
Mi. 19.10.2016Vorlesung 1§0 Vorbereitung: O-Notation
Fr. 21.10.2016Vorlesung 2Teil A: Logik und Berechenbarkeit
Kapitel 1 Aussagenlogik
§1 Syntax der Aussagenlogik
§2 Semantik der Aussagenlogik
Mi. 26.10.2016Vorlesung 3§3 Äquivalenz und Normalformen
Fr. 28.10.2016Vorlesung 4§4 "Schnelle", randomisierte Algorithmen für das Erfüllbarkeitsproblem von k-KNF-Formeln
Mi. 2.11.2016Vorlesung 5§5 Resolution
Fr. 4.11.2016Vorlesung 6
Mi. 9.11.2016Vorlesung 7Kapitel 2 Prädikatenlogik
§1 Syntax der Prädikatenlogik
§2 Semantik der Prädikatenlogik
Fr. 11.11.2016Vorlesung 8

LEGO Turing Machine
Kapitel 3 Berechenbarkeit
§1 Turingmaschine und Church-Turing These

Mi. 16.11.2016Vorlesung 9
Fr. 18.11.2016Vorlesung 10
§2 Unentscheidbarkeit
Mi. 23.11.2016Vorlesung 11
Fr. 25.11.2016Vorlesung 12
Mi. 30.11.2016Vorlesung 13
Fr. 2.12.2016Vorlesung 14
Teil B: Komplexitätstheorie
Kapitel 4 NP-Vollständigkeitstheorie
§1 Die Klassen P und NP
Mi. 7.12.2016Vorlesung 15
§2 Das Cook-Levin Theorem
Fr. 9.12.2016Vorlesung 16
§3 Die 21 NP-vollständigen Probleme von Karp und weitere
Mi. 14.12.2016Vorlesung 17
Fr. 16.12.2016Vorlesung 18
§4 Such- und Entscheidungsprobleme
§5 NP-unvollständige Probleme
Mi. 21.12.2016Vorlesung 19
Kapitel 5 Weitere Komplexitätsklassen
§1 Randomisierte Berechnung
Mi. 11.1.2017Vorlesung 20§2 Die Polynomielle Hierarchie
Fr. 13.1.2017Vorlesung 21
Mi. 18.1.2017Vorlesung 22§3 Interaktive Beweise
Fr. 20.1.2017Vorlesung 23
Mi. 25.1.2017Vorlesung 24
Fr. 27.1.2017Vorlesung 25
Mi. 1.2.2017Vorlesung 26§4 Das PCP Theorem und seine Konsequenzen
Mi. 3.2.2017Vorlesung 27