Logik in der Informatik
Prof. Dr. Martin Grohe

Logbuch zur Vorlesung Parametrische Algorithmen und Komplexitätstheorie

Mo, 14. 4. 2008: Organisatorisches; Einführung; Skript Seiten 1-5 (Kapitel 1): parametriserte Probleme, XP, FPT, para-NP, einfache Eigenschaften.
Mi, 16. 4. 2008: Skript Seiten 7-9 (Kapitel 2 bis Definition 2.14): Methode der beschränkten Suchbäume für vertex covers und hitting sets.
Mo, 21. 4. 2008: Skript Seiten 9-11 (Kapitel 2 bis Definition 2.25): Gradbeschränktes dominating set und planare Graphen.
Mi, 23. 4. 2008: Skript Seite 12 (Ende Kapitel 2): FPT für dominierende Mengen planarer Graphen.
Mo, 28. 4. 2008: Skript Seiten 13-14 (Kapitel 3, Abschnitt 3.1): Definition W[P], Charakterisierung durch Zertifikate.
Mi, 30. 4. 2008: Skript Seiten 14-15 (Kapitel 3, Abschnitt 3.2): Reduktionen, Beispiele, Vollständigkeit, W[P]-Vollständigkeit von p-Nondeterministic-Acceptance.
Mo, 5. 5. 2008: Skript Seiten 15-18 (Kapitel 3, Abschnitt 3.2 und 3.3): Schaltkreise, W[P]-vollständige Schaltkreisprobleme, RAM Syntax und Konfigurationen.
Mi, 7. 5. 2008: Skript Seiten 18-20 (Kapitel 3, Abschnitt 3.3 und Kapitel 4, Abschnitt 4.1): Nichtdeterministische RAMs für von W[P], Alternative Charakterisierungen FPTs (noch ohne Beweis).
Mi, 14. 5. 2008: Skript Seiten 20-21 (Kapitel 4, Abschnitte 4.1 und 4.2): Alternative Charakterisierungen FPTs (Beweis), Erste Kernelisierung p-Vertex-Cover, Sonnenblumen.
Mo, 19. 5. 2008: Skript Seite 21 (Kapitel 4, Abschnitt 4.2): Sonnenblumenlemma, Kernelisierung p-c-Hitting-Set, lineare Programmierung.
Mi, 21. 5. 2008: Skript Seiten 21-24 (Kapitel 4, Abschnitt 4.2 und Kapitel 5, Abschnitt 5.1): Kernelisierung für p-Vertex-Cover durch lineare Programmierung, Definition W[1], W[2], erste Eigenschaften.
Mo, 26. 5. 2008: Skript Seiten 24-25 (Kapitel 5, Abschnitte 5.1 und 5.2): Reduktionen zwischen p-Clique, p-Hitting-Set, Akzeptanzproblemen und Constraint-Satisfaction-Problemen.
Mi, 28. 5. 2008: Skript Seiten 25-26 (Kapitel 5, Abschnitt 5.2): Erste W[1]-Vollständigkeiten, aussagenlogische Formelklassen, p-WSAT, p-PSAT
Mo, 2. 6. 2008: Skript Seiten 26-27 (Kapitel 5, Abschnitt 5.2): Reduktion von p-WSAT auf p-PSAT, W[1]-Vollständigkeit von p-WSAT und p-PSAT, Vokabulare, Strukturen, Syntax der Logik erster Stufe.
Mi, 4. 6. 2008: Skript Seiten 27-28 (Kapitel 5, Abschnitte 5.2 und 5.3): Syntax und Semantik der Logik erster Stufe, Σ₁ und ähnliche Teilklassen, W[1]-vollständige model-checking-Probleme; gewichtete Fagin-Definitionen.
Mo, 9. 6. 2008: Skript Seite 28 (Kapitel 5, Abschnitte 5.3 und 5.4): Charakterisierung von W[1] durch gewichtete Fagin-Definitionen und als κ-endnichtdeterministisches W[P]; erste Reduktionen für W[2]-Vollständigkeiten.
Mi, 11. 6. 2008: Skript Seiten 28-29 (Kapitel 5, Abschnitt 5.4): W[2]-vollständige aussagenlogische Probleme, W[2}-Vollständigkeit von p-Hitting-Set.
Mo, 16. 6. 2008: Skript Seite 29 (Kapitel 5, Abschnitt 5.4): W[2]-Vollständigkeit von p-Dominating-Set, Charakterisierung von W[2] durch gewichtete Fagin-Definitionen, W[2]-vollständige Model-Checking-Probleme (unfertig).
Mi, 18. 6. 2008: Skript Seiten 29-30 (Kapitel 5, Abschnitte 5.4 und 5.5): W[2]-vollständige Model-Checking-Probleme; monotoner/antotoner Kollaps für W[2]/W[1].
Mo, 23. 6. 2008: Skript Seiten 30-33 (Kapitel 5, Abschnitt 5.6 und Kapitel 6, bis Abschnitt 6.1): Die W-Hierarchie; Tree-Independent-Set, HR-Terme, Fenster, Weite, p-HR-Independent-Set.
Mi, 25. 6. 2008: Skript Seiten 33-36 (Kapitel 6, Abschnitte 6.1 bis 6.3): Probleme über HR-Termen, p-HR-CNF-Sat, MSO, Typen.
Mo, 30. 6. 2008: Skript Seite 36 (Kapitel 6, Abschnitt 6.3): Typen und Formeln, Typen und Redukte, Typen und Summen.
Mi, 2. 7. 2008: Skript Seite 36 (Kapitel 6, Abschnitte 6.3 und 6.4): Typen und Summen, p-MC_HR(MSO) ist in FPT, p-WD_HR(MSO).
Mo, 7. 7. 2008: Skript Seiten 36-37 (Kapitel 6, Abschnitte 6.4 und 6.5): p-WD_HR(MSO) ist in FPT, Baumzerlegungen von Strukturen.
Mi, 9. 7. 2008: Skript Seiten 37-38 (Kapitel 6, Abschnitte 6.5 und 6.6): Vergleich Baumzerlegungen und HR-Terme, Baumzerlegungen von Graphen, Vergleich mit denen von Strukturen; Trenner, balancierte Trenner.
Mo, 14. 7. 2008: Skript Seiten 38-39 (Kapitel 6, Abschnitt 6.6): Berechnen balancierter Trenner, Approximieren von Baumzerlegungen, Folgerungen.
Mi, 16. 7. 2008: Skript Seiten 39-40 (Kapitel 6, Abschnitte 6.7 und 6.8): Probleme mit ohne Einschränkung kleiner Baumweite, Beispiele p-Feedback-Vertex-Set, p-Convex-Recolouring; Erweiterung auf GSO; Ende der Vorlesung.

Mark Weyer