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.

Seite 21: vorherige Seite | nächste Seite | Übersicht

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.

Seite 22: vorherige Seite | nächste Seite | Übersicht

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

Seite 23: vorherige Seite | nächste Seite | Übersicht

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.

Seite 24: vorherige Seite | nächste Seite | Übersicht

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

Seite 25: vorherige Seite | nächste Seite | Übersicht

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.

Seite 26: vorherige Seite | nächste Seite | Übersicht

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.

Seite 27: vorherige Seite | nächste Seite | Übersicht

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.

Seite 28: vorherige Seite | nächste Seite | Übersicht

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)

Seite 29: vorherige Seite | nächste Seite | Übersicht

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++).

Seite 30: vorherige Seite | nächste Seite | Übersicht