OOPM, Ralf Lämmel - userpages.uni-koblenz.desoftlang/oopmcourse/slides/qa.pdf · (C) Ralf Lämmel, OOPM, Universität Koblenz-Landau Themen für die Klausur V/Ü 2 1.Sortieren 2.Algebraische

KlausurvorbereitungOOPM, Ralf Lämmel

Image: Stuart Miles / FreeDigitalPhotos.net http://www.freedigitalphotos.net/images/view_photog.php?photogid=2664

(C) Ralf Lämmel, OOPM, Universität Koblenz-Landau

Themen für die Klausur V/Ü

2

1.Sortieren2.Algebraische Spezifikation3.UML-Klassendiagramm4.Spezifikation abstrakter Datentypen5.Glassbox-Testen6.Verifikation von Algorithmen7.UML-Zustandsdiagramme8.Komplexität von Algorithmen

Analog für die Programmierklausur.Lasst uns eine gemischte Vorbereitung betreiben.


Fragen zum Verwenden eines Programmes

3


Thema: Programmierung mit Feldern

4

Geben Sie Code an zur Konstruktion eines Feldes mit den Elementen 42 und 88 und einem Aufruf der

angegeben Methode sum.

public static int sum(int[] a) {int result = 0;for (int i=0; i<a.length; i++)

result += a[i];return result;

}

(C) Ralf Lämmel, OOPM, Universität Koblenz-Landau 5


Wozu?

Einfache und omnipräsente zusammengesetzte Datenstruktur. Gute Vorbereitung auf Listen.

Erlangen der Einsicht, dass Datenmodellierung so wichtig in der Programmierung ist wie die eigentliche Modellierung der Funktionalität.


Thema: Programmierung mit Schnittstellen

6

Geben Sie Code an für eine Schleife über solche feldartige Typen so dass alle Elemente verdoppelt

werden.

public interface IntArray {int getLength();int getAt(int i);void setAt(int i, int x);

}



7

Wozu?

Schnittstellen sind essentiell für Abstraktion.

Abstraktion ist essentiell für IT.


Thema: Programmierung mit Zeigern

8

public class IntListEntry {public int item;public IntListEntry next;

}

Geben Sie Code an zur Konstruktion einer zyklischen Liste mit den Elementen 42 und 88.



9

Wozu?

Kenne Dein Paradigma; sei kein Stümper!

Leide und warte auf ein besseres Paradigma!

Propaganda!


public class UnboundedIntStack {

...

public void push(int item) { ... }

public boolean isEmpty() { ... }

public int top() { ... }

public void pop() { ... }

}

Thema: Abstrakte Datentypen

Geben Sie Code an zur Konstruktion eines Kellers mit dem obersten Element 42 und darunter 88.


Fragen zum Anpassen eines Programmes

11


Thema: Strukturierte Programmierung

12

Gegeben sei folgendes Programmfragment:

while (condition1()) { statement1(); if (condition2()) break; statement2();}

Schreiben Sie das Programm so um, dass es keine Verwendung von “break” (oder goto u.ä.) macht. Hinweis: Verwenden Sie eine Hilfsvariable.


Thema: Numerische Algorithmen

13

Gegeben sei folgendes Programmfragment:

for (int i = 0; i < 42; i++) { result += delta(i);}

Schreiben Sie das Programm so um, dass die Schleife nicht durch die festcodierte Anzahl der Schleifendurchläufe sondern durch die Unterschreitung eines gewissen Epsilon für das Delta abgebrochen wird.



14

static double sin(double x) {double result = 0;int n = 0;double delta;do {

delta = power(-1,n) * power(x,2*n + 1) / factorial(2*n + 1);result += delta;n++;

} while (Math.abs(delta) > MAX_ERROR);return result;

}

Optimieren Sie den Code.


http://cso.ulb.ac.be/~fbueken/WhyMathPhDDay050912.pdf

Propaganda!


Thema: Rekursive Funktionen

16

Gegeben sei folgendes Programm:

public static int foo(int[] a, int i) { if (i==a.length-1) return a[i]; int z = foo(a, i+1); return z > a[i] ? z : a[i];}

Schreiben Sie das Programm so um, dass es nur Endrekursion verwendet.


public static boolean even(int n) {return (n==0) || !even(n-1);

}


Ändern Sie den Code minimal so ab, dass er nicht mehr den Kurzschluss von “||” ausnutzt.



18

Wozu?

Noch fundamentaler als strukturierte Programmierung, da Rekursion in an allen modernen Sprachen zur Organisation von Funktionalität zur Verfügung steht.


Thema: Verbunde und Datenkapseln

19

Gegeben sei folgender Verbundtyp:

public class Point { public int x; public int y;}

Schreiben Sie diesen Typ so um, dass die Komponenten x und y private Sichtbarkeit bekommen und dafür öffentliche Getter zur Verfügung stehen. Auch soll es keine Setter geben, aber einen Konstruktor, der x und y initialisiert.



Wozu?

Daten und Funktionen kommen selten allein. Am besten ist, wenn man sie verkapselt. Dann gehen sie einander nicht verloren. Das ist so ähnlich wie das System der Ehe -- eine Art der Absicherung. (Es geht auch ohne und manchmal besser.)



21

Gegeben sei folgende Schnittstelle:

public interface SkypeUser { void addContact(SkypeUser u);}

Ändern Sie diese Schnittstelle wie folgt ab: 1. “SkypeUser” erbt von einer weiteren Schnittstelle “Contact” mit Methoden für den Zugriff auf Vor- und Nachnamen. (Definieren Sie auch “Contact”.) 2. Erweitern Sie “SkypeUser” mit Methoden für den Zugriff auf den Skype-Nutzernamen.


Fragen zur Analyse eines Programmes

22


public static int sum(int n) {int result;while (n>0)

result += n--;return result;

}

Überprüfen Sie das Programm in Hinblick auf Java’s Sprachregeln zur Initialisierung von Variablen? Welches Problem tritt hier auf?




Führen Sie das Programm symbolisch (“in Gedanken”) aus. Welches Problem tritt auf?

public static int sum(int[] a) {int result = 0;for (int i=0; i<=a.length; i++)

result += a[i];return result;

}


public static int factorial(int n) {

return (n == 0) ? 1 : n * factorial(n-1);

}


Skizzieren Sie den Code für eine Analyse, welche das maximale Argument für n ermittelt.


Thema: Verifikation von Programmen

26

Type to enter text

{ P }

r = r - y

{ x == q * y + r && r >= 0 && q >= 0 }

q = q + 1

Leiten Sie P ab.


TODO: Ablesen der Zwischen- und Vorbedingungen von hinten anfangend

27

Type to enter text

{ ??? }r = r - y

{ x == q * y + r && r >= 0 && q >= 0 }

q = q + 1

{ ??? }


Hintere Zuweisung in der Schleife

28

{ x == (q + 1) * y + r && r >= 0 && q + 1 >= 0 }

{ x == q * y + r && r >= 0 && q >= 0 }

q = q + 1

Ermittlung der Vorbedingung aus der Nachbedingung.Substituiere q durch q + 1.


TODO: Ablesen der Vorbedingung

29

Type to enter text

{ ??? }r = r - y

{ x == q * y + r && r >= 0 && q >= 0 }

q = q + 1

Nun müssen wir weiter nach vorn gehen.

{ x == (q + 1) * y + r && r >= 0 && q + 1 >= 0 }


Vordere Zuweisung in der Schleife

30

{ x == (q + 1) * y + (r - y) && r - y >= 0 && q + 1 >= 0 }

{ x == (q + 1) * y + r && r >= 0 && q + 1 >= 0 }

r = r - y

Ermittlung der Vorbedingung aus der Nachbedingung.Substituiere r durch r - y.


Betrachtung von Anweisungsfolgen

31

{ x == q * y + r && r >= 0 && q >= 0 }

q = q + 1

{ x == (q + 1) * y + (r - y) && r - y >= 0 && q + 1 >= 0 }

{ x == (q + 1) * y + r && r >= 0 && q + 1 >= 0 }

r = r - y

Die innere Bedingung war nur Mittel zum Zweck.


Abschließende Vereinfachung

32

P ≡ x == (q + 1) * y + (r - y) && r - y >= 0 && q + 1 >= 0 ≡ x == q * y + r && r >= y && q + 1 >= 0



Wozu?

Was erwarten wir uns von Software in Flugzeugen, Steuerungssystemen, Banken, Krankenhäusern?

Sollte es für einen Manager mystisch erscheinen, wie man (in etwa) sichere Software erhält?


Thema: Komplexität von Algorithmen

34

public static int power(int x, int n) {

int result = 1;

for (int i=1; i<=n; i++)

result *= x;

return result;

}

Bestimmen Sie die Summe aller Operationen (nur Vergleichs- und arithmetische Operationen) für

42^3.



35

Bestimmen Sie die Anzahl der Vergleiche und

arithmetischen sowie logischen Operationen für

den schlechtesten Fall.

public static void insertionSort(int[] a) {for (int i=1; i<a.length; i++) {

int x = a[i];int j = i;while (j > 0 && a[j-1] > x) {

a[j] = a[j-1];a[j-1] = x;j--;

}}

}


public static void insertionSort(int[] a) {for (int i=1; i<a.length; i++) {

int x = a[i];int j = i;while (j > 0 && a[j-1] > x) {

a[j] = a[j-1];a[j-1] = x;j--;

}}

}

(n = a.length)

(n)+(n-1)

0

0

(2+...+n)+(3*(1+...+n-1))

1+...+n-1

1+...+n-1

1+...+n-1

Der schlimmste Fall ist, dass die Eingabe umgekehrt sortiert ist, da dann jedes Einfügen alle bisherigen

Ausgabeelemente verschieben muss.


(n)+(n-1)

0

0

(2+...+n)+(3*(1+...+n-1))

1+...+n-1

1+...+n-1

1+...+n-1

n2 : 7/2n2

n : -1/2n

1 : -2

3*n*(n-1)/2 = 3/2n2 - 3/2n

(n+1)*n/2-1 = n2/2 + n/2 - 1

3*n*(n-1)/2 = 3/2n2 - 3/2n

2n - 1

7/2n2-1/2n-2

Nebenrechnung


public static int binary(int[] a, int x) {int first = 0;int last = a.length - 1;while (first <= last) {

int middle = first + ((last - first) / 2);if (a[middle] < x) {

first = middle + 1;} else if (a[middle] > x) {

last = middle - 1;} else

return middle;}return -1;

}

Welche asymptotische Zeitkomplexität hat binäre Suche? Begründen Sie!



Wozu?

Effizienz von IT-Systemen ist mitunter kritisch.

Effizienz ist oft ein Wettbewerbskriterium.

Effizienz ist Geld.

39



public static int fib(int n) {

return n == 0 ? 0 : n == 1 ? 1

: fib(n - 2) + fib(n - 1);

}


Vervollständen Sie den Aufruf fib(3) in einem Baum rekursiver Aufrufe. Wie viele rekursive

Aufrufe gibt es für fib(3)?


Aufgaben zum Modellieren eines Programmes

41


Thema: UML-Klassendiagramme

42

Natürlich!

Lasst uns auch anders modellieren hier.



43

Geben Sie eine Problembeschreibung für die lineare Suche an.



44

Geben Sie eine Problembeschreibung für die binäre Suche an.


Betrachten Sie die folgende Signatur:

public static void insert(int x, int l, int[] a) { ... }

x soll hier in ein bereits sortiertes a der Länge l einsortiert werden. Geben Sie einen Grenz- oder Fehlerfall an für eine von Ihnen angenommene Implementation von insert.

Thema: Sortieralgorithmen


Betrachten Sie die folgende Signatur:

public static void insert(int x, int l, int[] a) { ... }

x soll hier in ein bereits sortiertes a der Länge l einsortiert werden. Geben Sie Vor- und Nachbedingungen für eine von Ihnen angenommene Implementation von insert an.




Wozu?

Informatikfachleute ohne ein bisschen systematische Kenntnis von Sortieralgorithmen sind wie Jazzer die keine Tonleiter spielen können.



48

public class SimpleIntQueue {public void enqueue(int item) { ... }public boolean isEmpty() { ... }public int front() { ... }public void dequeue() { ... }

}

Geben Sie einfachste aber sinnvolle Vor- und Nachbedingungen zu enqueue und dequeue an.



49

public class SimpleIntQueue {public void enqueue(int item) { ... }public boolean isEmpty() { ... }public int front() { ... }public void dequeue() { ... }

}

Nutzen Sie Zusicherungen (assert) auf der Basis von isEmpty und front um mindestens zwei verschiedene

Eigenschaften einer Schlangenimplementation zu überprüfen.


Weitere Fragen zu Konzepten der Programmierung

50


Thema: Modellierung von Struktur

Das unten angebene Klassendiagramm beschreibt die Komposition aus Abbildungen (“figures”) aus Formen (“shapes”). Was betont die Verwendung

der ausgefüllten Raute für die Komposition gegenüber einer unausgefüllten Raute oder einer

beliebigen Asssoziation?


Thema: Strukturierte Programmierung

Geben Sie ein möglichst kurzes, strukturiertes (nicht-rekursives) Java-Programm an, welches

nicht terminiert.



Was ist die Bedeutung der angegebenen Methode zur Bestimmung des sogenannten

Maschinenepsilons?

public static float macheps() {float r = 1.0f;do

r /= 2.0f;while ((1.0f + (r / 2.0f)) != 1.0f);return r;

}



Was ist der zeitliche Aufwand für den Zugriff auf ein Feldelement und wodurch wird dieser geringe

zeitliche Aufwand ermöglicht?



Welches Schema der Rekursion kommt zur Anwendung? Warum terminiert diese Methode?

public static int factorial(int n) {if (n == 0)

return 1;else

return n * factorial(n-1);}


8 2 4 9 7

2 4 7 8 9

2 4 8 9 7

2 4 8 9 7

2 8 4 9 7

8 2 4 9 7

Zeitachse


Welcher Sortieralgorithmus kommt hier zur Anwendung? Begründen Sie Ihre Aussage.


public class Point {

private double x, y;

public double getX() { return x; }

public double getY() { return y; }

public Point(double x, double y) {

this.x = x;

this.y = y;

}

}


Welche Einschränkung modelliert der angegebene Datentyp für Punkte verglichen zu einem

Verbundtyp mit öffentlichen Koordinaten x und y.


int bar(int x, int y){ if ((x>0) && (y>0))

if (y>1) return x;

else return y;

return x+y;}

Thema: Testen von Programmen

Geben Sie eine möglichst geringe Zahl von Aufrufen an, welche Bedingungsüberdeckung

erreicht.


q = 0; r = x; while (r >= y) { r = r - y; q = q + 1; }

{ x == y ∗ q + r }

Thema: Spezifikation von Programmen

{ x >= 0 && y > 0 }

Ist die angegebene Nachbedingung stark genug, um Division mit Rest zu beschreiben? Ist dies ein

Problem für den Beweis?


{ I && B } S { I } ___________________________

{ I } while (B) S { I && !B }


Was bedeutet die angegebene Hoare-Regel?(Fassen Sie sich unbedingt kurz.)


O(f(n)) =

{ g: N → N |

∃n0 > 0. ∃c > 0. ∀ n ≥ n0.

g(n) ≤ c*f(n) }


Welche Menge von Funktionen wird hier definiert?(Fassen Sie sich unbedingt kurz.)


public class Bank {private Account[] accounts = new Account[42];public float totalBalance() {

float result = 0;for (Account a : accounts)

result += a.getBalance();return result;

}...

}


Account sei eine Schnittstelle. An welcher Stelle im Programm tritt späte Bindung auf und was

bedeutet das?



Geben Sie ein möglichst kleines Code-Fragment an, welches einen Verbund oder eine Datenkapsel

zu “Müll” werden läßt.


1 3 7 42 88


Geben Sie zwei verschiedene, binäre Suchbäume zur Repräsentation des angegebenen, sortierten Feldes an? Welcher der beiden Suchbäume ist besser zur binären Suche geeignet und warum?


Thema: Objektorientierung

Was unterscheidet eine statische Methode von einer regulären Methode

(also von einer Instanzmethode)?


Thema: Objektorientierte Verträge

Wie darf sich die Vorbedingung in einer Unterklasse von der Vorbedingung in der Oberklasse unterscheiden und warum ist

eine solche Festlegung sinnvoll?


Thema: Ausnahmebehandlung

Ist jedes Programm weiterhin korrekt, wenn man eine Klasse für ungeprüfte Ausnahmen in eine

Klasse für geprüfte Ausnahmen umwandelt (und sonst nichts ändert)? Begründen Sie Ihre Aussage.


Thema: Generische Typen

Programmieren Sie eine Schleife, welche die Anzahl der Elemente vom Typ Integer in

einer Liste wie der folgenden zählt.

List<Object> l = new LinkedList<Object>();

l.add(1);

l.add("2");

l.add(3);


Wiederholung zu Zeigern, Rekursion, Testen und

Komplexität auf der Basis der einfach verketten Listen

69

Siehe Online-Repositorydata.list.singlylinked.variation


Verbundtyp für Listen

70

public class IntListEntry {public int item;public IntListEntry next;

}Heute definieren wir in der Tat (der absoluten Klarheit halber) jegliche

Funktionalität außerhalb dieser Klasse.


Größe einer Liste:Iterative Fassung

71

public static int size(IntListEntry i) {int j = 0;while (i!=null) {

j++;i=i.next;

}return j;

}

j zählt wie oft wir “.next” navigieren

können.


Größe einer Liste:Rekursive Fassung

72

public static int size(IntListEntry i) {return i==null ?

0: size(i.next) + 1;

}

Was ist zur Rekursionsform dieser Definition zu sagen?

Allgemeine Fragen bei der rekursiven Programmierung:1. Was ist der Basisfall?2. Was ist der Rek.-Parameter?3. Wie kombinieren die Fälle?


Endrekursive Formulierung

73

public static int size(IntListEntry i) {return size(0, i.next);

}

private static int size(int s, IntListEntry i) {return i==null ?

s: size(s+1,i.next);

}Die Größe wird also über

einen Hilfsparameter aggregiert.


Iterative Entsprechung

74

public static int size(int s, IntListEntry i) {while (i!=null) {

s = s + 1;i = i.next;

}return s;

}

Dies ist vorerst ein informales Beispiel. Wir wenden also die Konvertierung “intuitiv” an. Ein voll schematisches Beispiel soll folgen. Übung: Wenden Sie das Konvertierschema später selbst

auf diese Aufgabe an.


Eine sortierte Liste

75

public static IntListEntry sortedList() {IntListEntry e1 = new IntListEntry();IntListEntry e2 = new IntListEntry();IntListEntry e3 = new IntListEntry();e1.item = 42;e1.next = e2;e2.item = 77;e2.next = e3;e3.item = 88;return e1;

}


Eine unsortierte Liste

76

public static IntListEntry unsortedList() {IntListEntry e1 = new IntListEntry();IntListEntry e2 = new IntListEntry();IntListEntry e3 = new IntListEntry();e1.item = 42;e1.next = e2;e2.item = 1;e2.next = e3;e3.item = 88;return e1;

}


Iterativer Sortiertheitstest

77

public static boolean isSorted(IntListEntry i) {if (i==null)

return true;while (i.next!=null) {

if (i.item > i.next.item)return false;

i = i.next;}return true;

}

Wir schauen, ob wir noch 2 Elemente vor uns haben, die wir

vergleichen können.

Wenn wir eine Inversion finden, dann brechen wir den

Sortiertheitstest mit false ab.

Zum nächsten Element.

Falls wir keine Inversion finden, geben wir true zurück.


Rekursiver Sortiertheitstest

78

public static boolean isSorted(IntListEntry i) {

if (i==null || i.next == null)

return true;

if (i.item > i.next.item)

return false;

return isSorted(i.next);

}

Wir schauen, ob wir noch 2 Elemente vor uns haben, die wir

vergleichen können.

Wenn wir eine Inversion finden, dann brechen wir den

Sortiertheitstest mit false ab.

Testen des Rests der Liste


Testfälle

79

@Testpublic void testIsSortedIteratively() {

assertTrue(isSortedIteratively(sortedList()));}

@Testpublic void testIsNotSortedIteratively() {

assertFalse(isSortedIteratively(unsortedList()));}

@Testpublic void testIsSortedRecursively1() {

assertTrue(isSortedRecursively(sortedList()));}

@Testpublic void testIsNotSortedRecursively() {

assertFalse(isSortedRecursively(unsortedList()));}

Siehe Online Repository für mehr Varianten und zugehörige Testfälle.

Sind dies Normalfälle, Grenzfälle oder

Fehlerfälle? Können Sie (weitere) Grenz- bzw. Fehlerfälle angeben?


Endrekursion

Schemavariablen: g, p, r

Schema:

f(x) =

g(x), falls p(x)

f(r(x)), sonst

Bedeutung: iterative Implementation trivial

Endrekursive Formulierung oft relativ einfach

80

http://calvinlawson.files.wordpress.com/2009/02/tail-recursion.jpg

Der rekursive Aufruf ist die letzte Operation.


Anwendung auf isSorted

81

public static boolean isSorted(IntListEntry i) {if (p(i))

return g(i);else

return isSorted(r(i));}

Das ist das programmierte, rekursive Schema. Nun müssen wir

noch die Komponenten p, g, r bestimmen.


Ermittlung von Parametern

82

public static boolean p(IntListEntry i) {return i == null || i.next == null || i.item > i.next.item;

}

public static boolean g(IntListEntry i) {return i == null || i.next == null;

}

public static IntListEntry r(IntListEntry i) {return i.next;

}

Test auf Basisfall

Ergebnis für Basisfall

Anpassung des Parameters für den rekursiven Aufruf


Umwandlung von Endrekursion in eine iterative Formulierung

Rekursiv: f(x) =g(x), falls p(x)f(r(x)), sonst

Iterativ: f(x) =Solange p(x) nicht gilt‣ x = r(x)

Gib g(x) zurück.

83


Anwendung auf isSorted

84

public static boolean isSorted(IntListEntry i) {

while (!p(i))

i = r(i);

return g(i);

}

Das ist das programmierte, iterative Schema. Nun müssen wir

noch die Komponenten p, g, r bestimmen.


Einsetzen der Parameter

85

public static boolean isSorted(IntListEntry i) {while (!( i == null ||

i.next == null || i.item > i.next.item))

i = i.next;return i == null || i.next == null;

}


Größe einer Liste:Iterative Fassung

86

public static int size(IntListEntry i) {int j = 0;while (i!=null) {

j++;i=i.next;

}return j;

}

Wie viele Zeilen (verschieden von “}”) werden in Abhängigkeit von

der Größe der Eingabeliste ausgeführt?

1+(n+1)+2*n+1


Größe einer Liste:Rekursive Fassung

87

public static int size(IntListEntry i) {return i==null ?

0: size(i.next) + 1;

}

Wie viele rekursive Aufrufe gibt es abhängig von der Größe der Eingabeliste?


Iterativer Sortiertheitstest

88

public static boolean isSorted(IntListEntry i) {if (i==null)

return true;while (i.next!=null) {

if (i.item > i.next.item)return false;

i = i.next;}return true;

}

Wie viele Zeilen (verschieden von “}”) werden im schlechtesten Fall ausgeführt? (Warum betrachten wir den schlechtesten Fall? Was

ist der schlechteste Fall?)

Objektorientierte Entwurfsexperimente

http://www.masternewmedia.org/images/passionate-design_id820440_size400.jpg

http://www.dezeen.com/2009/01/13/british-design-classics-stamps-by-royal-mail/


Ein Entwurfsproblem

90

Implementiere Operationen für Firmenobjekte.Die Gesamtsumme an Gehältern für alle Angestellte.Eine Gehaltserhöhung um einen bestimmten Betrag.

MSFT

VB C#

DevHR

AndersErikPaul

Firma

Abteilungen

Unter-abteilungen

Angestellte


Zu wiederholende Konzepte

Virtuelle vs. statische Methoden

Komposition in UML

Typtest und Cast

Listen und Keller

Iteration

Komplexität

91


Ein Objektmodell für das Problem

92


Implementiere Operationen für Firmenobjekte Variante 1: (Virtuelle) Methoden

93

Für alle Varianten des Entwurfproblems sieheRepository, Package oo.company und darunter.


Abstraktion für Variante 1

Objektstrukturen sind aggregierende Strukturen.

Komponente: Jede Art von Objekt.

Blatt: Es gibt primitive Komponenten.

Kompositum: Es gibt aggregierende Komponenten.

Operationen sind gleichermassen auf allen Typen definiert.

Blatt: Operation unmittelbar (lokal) definiert.

Kompositum: Iteration über aggregierte Objekte.

94


Implementiere Operationen für Firmenobjekte Variante 1’

95


Entwurfsmuster Kompositum

Intention: einheitliche Behandlung von primitiven Komponenten und aggregierenden Komponenten bei der Anwendung von Operationen.

Szenario: geometrische Objekte in einer CAD-Anwendung. Es gibt primitive Objekte (Linien, ...). Es gibt auch zusammengesetzte Objekte (Rechtecke, Gruppen, ...). Alle sollen “gemalt” werden können.

96


Entwurfsmuster

97

Ein Entwurfsmuster gibt eine bewährte generische Lösung für ein immer wiederkehrendes Entwurfsproblem, das in bestimmten Situationen auftritt.

Design Patterns. Elements of Reusable Object-Oriented Software Addison-Wesley Professional Computing Series, 1995.


Entwurfsmuster

Iterator (siehe Vorlesung zu generische Typen)

State (siehe Vorlesung mit UML-Zustandsdiagrammen)

Model-View Controller (siehe Vorlesung zu Ereignissen)

Abstrakte Fabrik (siehe create* in oo.shapes.awtish)

Interpreter (denkbar für Interpreter von Softwaresprachen)

...

98


Entwurfsbewertung

Typ-sichere Implementation der OperationenAlle Firmenobjekte implementieren die Operationen.

Modulare Implementation der OperationenDas Verhalten wird für jeden Typ separat festgelegt.

Antizipierte Implementation der OperationenDie betroffenen Klassen beherbergen die Operationen.

Jede neue Operation verlangt eine Änderung der Klassen.

99

Gibt es einen Entwurf in dem die Klassen die Operationen nicht antizipieren müssen?


Implementiere Operationen für Firmenobjekte Variante 2: Typ-Test und -Cast

100

Operation sind außerhalb der Company-Klassen zu implementieren.


Implementation von getTotal außerhalb der Company-Klassen

Spezialisierung in Company-Klassen impliziert Typ-Test/-Cast

101

/** * Compute the total of all salaries for the employees of a department */private static double getTotal(Department d) {

double total = 0;total += d.getManager().getSalary();for (Unit u : d.getUnits()) {

if (u instanceof Employee) {Employee eu = (Employee)u;total += eu.getSalary();continue;

}if (u instanceof Department) {

Department du = (Department)u;total += getTotal(du);continue;

}throw new UnsupportedOperationException();

}return total;

}

Typ-Test

Typ-Test

Typ-Cast

Typ-Cast

Fallunter-scheidung über Typ.


Entwurfsbewertung

Nicht antizipierte Implementation der OperationDie Operation wird außerhalb der Klassen implementiert.

Neue Operationen lassen die Klassen unberührt. Typ-unsichere Implementation der Operation

Typ-basierte Fallunterscheidung könnte scheitern.Nicht-modulare Implementation der Operation

Die Fallunterscheidung ist monolithisch.

102

Gibt es einen Entwurf mit nicht-antizipierten und typ-sicheren und modularen Operationen?


Implementiere Operationen für Firmenobjekte Variante 3: Sammeln von Objekten von Interesse

103


Benutzung der gesammelten Objekte von Interesse

104

/** * Compute the total of all salaries for the employees of the company */private static double getTotal(Company c) {

double total = 0;for (Employee e : c.getEmployees())

total += e.getSalary();return total;

}

/** * Increase the salaries for all employees of the company by a fixed amount */private static void increase(Company c, double x) {

for (Employee e : c.getEmployees())e.setSalary(e.getSalary() + x);

}


Sammeln von Objekten von Interesse

105

public class Company {

...

/** Return all aggregated employees as a list */public Collection<Employee> getEmployees() {

LinkedList<Employee> list = new LinkedList<Employee>();list.add(getCeo());list.add(getCsa());for (Department d : getDepartments())

d.getEmployees(list);return list;

}}


EntwurfsbewertungNicht-antizipierte Operationen sind möglich.

... wenn sie auf der Liste der Angestellten definierbar sind. Die Operationen sind typ-sicher.Die Listen-Erstellung ist modular.

Modularität von Operation erscheint irrelevant.Der Container verursacht Kosten.

Linear mit der Anzahl der Angestellten.Kosten entstehen komplett vor der Nutzung des Containers.

Die Collection/List-Schnittstelle ist zu umfangreich.

106

Können wir die benannten Probleme mitigieren?


Implementiere Operationen für Firmenobjekte Variante 3’: Iterieren über Objekte von Interesse

107


Zustand des Iterators

108

MSFT

VB C#

DevHR

AndersErikPaul

next

CSA



109

MSFT

VB C#

DevHR

AndersErikPaul

next

CSA

CEO



110

MSFT

VB C#

DevHR

AndersErikPaul

next

CSA

CEO

Manager HR



111

MSFT

VB C#

DevHR

AndersErikPaul

next

CSA

CEO

Manager HR

Manager Dev



112

MSFT

VB C#

DevHR

AndersErikPaul

nextCSACEO

Manager HRManager DevManager VB



113

MSFT

VB C#

DevHR

AndersErikPaul

nextCSACEO


Paul



114

MSFT

VB C#

DevHR

AndersErikPaul

nextCSACEO


PaulErik



115

MSFT

VB C#

DevHR

AndersErikPaul

nextCSACEO


PaulErik

Manager C#



116

MSFT

VB C#

DevHR

AndersErikPaul

nextCSACEO


PaulErik

Manager C#Anders



117

MSFT

VB C#

DevHR

AndersErikPaul

nextCSACEO


PaulErik

Manager C#Anders

null


Implementation des Iterators

118

class Employees implements Iterator<Employee> {

private Stack<Object> stack = new Stack<Object>();

/** Construct an iterator from a company */Employees(Company c) {...}

/** Pull from the iterated structure to find the next employee */private void pull() { ... }

/** Test whether there is another employee */public boolean hasNext() {

pull();return !stack.isEmpty();

}

/** Return the next employee */public Employee next() {

pull();if (stack.isEmpty())

throw new NoSuchElementException();return (Employee)stack.pop();

}

/** Removal is unsupported for this iterator */public void remove() { throw new UnsupportedOperationException(); }

}

/* * A stack of objects that are still to be visited. * Objects of the following types can be on the stack: * (i) Employee; * (ii) IteratorDepartment (due to Company); * (iii) IteratorUnit (due to Department). */

Vorsicht! Schwierig!

Gegebenenfalls ignorieren!


Anfordern vom Iterator-Keller

119

/** Pull from the iterated structure to find the next employee */private void pull() {

while (true) {if (stack.isEmpty())

return;if (stack.peek() instanceof Employee)

return;if (stack.peek() instanceof Iterator) {

Iterator i = (Iterator)stack.peek();if (i.hasNext()) {

Unit u = (Unit)i.next();pushUnit(u);

}else

stack.pop();}

}}




Erweitern des Iterator-Kellers

120

/** Construct an iterator from a company */Employees(Company c) {

stack.push(c.getDepartments().iterator());stack.push(c.getCsa());stack.push(c.getCeo());

}

/** Push a unit on the iterator stack */private void pushUnit(Unit u) {

if (u instanceof Department) {Department d = (Department)u;stack.push(d.getUnits().iterator());stack.push(d.getManager());return;

}if (u instanceof Employee) {

Employee e = (Employee)u;stack.push(e);return;

}}




Entwurfsbewertung

Iteratoren sind immer noch antizipierend.Was wäre wenn wir eine Operation über Managern brauchen?

Iteratoren sind auf sequentielle Verarbeitung getrimmt.Was wäre wenn wir eine beliebige Operation brauchen?

z.B. ein Operation die abhängig von Werten verzweigt?

121

Wir stoppen hier in OOPM.

Documents

OOPM, Ralf Lämmel - userpages.uni-koblenz.desoftlang/oopmcourse/slides/qa.pdf · (C) Ralf Lämmel, OOPM, Universität Koblenz-Landau Themen für die Klausur V/Ü 2 1.Sortieren 2.Algebraische