Zwischenbericht der Projektgruppe Transportoptimierung Bericht Nr. 1998/06 P Universität Stuttgart Zwischenbericht der Projektgruppe Transportoptimierung Jörg Fleischmann Lars Hermes Tobias Spribille Frank Wagner Betreuung Prof. Dr. Volker Claus Dipl.-Inform. Friedhelm Buchholz Dipl.-Inform. Stefan Lewandowski Abteilung Formale Konzepte Fakultät Informatik Universität Stuttgart 4. Mai 1998 Prof. Dr. Volker Claus Abteilung Formale Konzepte Institut für Informatik Universität Stuttgart Breitwiesenstr. 20-22 D-70565 Stuttgart Telefon: 0711-7816-300 (Prof. Dr. V. Claus) 0711-7816-301 (Sekretariat) 0711-7816-330 (FAX) E-Mail: claus@informatik.uni-stuttgart.de Inhaltsverzeichnis 1 Vorwort 8 1.1 Die Projektgruppe im Informatikstudium . . . . . . . . . . . . . 8 1.2 Die Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Seminarvorträge 11 2.1 Constraint Programming . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.3 Anwendungsbeispiele . . . . . . . . . . . . . . . . . . . . . 13 2.1.4 Constraints als Vorgaben . . . . . . . . . . . . . . . . . . 14 2.1.5 Constraints als Beziehungen . . . . . . . . . . . . . . . . . 18 2.1.6 EinÄufl des Benutzers . . . . . . . . . . . . . . . . . . . . 23 2.1.7 Komplexität . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Objektorientierte Spezi?kation . . . . . . . . . . . . . . . . . . . 25 2.2.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Das Objektmodell . . . . . . . . . . . . . . . . . . . . . . 25 2.2.3 Objekte und Klassen . . . . . . . . . . . . . . . . . . . . . 28 2.2.4 Klassi?zierung . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.5 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2.6 Prozefl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3 Flüsse in Netzwerken . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3.2 De?nitionen . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3.3 Das Minimum Cost Flow Problem . . . . . . . . . . . . . 52 2.3.4 Spezialfälle . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3.5 Verallgemeinerungen . . . . . . . . . . . . . . . . . . . . . 58 2.3.6 Das Integer Generalized Flow Problem ist NP-hart . . . . 60 2.3.7 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.4 Nachbarschaftssuche im Rd . . . . . . . . . . . . . . . . . . . . . 64 2.4.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . 64 2.4.2 Baumstrukturen . . . . . . . . . . . . . . . . . . . . . . . 65 2.4.3 Das Gitterverfahren >= mehrdimensionales Hashing . . . . 72 2.4.4 Das Closest Pair Problem >= CPP . . . . . . . . . . . . . . 80 3 Anforderungsanalyse 85 3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.2 Umgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.3 Aufbau des Systems . . . . . . . . . . . . . . . . . . . . . . . . . 86 5 3.3.1 Benutzungsschnittstelle . . . . . . . . . . . . . . . . . . . 86 3.3.2 Datenverwaltung . . . . . . . . . . . . . . . . . . . . . . . 86 3.3.3 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3.4 Automatische Tourplanung . . . . . . . . . . . . . . . . . 87 3.3.5 Ermittlung von Analysedaten . . . . . . . . . . . . . . . . 87 3.3.6 Anbindung an ein Verkehrstool . . . . . . . . . . . . . . . 87 3.4 Ist-Zustand beim Kunden . . . . . . . . . . . . . . . . . . . . . . 87 3.4.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.4.2 Dienste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.4.3 Ressourcen . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.4.4 Planung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.5 Erfahrungsbericht . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6 Notwendige Eingabedaten . . . . . . . . . . . . . . . . . . . . . . 93 3.6.1 Kunden erfassen . . . . . . . . . . . . . . . . . . . . . . . 93 3.6.2 Dienst anfordern . . . . . . . . . . . . . . . . . . . . . . . 94 3.6.3 Touren eingeben . . . . . . . . . . . . . . . . . . . . . . . 96 3.7 Szenarien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.7.1 Schulfahrten . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.7.2 MSD / PÄegedienst . . . . . . . . . . . . . . . . . . . . . 98 3.7.3 Essen auf Rädern . . . . . . . . . . . . . . . . . . . . . . . 100 3.7.4 Individualfahrten . . . . . . . . . . . . . . . . . . . . . . . 101 3.7.5 Pläne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4 Spezi?kation 104 4.1 Gesamtsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.1.1 Umgebung des Produktes . . . . . . . . . . . . . . . . . . 104 4.1.2 Warum Java? . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.1.3 Verwendete Tools . . . . . . . . . . . . . . . . . . . . . . . 105 4.1.4 Funktionalität . . . . . . . . . . . . . . . . . . . . . . . . 106 4.1.5 Entwicklungsphilosophie . . . . . . . . . . . . . . . . . . . 108 4.2 Datenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.2.1 Klassendiagramme . . . . . . . . . . . . . . . . . . . . . . 108 4.2.2 Klassen-Beschreibungen . . . . . . . . . . . . . . . . . . . 115 4.2.3 Tourkonzept . . . . . . . . . . . . . . . . . . . . . . . . . 136 4.3 Verkehrsmodul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 4.3.1 Das Verkehrstool: Map&Guide . . . . . . . . . . . . . . . 138 4.3.2 Aufbau des Verkehrsmoduls . . . . . . . . . . . . . . . . . 138 4.3.3 Korrektur von Entfernungen . . . . . . . . . . . . . . . . . 139 4.4 Datenausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 4.4.1 Dienstpläne . . . . . . . . . . . . . . . . . . . . . . . . . . 139 4.4.2 Analysedaten . . . . . . . . . . . . . . . . . . . . . . . . . 140 4.4.3 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 4.4.4 Anfragen . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 4.4.5 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 143 4.5 Lokale Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . 143 4.5.1 Ein- und Ausgabe der Optimierung . . . . . . . . . . . . . 144 4.5.2 Was soll optimiert werden? . . . . . . . . . . . . . . . . . 144 4.5.3 EÖzienz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.5.4 Mafle für verschiedene Parameter . . . . . . . . . . . . . . 145 4.5.5 Wie könnte eine gute Lösung gefunden werden? . . . . . . 145 7 4.5.6 Generischer Ansatz . . . . . . . . . . . . . . . . . . . . . . 153 4.6 Inkrementelle Optimierung . . . . . . . . . . . . . . . . . . . . . 160 4.6.1 Touren erweitern . . . . . . . . . . . . . . . . . . . . . . . 160 4.6.2 Dienstwünsche einfügen . . . . . . . . . . . . . . . . . . . 161 4.6.3 Inkrementelles Verbessern . . . . . . . . . . . . . . . . . . 161 4.6.4 Bewertung Tourenmengen . . . . . . . . . . . . . . . . . . 161 4.7 Die BenutzungsoberÄäche . . . . . . . . . . . . . . . . . . . . . . 163 4.7.1 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 163 4.7.2 Hauptmenu . . . . . . . . . . . . . . . . . . . . . . . . . . 163 4.7.3 Dienste anfordern . . . . . . . . . . . . . . . . . . . . . . 163 4.7.4 Obertour eingeben . . . . . . . . . . . . . . . . . . . . . . 169 4.7.5 Untertour eingeben . . . . . . . . . . . . . . . . . . . . . . 170 4.7.6 Mitarbeiter eingeben . . . . . . . . . . . . . . . . . . . . . 171 4.7.7 Fahrzeug eingeben . . . . . . . . . . . . . . . . . . . . . . 172 4.7.8 Fahrzeugtyp eingeben . . . . . . . . . . . . . . . . . . . . 174 4.7.9 Kunden eingeben . . . . . . . . . . . . . . . . . . . . . . . 174 4.7.10 Rechnungsempfänger eingeben . . . . . . . . . . . . . . . 175 4.7.11 Kontaktperson eingeben . . . . . . . . . . . . . . . . . . . 176 5 Entwurf 177 5.1 Grobentwurf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.1.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.1.2 BenutzungsoberÄäche . . . . . . . . . . . . . . . . . . . . 177 5.1.3 Datenhaltung . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.1.4 Verkehrsmodul . . . . . . . . . . . . . . . . . . . . . . . . 185 5.1.5 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 186 5.1.6 Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . 189 5.2 Feinentwurf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 5.2.1 Klasse Person und zugehörige Klassen . . . . . . . . . . . 190 5.2.2 Klasse Dienstwunsch und zugehörige Klassen . . . . . . . 194 5.2.3 Klasse Fahrzeug und zugehörige Klassen . . . . . . . . . . 197 5.2.4 Klasse Tour und zugehörige Klassen . . . . . . . . . . . . 199 5.2.5 Datenhaltung . . . . . . . . . . . . . . . . . . . . . . . . . 201 5.2.6 Vorgehensweise bei der Eingabe . . . . . . . . . . . . . . . 202 5.2.7 Verkehrsmodul . . . . . . . . . . . . . . . . . . . . . . . . 204 A Begriöslexikon 207 Literaturverzeichnis 210 Kapitel 1 Vorwort 1.1 Die Projektgruppe im Informatikstudium Eine Projektgruppe ist eine besondere Form der Lehrveranstaltung im Rahmen des Informatikstudiums. Sie vereinigt Seminar bzw. Hauptseminar (2 SWS), Fachpraktikum (4 SWS) und Studienarbeit (10 SWS) in einer thematisch durchgehenden Lehrveranstaltung über den Zeitraum eines Jahres (hierfür sind 16 SWS angesetzt). Während dieser Zeit arbeitet eine Gruppe von (etwa fünf) Studenten von der Erarbeitung theoretischer Grundlagen bis zur Implementierung eines lauöähigen Programms gemeinsam an einem zentralen Thema. Dadurch können Ausbildungsziele verfolgt werden, die sich kleineren, in sich abgeschlossenen Lehrveranstaltungen von Natur aus nicht oder nur begrenzt erschlieflen: - Arbeiten im Team - Analyse von Problemen, Strukturierung von Lösungen und gemeinsamer Entwurf geeigneter Systeme - Selbständige Erarbeitung von Lösungsvorschlägen und deren Vorstellung und Verteidigung in einer Gruppe - Übernahme von Verantwortung für die Lösung von Teilaufgaben und die Erstellung von Modulen - Mitwirkung an einer umfassenden Dokumentation - Erstellen eines Software-Produktes, das ein Einzelner innerhalb des vorgegebenen Zeitraumes unmöglich bewältigen kann. Hierbei sollen sämtliche Phasen eines Software-Lifecycles >= von der Planung bis zur Wartung >= durchlaufen werden - Projekt-Planung und Kosten/Nutzen-Analyse - Einsatz von Werkzeugen - Persönlichkeitsbildung (Übernahme von Verantwortung, Selbstvertrauen, Verläfllichkeit, Rücksichtnahme, Durchsetzungsfähigkeit usw.) 8 1.1. DIE PROJEKTGRUPPE IM INFORMATIKSTUDIUM 9 Das Konzept der Projektgruppe wird bereits seit Jahren an anderen Universitäten wie z.B. in Oldenburg und Dortmund erprobt und durchgeführt. Dort sind Projektgruppen zum Teil schon PÄichtveranstaltungen im Rahmen des Informatikstudiums. An der Universität Stuttgart gibt es seit 1994 Projektgruppen im Fach Informatik. Im neu eingerichteten Studiengang Software-Technik ist die Teilnahme verbindlich vorgeschrieben. Durch die eher kleine Teilnehmerzahl von 4 Studenten pro Projektgruppe (die ursprünglich für bis zu zehn Studierende vorgesehen war) können in der Praxis leider nicht alle Projektziele realisiert werden. Als ungünstig für die Teilnehmer hat sich auch erwiesen, dafl die Arbeit in vollem Umfang in der vorlesungsfreien Zeit weitergeführt werden soll, was zwangsläu?g zu Kollisionen mit Prüfungsvorbereitung und Urlaub führt. Der Ablauf der Projektgruppe ist in verschiedene Phasen unterteilt: Seminarphase Zu Beginn des Projekts werden verschiedene, für die folgende Arbeit grundlegende Themen erarbeitet. Literaturrecherche sowie Aufarbeitung und Präsentation des Materials sind wesentliche Arbeitsschritte, die hierbei gelernt werden sollen. Anforderungsanalyse Die Projektgruppe analysiert die Aufgabenstellung durch Diskussion mit dem Kunden sowie Erarbeitung verschiedener Möglichkeiten der Modellierung. Ziel dieser Phase ist es, ein möglichst genaues Bild der zu modellierenden Objekte aus der realen Welt zu bekommen, sowie alle Begriöe festzulegen und zu standardisieren. Damit kann im folgenden eine Abbildung auf Verfahren und Strukturen der Informatik erfolgen. Spezi?kation Die jetzt genau bekannte Aufgabenstellung und Anforderung des Kunden wird modelliert. Dabei werden bekannte Problemlösungen aus der Literatur genauso gesammelt wie eigene Ideen. Abwägungen zwischen unterschiedlichen Ansätzen in Hinblick auf die gewünschten Eigenschaften des Ergebnisses (Flexibilität, Schnelligkeit, Erweiterbarkeit, etc.) müssen hier getroöen werden. Dabei soll eine möglichst genaue, in Teilen auch formale, Beschreibung des zu programmierenden Systems entstehen. Entwurf Aufbauend auf die Spezi?kation werden hier die einzelnen Komponenten des Programms bis ins Detail beschrieben. Die verschiedenen Schnittstellen sowohl zum Benutzer als auch innerhalb des Programms werden genau festgelegt, ebenso die zu verwendenden Datenstrukturen und Algorithmen. Der Entwurf soll eine möglichst eindeutige Beschreibung des Programms darstellen und somit direkt als Vorlage für die Implementierung dienen. Alle wesentlichen Design-Entscheidungen, die bisher noch nicht getroöen werden, fallen im Entwurf. Implementierung Nach Einarbeitung in eine Programmiersprache und zugehörige Entwicklungsumgebungen werden die Vorgaben von Spezi?kation und Entwurf konkret in Code umgesetzt. Test Das lauöähige Programm wird bereits während der Codierung mit möglichst realistischen Daten getestet, um Programmfehler zu entdecken und die Handhabbarkeit zu prüfen. 10 KAPITEL 1. VORWORT Dokumentation/Präsentation Die gesamte Arbeit der Projektgruppe wird fortlaufend dokumentiert. Der Stand nach dem Entwurf (?Zwischenbericht?) sowie der Überblick über das gesamte Projekt (?Endbericht?) werden gedruckt und ähnlich einer Studienarbeit verööentlicht. Das Ergebnis der einjährigen Arbeit wird auflerdem in einer Präsentationsveranstaltung der interessierten Ööentlichkeit vorgeführt. 1.2 Die Aufgabenstellung Neben den allgemeinen Lehrinhalten im Rahmen des Informatikstudiums hat diese Projektgruppe ein konkretes Ziel: Es soll ein Programm zur Verwaltung und Optimierung von sozialen Fahrdiensten entwickelt werden, das dann beim DRK in Stuttgart eingesetzt wird. Das Programm soll alle für das DRK in Zusammenhang mit seinen Fahrdiensten wichtigen Daten erfassen und verwalten. Die momentan manuell durchgeführte Planung soll in Zukunft computergestützt ablaufen können, was den Planern beim DRK einen besseren Überblick über die Dienste und Einsatz von Mitarbeitern und Fahrzeugen liefern soll. Auflerdem ist vorgesehen, die Optimierung von Fahrdiensten auch automatisch auszuführen, um aufwendige Handarbeit einzusparen oder gar bessere Ergebnisse zu bekommen. Zunächst wird das Programm also denjenigen Ausschnitt der realen Welt modellieren, der soziale Fahrdienste (und zwar ganz speziell aus Sicht des DRK Stuttgart) betriöt. Dabei geht die Anforderungsanalyse vom Ist-Zustand beim DRK aus, so dafl das Programm letztlich in der Lage ist, diesen möglichst exakt wiederzugeben. Dennoch sollen einzelne Komponenten des Programms unabhängig austauschund erweiterbar sein. Durch Einsatz objektorientierter Analyse- und Designmethoden von der Spezi?kation bis zur Implementierung wird ein modularer Programmaufbau erreicht, der die einzelnen Komponenten weitgehend unabhängig voneinander und damit austauschbar macht. Kapitel 2 Seminarvorträge 2.1 Constraint Programming (Tobias Spribille) 2.1.1 Einführung Ein Computer ist von seiner Grundstruktur her für eine imperative Vorgehensweise bei der Problemlösung geschaöen. Dies schlägt sich auch in den meisten gängigen Programmiersprachen und bekannten Algorithmen nieder: Um ein Problem zu lösen, wird eine Folge von konkreten Handlungsanweisungen angegeben, die aus einem Startwert die zugehörige Lösung berechnen. Alle Eigenschaften der Lösung sind implizit in den einzelnen Teilen der Rechenvorschrift enthalten. Deshalb ist einem Programm oft nicht leicht anzusehen, was es überhaupt macht. Ebenso aufwendig kann es sein, zu einem Problem einen Algorithmus zu ?nden, der die Lösung berechnet, deren Eigenschaften oft recht einfach anzugeben sind. Von eben diesen Eigenschaften der Lösung geht das deklarative Programmierparadigma aus, das in Sprachen wie z.B. PROLOG zum Einsatz kommt. Der Programmierer beschreibt in einer formalen Syntax die Eigenschaften, die die gesuchte Lösung haben soll, und das System ermittelt diese daraus. int fib(int x) { int f1 = 0, f2 = 1; while (x-- >= 1) { int temp = f1 + f2; f1 = f2; f2 = temp; } return f2; } fib(0,0). fib(1,1). fib(N,X) :- fib(N-1,Y), fib(N-2,Z), X is Y+Z. Abbildung 2.1: Imperative und deklarative Berechnung der Fibonacci-Zahlen 11 12 KAPITEL 2. SEMINARVORTRÄGE Die Bezeichnung Constraint Programming steht für solche deklarativen Problemlösungsmethoden, bei denen für eine Menge von Variablen Werte gefunden werden müssen, die einer Menge von Bedingungen (den constraints) genügen. Zu deklarativ spezi?zierten Problemen gibt es im Unterschied zu den imperativen Verfahren nicht immer eine eindeutige Lösung. Für praktische Problemstellungen wie die Transportoptimierung ist es aber ausreichend, irgendeine mögliche Lösung zu ?nden, die alle Anforderungen erfüllt. Ein PROLOG-Interpreter ?ndet die Lösung mit den angegebenen Eigenschaften durch eine Tiefensuche im exponentiell groflen Lösungsraum. Dies kann bei groflen Problemen sehr lange dauern. Deshalb werden für Constraint Programming spezielle Lösungsalgorithmen benutzt, die durch geschickte Wahl der Suchrichtung und/oder Einsatz von Heuristiken möglichst früh auf eine Lösung stoflen sollen oder die Anzahl der zu betrachtenden Möglichkeiten reduzieren. 2.1.2 Grundlagen De?nition 2.1.1 Ein Constraint Satisfaction Problem (oder kurz CSP) ist ein Tripel (V ; W ; C), bestehend aus: - Einer Menge von Variablen V = fV1; : : : ; Vng mit Wertebereich W . - Einer Menge von Constraints C = fC1; : : : ; Crg. Ein Constraint ist eine Beziehung zwischen Variablenwerten: Cj : P(V) ? (V !W) ! B fö(Vi1); : : : ; ö(Vik )g 7! ftrue, falseg Gesucht ist eine Variablenbelegung ö 2 (V !W), die alle Constraints erfüllt: 8j 2 f1; : : : ; rg : Cj(fVi1 ; : : : ; Vik g; ö) = true De?nition 2.1.2 Ein hierarchisches CSP de?niert zusätzlich eine Hierarchie auf den Constraints: H : C ! f1; : : : ; hmaxg Constraints, die höher in der Hierarchie stehen, sind wichtiger als tiefere, und ihre Erfüllung hat Priorität vor allen anderen Constraints. Es gibt verschiedene Arten von CSPs: - ein unterbestimmtes (underconstrained) CSP hat mehrere Lösungen, da die Constraints nicht alle Variablen eindeutig bestimmen. Da in vielen Anwendungen nicht der Benutzer entscheiden kann, welche Lösung gewählt werden soll, könnte hier mit Heuristiken versucht werden, dessen Intention zu treöen. - ein überbestimmtes (overconstrained) CSP enthält mehr Constraints, als zur eindeutigen Bestimmung der Variablenwerte notwendig wären. Dies ist auf zwei verschiedene Arten möglich: >= Einige Constraints sind redundant, d.h. es kann eine Lösung gefunden werden, die allen Constraints genügt (aber bereits mit einer Teilmenge auch gefunden worden wäre) 2.1. CONSTRAINT PROGRAMMING 13 >= Es entsteht ein KonÄikt, da nicht alle Constraints gleichzeitig erfüllt werden können. Über eine Hierarchie kann von vornherein festgelegt werden, welche Constraints in einem solchen Fall wichtiger sind, und welche am ehesten wegfallen dürfen. Eine Möglichkeit der KonÄiktlösung ist auch, die Lösung mit dem minimalen Fehler zu wählen. - Probleme mit dynamisch sich ändernden Constraints lassen sich mit inkrementellen Verfahren lösen, die die Constraints in ihrer Entstehungsreihenfolge einzuplanen versuchen. Bei einer Änderung mufl meist nur ein kleiner Teil der Werte neu berechnet werden, so dafl sich diese Verfahren besonders für interaktive Anwendungen eignen. 2.1.2.1 Vorteile von Constraint Programming Aus den bisher vorgestellten Eigenschaften lassen sich bereits einige Vorteile von Constraint Programming gegenüber expliziten Lösungsverfahren für ein Problem erkennen: - Man mufl nur die Eigenschaften einer Lösung beschreiben, nicht den Weg dorthin - Bedingungen können sich dynamisch ändern (in Form von zusätzlichen Constraints) - lokale Zusammenhänge können ein globales Verhalten beschreiben 2.1.3 Anwendungsbeispiele 2.1.3.1 Robotersteuerung Einfache Roboter wie den Kran in Bild 2.2 links lassen sich noch recht einfach durch explizite Angabe der Bewegung für die einzelnen Teile steuern. Mit zunehmender Anzahl der Freiheitsgrade werden die Zusammenhänge jedoch so komplex, dafl dies nicht mehr ohne weiteres möglich ist. Für die Roboterhand in Bild 2.2 rechts müssen zahlreiche mechanische Beziehungen zwischen den sieben Teilen berücksichtigt werden. Diese können als Constraints formuliert werden, aus denen dann ein geeigneter Lösungsalgorithmus die Bewegung der einzelnen Teile ermittelt. Abbildung 2.2: Roboter mit wenigen und vielen Freiheitsgraden Hier ist gut erkennbar, wie sich lokale Constraints (Bedingungen an den Gelenken, die nur die Lage zweier benachbarter Glieder beschreiben) auf das globale Verhalten des Roboters auswirken. 14 KAPITEL 2. SEMINARVORTRÄGE 2.1.3.2 Selbsterklärende Simulation Ein Simulationssystem, dessen Wertebeziehungen durch Constraints realisiert sind, kann nicht nur gültige Werte berechnen, sondern ist überdies in der Lage, die Zusammenhänge zwischen diesen Werten zu erklären. So kann dem Benutzer auf Anfrage mit beliebigem Detaillierungsgrad mitgeteilt werden, warum eine Variable einen gewissen Wert hat. Im folgenden Beispiel könnte erklärt werden, warum die Fahrt erst um 7.30 Uhr beginnen kann. Beispiel aus der Transportoptimierung Betrachtet werden soll ein Teilzusammenhang aus der Behindertenbeförderung: Zwei Behinderte sollen morgens von einem Fahrzeug nacheinander zu Hause abgeholt werden. Die dabei zu beachtenden zeitlichen Zusammenhänge könnten folgendermaflen als hierarchisches CSP mit drei Variablen und vier Constraints formuliert werden: V1 : Weckzeit für den Behinderten, der zuerst abgeholt wird V2 : Abholzeit für den ersten Behinderten V3 : Abholzeit für den zweiten Behinderten C1 : V1 >= 6; 5 (die Eltern des Behinderten, die ihn betreuen, wollen nicht so früh aufstehen), Stärke 1 C2 : V2 ? V1 >= 1 (bis der Behinderte fertig zum Abholen ist, dauert es eine Stunde), Stärke 3 C3 : V3 ? V2 >= 1 2 (die Fahrt von der Wohnung des ersten Behinderten zum zweiten dauert eine halbe Stunde), Stärke 4 C4 : V3 <= 7; 5 (die Eltern des zweiten Behinderten wollen früh zur Arbeit, damit sie früh Feierabend haben), Stärke 1 2.1.3.3 Intelligente Computergraphik In der Computergraphik müssen oft geometrische Zusammenhänge zwischen Objekten erfüllt werden. Viele Graphikprogramme bieten deshalb Funktionen an, die z.B. das Zeichnen von parallelen Linien erlauben. Dadurch ist der Zusammenhang aber nur unmittelbar nach dem Einfügen der Linien gegeben. Wird eine Linie gedreht, ändern sich auch die geometrischen Zusammenhänge. Constraints zur Überwachung solcher Beziehungen würden die zweite Linie mitdrehen und so die Parallelität aufrechterhalten. Dadurch können lokale interaktive Änderungen einen globalen Eöekt haben. Ein Objekt hat kein festes Verhalten mehr, dieses ergibt sich erst aus der Kombination von Objekt und Constraints. Durch die Angabe von Constraints ?programmiert? der Benutzer sozusagen das System [Gle95]. 2.1.4 Constraints als Vorgaben 2.1.4.1 Einführung In Abschnitt 2.1.2 wurde ein Constraint als eine Beziehung zwischen Variablen de?niert. Ein Programm, das zu einer Constraintmenge eine Variablenbelegung ?ndet, also ein CSP löst, heiflt Constraint Solver. Ein Beispiel für einen solchen Lösealgorithmus soll im folgenden betrachtet werden. 2.1. CONSTRAINT PROGRAMMING 15 2.1.4.2 Disjunktive Zerlegung De?nition In [FH95] wird ein grundlegendes Verfahren zur Lösung von Constraint Satisfaction Problems angewandt, das nach dem Verfahren Teile und Herrsche arbeitet. Die Hauptrolle spielt dabei die Zerlegung des Problems in Teilprobleme, die jedes für sich auf Lösungen untersucht werden. Damit ist diese Methode für Parallelisierung sehr gut geeignet. Das Verfahren geht folgendermaflen vor: Lege das Ausgangsproblem auf den Stack while Stack 6= ; Nimm ein Problem P vom Stack if alle Variablen in P sind instantiiert return(P ) else Zerlege P in Teilprobleme fPig Lege alle nichtleeren Pi auf den Stack endif endwhile return(;) Zunächst sind alle Variablen uninstantiiert. Sie werden instantiiert, indem bei der Zerlegung Werte oder Teile der (endlichen) Wertemengen dafür festgelegt werden. Ein Teilproblem heiflt leer, wenn der Wertebereich einer instantiierten Variablen leer ist, wenn es also keine möglichen Werte mehr gab, die mit den anderen instantiierten Variablen konsistent sind. Dabei heiflen zwei Werte für zwei Variablen konsistent, wenn es keinen Constraint gibt, der diese Wertekombination verbietet. De?nition 2.1.3 Eine disjunktive Zerlegung ist eine Zerlegung eines Problems in Teilprobleme mit folgenden Eigenschaften: 1. Konsistenz: Die Werte instantiierter Variablen sind zueinander konsistent. 2. Reduktion: Jedes der Pi hat weniger mögliche Wertekombinationen oder mehr instantiierte Werte als P . 3. Semi-Vollständigkeit: Wenn es zu P eine Lösung gibt, dann auch zu mindestens einem der Pi. Satz 2.1.1 Eine disjunktive Zerlegung garantiert, dafl das oben vorgestellte Zerlegungsverfahren für lösbare Probleme eine der Lösungen und sonst die leere Menge zurückgibt. Beweis 2.1.1 Da die Wertebereiche der Variablen endlich sind, folgt aus der Reduktionseigenschaft, dafl irgendwann alle Teilprobleme entweder leer sind oder nur instantiierte Variablen besitzen. Nun betrachtet man den Baum, der entsteht, wenn die Teilprobleme nach der Zerlegung als Knoten unter das Problem gehängt werden, von dem sie ausgehen. Dann folgt aus der Semi-Vollständigkeit, dafl auf jeder Ebene ein Knoten existiert, der eine Lösung des Wurzelproblems enthält. Wenn man diesen Pfad von der Wurzel aus verfolgt, kommt man nach endlich vielen Schritten an ein 16 KAPITEL 2. SEMINARVORTRÄGE Blatt, das alle Variablen instantiiert hat und somit eine Lösung für das Ausgangsproblem darstellt. Weitere wünschenswerte Eigenschaften könnten sein: 1. Vollständigkeit: Jede Lösung von P ist auch Lösung mindestens eines der Pi. 2. Redundanzfreiheit: Jede mögliche Wertekombination für P existiert in höchstens einem der Pi. 3. Reduzierbarkeit: Die Summe der Gröflen (möglichen Wertekombinationen) der Pi kann kleiner sein als die Gröfle von P . Diese Eigenschaften gelten unabhängig von der Reihenfolge, in der die Probleme und Teilprobleme betrachtet werden. Zum einen kann die Reihenfolge variiert werden, in der die Teilprobleme auf den Stack gelegt werden, zum anderen mufl die Menge der noch zu bearbeitenden Probleme gar nicht unbedingt als Stack organisiert sein. Diese Entscheidung, in welcher Reihenfolge die Teilprobleme erledigt werden, ist ein guter Ansatzpunkt für heuristische Verfahren. Beispiel aus der Transportoptimierung Um verschiedene Arten solcher Zerlegungsstrategien vergleichen zu können, soll das Verfahren auf folgendes Beispiel angewandt werden: Ein Fahrdienst besteht aus vier Touren pro Tag, zu denen drei verschiedene Fahrzeuge eingesetzt werden können. Da jeder Bus nach der Tour gereinigt oder für die nächste Fahrt ausgerüstet werden mufl (z.B. mit speziellen Sitzen), können zwei aufeinanderfolgende Fahrten nicht mit dem selben Fahrzeug gemacht werden (?aufeinanderfolgend? ist hier zyklisch gemeint, z.B. wenn die Autos rund um die Uhr im Schichtbetrieb eingesetzt werden). Das Problem, die Fahrzeuge den Touren zuzuordnen, besteht also aus den Variablen T1; : : : ; T4 für die Touren, mit jeweils der Wertemenge fa; b; cg, entsprechend den drei Fahrzeugen. Die Bedingungen ergeben vier Constraints: Ci : Ti 6= Ti?1; i = 1; : : : ; 4 Backtracking Diese einfachste Form der Suche im Zerlegungsbaum de?niert die Zerlegung in zwei Teilprobleme: - P1: Sei V1 die erste nicht instantiierte Variable, v1 2 dom(V1). Wenn v1 konsistent mit den bisher instantiierten Variablen ist, instantiiere V1 mit dom(V1) = fv1g, sonst mit dom(V1) = ;. - P2: dom(V1) = dom(V1) n fv1g. Ein Ausschnitt des Baumes ist in Abbildung 2.3 zu sehen. Jeder Knoten steht für ein Teilproblem, die vier Zeilen jedes Knotens geben die Wertemengen der Variablen T1 : : : T4 an. Die Werte instantiierter Variablen sind unterstrichen. Forward Checking Da mit der Instantiierung einer Variablen sich bereits die Wertebereiche anderer Variablen verkleinern (weil Constraints manche Kombinationen von Werten mit den instantiierten Werten ausschlieflen), ist es sinnvoll, den Baum zu verkleinern, indem nur die jeweils konsistenten Werte weiterbetrachtet werden. Dies führt zu folgender Zerlegung: 2.1. CONSTRAINT PROGRAMMING 17 Abbildung 2.3: Backtracking - P1: dom(V1) = fv1g. Für alle anderen uninstantiierten Variablen W : dom(W ) = fw 2 dom(W ) j w ist konsistent zu v1g - P2: dom(V1) = dom(V1) n fv1g. Ein Ausschnitt des Baumes ist in Abbildung 2.4 zu sehen. Backtracking mit kartesischem Produkt Hier können Variablen mit ganzen Wertemengen instantiiert werden. Jedes Element aus dem kartesischen Produkt dieser Wertemengen ist eine Lösung des Problems. Damit müssen sehr viel weniger Einzelfälle unterschieden werden (z.B. in Abbildung 2.4 die Zerlegung der Wertemenge fbcg für T4). Sei fSig die Partition von dom(V1) in disjunkte Mengen Si. Dabei sind zwei Werte in der gleichen Teilmenge, wenn sie mit denselben Werten der bereits instantiierten Variablen konsistent sind. Zu jeder Teilmenge Si ergibt sich das Teilproblem Pi: - Pi: dom(V1) = Si Für alle bereits instantiierten Variablen W : dom(W ) = fw 2 dom(W ) j w ist konsistent zu den Werten in Sig Ein Ausschnitt des Baumes ist in Abbildung 2.5 zu sehen. 18 KAPITEL 2. SEMINARVORTRÄGE Abbildung 2.4: Forward Checking Abbildung 2.5: Backtracking mit kartesischem Produkt Komplexität Satz 2.1.2 Der Stack für die Disjunktive Zerlegung wird O(t ? jV j) Knoten grofl. Dabei ist t <= jW j die Anzahl der Teilprobleme, die bei einem Zerlegungsschritt maximal enstehen. Beweis 2.1.2 Auf jeder Ebene des Zerlegungsbaumes können t ? 1 noch unbehandelte Knoten stehen. Da bei jedem Zerlegungsschritt eine Variable instantiiert wird, können nur jV j solche Ebenen entstehen. Satz 2.1.3 Die Gröfle des Zerlegungsbaumes ist in O(jW jjVj). Beweis 2.1.3 Betrachte exemplarisch Backtracking mit kartesischem Produkt: Im schlechtesten Fall gibt es genausoviele Teilprobleme wie Variablenwerte. Auf jeder Ebene wird eine Variable instantiiert, es kann also jV j Ebenen geben, deren Knoten je jW j Unterknoten haben. 2.1.5 Constraints als Beziehungen 2.1.5.1 Einführung Mit einem deklarativen Programm kann man einfach nur Beziehungen überprüfen (z.B. wird das PROLOG-Programm von Seite 11 auf die Eingabe ?fib(7,13).? mit ?Yes? antworten, da 13 die siebte Fibonacci-Zahl ist). Der hauptsächliche Sinn und Zweck der deklarativen Programmierung besteht jedoch darin, dafl der Rechner die Lösung selbst bestimmt, also auf Eingabe von ?fib(7,X).? mit ?X=13? antwortet. Ebenso sind Constraints nicht nur Bedingungen, die eine potentielle Lösung auf ihre Korrektheit prüfen, sondern können auch selbständig aus gegebenen 2.1. CONSTRAINT PROGRAMMING 19 Daten Werte entsprechend ihrer Bedingung berechnen: Ein Constraint, der eine Summenbeziehung ausdrückt, könnte wie in Abbildung 2.6 links dargestellt werden. Die Beziehung a+ b = c kann auf drei Arten sichergestellt werden: Sind a und b gegeben, kann man c := a + b berechnen. Genausogut liefle sich aber a := c ? b oder b := c ? a berechnen, d.h. aus zwei gegebenen Variablen kann automatisch die dritte berechnet werden, so dafl der Constraint erfüllt ist. Ein Constraint hat also keine fest de?nierten Ein- und Ausgabevariablen, sondern eine Reihe von Methoden, die angeben, wie aus einem Teil der Variablen ein anderer berechnet werden kann. Constraints mit Methoden können zu Constraint-Netzen zusammengesetzt werden. In Abbildung 2.6 rechts ist ein Netz aus zwei Constraints abgebildet, das einen Zusammenhang aus der Transportoptimierung veranschaulicht: Aus dem Anfahrtszeitpunkt beim DRK ergibt sich durch Addieren der Fahrtzeit (Konstante dt1) die Ankunftszeit beim Behinderten. Mit einer weiteren Fahrtzeit (dt2) erhält man die Ankunftszeit an der Schule. Wie oben erläutert kann hier sowohl aus dem Abfahrtszeitpunkt beim DRK die Ankunftszeit an der Schule berechnet werden als auch umgekehrt. Abbildung 2.6: Constraint als Wertebeziehung 2.1.5.2 Constraint-Netze am Beispiel des Solvers ?SkyBlue? In [San95] wird der an der University of Washington entwickelte inkrementell Constraint Solver ?SkyBlue? vorgestellt, der mit Netzen aus hierarchischen Constraints arbeitet. Obwohl das allgemeine CSP NP-hart ist (siehe Abschnitt 2.1.7), gehen die Entwickler des Algorithmus' davon aus, dafl in praktisch vorkommenden Problemstellungen das Einfügen/Entfernen eines Constraints in linearer Zeit möglich ist. Grundlegende Vorgehensweise Um eine Menge von Constraints zu erfüllen, wird zu jedem Constraint eine Methode gewählt. Aus den Variablen und den Constraints als Knoten sowie den gewählten Methoden als Kanten entsteht der Methodengraph. Kantenrichtungen geben an, welcher Constraint welche Variable setzen darf. Haben mehrere Constraints dieselbe Variable in ihrem Ausgabebereich, entsteht ein KonÄikt. Enthält der Graph keine Zyklen und keine KonÄikte, kann eine den Constraints entsprechende Variablenbelegung ermittelt werden, indem die gewählten Methoden in topologischer Reihenfolge ausgeführt werden. Zyklen werden hier zu speziellen Knoten zusammengefaflt, die zunächst wie normale Knoten behandelt werden, und wenn die zugehörige Methode aufgerufen wird, von einem speziellen AuÄöse-Algorithmus behandelt werden. ?SkyBlue? benutzt Constraint-Hierarchien, um optimale Methodengraphen zu erzeugen. Ein Methodengraph heiflt hier optimal, wenn kein unerfüllter Cons- 20 KAPITEL 2. SEMINARVORTRÄGE traint erfüllt werden könnte, ohne dafl durch die veränderte Methodenwahl ein KonÄikt mit Constraints gleicher oder höherer Stärke auftritt. Der SkyBlue-Algorithmus Ausgehend von leerem Methodengraph werden einzelne Constraints hinzugefügt/entfernt. In jedem Schritt wird der neu entstandene Graph optimiert und die gewählten Constraint-Methoden werden ausgeführt, damit die Variablenwerte die jeweiligen Constraints erfüllen. Wird ein neuer Constraint hinzugefügt bzw. ein bestehender entfernt, versucht der Algorithmus, die nicht erfüllten Constraints durch die Konstruktion von Methoden-Ketten zu erfüllen. Können in einem Methodengraphen keine zusätzlichen Constraints durch Methoden-Ketten erfüllt werden, ist dieser optimal. Methoden-Ketten Um einen Constraint zu erfüllen (den Ausgangsconstraint der Kette), wählt ?SkyBlue? eine Methode dieses Constraints. Steht diese Methode in KonÄikt mit anderen, bereits erfüllten Constraints, werden diese zunächst aufgehoben. Gleichstarke oder stärkere Constraints müssen wieder erfüllt werden, indem für sie andere Methoden gewählt werden, die nicht mit dem Ausgangsconstraint kollidieren. Diese neu gewählten Methoden können wiederum in KonÄikt zu anderen Constraints stehen, für die dann neue Methoden gewählt werden, so dafl eine Kette von Constraints mit neu gewählten Methoden entsteht. Dies geht im Detail folgendermaflen: Anfangs besteht die Kette nur aus dem Anfangsconstraint (AC). Constraints, die dazu in KonÄikt stehen, werden aufgehoben und in die Kette eingereiht. Dabei werden Constraints, die gleich oder stärker als der AC sind, wieder erfüllt, indem für sie andere Methoden gewählt werden, die mit keinem Constraint der Kette kollidieren. Hierbei können durch KonÄikte weitere Constraints die Kette verlängern. Konnten auf diese Weise alle stärkeren Constraints in der Kette erfüllt werden, ist der AC erfüllbar und der Methodengraph kann entsprechend angepaflt werden. Sollte beim Verfolgen der Kette für einen Constraint keine Methode wählbar sein, die mit der gesamten Kette kollisionsfrei ist, erfolgt ein Backtracking- Schritt: Der Erfüllungsvorgang wird schrittweise zurückgenommen, bis für einen Constraint eine andere Methode gewählt werden kann, mit der dann weiterverzweigt wird. Sollte keine konÄiktfreie Kette möglich sein, kann der Ausgangsconstraint nicht erfüllt werden, der Methodengraph bleibt unverändert. In Abbildung 2.7(a) ist der Methodengraph zum Beispiel aus Abschnitt 2.1.3.2 zu sehen. Der starke Constraint C2 ist nicht erfüllt (dargestellt durch die gestrichelten Linien) und soll eingeplant werden. Dies kann geschehen, indem C3 zunächst aufgehoben wird. Damit kann C2 die Variable V2 bestimmen (V1 ist hierfür die Eingabe), siehe Abbildung 2.7(b). Da aber C3 stärker ist, mufl dieser seinerseits wieder erfüllt werden. Dies kann geschehen, indem C4 aufler Kraft gesetzt wird. Da es für C4 keine alternative Methode gibt, und C2 stärker ist als C4, ist in Abbildung 2.7(c) ein optimaler Methodengraph erreicht. Ebenso wäre es im ersten Schritt möglich gewesen, C1 aufzuheben und zum optimalen Graphen 2.7(d) zu gelangen. In beiden Fällen ist ein Constraint der Stärke 1 nicht erfüllt, im Vergleich zu 3 im Ausgangsgraphen (a). Worst case: exponentielle Laufzeit Da das allgemeine CSP NP-hart ist (siehe Abschnitt 2.1.7), liegt die Vermutung nahe, dafl auch das hier vorgestellte 2.1. CONSTRAINT PROGRAMMING 21 Abbildung 2.7: Optimierung eines Methodengraphs Verfahren im worst case exponentielle Laufzeit hat. In Abbildung 2.8 ist ein Beispiel hierfür angegeben: Um den Constraint C1 zu erfüllen, mufl für C2 eine andere Methode gewählt werden. Da C2 bis C4 aus je zwei Variablen die Werte der anderen beiden ermitteln können, gibt es hierfür verschiedene Möglichkeiten. Eine Möglichkeit ist hier mit b bezeichnet. Für C3 könnte jetzt ebenfalls b gewählt werden, bei C4 scheitert allerdings sowohl b als auch die Alternative c (in der ein Pfeil auf die andere Variable von C5 zeigt) am KonÄikt mit dem stärkeren C5 (Abbildung 2.8(b)). Im Backtrackingschritt wird für C3 die Möglichkeit c geprüft, was ebenfalls scheitert, egal welche Methode für C4 gewählt wird (Abbildung 2.8(c)). Erneutes Backtracking probiert die Methode c für C2 und nacheinander b und c für C3. Dies scheitert analog (Abbildung 2.8(d) und (e)). Es wurden also für C2 zwei Methoden (b und c) probiert, für jeden dieser Fälle zwei Methoden für C3 und dafür wiederum jeweils zwei Methoden für C4. Es muflten insgesamt also 23 mögliche Methodenkombinationen geprüft werden, bevor feststand, dafl C1 nicht erfüllt werden kann. Es ist leicht zu sehen, dafl C2 bis C4 durch n Constraints gleicher Art ersetzt werden können, wodurch die Suche 2n Schritte dauern würde. Möglichkeiten zur Steigerung der EÖzienz Gröflere Methodengraphen haben deutlich mehr KonÄikte zur Folge, was sich negativ auf die Laufzeit auswirkt. Als Maflnahmen zur Einschränkung der jeweils zu betrachtenden Constraints kommen hier in Frage: 1. Schrittweises Propagieren in Fluflrichtung: Analog zur Weitergabe von Werten innerhalb eines Constraintnetzes kann nach dem Hinzufügen eines Constraints von den Variablen ausgegangen werden, die dadurch neu bestimmt wurden. Nur diejenigen Variablen, Methoden und Constraints, die in Pfeilrichtung erreichbar sind, müssen neu betrachtet werden. 2. Unerfüllte Constraints nach Stärke abarbeiten: Konnte ein Constraint durch Konstruktion einer Methodenkette erfüllt werden, so wurden notwendigerweise alle stärkeren Constraints auch erfüllt (siehe Arbeitsweise des Algorithmus in 2.1.5.2). Unerfüllt bleiben damit nur Constraints, die schwächer als der Ausgangsconstraint der Kette sind. 22 KAPITEL 2. SEMINARVORTRÄGE Abbildung 2.8: Beispiel für den Worst case Versucht man also, die unerfüllten Constraints in der fallenden Reihenfolge ihrer Stärke zu erfüllen, mufl jeder dieser Constraints nur einmal bearbeitet werden. Insbesondere kann abgebrochen werden, sobald an einer Stelle keine Methodenkette mehr möglich ist, da dann für schwächere Constraints erst recht keine Kette erzeugt werden kann (die ja den momentanen, stärkeren Constraint mit erfüllen müflte). 3. Änderungsstärken für Variablen berechnen: Soll durch einen neu eingefügten Constraint C1 ein anderer Constraint C2 aufgehoben werden (da dieser dieselbe Variable in seinem Ausgabebereich hatte), setzt dies voraus, dafl in der entstehenden Methodenkette sowohl für C2 als auch für folgende abhängige Constraints, die stärker als C1 sind, alternative kon- Äiktfreie Methoden möglich sind. Wenn bereits im voraus bekannt wäre, ob dies für eine bestimmte Stärke von C1 möglich ist, könnte der aufwendige erfolglose Versuch, eine Kette zu konstruieren, entfallen. Dies wird durch das Ermitteln und Speichern von Änderungsstärken zu jeder Variable möglich. Die Änderungsstärke ist die Stärke des schwächsten Constraints, der aufgehoben werden müflte, damit die Variable nicht mehr durch Constraints bestimmt ist, und somit durch einen neu hinzukommenden Constraint bestimmt werden kann. 2.1. CONSTRAINT PROGRAMMING 23 function Änderungsstärke(constraint C, variable v) min := Stärke(C) Für alle Methoden m zum Constraint C vm := Ausgabevariable von m if (Stärke(vm) < min) min := Stärke(vm) end für alle return min end function Damit kann direkt ermittelt werden, ob das Aufheben eines Constraints zum Zwecke der Bestimmung einer Variablen durch einen neuen Constraint Erfolg hat: Ist die Änderungsstärke der Variablen kleiner als die Stärke des neuen Constraint, kann die Änderung gewinnbringend durchgeführt werden, sonst ist sie nicht möglich. 2.1.6 EinÄufl des Benutzers In den vorherigen Abschnitten wurde gezeigt, wie Constraint Solver versuchen, die EÖzienz der Lösungssuche durch geeignete Reduzierung von Wertemengen oder zu betrachtenden Variablen zu steigern. Dabei ist es wichtig, sich nicht nur auf die Fähigkeiten des Solvers zu verlassen. Durch geschickte Wahl des Datenmodells kann die Zahl der Constraints gering gehalten werden, indem manche Bedingungen als implizite Constraints bereits durch das Modell sichergestellt werden: - Soll der Wert einer Variable nicht verändert werden, so braucht dafür kein neuer Constraint eingefügt zu werden, sondern man entfernt diese Variable aus der Variablenmenge des Solvers, dem working set. - Solche unveränderlichen Variablen müssen unabhängig von anderen Variablen sein. Dies läflt sich oft durch Wahl der passenden numerischen Repräsentation für ein Datenobjekt erreichen. In Abbildung 2.9 sollte die Beschreibung der Schwungstange durch Anfangspunkt, Winkel und Länge (statt durch Anfangs- und Endpunkt) erfolgen. Winkel und Länge als Konstanten können aus dem working set entfernt werden. - Wertegleichheit läflt sich durch merging erreichen: Variablen, die gleich sein sollen, werden zusammengefaflt, so dafl alle Constraints, die diesen Wert benutzen, auf dieselbe Variable zugreifen. Die einheitliche Gröfle der verschiedenen Räder in Abbildung 2.9 könnte somit durch einen einzigen Wert repräsentiert werden (statt einem pro Rad mit zugehörigem Gleichheitsconstraint). Implizite Constraints sind im Unterschied zu explizit numerisch angegebenen Constraints exakt. Dies kann von Vorteil sein, hat aber auch den Nachteil, dafl der Solver keine Wertetoleranzen zur Beschleunigung der Suche nach einer nahezu optimalen Lösung ausnutzen kann. 2.1.7 Komplexität Die vorgestellten Constraint-Solving-Verfahren versuchen durch eine geschickte Steuerung der Lösungssuche die Laufzeit zu verringern. Verschiedene Heuristische Verfahren kommen zum Einsatz oder könnten an passenden Stellen noch 24 KAPITEL 2. SEMINARVORTRÄGE Abbildung 2.9: Beispiel für implizite Constraints eingebaut werden. Dies ist für eine akzeptable Laufzeit vermutlich unumgänglich, denn es gilt: Satz 2.1.4 CSP ist NP-hart. Beweis 2.1.4 3SAT <=p CSP Eingabe für 3SAT ist eine logische Formel in konjunktiver Normalform mit höchstens drei Variablen pro Klausel. Diese Formel läflt sich direkt auf ein CSP abbilden: Die Variablen des CSP sind genau die logischen Variablen aus 3SAT. Jede Klausel ergibt einen Constraint, der prüft, ob die Klausel erfüllt ist. Dieses CSP hat genau dann eine Lösung, wenn die Formel erfüllbar ist. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 25 2.2 Objektorientierte Spezi?kation nach der Booch-Methode (Lars Hermes) 2.2.1 Einleitung Heutige (industriell) erstellte Software-Systeme haben eine derartige Komplexität, dafl es für einen einzelnen Entwickler nicht mehr möglich ist, diese zu überblicken und zu verstehen, geschweige denn, ein solches System alleine zu entwickeln. Man betrachte z.B. ein Software-System, das die Abläufe in einem Kraftwerk steuert. Wie kann dieses Problem nun gelöst werden? Ganz einfach, indem das System in kleinere, handhabbare Teile zerlegt wird und auf diese Teile Entwicklungsteams angesetzt werden. Wie kann diese Zerlegung nun erfolgen? Da gibt es zwei unterschiedliche Ansätze: - Algorithmische Zerlegung - Objektorientierte Zerlegung 2.2.1.1 Algorithmische Zerlegung Die algorithmische Zerlegung betrachtet die Elemente Datenstrukturen und Algorithmen als getrennte Einheiten. Sie setzt ihre Schwerpunkte auf die Konzentration der Anordnung der Ereignisse, d.h., dafl die Daten durch Prozeduren manipuliert werden, und auf die Zusammenstellung von Modulen, die jedes für sich einen wichtigen Abschnitt im Gesamtablauf des Systems darstellen. 2.2.1.2 Objektorientierte Zerlegung Die objektorientierte Zerlegung betrachtet die Datenstrukturen und Algorithmen als zusammengehörende Elemente. Genauer: die Daten sind im Objekt eingeschlossen und können nur durch die Methoden des Objekts, die die Schnittstelle nach auflen darstellen, manipuliert werden. Welche Schwerpunkte hat die objektorientierte Zerlegung nun? Zum einen werden Objekte verwendet, die Aktionen auslösen oder von Aktionen anderer Objekte betroöen sind. Zum anderen wird das zu zerlegende Problem als Menge autonomer Bestandteile (= Objekte) betrachtet. 2.2.2 Das Objektmodell 2.2.2.1 Überblick Objekte Das Objektmodell beinhaltet die Gesamtheit der Elemente des objektorientierten Entwurfs. Objektorientiert ist als Schlagwort heute in aller Munde. Trotzdem gibt es keine einheitliche De?nition, da es sich aus verschiedenen Quellen ableitet. Das Konzept des Objekts bildet jedoch das Fundament der Objektorientierung. Informell läflt sich das Objekt als greifbare Einheit de?nieren, die ein wohlde?niertes Verhalten zeigt. Ste?g und Bobrow gehen in ihrer De?nition noch weiter und bezeichnen Objekte als ?Einheiten, die die Eigenschaften von Prozeduren und Daten kombinieren; sie führen Programmschritte durch und speichern einen lokalen Status?[SB84]. Tiefer geht die De?nition von Jones: ? : : : Objekte besitzen eine gewisse Integrität, die nicht verletzt werden 26 KAPITEL 2. SEMINARVORTRÄGE sollte : : : . Ein Objekt kann nur seinen Status verändern, sein Verhalten aufzeigen, manipuliert werden oder in einer Beziehung zu anderen Objekten stehen, immer in genau der Art und Weise, die dem Objekt entspricht. Anders ausgedrückt, es gibt invariante Eigenschaften, die ein Objekt und sein Verhalten charakterisieren.?[Jon79] OOP De?nition 2.2.1 Objektorientierte Programmierung ist eine Implementierungsmethode, bei der Programme als kooperierende Ansammlung von Objekten angeordnet sind. Jedes dieser Objekte stellt eine Instanz einer Klasse dar, und alle Klassen sind Elemente einer Klassenhierarchie, die durch Vererbungsbeziehungen gekennzeichnet ist.[Boo94] Aus dieser De?nition lassen sich drei wichtige Bestandteile ableiten: 1. Grundbausteine sind Objekte und nicht Algorithmen 2. Jedes Objekt ist eine Instanz einer Klasse 3. Klassen stehen miteinander in Vererbungsbeziehung OOD De?nition 2.2.2 Objektorientiertes Design ist eine Designmethode, die den Prozefl der objektorientierten Zerlegung beinhaltet, sowie eine Notation für die Beschreibung der logischen und physikalischen, wie auch statischen und dynamischen Modelle des betrachteten Systems.[Boo94] Wichtig hierbei ist, dafl objektorientiertes Design 1. zu einer objektorientierten Zerlegung führt und 2. unterschiedliche Notationen benutzt werden, um neben den statischen und dynamischen Aspekten des Systems auch die verschiedenen Modelle des logischen (Klassen- und Objektstruktur) und physikalischen (Modul- und Prozeflarchitektur) Designs eines Systems zu beschreiben. OOA De?nition 2.2.3 Die objektorientierte Analyse ist eine Analysemethode, die die Anforderungen aus der Perspektive der Klassen und Objekte, die sich im Vokabular des Problembereichs ?nden, betrachtet.[Boo94] Die OOA legt gröflten Wert auf die Erzeugung von Modellen der realen Welt, und zwar mit Hilfe einer objektorientierten Sicht der Welt. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 27 OOA OOD OOP Ergebnisse als Modell Ergebnisse als Entwürfe Abbildung 2.10: Zusammenhang OOA-OOD-OOP 2.2.2.2 Elemente des Objektmodells Die vier Hauptelemente des Objektmodells sind: - Abstraktion - Kapselung - Modularität - Hierarchie Wenn ein Hauptelement fehlt, handelt es sich nicht mehr um Objektorientierung Weiterhin gibt es drei weniger wichtige Elemente: - Typisierung - Nebenläu?gkeit - Persistenz Diese Elemente sind zwar nützlich, aber kein unentbehrlicher Bestandteil des Objektmodells. Abstraktion Bei der Abstraktion handelt es sich um eine Verallgemeinerung, bei der man sich auf die wesentlichen Details eines Objektes konzentriert und die weniger wichtigen ignoriert. Unter wichtigen Details versteht man diejenigen Charakteristika, die die Eigenschaften eines Objektes ausmachen >= die Einteilung in wichtige und unwichtige Details hängt selbstverständlich von der Perspektive des Betrachters ab. Die Abstraktion macht das Verständnis der Zusammenhänge eines komplexen Objektes einfacher. Kapselung Bei der Kapselung handelt es sich um eine Methode, die Details der Objekt-Implementierung zu verbergen, man bezeichnet sie deshalb auch als ?information hiding?. Die Kapselung verbietet also einen Blick in die Interna (das sind i.a. die Daten oder spezielle Methoden) eines Objektes. Auf diese verborgenen Elemente kann von auflen nur über die Schnittstelle des Objektes zugegriöen werden; dabei handelt es sich um die Methoden, die ein Objekt zur Verfügung stellt. 28 KAPITEL 2. SEMINARVORTRÄGE Modularität Die Modularität packt Abstraktionen in eigenständige Einheiten. Diese Einheiten sollten funktional zusammengefaflt werden. Hierarchie Die Abstraktionen werden mittels der Modularität in funktionale Einheiten gepackt. Diese Einheiten bilden eine Hierarchie. Mit anderen Worten: Die Abstraktionen werden von oben nach unten immer detaillierter. Typisierung Strenge Typisierung verhindert die Vermischung von Abstraktionen. Die Typisierung hilft bei der Einschränkung von Abstraktionen, d.h. sie stellt eine Art Überwachungsmechanismus dar, der kontrolliert, dafl die Abstraktionen nur in dem für sie vorgesehenen Aktionsrahmen agieren. Nebenläu?gkeit Mit der Nebenläu?gkeit wird es verschiedenen Objekten erlaubt, gleichzeitig in einem System zu agieren. Dies ist natürlich nur möglich, solange die parallel ablaufenden Objekte nicht voneinander abhängen. Persistenz Die Persistenz ist ein Mechanismus, der das ?Überleben? eines Objektes durch Raum und Zeit ermöglicht. Wobei mit Raum gemeint ist, dafl das Objekt seinen Speicherplatz z.B. vom Hauptspeicher auf Diskette wechseln kann, ohne seine Informationen zu verlieren. Über die Zeit hinweg bedeutet, dafl das Objekt seinen Erzeuger überleben kann, d.h. dafl ein Objekt weiterexistieren kann, obwohl sein Aufrufer bereits nicht mehr existiert. 2.2.3 Objekte und Klassen 2.2.3.1 Objekte Was sind Objekte? Jedes Objekt besitzt einen Status, ein Verhalten und eine Identität: Status Unter Status versteht man die unveränderlichen Eigenschaften eines Objekts plus deren dynamischen Werte. Betrachtet man z.B. das Objekt Aufzug: Dessen unveränderliche Eigenschaften sind, dafl er sich nur in vertikaler, nicht aber in horizontaler Richtung bewegen kann, seine dynamischen Werte können z.B. das aktuelle Stockwerk sein und das nächste, an dem er halten soll. Verhalten Das Verhalten bezeichnet die Art und Weise, wie das Objekt durch Statusänderungen oder durch Nachrichtenübergabe agiert bzw. reagiert. Beim Beispiel des Aufzugs wäre dessen Verhalten eine Bewegung nach oben bzw. nach unten, das Verhalten eines Objekts hat also EinÄufl auf die dynamischen Werte seines Status'. Identität Die Identität eines Objekts trägt zu seiner Einzigartigkeit bei. Wie man später sehen wird, handelt es sich bei Objekten um Instanzen von Klassen. Diese Klassen geben ihren Instanzen ihren Status und ihr Verhalten vor. Durch die Identität werden Objekte von derselben Klasse voneinander unterscheidbar. Beim Aufzug wäre das z.B. der Aufzug des Eiöelturms oder der Aufzug in der Fakultät Informatik. Beide haben denselben Status und dasselbe Verhalten, aber jeder eine eigene Identität. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 29 Zusammenarbeit zwischen Objekten Zwischen Objekten gibt es zwei Arten von Zusammenarbeit: - Links Einfache Zusammenarbeit zwischen Objekten. Es handelt sich hierbei um eine gleichberechtigte Client-/Supplier-Beziehung. - Aggregation Diese gibt eine Ganzes-/Teil-Hierarchie zwischen Objekten an, d.h. ein Aggregat-Objekt umschlieflt ein Attribut-Objekt, das Bestandteil des Aggregats ist. Diese Bestandteil-Beziehung kann (mufl aber nicht) physikalischer Natur sein. Z.B. bilden bei einem Objekt Aktionär die Aktien, die er besitzt, das Attribut, diese sind jedoch nicht physikalischer Bestandteil des Aktionärs. Anders sieht es bei einem Objekt Flugzeug aus, dessen Tragfächen einen physikalischen Bestandteil bilden. Peter:Zivi f:Fuehrerschein faehrt Bus:Fahrzeug Paul:Kunde r:Rollstuhl betreut besucht Schule1:Schule Abbildung 2.11: Beispiel für die Zusammenarbeit zwischen Objekten (bei den Objekten Zivildienstleistender (Zivi) und Kunde handelt es sich um Aggregate) 30 KAPITEL 2. SEMINARVORTRÄGE 2.2.3.2 Klassen Was ist eine Klasse? Eine Klasse gibt eine gemeinsame Struktur und ein gemeinsames Verhalten für deren Instanzen (= Objekte) vor. Eine Klasse kann im Prinzip als Schablone für das von den Objekten realisierte Verhalten und deren Eigenschaften gesehen werden. Zusammenarbeit zwischen Klassen Klassen können auf verschiedene Arten in Beziehung miteinander stehen: - Assoziation - Vererbung - Aggregation - Verwendung - Instantiierung - Metaklasse Assoziation Einzelne Klassen stehen in Verbindung miteinander. Diese Abhängigkeiten lassen sich durch Rollen darstellen, die die Klassen in ihrer Beziehung miteinander übernehmen. Weiter kann der Assoziation zweier Klassen eine Kardinalität zugeordnet werden. Die Kardinalität zeigt, dafl für die Anzahl von Instanzen der einen Klasse eine oder mehrere Instanzen der anderen Klasse vorhanden sein können. Vererbung Klassen können voneinander abgeleitet werden, d.h. die abgeleitete Klasse (= Subklasse) ?erbt? die Attribute und Methoden von der Vorgängerklasse (= Superklasse). Es gibt zwei Arten von Vererbung : die Einfachvererbung, bei der jede Subklasse von genau einer Superklasse erben kann, oder die Mehrfachvererbung, bei der jede Subklasse mehrere Superklassen haben kann. Aggregation Für die Aggregation von Klassen kann eine direkte Parallele zur Aggregation von Objekten gezogen werden, d.h. die Aggregation von Klassen gibt, genauso wie die Aggregation zwischen Objekten, eine Ganzes- /Teilhierarchie zwischen Klassen an. Im Unterschied zu der Assoziation, die keine Richtung besitzt, besitzt die Aggregation eine Richtungsangabe. Aggregate dürfen nicht zyklisch sein. Verwendung Bei der Verwendung handelt es sich um eine Verfeinerung der Assoziation. Man spricht von einer Client-/Supplierbeziehung, d.h. eine Klasse bietet Dienste an (Supplier), die eine andere Klasse benutzt (Client). Instantiierung Eine parametrisierte Klasse stellt eine Klassenfamilie dar, deren Verhalten unabhängig von ihrem formalen Parameter (= abstrakter Datentyp) de?niert ist. Durch die Instantiierung einer Klasse wird deren formaler Parameter durch einen aktuellen Parameter (= realer Datentyp) ersetzt. Bei der Instantiierung handelt es sich somit um die Bildung einer konkreten Klasse (Vergleichbar mit dem Konzept der Templates in C++). 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 31 Metaklasse Eine Metaklasse bezeichnet die Klasse einer Klasse. Von einer Metaklasse dürfen keine Instanzen gebildet werden. Hauptsächlicher Verwendungszweck von Metaklassen: Zur Verfügung Stellen von Klasseninstanzvariablen (Dieses Konzept ist vergleichbar mit den statischen Elementen in C++). Zivis Fuehrerschein Rollstuhl Behinderte Hebebuehne Fahrzeug Transporter transporter Spezial- Abbildung 2.12: Beispiel 1 In Beispiel 1 stehen die Klassen Zivis und Behinderte in Beziehung. Die Klassen Zivis und Führerschein bilden eine Aggregation, ebenso wie die Klassen Behinderte und Rollstuhl. Die Klasse Zivis verwendet die Klasse Spezialtransporter. Spezialtransporter erbt von den Klassen Transporter und Hebebühne, die Klasse Transporter erbt wiederum von der Klasse Fahrzeug. 32 KAPITEL 2. SEMINARVORTRÄGE Stunden Stunden- abrechnung Abrech.- art Abrechnung Zivi Stunden PersNr Abbildung 2.13: Beispiel 2 In Beispiel 2 wird die Klasse Stundenabrechnung von der Klasse Abrechnung instantiiert, in dem sie die Klasse Stunden verwendet. Die Metaklasse der Klasse Zivi bietet die Klasseninstanzvariable PersNr. an, die im System nur einmalig vorkommen darf. 2.2.3.3 Klassen und Objekte in Analyse und Design Für den Entwickler stellen sich während der Analyse und in der frühen Designphase zwei grundlegende Fragen: - Finden der Klassen und Objekte, die das Vokabular des Problembereichs bilden. Die gefundenen Klassen und Objekte nennt man auch die Schlüsselabstraktionen des Systems. - Gruppierung der einzelnen Objekte mit anschlieflendem Aufstellen einer Struktur, in der diese Objektgruppen zusammenarbeiten und so dem von den Problemanforderungen erwünschten Verhalten gerecht werden. In diesem Schritt werden also die Mechanismen gefunden, die zur Problemlösung beitragen. 2.2.4 Klassi?zierung 2.2.4.1 Probleme bei der Klassi?zierung Welche Möglichkeiten gibt es, um die Schlüsselabstraktionen und die Mechanismen eines Problems zu ?nden? Oder einfacher ausgedrückt, wie ?ndet man die passenden Klassen bzw. Objekte, und wie arbeiten diese zusammen? Um diese Frage zu klären, sollte man sich zuerst Gedanken darüber machen, welche Probleme bei dem Finden von Klassen auftreten können. Unterhalten sich mehrere 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 33 Personen über ein Problem, von dem sie versuchen, dessen Schlüsselabstraktionen zu ?nden, wird jeder einzelne auf seine eigene Lösung kommen. Es müssen also Strategien angewendet werden, um das Finden der Schlüsselabstraktionen und Mechanismen im Entwicklungsteam zu steuern. 2.2.4.2 Analyseansätze Bei der Analyse gibt es keine deterministische Vorgehensweise. Das Entdecken geeigneter Klassen und Objekte zur Modellierung des Problems während der Analysephase und das Finden geeigneter Abstraktionen und Mechanismen zur Realisierung des gewünschten Verhaltens hängen weitgehend von der Erfahrung der Entwickler ab. Die vorgestellten Analyseansätze sollen beispielhaft skizzieren, wie geeignete Klassen und Objekte gefunden werden können. - klassischer Ansatz - Verhaltensanalyse - Bereichsanalyse - Gebrauchsfall-Analyse - informelle sprachliche Beschreibung - CRC-Karten - (Strukturanalyse) Klassischer Ansatz Mit diesem Ansatz werden Klassen abgeleitet, indem die real existierenden Objekte und Verantwortlichkeiten des zu modellierenden Systems direkt übernommen werden. - reale Dinge (z.B. Fahrzeuge, Touren : : : ) - Rollen (z.B PÄeger, Fahrer : : : ) - Ereignisse (z.B. Transport : : : ) - Interaktionen - Organisatorische Einheiten - : : : Verhaltensanalyse Bei diesem Ansatz bildet man Klassen derart, dafl Objekte die ein ähnliches Verhalten aufzeigen, in einer Klasse zusammengefaflt werden. Es wird das dynamische Verhalten betrachtet, d.h. welchen Zweck erfüllen die Objekte innnerhalb des Systems? Durch diesen Ansatz könnte man auf folgende Klassenkandidaten kommen: - Zivis, die Schulfahrten erledigen - Zivis, die Essen ausfahren - Planer, die Touren zusammenstellen - Fahrzeuge, die Rollstuhlfahrer transportieren - : : : 34 KAPITEL 2. SEMINARVORTRÄGE Bereichsanalyse Die Bereichsanalyse bildet Klassen, deren Objekte sich einem gemeinsamen Bereich zuordnen lassen. Unter Bereich werden verwandte Bestandteile innerhalb des zu modellierenden Systems verstanden. Diese Methode eignet sich i.a. dazu, neue Schlüsselabstraktionen zu ?nden, wenn während der Analyse ein Stillstand auftritt, indem Bereichsexperten hinzugezogen werden, d.h. Fachleute, die mit dem zu modellierenden Problem tagtäglich zu tun haben. Durch die Bereichsanalyse könnten folgende Klassen gefunden werden: - Dialysepatienten - Schüler einer bestimmten Schule - Schulwege zu einer bestimmten Schule - Transporter für Rollstuhlfahrer - Zivis mit spezieller Ausbildung im PÄegedienst - : : : Gebrauchsfall-Analyse Unter Gebrauchsfall versteht man ein Muster für die jeweilige Anwendung in Teilbereichen des Problems. Die Gebrauchsfälle müssen jedoch wieder durch die anderen Ansätze auf einzelne Klassenkandidaten untersucht werden. Ein Beispiel für einen Gebrauchsfall wäre z.B.: ?Ein Zivi startet morgens am DRK, holt unterwegs eine bestimmte Anzahl von Schülern ab, in dem er einer vorgegebenen Tour folgt, bringt diese zur Schule und fährt zurück zum DRK.? Informelle sprachliche Beschreibung Bei dieser Analysemethode beschreibt man das Problem, indem ein in Umgangssprache verfaflter Text erstellt wird, der die Anforderungen genau beschreibt. Kandidaten für Klassen sind hierbei die Substantive innerhalb des Textes und die Verben könnten potentielle Methoden darstellen. Diese Methode ist mit Vorsicht zu genieflen, da umgangssprachliche Beschreibung ein höchst ungenaues Mittel zur Beschreibung eines Problems ist. Desweiteren mufl man auch darauf achten, dafl Verben substantiviert werden können. Ein Vorteil dieser Methode ist, dafl der Entwickler gezwungen wird, im Vokabular des Problembereichs zu denken. CRC-Karten Diese Methode ist keine Analysemethode im eigentlichen Sinne. Sondern vielmehr eine Möglichkeit, die anderen Analyseansätze visuell zu unterstützen. CRC steht für Class >= Responsibilities >= Collaborators, also für Klasse >= Verantwortlichkeit >= Beteiligung. Wie kann man die anderen Ansätze damit unterstützen? CRC-Karten sind im Prinzip Karteikarten, bei denen oben der Klassenname steht, auf der linken Seite die Verantwortlichkeiten (was macht die Klasse?) und auf der rechten Seite die Beteiligungen (welche Klassen sind noch betroöen?). Zur besseren Übersicht können die Karten farblich unterschiedlich sein und an eine Pinnwand geheftet werden (zusätzlich können diejenigen Klassen mit Linien verbunden werden, die zusammenarbeiten). 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 35 Strukturanalyse Die Strukturanalyse ist nur bedingt für die objektorientierte Spezi?kation einsetzbar. Da sie ihre Ursprünge in der strukturierten Analyse bzw. strukturierten Programmierung hat. Hier wird das Modell des Systems mittels DatenÄufldiagrammen erstellt. Was könnte nun eine Klasse sein? - externe Entitäten - Datenelemente - Steuerungselemente - : : : Abschlieflend läflt sich sagen, dafl keine dieser Analysemethoden für sich alleine ausreichen wird, um ein vollständiges Modell und die ersten Designansätze für ein System zu liefern. Eine Kombination sollte jedoch eine gute Grundlage liefern. 2.2.4.3 Zentrale Fragen der Analyse Bevor man sich jedoch darauf stürzt, irgendwelche Klassen zu ?nden, die das System modellieren könnten, ist es nötig, sich zu überlegen, welche Ziele mit der Analyse verfolgt werden sollten. Es sind hierbei zwei wichtige Punkte zu nennen: - Was ist das gewünschte Verhalten des Systems, d.h. was soll das System leisten, was wird von ihm erwartet? - Was sind die Rollen und Verantwortlichkeiten der Objekte, die dieses Verhalten realisieren? Diese Frage erfordert natürlich, dafl schon eine gewisse Vorstellung der Objekte vorhanden ist. 2.2.4.4 Zentrale Fragen des Designs Die Aufgabe des Designs besteht darin, die in der Analyse gefundenen Schlüsselabstraktionen und Klassen sinnvoll im System unterzubringen und gegebenenfalls zu erweitern. Dabei sollte zuerst überlegt werden, wie das Design auszusehen hat und was damit bezweckt werden soll. - Welche Klassen existieren und in welcher Beziehung stehen diese Klassen? Diese Frage läflt sich nicht eindeutig dem Design zurechnen, da auch schon während der Analyse Klassen entdeckt bzw. erfunden werden. Dieses Problem, dafl Analyse und Design nicht sauber zu trennen sind, wird jedoch noch häu?ger auftreten. - Welche Mechanismen werden verwendet, um die Zusammenarbeit der Objekte zu steuern? - Wo sollen die einzelnen Klassen und Objekte deklariert werden? - Welchem Prozessor sollte ein Prozefl zugeordnet werden, und wie sollte für einen bestimmten Prozessor die zeitliche Reihenfolge der verschiedenen Prozesse festgelegt werden? 36 KAPITEL 2. SEMINARVORTRÄGE 2.2.5 Notation 2.2.5.1 Klassendiagramme Wozu dienen die Klassendiagramme? Sie dienen der Darstellung der Existenzen von Klassen und deren Beziehungen miteinander. Das Klassendiagramm erzeugt eine logische Sicht des zu entwickelnden Systems. In der Analysephase hilft das Klassendiagramm, die Klassen und deren Verantwortlichkeiten darzustellen. Während des Designs zeigt das Klassendiagramm die Struktur des Systems. Klassenname form. Arg. Name der param. Klasse akt. Arg. Name der instant. Klasse Klassenkategorie Name Klassen Name der Metaklasse Klassen-Utility-Name Abbildung 2.14: Klassen-Icons Klassen-Icons Bis auf Klassenkategorien und Klassenutilities sind die Bedeutungen der einzelnen Icons bereits bei der Zusammenarbeit von Klassen erklärt worden. Ein Klassenutility bietet globale Attribute und Methoden an, auf die alle Klassen zugreifen können. Die Klassenkategorien helfen bei der Strukturierung der Klassendiagramme. In einer Klassenkategorie werden diejenigen Klassen zusammen gefaflt, die im Klassendiagramm eine funktionale Einheit bilden, d.h. Klassenkategorien bilden Klassenbibliotheken. Im Bsp. verwendet die Klassenbiblithek ?Fahrdienste des DRK? zum Beispiel die GUI-Bibliothek, um die graphische OberÄäche darzustellen. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 37 Fahrdienste des DRK Essen auf Rädern Schulfahrten Touren zus.stellen GUI- Bibliothek Abbildung 2.15: Beispiel für ein Klassenkategorie-Diagramm Klassenbeziehungen Arten von Klassenbeziehungen : - Assoziation: Einfache Beziehungen zwischen Klassen untereinander. Eine Klasse kann auch eine Assotiation zu sich selbst besitzen (= reÄexive Assoziation). - Vererbung ("is-a"-Beziehung): Der Pfeil zeigt auf die Oberklasse. Vererbungsbeziehungen dürfen keine Zyklen enthalten. - Eigentum (Aggregation oder ?has?-Beziehung): Der ausgefüllte Kreis am Ende der Assoziation gibt das Aggregat an. Die Klasse am anderen Ende gibt den Teil an, dessen Instanzen im Aggregat- Objekt enthalten sind. - Verwendung (Client-/Supplier-Beziehung): Der Kreis am Ende der Assoziation gibt den Client an, der auf irgendeine Art und Weise vom Supplier abhängig ist, um bestimmte Dienstleistungen zu realisieren (z.B. Operationen der Clientklasse rufen Operationen der Supplierklasse auf). - Instantiierung: Die instantiierte Klasse (mit aktuellem Parameter) zeigt auf die parametrisierte Klasse (mit formalem Parameter). - Metaklasse (Klasse einer Klasse): Metaklassen werden verwendet, um Klasseninstanzvariablen und - 38 KAPITEL 2. SEMINARVORTRÄGE operationen zur Verfügung zu stellen, können also selbst keine Instanzen besitzen. Metaklassen können aber von anderen Klassen erben. Vererbung Assoziation "Eigentum"-Beziehung "Verwendung"-Beziehung Instantiierung Metaklasse Abbildung 2.16: Klassenbeziehungen Kennzeichnungen der Beziehungen Beziehungen können beschrieben werden, um die Zusammenarbeit der Klassen deutlich zu machen: - Rolle: Sie gibt den Zweck oder den Umfang der Beziehung einer Klasse zu einer anderen an. (z.B. Fahrer, Mitarbeiter, Planer, : : : ) - Schlüssel: Ein Attribut, dessen Wert ein einzelnes Zielobjekt eindeutig identi?ziert. (z.B. Fahrzeugnummer, Mitarbeitername, Kunden-ID, : : : ) - Einschränkung: Durch die Einschränkung wird eine sematische Bedingung einer Klasse oder einer Beziehung beschrieben, die erfüllt sein mufl, solange sich das System in einem stabilen Zustand be?nden soll (z.B. TÜV am Fahrzeug darf nicht abgelaufen sein). - Kardinalität: Sie gibt an, wieviele Instanzen der einen Klasse in der Instanz der jeweils anderen Klasse vorhanden sein dürfen. - Attributklasse: Die Attributklassen beschreiben die Eigenschaften der Assoziationen. D.h. jede Assoziation mufl eine Instanz der Attributklasse sein. Beschriftung Rolle [Schlüssel] {Einschränkung} Kardinalität Attributklasse Abbildung 2.17: Kennzeichnungen der Beziehungen 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 39 Kennzeichnungen für das Enthaltensein Das (physikalische) Enthaltensein wird dargestellt als Anmerkung am Ende einer ?Eigentum?-Beziehung. Es können zwei Arten unterschieden werden: - über den Wert: Gibt das (physikalische) Beinhalten des Wertes des Bestandteils an. - über eine Referenz: Gibt das (physikalische) Beinhalten über einen Zeiger oder eine Referenz auf den Bestandteil an. Wert Referenz Abbildung 2.18: Kennzeichnungen für das Enthaltensein Eigenschaften In einigen objektorientierten Sprachen sind die Beziehungen von ihrer Sematik her gesehen fundamental verschieden, so dafl spezielle Symbole eingeführt werden müssen: - abstrakte Klasse: Von abstrakten Klassen können keine Instanzen erzeugt werden, sie dienen in der Regel dazu, ein Klassengerüst zur Verfügung zu stellen. D.h. die abstrakte Klasse gibt die Schnittstellen der Methoden vor, deren Implementierung in der Verantwortung der Unterklasse liegt. - static: Die Bezeichnung eines Klassenelementobjekts oder einer -funktion (statische Klassen ?nden z.B. in der Programmiersparche C++ Verwendung; Smalltalk oder CLOS verwenden dagegen Metaklassen). - virtual: Diese Eigenschaft wird benutzt, um eine gemeinsam verwendete Basisklasse oder eine polymorphe Operation zu bezeichnen. - friend: Eine friend-Klasse erhält von einer anderen Klasse Rechte, um auf deren nicht- public-Teile zugreifen zu dürfen. Exportsteuerung Die meisten OO-Sprachen bieten eine klare Trennung zwischen Schnittstelle und Implementierung einer Klasse. Mit Hilfe der Exportsteuerung kann der Zugriö auf die Schnittstelle genau spezi?ziert werden. - public: Die Schnittstelle ist für alle Clients erreichbar. - protected: Nur Unterklassen, Friend und die Klasse selbst dürfen auf die Schnittstelle zugreifen. 40 KAPITEL 2. SEMINARVORTRÄGE A abstrakte Klasse S static F friend V virtual Abbildung 2.19: Eigenschaften - private: Auf die Schnittstelle dürfen nur die Klasse selbst oder ein Friend zugreifen. - implementation: Nur die Implementierung hat Zugriö (siehe abstrakte Klassen). public protected private implementation Abbildung 2.20: Exportsteuerung Klassenname verschachtelte Klasse Abbildung 2.21: geschachtelte Klassen Geschachtelte Klassen Klassen können ineinander geschachtelt werden. Dies soll bei der Kontrolle über den Namensraum helfen, da Instanzen von eingeschlossenen Klassen nur in der umgebenden Klasse existieren können. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 41 Text Abbildung 2.22: Notizen Notizen Notizen können entweder an Klassenkategorien oder an Klassen direkt angehängt werden und dienen zur näheren Beschreibung bzw. Orientierung. Klassenspezi?kation Die graphische Sicht der Klassen und deren Zusammenarbeit alleine helfen nicht bei der Systementwicklung. Klassen und später deren Operationen müssen näher spezi?ziert werden. Wie könnte eine solche Klassenspezi?kation nun aussehen? Hier ein Beispiel (die ersten sechs Einträge sollten unbedingt enthalten sein): Name: Bezeichner Definition: Text Verantwortlichkeiten: Text Attribute: Liste der Attribute Operationen: Liste der Operationen Einschränkungen: Liste der Einschränkungen Status Maschine: Referenz auf Statusmaschine (s.u.) Exportsteuerung: public | protected | private | implementation Kardinalität: Ausdruck Parameter: Liste formaler und generischer Parameter Persistenz: transient | persistent Nebenläufigkeit: sequentiell | überwacht | synchron | aktiv Speicherkomplexität: Ausdruck Operationsspezi?kation Eine Klasse beinhaltet verschiedene Operationen, die jede einzeln spezi?ziert werden mufl. Das folgende Beispiel zeigt, wie eine solche Spezi?kation aussehen könnte (die ersten vier Einträge sollten wieder unbedingt enthalten sein): Name: Bezeichner Definition: Text Rückgabeklasse: Referenz auf die Klasse Argumente: Liste formaler Argumente Exportsteuerung: public | protected | private | implementation Protokoll: Text Vorbedingungen: Text | Referenz auf Quellcode | Referenz auf Objektdiagramm Semantik: Text | Referenz auf Quellcode | Referenz auf Objektdiagramm 42 KAPITEL 2. SEMINARVORTRÄGE Nachbedingungen: Text | Referenz auf Quellcode | Referenz auf Objektdiagramm Ausnahmen: Liste der Ausnahmen Nebenläufigkeit: sequentiell | überwacht | synchron Speicherkomplexität: Ausdruck Zeitkomplexität: Ausdruck 2.2.5.2 Zustandsdiagramm Das Zustandsdiagramm zeigt die Existenz von Klassen und, viel wichtiger, wie sie ihr Verhalten ändern. Mit Hilfe von Zustandsdiagrammen läflt sich das dynamische Verhalten von einzelnen Klassen modellieren. Name Attribute Ereignis/Aktion Start Stop Verschachtelung Status-Icon Histrory H Status 1 Status 2 Status 3 Oberstatus Abbildung 2.23: Elemente des Zustandsdiagramms Be?ndet sich ein Querstrich an der Pfeilspitze einer Aktion oder eines Ereignisses, handelt es sich bei dem Status, auf den der Pfeil zeigt, um einen verschachtelten Status, d.h. wird eine Hierarchieebene tiefer gegangen, so öö- net sich der Status zu einem neuen Oberstatus. Das History-Icon gibt an, dafl der Vorgängerzustand gespeichert wird und nach Abarbeitung der aktuellen Zustandsfolge in den Vorgängerzustand zurückgekehrt wird. Das Beispiel zum Zustandsdiagramm in Abbildung 2.24 zeigt exemplarisch an der Klasse Zivi, in welchen Zuständen sich diese Klasse be?nden kann, bzw. wie ein Zivi modelliert werden kann. 2.2.5.3 Objektdiagramme Das Objektdiagramm stellt die Existenz von Objekten und deren Beziehungen bzw. deren Interaktionen miteinander dar. Mit Hilfe von Objektdiagrammen können Szenarien durchgespielt werden, um zu testen, ob das System das gewünschte Verhalten modelliert. Im Beispiel in Abbildung 2.26 wird mit Hilfe eines Objektdiagramms modelliert, wie ein Zivi einen Schüler zur Schule bringt. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 43 Betreuungs- aufgabe Betreuung nichts zu tun Probleme H Schulfahrt fertig unterwegs einladen einladend ausladen Schulfahrt fertig Probleme Probleme Probleme erkennen melden beseitigen in der Schule unbeschäftigt Abbildung 2.24: Beispiel für Zustandsdiagramme für die Klasse Zivis Objekt-Icon Link Nachrichten/Objekt/Wert Rolle {Einschränkung} [Schlüssel] Name Attribute Synchronisation einfach synchron eingeschränkt timeout asynchron Sichtbarkeitsbereich G global P parameter F field L local Abbildung 2.25: Elemente des Objektdiagramms 44 KAPITEL 2. SEMINARVORTRÄGE Max:Zivi Schulfahrt 1:welcheAufg() Dienstplan AktPlan: 2:welcheFzg() Schlüssel DRKPark Fuhrpark 3:benutze Bus:Fzg Moritz Moritz:Schüler Moritz 5:bringe(Schule) XY:Schule 4:hole(Schüler) muß pünktlich sein Abbildung 2.26: Beispiel für ein Objektdiagramm 2.2.5.4 Interaktionsdiagramm Das Interaktionsdiagramm ist eine andere Darstellungsform des Objektdiagramms. Es stellt die Interaktionen zwischen Objekten in zeitlichem Ablauf dar. Das Beispiel in Abbildung 2.27 ist direkt aus dem obigen Beispiel zum Objektdiagramm abgeleitet. 2.2.5.5 Moduldiagramm Anders als die vorhergehenden Diagramme bietet das Moduldiagramm keine logische Sicht auf das zu entwickelnde System, sondern eine physikalische. Das Moduldiagramm modelliert die Aufteilung in einzelne Module, d.h. die Hierarchiestufen der Implementierung. Innerhalb der Module be?nden sich die Klassen, die durch die Module in funktionale Einheiten gegliedert sind. Mit Hilfe der Untersysteme lassen sich einzelne Modulbäume hierarchisch anordnen. Ob eine strikte Trennung zwischen Modulspezi?kation und Modulrumpf besteht, ist abhängig von der Programmiersprache. 2.2. OBJEKTORIENTIERTE SPEZIFIKATION 45