• https://fsi.informatik.uni-erlangen.de/forum/thread/7553-Frage-zur-Klausur-vom-19-02-2009-Aufgabe-8b
• https://fsi.informatik.uni-erlangen.de/forum/thread/7085-19-02-2009-Aufgabe-1
• https://fsi.informatik.uni-erlangen.de/forum/thread/8839-Klausur-19-02-2009 (Aufgabe 3)
• https://fsi.informatik.uni-erlangen.de/forum/thread/8840-Klausur-vom-19-02-2009-Aufgabe-4
• https://fsi.informatik.uni-erlangen.de/forum/thread/8848-19-02-09-Altklausur wp
• https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung

a) Falsch, es muss sortiert sein

b) Nummer 3: eine Schleife korrekt ist

c) Richtig

d) Richtig

e) Bucketsort, Mergesort

f) 1 - exakt n-1 Kanten

g) 4 - O(n²
* log n)

h) 2 - O(n
*(log n)²)

i) 1 - kontextsensitiven Grammatiken

a)

b) Pfade von Knoten A nach …

a)

Java-Datei zum selbst testen:
:pruefungen:bachelor:aud:test.java.txt

b)

Java-Datei zum selbst testen:
:pruefungen:bachelor:aud:test-07-08_2.java.txt

a)

contains(x, create) = false
contains(x, append(x, L)) = true
contains(x, append(y, L)) = contains(x, L)

b) A → D

c)

append(head(append(D, create), append(A, create)) = 
A1
= append(head(prepend(D, create), append(A, create)) = 
A1
= append(head(prepend(D, create), prepend(A, create)) = 
A3
= append(D, prepend(A, create)) = 
A2
= prepend(A, append(D, create)) = 
A1
= prepend(A, prepend(D, create))

a)

public static int f(int n) {
	if (n < 3)
		return n + 1;
 
	return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
}

b)

Vorüberlegungen:

public static int f(int n) {
	return lin(1, 2, 3, n);
}

Die Basisfälle der Funktion sind für n < 3 gegeben:
f(0) = 1
f(1) = 2
f(2) = 3

Aus dem gegebenen Aufruf und dieser Basisfälle lässt sich schließen:
a = 1 = f(0) → f(n - 3)
b = 2 = f(1) → f(n - 2)
c = 3 = f(2) → f(n - 1)

Somit wissen wir:
lin(a, b, c, steps) → lin(f(n - 3), f(n - 2), f(n - 1), steps)

Wir starten also am Basisfall n < 3 (⇒ Bottom-Up), weshalb nur noch der „sonst“-Teil beachtet werden muss.

Nächster „step“: n + 1

lin(f(n - 2), f(n - 1), f(n), steps - 1) (*)

f(n - 2) und f(n - 1) sind bereits berechnet und müssen nur nach links geschoben werden.
f(n) berechnet sich wie in Aufgabe a), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c:

f(n) = 1 + (((c - b) * a) % 100) (* *)

(* *) in (*) eingesetzt ergibt:

lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)

public static int f(int n) {
	return lin(1, 2, 3, n);
}
 
private static int lin(int a, int b, int c, int steps) {
	if (steps == 0)
		return a;
 
	return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
}

Warum steht das Ergebnis gerade in a?

Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift:
f(0) = 1
f(0) = lin(1, 2, 3, 0)
Das Ergebnis steht in Variable a.

c)

public static int f(int n) {
	int a = 1;
	int b = 2;
	int c = 3;
 
	while(n > 0) {
		int fn = 1 + (((c - b) * a) % 100);
		a = b;
		b = c;
		c = fn;
		n--;
	}
 
	return a;
}

a)

     27
    /  \
  23	42
 /     /  \
7     32  64
             \
             81

b)
Für die maximale Höhe müssen die Werte in auf- oder absteigend sortiert in den Baum eingefügt werden.
Schlüsselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81
Kosten: O(n)

Für einen perfekt balancierten Baum fügt man immer das mittlere Element der sortierten Reihe ein, teil die Reihe in zwei Restreihen auf und fährt mit diesen genauso fort.
Schlüsselfolge für minimale Höhe: 32, 23, 7, 27, 64, 42, 81
Kosten: O(log n)

c)

Verwendete Definitionen:

• Höhe eines Blatts: 0
• Daraus folgt die Höhe des leeren Baums: -1
• Balancefaktor: (Höhe des linken Teilbaums) - (Höhe des rechten Teilbaums)

d)

• Rotation an Knoten: 64

• Einfachrotation gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind

e)

a) Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein.

b)

        13
      /     \
    6        9
  /   \     /
 2     5  8

c)

public int leftChildIndex (int parentIndex) {
	return parentIndex * 2 + 1;
}

d)

public int parentIndex (int childIndex) {
	return (childIndex % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2;
}

e)

//keine garantie!
public void add (int priority) {
	array[n] = priority;
	int p = parentIndex(n);
 
	while(p >= 0 && array[p] < array[n]) {
		// swap ohne temporäre Variable, da immer nur priority nach oben geswappt wird
		array[n] = array[p];
		array[p] = priority;
 
		n = p;
		p = parentIndex(n);
	}
 
	n++;
}

f) O(log n)

a)

wp("if (a > b - 5) {a = b++ - 4;}", a = b - 5) =
[(a > b - 5) ∧ wp("a = b++ - 4;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] =
[(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] =
[(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ (a = b - 5) =
[(a > b - 5) ∧ wp("a = b - 4;", a = b + 1 - 5)] ∨ (a = b - 5) =
[(a > b - 5) ∧ (b - 4 = b + 1 - 5)] ∨ (a = b - 5) =
[(a > b - 5) ∧ (b - 4 = b - 4)] ∨ (a = b - 5) =
[(a > b - 5) ∧ true] ∨ (a = b - 5) =
(a > b - 5) ∨ (a = b - 5) =
(a ≥ b - 5)

b)

i)

Nummer 3: (x mod 2) = (i mod 2) ∧ y ≥ 0

ii)

Zu zeigen: P => wp(A,I)

Nachweis:
wp(A,I) =
wp("x = i; y = 0; r = false;", (x mod 2) = (i mod 2) ∧ y ≥ 0) =
wp("x = i; y = 0;", (x mod 2) = (i mod 2) ∧ y ≥ 0) =
wp("x = i;", (x mod 2) = (i mod 2) ∧ 0 ≥ 0) =
(i mod 2) = (i mod 2) ∧ 0 ≥ 0 =
true ∧ true =
true

P => wp(A,I) =
((i ≥ 0) => true) =
(¬(i ≥ 0) ∨ true) =
true

iii)

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

Nachweis:
wp(A,I) =
wp("x = x - 2; y = y + 1;", (x mod 2) = (i mod 2) ∧ y ≥ 0) =
wp("x = x - 2;", (x mod 2) = (i mod 2) ∧ y + 1 ≥ 0) =
(x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0

{I ∧ b} => wp(A,I) = 
{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} => ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = 
¬{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = 
(x mod 2) != (i mod 2) ∨ (y < 0) ∨ (x ≤ 1) ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) =

(y + 1 ≥ 0) gilt immer, da y vor der Schleife immer 0 ist, und in der Schleife immer wieder inkrementiert wird.
(y < 0) ist aus selbigem Grund immer falsch.

(x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2)

Da das Axiom "a mod 2 = (a - 2) mod 2" für a ≥ 2 gilt:
aus   ¬(x ≤ 1)   folgt   (x > 1)
und daraus über das Axiom, dass
(x - 2 mod 2) = (i mod 2) = true

Das heißt:
(x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2) =
true