Theory of Constraint Satisfaction Problems
Vorlesung im Sommersemester 2019
Ansprechpartner
Name
- E-Mail schreiben
Termine
Vorlesung:
Di, 08:30 - 10:00 Uhr im 5055
Do, 14:30 - 16:00 Uhr im 5055
Übung:
Fr, 10:30 - 12:00 Uhr im 5054
Inhalt
Ein Constraint-Satisfaction-Problem (CSP) bedingt, dass Werte Variablen zugewisen werden, die bestimmten Beschränkungen unterliegen. CSPs traten erstmals in den siebzigern auf, um Berechnungsprobleme, die in der Bildverarbeitung auftraten, abzubilden. Es wurde schnell erkannt, dass beschränke Erfüllbarkeit zu einem mächtigen Rahmenwerk führt, mit dem eine breite Auswahl von kombinatorischen Problemen dargestellt werden können. Heutzutage sind CPS allgegenwärtig in vielen verschieden Bereichen der Informatik, angefangen bei künstlicher Intelligenz und Datenbanksystemen, bis hin zu Entwicklung von Schaltkreisen, Netzwerkoptimierung und der Theorie von Programmiersprachen.
Es ist daher wichtig effiziente Algorithmen zur Lösung dieser CSP zu entwickeln, wenn nicht mit exakter dann mit annähernder Lösung, und ihre Komplexitätstheoretischen Grenzen zu verstehen. In den letzen 20 Jahren entstand eine umfassende Theorie um diese Fragen, die Verbindungen zu vielen anderen Abzweigungen der theoretischen Informatik und Mathematik besitzt.
Literatur
R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.
K.R. Apt. Principles of Constraint Programming. Cambridge University Press, 2003.
Organisation
Vortragssprache in Englisch.
Dozent