Algorithmen und Programmierung III
WS 2002/2003 Übung
1
H. Schweppe
Ausgabe:
17.10.2002
Abgabe:
29.10.2002
Aufgabe 1.1 (4 P)
Das folgende Programm soll feststellen, ob ein Dreieck mit Seitenlängen a, b
und c gleichseitig (1), gleichschenklig(2) oder beliebig (3) ist. Der berechnete
Wert ist 1,2 oder 3.
//
pre: a,b,c > 0
int triangle (int a, int b, int c) {
if (a==b) {
if(b==c) {
//
return 1;
}
else
{ Aufgabe: a) Geben Sie die
Invarianten (jeweils hinter //) an.
//gleichschenklig Ist das Programm korrekt?
return 2;
Begründen Sie, warum das
Programm korrekt /fehlerhaft ist.
}
}
else {
if {b==c) {
//
return 2;
}
else {
// return 3;
}
} //post: ...
Aufgabe 1.2 ( 6 P)
(a) Zeige: Wenn f(n) = O(g(n)) und d(n) = O(h(n)), dann ist f(n)+d(n) = O(g(n) + h(n)). (2P)
(b) Zeige: 3(n + 1) 7 + 2n log n = O(n 7 ). (3P)
(c) Die Algorithmen A und B lösen dasselbe Problem. A benötigt 10n log n Operationen, B braucht n 2 Operationen. Zu bestimmen ist das kleinste n0 so dass A weniger Operationen als B benötigt für n >= n0 (2P)
Aufgabe 1.3 ( 8 P)
In Alp2 (Skript 2.11.4) wurde die Datenstruktur Stapel mit den Operationen
push(Object element) und
Object pop()
implementiert. Die Implementierung ist nicht typsicher. Implementieren Sie das Interface
public interface IntStack {
// throws
Exception
public
void pushInt(int element);
//post:
element is top of stack
public
int popInt()
throws Exception;
//pre: stack is
not empty, otherwise exception thrown
//result: top element of stack
//post: stack without top element
}
als Klasse IntStackAdapter
unter Verwendung des Adapter-Musters auf Basis der Klasse Stack.
Den Code für die Klasse
Stack finden Sie hier. Testen Sie die Klasse
mit Hilfe einer eigenen Klasse, z.B. als JUnit-Test-Klasse.
Aufgabe 1.4 ( 8 P) (Wiederholung: verkettete Listen)
Eine einfach verkettete Liste soll in situ umgedreht werden, d.h. die entsprechende Methode wirkt wie die bekannte Haskell-Funktion reverse ::[a] ->[a], jedoch ohne dabei alle Elemente zu kopieren.
Die Implementierung verwendet ein
'Wächterelement' (sentinel), das keine Nutzdaten enthält.
Implementieren Sie neben der Methode
public void reverse() auch die Methode printList(),
die die Elemente der Liste 'links nach rechts' ausgibt. Das Quellcodefragment
finden Sie hier.
Selbstverständlich gehört eine Testsuite zur Lösung. Sie können die reverse()
rekursiv oder iterativ implementieren. Im
zweiten Fall nicht die Schleifeninvariante vergessen!
Aufgabe 1.5 ( 4 P) (Wiederholung:Objektorientierung)
a) Wir betrachten eine Klassenhierachie für
geometrische Objekte. class Rechteck kann man als Unterklasse von
class
Quadrat modellieren - oder umgekehrt. Geben
Sie die entsprechenden Klassenfragmente an. Gibt es Gründe, die für eine der Alternativen sprechen?
(Kurze Begründung).
b) Angenommen
class B extends A {…}
und
class C extends A {…}.
Welche der Anweisungen ist / sind
falsch (knappe Begründung)?
1)
B b = new A();
2)
A a = new B();
3) C a = (C) new B();
4)
keine
c) Gegeben sei eine Klasse
class Animal und
eine Subklasse class
Cat extends Animal. In beiden wird die
Methode noise() vereinbart. Welche Methode wird in folgendem Codestück ausgeführt:
Animal s = new Cat();
System.out.println(s.noise());
d) Die Klasse
Y erweitert die Klasse X:
class Y extends X {...}. Welche der folgenden
cast-Operationen ist falsch /überflüssig /richtig?
X x = (X) new Y();
Y y = (Y) x;
Y a = (Y) ((X) (new Y()));
Aufgabe 1.6 (Verständnisfragen 2 P)
a)
Gibt es einen Unterschied zwischen Mustern (patterns) und Makros?
b) Warum kann man einen Algorithmus
normalerweise nicht wirklich durch eine Laufzeit-Messreihe (Benchmark)
charakterisieren?
c) Gibt es Situationen (welche?), in denen ein Benchmark Algorithmen besser
charakterisiert, als eine Laufzeitanalyse?
d) richtig oder falsch: Die Verwendung eines Interface in Java, wie etwa in
1.4., ist mit Laufzeiteinbußen für das Programm verbunden (kurze
Begründung)
}