Einführung in die Constraint-Programmierung (eBook)

Grundlagen, Methoden, Sprachen, Anwendungen

Petra Hofstedt, Armin Wolf (Autoren)

eBook Download: PDF

2007 | 1. Auflage
390 Seiten
Springer-Verlag
978-3-540-68194-6 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 2.3.2007
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Informatik ► Software Entwicklung
• ISBN-10: 3-540-68194-9 / 3540681949
• ISBN-13: 978-3-540-68194-6 / 9783540681946