Theory of Constraint Satisfaction Problems

 

Vorlesung im Sommersemester 2016

Ansprechpartner

Telefon

work
+49 241 80 21725

E-Mail

E-Mail
 
 

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

Martin Grohe