WS 2002/2003                   Übung  5                          H. Schweppe
        

        Ausgabe: 14.11.2002
        Abgabe:   26.11.2002 

Aufgabe 5.1 ( 17   P)  
 In Aufgabe 3.3 wurde ein abstrakter Datentyp "Polynom " als Java-Interface definiert. Ziel dieser Aufgabe ist die Implementierung von Klassen, die dieses Interface implementieren. 
a) (6) Als Repräsentation eines Polynoms vom Grad n soll ein Feld  float[] coeff  mit n+1 Elementen gewählt werden, das die Koeffizienten aufnimmt. Die Variable int degree  gibt den Grad an. Beispiel:  3.5 * x³ + 2*x +5.1  hat die Darstellung   coeff == {3.5, 0, 2.0, 5.1} , degree == 3.
Es werden also keine führenden Nullen dargestellt. Damit ist degree eigentlich redundant (wieso?). Implementieren Sie das Interface für diese Repräsentation. 
b) (3) Geben Sie die Abstraktionsfunktion und die Repräsentationsinvariante an. 
c) (1) Begründen Sie informell, warum Ihre Implementierung der Methoden die Repräsentationsinvariante einhält.
d) (3) Schlagen Sie eine speichereffektivere Repräsentation für Polynome vor, bei denen viele Koeffizienten 0 sind ("dünn besetzte Polynome"). Beispiel:  2.0 *x²³ + 2.5*x 
e) (4) Auch hierfür sind Abstraktionsfunktion und Repräsentationsinvariante gesucht. 
Hinweis: Für die Multiplikation und Addition von Polynomen  sollen Operanden mit unterschiedlicher Repräsentation (a bzw. d) zugelassen sein. Das Ergebnis wird gemäß a) repräsentiert.  Der Quellcode für ein Interface Polynom steht im Netz. 

Aufgabe  5.2 ( 4   P)  
Die Vektordarstellung von IntSet (siehe VL  class IntSet1) soll so verändert werden, dass keine  Werte mehrfach vorkommen. 
a) (3) Wie ändern sich Repräsentationsinvariante bzw. Abstraktionsfunktion?
b) (3) Reimplementieren Sie die Repräsentation (ursprüngliche Implementierung  hier im Web).

Aufgabe 5.3 ( 3  P)  

Gegeben sei eine Klasse Counter mit folgenden Methoden: 

public class Counter {
// model:  int count >= 0    
// inv: getCount() >= 0
 private int count;
     // happens to to be identical to model
   public Counter(){ ... }      //effects: makes count = 0
   public int getCount(){ ... } //effects: return the value of count
   public void inc(){ ... }     //effects: count = COUNT +1 
}  
Betrachte jetzt 2 mögliche Unterklassen Counter2 und Counter3 mit den folgenden zusätzlichen Operationen:

public class Counter2 {
// inv: count >= 0
  public Counter2(){ ... } //effects: makes count = 0
  public void inc(){ ... } //effects: count = 2*COUNT
}
und
public class Counter3 {
    // inv: count >= 0
   public Counter3(int k ){ ... } //effects: makes count contain k
   public void inc(int k){ ... }  //effects: if count >= k     
                                  //            count = COUNT - k 
}

Entscheiden und begründen Sie, ob Counter2 bzw. Counter3 legitime Unterklassen von Counter im Sinne der Vererbung von Spezifikationen sind.

Aufgabe 5.4 ( 4 P)  
Wir gehen von einer Implementierung von Vektoren mit Hilfe von Feldern aus.  In den Vektor wird immer am Ende eingefügt. Ist kein Platz mehr vorhanden, wird das Feld der Größe m durch Kopieren in eines der Größe   f(m) überführt (in der VL war  f(m) =m+ const   bzw. im Fall der Verdopplung f(m) =2* m ). 
Zeigen Sie, dass die Laufzeit T(n) zum Einfügen von n  Werten  bei Vergrößerung des Vektors um jeweils éÖ m ù   O(n ^3/2 ) ist.
éÖ m ù   bezeichnet die nächstgrößere ganze Zahl von Wurzel aus m .

Aufgabe 5.5 ( 8 P)  
a) (1) Geben  Sie eine Implementierung  der Operation  next für Schlangen von Booleschen Werten auf der Basis der in der VL definierten Repräsentation an. (next liefert das nächste Schlangenelement, verändert die Schlange aber nicht , siehe Spezifikation). 
b)(2) John Dump beschließt, das interface Stack  um eine Operation  zu erweitern. Warum ist das eine sehr schlechte Idee? (Hinweis: Noch schlimmer ist es, eine Operation zu entfernen. Also:   Quidquid agis, prudenter agas et respice finem - was du auch tust,  tu's klug und bedenke das Ende) 
c) (1) J.D. vertritt die Auffassung, dass das Maximale, was man mit Datenabstraktion erreichen kann, der Schutz der Implementierung eines Typs vor Änderungen durch ein Klientenprogramm ist. Kommentieren Sie die Auffassung. 
d) (0,5) In Ausnahmefällen kann ein Java-Interface die Implementierung einer Methode enthalten. Ja / Nein? 
e) (1,5)  Ein Interface in Java stellt niemals einen Konstruktor zur Verfügung. Ja/ Nein mit Begründung.
f)  (2) Implementieren Sie die Haskell-Funktion size :: S t -> Int für die in der Vorlesung angegebene Repräsentation (mehrfach vorkommende Werte in der Repräsentation erlaubt).

36 Punkte.