• https://fsi.informatik.uni-erlangen.de/forum/thread/8871-Klausur-06-08-2009-Aufgabe-7

a) [Nicht mehr Stoff aktueller Semester]

b) (unsicher)

• O(log n)
• O(n²)
• O(2^n)

c) Falsch, der Balancefaktor entspricht der Differenz der beiden Höhen

d) Falsch, implizit (also automatisch) geht es nur in die andere Richtung (Ober o = new Unter();). Explizit mit Cast geht zur Compilezeit (Unter u = (Unter) new Ober();) auch, wirft aber eine ClassCastException zur Laufzeit.

e) Richtig

f) Richtig, beispielsweise oft beim Comparable Interface benutzt: LinkedList<Comparable>

g) Falsch, HeapSort ist in-place

h) O(n²)

i) richtig, O(|v| + |E|)

a)

Anmerkung:
Bei dem gegebenen UML-Klassendiagramm wird keine grafische Unterscheidung zwischen „implements“ und „extends“ getroffen.
In Java gilt jedoch:

Interface extends Interface		// OK
Interface implements Interface	// Falsch
Interface extends Class		// Falsch
Interface implements Class		// Falsch
 
Class extends Interface		// Falsch
Class implements Interface		// OK
Class extends Class			// OK
Class implements Class		// Falsch
 
// Wobei jede Class auch abstract sein kann

Daher sind die Pfeile immer eindeutig.

abstract class EierLegend implements Haustier {
	protected int eierSammeln() { // ... }
}
 
class Schaf extends WolleGebend implements Schlachtvieh, MilchErzeugend {
	public static final int SCHWARZ = 1;
	private static int anzahl = 0;
 
	public float melken() { // ... }
	public final void schlachten() { // ... }
	protected static int zaehlen() { // ... }
} 

b)

In Java ist (im Gegensatz zu manchen anderen Programmiersprachen) keine Mehrfachvererbung möglich. Die Klasse EierlegendeWollMilchSau erbt jedoch von den Klassen EierLegend, WolleGebend und Sau.

c)

Die Klassen EierLegend und WolleGebend sollten als Interface implementiert werden, ebenso, wie MilchErzeugend und SchlachVieh bereits Interfaces sind.
„Eigenschaften“ bzw. „Schnittstellen“ sollte ohnehin eher als Interface, als abstrakte Klasse implementiert werden.

Liste aller Änderungen:

• interface EierLegend
• interface WolleGebend
• Huhn implements EierLegend
• Schaf implements WolleGebend
• EierLegend extends Haustier
• WolleGebend extends Haustier
• EierlegendeWollMilchSau implements EierLegend
• EierlegendeWollMilchSau implements WolleGebend

d)

UML-Sequenzdiagramm

a)

Kaskadenartige, verschränkte Rekursion

b)

public static int foo(int n) {
	int ret;
 
	if (n == 0) {
		ret = 3;
	} else if (n == 1) {
		ret = 1;
	} else {
		ret = foo(n - 1) + bar (n - 2);
	}
 
	return ret;
}

c)

bar(3) 
    ---> foo(3)
              --->foo(2)
                       --->foo(1)
                       --->bar(0) 
              --->bar(1)
    ---> bar(2)
              --->foo(2)
                       --->foo(1)
                       --->bar(0) 
              --->bar(1)

d)

Es werden immer wieder die selben Wert neu berechnet z. b. foo(2). Optimierung durch dynamische Programmierung

e)

public static int foo(int n) {
	int ret;
 
	if(fooTable[n] == UNKNOWN) {
 
	// <Teilabschnitt von a)>
		if (n == 0) {
			ret = 3;
		} else if (n == 1) {
			ret = 1;
		} else {
			ret = foo(n - 1) + bar (n - 2);
		}
	// </Teilabschnitt von a)>
 
		fooTable[n] = ret;
	}
 
	ret = fooTable[n];
	return ret;
}

e)

• Laufzeit: O(n), da man, um von bar(n) auf bar(n + 1) zu kommen, lediglich die Aufrufe foo(n) und bar(n) zu berechnen sind und alle anderen Ergebnisse bereits in der Tabelle stehen
• Speicherbedarf: O(n), da man zwei Arrays der Größe (n + 1) beneq05oqabötigt (je eins für DP von foo und von bar)

a)

Die Zahlen werden von hinten (rechts) nach vorne (links) sortiert, damit bspw. die Zahl „78“ vor der Zahl „88“ steht. Wichtig ist hierbei, dass das Verfahren unbedingt stabil sortieren muss.

b)

c)

Anmerkung:
Mit Angabe von „from“ und „to“ wird eine Teilsortierung moeglich.

Beispiel-Code zur Aufgabe: https://fsi.cs.fau.de/forum/post/160481;nocount

public static void sortPos(int array[], int from, int to, int pos) {
	LinkedList<Integer>[] buckets = new LinkedList[10]; //Für jede Ziifer 0-9 einen Bucket erstellen
 
	for (int i = 0; i < buckets.length; i++) { //In jedem Bucket eine LinkedList erstellen
		buckets[i] = new LinkedList();
	}
 
	for (int i = from; i < to; i++) { //Buckets mit PLZs befüllen und sortieren
		int b = getDigit(array[i], pos);
		buckets[b].addLast(array[i]);
	}
 
	LinkedList<Integer> master = new LinkedList<>(); //Master Liste erstellen in die Werte sortiert kopiert werden können
 
	for (int i = 0; i < buckets.length; i++) { //In Master Liste einen Bucket nach dem anderen kopieren
		master.addAll(buckets[i]);
	}
 
	for(int i = from; i < to; i++) { //In ursprünglichen Array die Elemente aus Master Liste kopieren.
		array[i] = master.removeFirst();
	}
}
 
public static void radixSort(int[] array) {
	for (int i = 5; i >=1; i--) {
		sortPos(array, 0, array.length, i);
	}
}

a)

b)

c)

• Eulerpfad: Nein, da man mindestens eine Kante mehrmals benutzen müsste. Es weisen mehr als 2 Knoten einen ungeraden Grad auf.
• Eulerzyklus: Nein, es haben nicht alle Knoten einen geraden Grad.

d)

Anmerkung:
Je nach Implementierung sind hier viele Möglichkeiten denkbar.

Dijkstra: O(v log(v) + e) bei einer Implementierung mit Fibonacci-Heap

Kruskal: O(e * log(e)) bei Implementierung mit Pfadkompression

a)

b)

Die Hashfunktion mappt jeden Schlüssel garantiert auf einen Bucket mit ungerader Nummer.
Begründung:
Die Multiplikation mit 2 macht aus jedem Schlüssel garantiert eine gerade Zahl, die anschließende Addition mit 3 garantiert eine ungerade Zahl.
Eine ungerade Zahl modulo eine gerade Zahl ergibt wiederum eine ungerade Zahl.

c)

Primärkollision, wenn Bucket, wo es eigentlich eingefügt werden sollte, ein D hat. Sekundärkollision, wenn Bucket, wo es eigentlich eingefügt werden sollte, ein P oder S hat.

a)

wp("a += ++b - 2;", a + b > 0) =
wp("b = b + 1; a = a + b - 2;", a + b > 0) =
wp("b = b + 1;", (a + b - 2) + b > 0) =
((a + (b + 1) - 2) + (b + 1) > 0) =
(a + b - 1 + b + 1 > 0) =
(a + 2 * b > 0)

b)

wp("if (a > -2*b && b > 0) {a += ++b - 2;} else {b -= --a;}", a + b > 0) =
[(a > -2*b ∧ b > 0) ∧ wp("a += ++b - 2;", a + b > 0)] ∨ [(¬(a > -2*b ∧ b > 0) ∧ wp("b -= --a;", a + b > 0)] =

bereits in der a) berechnet:
wp("a += ++b - 2;", a + b > 0) = (a + 2 * b > 0)

durch die Aufgabenstellung gegeben:
wp("b -= --a;", a + b > 0) = (b > 0)

damit ergibt sich:
= [(a > -2*b ∧ b > 0) ∧ (a + 2*b > 0)] ∨ [(¬(a > -2*b ∧ b > 0) ∧ (b > 0)] =
[(a > -2*b) ∧ (b > 0) ∧ (a + 2*b > 0)] ∨ [((a ≤ -2*b) ∨ (b ≤ 0)) ∧ (b > 0)] =
[(a > -2*b) ∧ (b > 0) ∧ (a + 2*b > 0)] ∨ [(a ≤ -2*b) ∧ (b > 0)] =
[(a > -2*b) ∧ (b > 0) ∧ (a > -2*b)] ∨ [(a ≤ -2*b) ∧ (b > 0)] =
[(a > -2*b) ∧ (b > 0)] ∨ [(a ≤ -2*b) ∧ (b > 0)] =
(b > 0)

c)

i)

Antwort 1: Falsch
	c = 1, d = 1, e = 1, a ≥ b ≥ 0
	(a b) = c / d

	c / d = 1 / 1 = 1
	Kann offensichtlich nicht für jedes a und b gelten

Antwort 2: Falsch
	c = 1, d = 1, e = 1, a ≥ b ≥ 0
	c = (a + 1 - b)! - e! ∨ d = (e + 1)!

	(d = (e + 1)!) = (1 = (1 + 1)! = 2) kann nicht stimmen
	(c = (a + 1 - b)! - e!) = (1 = (a + 1 - b)! - 1!) = (0 = (a + 1 - b)!) kann offensichtlich nicht für jedes a und b gelten

Antwort 3: Richtig
	c = 1, d = 1, e = 1, a ≥ b ≥ 0
	c = a! / (a - e + 1)! ∧ d = (e - 1)!

	(d = (e - 1)!) = (1 = (1 - 1)!) = (1 = 0!) = (1 = 1) = (true)
	(c = a! / (a - e + 1)!) = (1 = a! / (a - 1 + 1)!) = (1 = a! / a!) = (1 = 1 / 1) = (true)
	gültig!

Antwort 4: Falsch
	c = 1, d = 1, e = 1, a ≥ b ≥ 0
	1 ≤ c ≤ a! - b!
	
	(1 ≤ c ≤ a! - b!) = (1 ≤ 1 ≤ a! - b!)
	Kann offensichtlich nicht für jedes a und b gelten

ii)

Invariante nachweisen:

Zu zeigen: {I ∧ b} => wp(A, I)

wp(A, I) =
wp("c = c * (a + 1 - e); d = d * e; e = e + 1;", c = a! / (a - e + 1)! ∧ d = (e - 1)!) =
wp("c = c * (a + 1 - e); d = d * e;", c = a! / (a - (e + 1) + 1)! ∧ d = ((e + 1) - 1)!) =
wp("c = c * (a + 1 - e);", c = a! / (a - (e + 1) + 1)! ∧ d * e = ((e + 1) - 1)!) =
(c * (a + 1 - e) = a! / (a - (e + 1) + 1)! ∧ d * e = ((e + 1) - 1)!) =
(c * (a + 1 - e) = a! / (a - e)! ∧ d * e = e!)

{I ∧ b} => wp(A, I) =
{(c = a! / (a - e + 1)! ∧ d = (e - 1)!) ∧ (e ≤ b)} => wp(A, I) =
¬{(c = a! / (a - e + 1)!) ∧ (d = (e - 1)!) ∧ (e ≤ b)} ∨ wp(A, I) =
(c ≠ a! / (a - e + 1)!) ∨ (d ≠ (e - 1)!) ∨ (e > b) ∨ wp(A, I) =
(c ≠ a! / (a - e + 1)!) ∨ (d ≠ (e - 1)!) ∨ (e > b) ∨ (c * (a + 1 - e) = a! / (a - e)! ∧ d * e = e!) =

Überlegung:
Gelten (c ≠ a! / (a - e + 1)!) und (d ≠ (e - 1)!) beide nicht, dann gilt offensichtlich:
(c = a! / (a - e + 1)!) ∨ (d = (e - 1)!)

Für diesen Fall müssen wir zeigen, dass dann (c * (a + 1 - e) = a! / (a - e)! ∧ d * e = e!) gilt

(d * e = e!) = (d = e! / e) = (d = (e - 1)!)
-> gilt

(c = a! / (a - e + 1)!) gilt, das heißt wir können das in (c * (a + 1 - e) = a! / (a - e)!) einsetzen:

((a! / (a - e + 1)!) * (a + 1 - e) = a! / (a - e)!) =
(a! / (a - e + 1 - 1)! = a! / (a - e)!) =
(a! / (a - e)! = a! / (a - e)!) =
(true)
-> gilt ebenfalls

Damit ist die Invariante gültig.