Constraint-Programmierung

Frontmatter

1. Einleitung

Zusammenfassung

Das englische Wort „Constraint“ bedeutet Einschränkung oder (Wert-, Rand-, Neben-)Bedingung. Constraints¹ eignen sich zur Darstellung unvollständiger Information, also zur Beschreibung der Eigenschaften und Beziehungen von teilweise unbekannten Objekten. Als recht allgemeiner und abstrakter Begriff haben Constraints die verschiedensten Ausprägungen und Arten. (Doch haben sie alle wichtige Gemeinsamkeiten, wie wir sehen werden.)

Thom Frühwirth, Slim Abdennadher

2. Prädikatenlogik und Kalküle

Zusammenfassung

Im ersten Abschnitt fixieren wir die Syntax der Prädikatenlogik erster Stufe, d.h. die verwendete Sprache. Die Semantik, also die Bedeutung der Sprache, wird im zweiten Abschnitt definiert. Im letzten Abschnitt werden logische Kalküle formal beschrieben. Ein logischer Kalkül sagt uns, wie man in einer Sprache der Logik rechnen kann.

Thom Frühwirth, Slim Abdennadher

3. Logikprogrammierung

Zusammenfassung

A logic program is a set of axioms or rules defining relationships between objects. A computation of a logic program is a deduction of consequences of the program. A program defines a set of consequences which is its meaning. The art of logic programming is constructing concise and elegant programs that have the desired meaning.

Thom Frühwirth, Slim Abdennadher

4. Constraint-Logikprogrammierung

Zusammenfassung

Die Constraint-Logikprogrammierung (CLP) entstand Mitte der achtziger Jahre als natürliche Fusion zweier deklarativer Paradigmen: Lösen von Constraints und Logikprogrammierung (Abb. 4.1).

Thom Frühwirth, Slim Abdennadher

5. Constrainterweiterungen

Zusammenfassung

In diesem Abschnitt¹ wollen wir uns mit zusätzlichen deklarativen Konstrukten beschäftigen, die die Programmierung mit Constraints flexibler machen. Diese Erweiterungen basieren auf der Idee, daß man nicht nur Konjunktionen von Constraintatomen, sondern beliebige Formeln von Constraints erlauben und behandeln können möchte.

Thom Frühwirth, Slim Abdennadher

6. Nebenläufige CL-Programmierung

Zusammenfassung

Nebenläufige Constraint-Logikprogrammierung (NCLP) (engl. concurrent constraint (CC) logic programming) kombiniert nebenläufige logische Programmierung [Sha89] mit Ideen der Constraint-Logikprogrammierung [Mah87] (Abb. 6.1). Das erste vereinheitlichte Modell für diese unterschiedlichen Sprachfamilien wurde mit der CC-Sprachfamilie [Sar93] vorgeschlagen.

Thom Frühwirth, Slim Abdennadher

7. Constraint Handling Rules

Zusammenfassung

Die Erfahrungen mit kommerziellen Anwendungen zeigen, daß oftmals kein homogenes Constraintproblem vorliegt, sondern eine subtile Kombination verschiedenster Constraintsysteme (siehe Kapitel 9). Häufig treten auch neuartige Constraints auf, die nur mit viel Aufwand in existierende Constraints übersetzt werden können. Oft ist die Übersetzung mit einem Verlust an Vollständigkeit verbunden.

Thom Frühwirth, Slim Abdennadher

8. Constraintsysteme

Zusammenfassung

In diesem Kapitel stellen wir alle gängigen Constraintsysteme vor. Für sie existiert eine Vielzahl von Varianten und Algorithmen, von denen wir aus didaktischen Gründen die anschaulicheren Verfahren näher betrachten. Diese Algorithmen stammen meist aus der Forschung im Bereich der Künstlichen Intelligenz. Um die Algorithmen zu spezifieren und gleichzeitig als Constraintlöser zu implementieren, verwenden wir die Constraint Handling Rules (CHR) aus Kapitel 7 mit Prolog als Basissprache. Damit können wir kompakt und deklarativ die wesentlichen Aspekte der Algorithmen beschreiben. Zu jedem Constraintsystem gibt es auch Ubungsaufgaben und teilweise Lösungsvorschläge, die im Anhang zu finden sind.

Thom Frühwirth, Slim Abdennadher

9. Anwendungen

Zusammenfassung

Seit Anfang der neunziger Jahre wird Constraint-Programmierung mit Erfolg von mehreren Firmen (Ilog mit Numerica, IlogSolver und IlogSchedule, Cosytec mit CHIP 4, Siemens Nixdorf mit IFProlog, Prologia mit Prolog IV) weltweit kommerziell eingesetzt. Die Zahl der kommerziellen Anwendungen wurde 1996 auf 300 geschätzt, der Umsatz mit Constrainttechnologie auf etwa 100 Millionen US-Dollar, mit steigender Tendenz [Wa196]. Die erwähnten Firmen haben jeweils mehrere hundert Kunden für ihre constraintbasierten Produkte gefunden. Während Frankreich, Großbritannien, USA und Asien stark wachsende Märkte für constraintbasierte Entscheidungshilfesysteme sind, ist der Markt in Deutschland erst im Entstehen.

Thom Frühwirth, Slim Abdennadher

10. A Übungsaufgaben und Lösungsvorschläge

Zusammenfassung

Die in diesem Anhang zusammengestellten Übungsaufgaben sind als Anregung gedacht, die vorgestellten Konzepte, Definitionen und Verfahren zu vertiefen. Die meisten der Übungsaufgaben sind in den unterschiedlichsten Constraint-Programmiersprachen und Constraintsystemen lösbar und wurden bereits im Rahmen von Lehrveranstaltungen verwendet. Weitere Übungsaufgaben und Lösungen finden Sie im Internet auf den Webseiten für dieses Lehrbuch (Adresse siehe Vorwort).

Thom Frühwirth, Slim Abdennadher

Backmatter