Ein Constraint ist eine Bedingung, die an Lösungen von Problemen gestellt wird. Solche Bedingungen treten bei den meisten Aufgabenstellungen auf: Werkzeugmaschinen können nur ein Produkt gleichzeitig anfertigen; Funkfrequenzen sollen so auf Funkgerte verteilt werden, dass möglichst wenige Interferenzen auftreten; in Computerspielen sollen automatische Spieler ein möglichst "intelligentes" Verhalten an den Tag legen, ohne die Spielregeln zu verletzen; beim Layout von Mikroprozessoren muss eine Anordnung der Basiselemente gefunden werden, bei dem alle benötigten Verbindungen möglich sind ohne dass überlange Konnektoren oder Hot-Spots auftreten.

Constraints sind ein Verfahren um viele Probleme anschaulich zu beschreiben ohne einen Lösunsalgorithmus angeben zu mssen. Für viele Constraintprobleme gibt es aber Algorithmen, die eine Lösung berechnen können. Daher ermöglichen Constraints gleichzeitig eine verständliche Spezifikation und eine effiziente Lösung vieler Probleme.

In diesem Seminar sollen Verfahren zur effizienten Lösung von Constraintproblemen behandelt werden. Dabei wird insbesondere auf Such- und Consistency Enforcement-Verfahren eingegangen. Weiterhin werde Methoden zur Lösung von Optimierungsproblemen und die damit zusammenhngenden Soft-Constraints behandelt.

Das Seminar besteht aus zwei Teilen: 4-5 doppelstündige Vorlesungen zur Vermittlung des grundlegenden Stoffs während des Semesters und eine Blockveranstaltung mit studentischen Vorträgen auf Frauenchiemsee am Ende des Semesters.

Literatur

• Edward Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993.  (PDF)

• Rina Dechter: Constraint Processing, Elsevier, 2003.

Veranstalter

• Prof. Dr. Martin Wirsing (0.58, Oettingenstr. 67; 2180 9154)
• Prof. Dr. Alexander Knapp (E0.6, Oettingenstr. 67; 2180 9179)

Betreuer

• Moritz Hammer (E0.9, Oettingenstr. 67; 2180 9182)
• Dr. Matthias Hölzl (E0.10, Oettingenstr. 67; 2180 9183)
• Philip Mayer (E10, Oettingenstr. 67; 2180 9134)
  
• Andreas Schroeder (E9, Oettingenstr. 67; 2180 9133)
• Gefei Zhang (E0.4, Oettingenstr. 67; 2180 9177)

Einführungsveranstaltung