Lehre WS24/25
Inhalt
Die Komplexitätstheorie klassifiziert Berechnungsprobleme gemäss algorithmischen Ressourcen wie Berechnungszeit oder Speicherplatz, die zu ihrer Lösung benötigt werden. Ziel ist ein theoretisches Verständnis davon welche Berechnungsprobleme effiziente Algorithmen erlauben und welche nicht. Eine zentrale Rolle spielt die Klasse P der in polynomieller Zeit lösbaren Berechnungsprobleme. Das zentrale Problem ist das P versus NP Problem, eines der Millenniumsprobleme der Mathematik, und Smale zufolge eines der drei grössten offenen Probleme der Mathematik. Die Vorlesung bietet eine Einführung in dieses Problem und die es umgebende Theorie.
Auf StudIP findet sich ein wöchentlich aktualisiertes Skript des aktuellen Standes.
Vorlesungen
Dienstag 12:00-14:00 IM HS 12
Mittwoch 12:00-14:00 JUR SR 147a
Übungen
Donnerstag 12:00-14:00 JUR SR 059
Literatur
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Das Pro-/Seminar behandelt die Theorie des Resolutionskalküls, der simpelste aller aussagenlogischen Kalküle. Er spielt in der Informatik eine zentrale Rolle und liegt insbesondere automatischen Theorembeweisern und SAT-Solvern zugrunde.
Eine Menge aussangenlogischer Klauseln ist genau dann unerfüllbar, wenn sie in diesem Kalkül widerlegbar ist. Zentrales Thema des Pro-/Seminars ist es, untere Schranken an die Längen solcher Widerlegungen zu zeigen.
Das Pro-/Seminar richtet sich an Studierende mit Grundkenntnissen in Logik, vorausgesetzt werden diese aber nicht. Es eignet sich auch als erster Kontakt mit der mathematischen Logik.
Das Oberseminar ist eine gemeinsame Veranstaltung mit Tobias Kaiser. Es beinhaltet Forschungsvorträge der Arbeitsgruppen und ihrer Gäste. Fortgeschrittene Studierende, die ihr Wissen in mathematischer Logik und/oder Komplexitätstheorie vertiefen wollen, können hier über ein gemeinsam gewähltes und gemeinsam erarbeitetes Thema vortragen.
Programm pdf
Bei einem Constraint Satisfaction Problem (CSP) geht es darum, zu entscheiden, ob es eine Zuordnung zu gegebenen Variablen gibt, die sich über einen bestimmten Bereich erstrecken und eine gegebene Menge von Beschränkungen erfüllen. Äquivalent dazu wird nach einem Homomorphismus zwischen gegebenen Strukturen gefragt. Ein berühmtes Beispiel ist das Erfüllbarkeitsproblem für den booleschen Bereich (SAT).
Die Geschichte der CSPs begann vor 50 Jahren, und in den letzten 25 Jahren spielen CSPs in der gesamten Informatik eine wichtige Rolle. Einerseits erlauben sie es, eine Vielzahl von kombinatorischen Problemen (in der Mathematik, Informatik, künstlichen Intelligenz...) auf natürliche und treue Weise zu modellieren. Andererseits sind sie mit allgemeinen algorithmischen Techniken für ihre Lösung oder allgemeinen Gründen für ihre Rechenhärte verbunden. Diese Techniken basieren auf der universellen Algebra.
Der Kurs bietet eine Einführung in den algebraischen Ansatz für CSPs. Kenntnisse der universellen Algebra werden nicht vorausgesetzt, sondern nach Bedarf entwickelt. Auch Kenntnisse der mathematischen Logik werden nicht vorausgesetzt. Die Studierenden sollten jedoch über Grundkenntnisse der Computerkomplexität verfügen, z.B. auf dem Niveau der Theoretischen Informatik II. Die Vorlesung wird von Übungen begleitet. Die Veranstaltung wird in englischer Sprache durchgeführt und richtet sich an Masterstudierende. Details sind auf StudIP zu finden.
Diese Seite teilen
