Einführung in die Constraint-Programmierung (eBook)

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