Eine Einführung in das EcliPse System

... [ Seminarthemen SS01 ] ... [ Inhaltsverzeichnis ] ... [ Das ECLiPSe System ] ...

Einführung in CLP

Einleitung

 Allgemein betrachtet besteht ein Algorithmus aus zwei Hauptkomponenten, der Logik und der Steuerung. Die Logik ist verantwortlich für das WAS (Was wollen wir berechnen), während die Kontrolle für das WIE (Wie soll dieses Ergebnis erreicht werden) zuständig ist.

Die Idealform einer Programmiersprache sollte sich zunächst mit der Logik und erst dann mit der Steuerung beschäftigen. Das Interessante an dem Ansatz der logischen Programmierung ist, daß es dieser Idealform sehr nahe kommt, indem es diese beiden Komponenten voneinander trennt. Der Programmierer ist für die Beschreibung des Problems, der Computer für die Lösung zuständig.

Damit steht die Methodik der logischen Programmierung der der herkömmlichen Programmiersprachen diametral gegenüber. Hierin liegt aber der Grund, warum sich die logische Programmierung mehr als andere Programmiersprachen für die Lösung von komplexen kombinatorischen Such- und Optimierungsproblemen eignen, in der die Elemente mittels sogenannter Constraints (Bedingungen) in Beziehung stehen.

Constraints

 Das englische Wort "Constraints" bedeutet Einschränkung oder Bedingung. Constraints eignen sich für die Beschreibung unvollständiger Informationen, also zur Beschreibung der Eigenschaften und Beziehungen von teilweise unbekannten Objekten. Zur Verdeutlichung sei ein einfaches Beispiel angeführt: Gerhard hat die letzte Ziffer seiner EC-Geheimzahl vergessen. Er weiß nur noch, daß es sich um eine ungerade Zahl handelt, die eine Primzahl ist. Desweiteren ist er sich sicher, daß es sich nicht um die eins handelt. Mit dieser Einschränkung beschränkt sich der Suchraum auf nur drei Zahlen, die er ohne Probleme am Automaten durchprobieren kann.
Etwas formaler gefaßt definieren Constraints Beziehungen zwischen einer Menge von Variablen X={x1,...,xn}, wobei die Werte, die von den Variablen angenommen werden können, im Vordergrund stehen. Die Wertemenge Wi einer Variablen xi wird Domain genannt. Das Ziel ist es, eine eindeutige Belegung für alle Variablen zu finden, so daß keine Widersprüche bezüglich der aufgestellten Menge von Constraints entstehen, das heißt, die Werte der Variablen erfüllen die Constraints. Es werden drei Arten von Constraints unterschieden: Die unären Constraints beziehen sich auf eine, die binären auf zwei und die u-nären setzen mehr als zwei Variablen miteinander in Beziehung, z.B. "X1+X2=X3". Die meisten Algorithmen der Constraint-Programmierung basieren allerdings auf einer Repräsentation des Problems mit maximal binären Constraints. Es wurden deshalb Verfahren entwickelt, n-äre Constraints auf binäre Constraints zurückzuführen.

Constraint-Programmierung

Mit der Einbettung von Constraints in die Logikprogrammiersprachen wurde es möglich, schnell und effizient komplexe Probleme mittels einer Kombination von Constraintlösen und Suche zu lösen. Der wesentliche Vorteil basiert auf der Forschungsarbeit die im Bereich der Constraints Solver geleistet wurde. Das Lösen von Constraints zielt auf das Vermeiden des "generate and test" Paradigmas durch die Verkleinerung des Suchraumes. Es wird also nicht ein vollständiger Suchbaum aufgezogen, in dem durch Tiefensuche gültige Lösungen gesucht werden, sondern es wird versucht zunächst die Constraints zu lösen, um ein Suchbaum aufzuspannen, der im günstigsten Fall nur noch aus gültigen Lösungen besteht. Die Realisation einer solchen Methode nennt man das "constrain-and-generate" Paradigma.

Dieses Kombination ist bekannt als CLP(X) Schemata, wobei X für die Art der zu behandelnden Elemente steht. CLP(R) zum Beispiel wird genutzt, wenn das Programm mit reellen Werten arbeitet, ein Thema zu dem in einem der folgenden Vorträge noch mehr gesagt werden wird. Diese Ausarbeitung wird sich mit CLP(FD) näher beschäftigen. FD steht für finite domains, also endliche Wertebereiche.

Nach oben
... [ Seminarthemen SS01 ] ... [ Inhaltsverzeichnis ] ... [ Das ECLiPSe System ] ...