Hofstedt / Wolf Einführung in die Constraint-Programmierung

Grundlagen, Methoden, Sprachen, Anwendungen
2007
ISBN: 978-3-540-68194-6
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 390 Seiten

Reihe: eXamen.press

Die Constraint-Programmierung liefert Methoden zur effizienten Modellierung von Systemen oder zur Lösung von Problemen, für die nur unvollständige Informationen vorliegen. Ebenso hilft sie kombinatorische Probleme zu lösen oder komplexe Deduktionssysteme zu entwickeln. Dieses kompakte Lehrbuch führt in die Constraint-Programmierung ein. Neben den Grundlagen stellen die Autoren Sprachen, Methoden und Verfahren zur Modellierung und Lösung von Constraint-Problemen vor. Darüber hinaus betrachten sie deren Anwendungsfelder und veranschaulichen diese anhand typischer Beispiele wie Terminplanung, Finanzwesen, Optimierung, Simulation und Diagnose.

Petra Hofstedt:

Studium der Informatik an der Technischen Universität Dresden, 1995 Abschluss zur Diplom-Informatikerin.- Von 1995 bis 1999 wissenschaftliche Mitarbeiterin an der TU Dresden mit den Forschungs- und Arbeitsschwerpunkten (Deklarative) Programmiersprachen, parallele Programmierung und theoretische Informatik.- 1997 Forschungsaufenthalt an der Rheinisch-Westfälischen Technischen Hochschule Aachen.- Von 1999 bis 2001 wissenschaftliche Mitarbeiterin und seit 2002 wissenschaftliche Assistentin im Fachbereich Informatik der Technischen Universität Berlin (Fachgebiet Übersetzerbau und Programmiersprachen), Forschungs- und Arbeitsgebiete: Constraint-Programmierung, Programmiersprachen und Compilerbau.- 2001 Promotion zum Thema 'Cooperation and Coordination of Constraint Solvers'.

Armin Wolf:

Studium der Informatik an der Universität Karslruhe, 1991 Abschluss zum Diplom-Informatiker.- Von 1992 bis 1994 wissenschaftlicher Mitarbeiter an der Technischen Hochschule Berlin. Arbeitsschwerpunkte: formale Spezifikationen und deklarative Programmierung.- Seit 1994 wissenschaftlicher Mitarbeiter und Projektleiter am Fraunhofer Institut für Rechnerarchitektur und Softwaretechnik (FIRST) in Berlin. Arbeitsschwerpunkte: Methoden, Verfahren und Anwendungen der Constraint-Programmierung, insbesondere in der Planung.- Oktober 1998 bis Oktober 2003 Forschungskoordinator am Institut FIRST. Unterstützung der Institutsleitung bei der Neustrukturierung des Instituts, dessen wissenschaftliche Ausrichtung sowie dessen Überleitung in die Fraunhofer Gesellschaft. Präsentation des Instituts nach innen und außen.- Seit Januar 1999 stellvertretender Leiter des Bereichs 'Planungstechnik' am Institut FIRST.- 1999 Promotion mit Auszeichnung zur adaptiven regelbasierten Constraint-Programmierung.

Autoren/Hrsg.

Hofstedt, Petra

Wolf, Armin

Inhaltsverzeichnis

1;Vorwort;7
2;Inhaltsverzeichnis;9
3;Teil I Einführung;13
3.1;1 Prädikatenlogik;14
3.1.1;1.1 Signaturen und Strukturen;14
3.1.2;1.2 Terme, Formeln und Gültigkeit;16
3.1.3;1.3 Aufgaben;22
3.2;2 Logische Programmierung;23
3.2.1;2.1 Syntax;23
3.2.2;2.2 Substitutionen und Unifikation;27
3.2.3;2.3 Die Semantik logischer Programme;31
3.2.4;2.4;42
3.2.5;2.5 Logische Programmierung mit Constraints – CLP;51
3.2.6;2.6 Aufgaben;58
4;Teil II Constraints, Constraint-Systeme und Constraint- Löser;60
4.1;3 Constraints und Constraint-Löser;62
4.1.1;3.1 Constraints und Constraint-Systeme;62
4.1.2;3.2 Erfüllbarkeit und Lösungen;67
4.1.3;3.3 Constraint-Löser;69
4.1.4;3.4 Aufgaben;79
4.2;4 Constraints über endlichen Wertebereichen – Finite- Domain- Constraints;80
4.2.1;4.1 Constraint-Satisfaction-Probleme;81
4.2.2;4.2 Konsistenztechniken;82
4.2.3;4.3 Lösungssuche durch Rücksetzen (Backtracking);99
4.2.4;4.4 Praktische Programmierung;103
4.2.5;4.5 Aufgaben;104
4.3;5 Lineare Arithmetische Constraints;106
4.3.1;5.1 Lineare (Un-)Gleichungen;106
4.3.2;5.2 Die Simplex-Methode;108
4.3.3;5.3 Erfüllbarkeit, Projektion und Folgerbarkeit;126
4.3.4;5.4 Praktische Programmierung;132
4.3.5;5.5 Aufgaben;133
5;Teil III Constraint-Sprachen;134
5.1;6 Constraint-logische Programmierung (CLP);136
5.1.1;6.1 Zustandsübergangssysteme;136
5.1.2;6.2 Syntax und Auswertung Constraint-logischer Programme;137
5.1.3;6.3 Deklarative Semantik;146
5.1.4;6.4 Logische Programmierung als CLP;147
5.1.5;6.5 Aufgaben;149
5.2;7 Nebenläufige Constraint-logische Programmierung;150
5.2.1;7.1 Das Modell der nebenläufigen Constraint- Programmierung;151
5.2.2;7.2 Nebenläufige Constraint-logische Programme;152
5.2.3;7.3 Anwendungen und Beispiele;164
5.2.4;7.4 Aufgaben;170
5.3;8 Constraint Handling Rules;172
5.3.1;8.1 Syntax;173
5.3.2;8.2 Deklarative Semantik;174
5.3.3;8.3 Operationale Semantik;176
5.3.4;8.4 Semantische Zusammenhänge;185
5.3.5;8.5 Anwendungen;186
5.3.6;8.6 Anmerkungen und Literaturhinweise;189
5.3.7;8.7 Aufgaben;190
5.4;9 Constraint-imperative und Constraint- objektorientierte Programmierung;192
5.4.1;9.1 Constraint-imperative Programmierung mit Turtle;193
5.4.2;9.2 Constraint-Programmierung in;208
5.4.3;mit firstcs;208
5.4.4;9.3 Aufgaben;224
6;Teil IV Modellierung von Constraint-Problemen;225
6.1;10 Realisierung und Verwendung globaler Constraints;226
6.1.1;10.1 Paarweise Verschiedenheit;227
6.1.2;10.2 Exklusive Belegung einer Ressource;239
6.1.3;10.3 Anmerkungen und Literaturhinweise;253
6.1.4;10.4 Aufgaben;254
6.2;11 Symmetrien und Redundanzen;257
6.2.1;11.1 Erkennen von Symmetrien;257
6.2.2;11.2 Aufbrechen von Symmetrien;259
6.2.3;11.3 Redundante Constraints;260
6.2.4;11.4 Anmerkungen und Literaturhinweise;267
6.2.5;11.5 Aufgaben;268
6.3;12 Modellierungsbeispiele;269
6.3.1;12.1 Kürzeste Golomb-Lineale;269
6.3.2;12.2 Teambildung bei Managerseminaren;274
6.3.3;12.3 Anmerkungen und Literaturhinweise;278
7;Teil V Lösung von Constraint-Problemen;279
7.1;13 Die Suche nach Lösungen von CSP;280
7.1.1;13.1 Generelle Suchverfahren;280
7.1.2;13.2 Das Labeling;285
7.1.3;13.3 Verallgemeinerte Lösungssuche;293
7.1.4;13.4 Anmerkungen und Literaturhinweise;300
7.1.5;13.5 Aufgaben;301
7.2;14 Optimale Lösungen von CSP;303
7.2.1;14.1 Constraint-Optimierungsprobleme (COP);303
7.2.2;14.2 Ein Lösungsverfahren für COP;304
7.2.3;14.3 Dichotomisches Optimieren;307
7.2.4;14.4 Gleichzeitige Optimierung mehrerer Zielfunktionen;310
7.2.5;14.5 Anmerkungen und Literaturhinweise;316
7.2.6;14.6 Aufgaben;317
8;A Lösungen;318
8.1;Lösungen zu Kapitel 1;319
8.2;Lösungen zu Kapitel 2;321
8.3;Lösungen zu Kapitel 3;328
8.4;Lösungen zu Kapitel 4;332
8.5;Lösungen zu Kapitel 5;337
8.6;Lösungen zu Kapitel 6;342
8.7;Lösungen zu Kapitel 7;345
8.8;Lösungen zu Kapitel 8;347
8.9;Lösungen zu Kapitel 9;352
8.10;Lösungen zu Kapitel 10;355
8.11;Lösungen zu Kapitel 11;360
8.12;Lösungen zu Kapitel 13;361
8.13;Lösungen zu Kapitel 14;367
9;Literatur;369
10;Index;381