===== Forendiskussionen =====
  * [[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]]

===== Lösungsversuch =====

==== Aufgabe 1 - Wissensfragen ====
**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

==== Aufgabe 2 - Graphen ====

**a)** 
^ A ^ B ^ C ^ D ^ E ^ F ^ Prioritäts-Warteschlange^
|[0] | ∞ | ∞ | ∞ | ∞ | ∞ | A |
| 0 | [4] | 5 | ∞ | ∞ | ∞ | B,C |
| 0 | 4 | [5] | ∞ | 5 | ∞ | C,E |
| 0 | 4 | 5 | 7 | [5] | ∞ | E,D |
| 0 | 4 | 5 | [6] | 5 | 10 | D,F |
| 0 | 4 | 5 | 6 | 5 | [10] | F |
| 0 | 4 | 5 | 6 | 5 | 10 |  |

**b)**
Pfade von Knoten A nach ...

^ ... ^ Kosten ^ Pfad ^ 
^ B | 4 | A -> B |
^ C | 5 | A -> C |
^ D | 6 | A -> B -> E -> D |
^ E | 5 | A -> B -> E |
^ F | 10 | A -> B -> E -> F |

==== Aufgabe 3 - Java ====

**a)**
^Zeile^Bildschirmausgabe bzw. keine Ausgabe^
^23 | BA |
^24 | AB |
^27 | keine Ausgabe |
^31 | BB |
^38 | CC |
^39 | AA |

Java-Datei zum selbst testen: \\
{{:pruefungen:bachelor:aud:test.java.txt|:pruefungen:bachelor:aud:test.java.txt}}

**b)**
^Zeile^Begrundung^
^7 |Compiler: A implementiert die Methode f() des Interfaces I nicht (korrekt) |
^19| Compiler: fehlender Cast von double zu int im return-Statement |
^21| Compiler: die Sichtbarkeit von A geerbte public Methode g() kann in der Unterklasse nicht eingeschränkt werden |
^34| Compiler: Statischer Zugriff auf Instanzvariablen (Beachte Unterschied: A <-> a) |
^40| Compiler: Cast von Ober- auf Unterklasse nicht möglich (andersherum jedoch schon) |
^44| Compiler: Interface I definiert keine Methode g() |

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

==== Aufgabe 4 - ADT ====
**a)**
<code>
contains(x, create) = false
contains(x, append(x, L)) = true
contains(x, append(y, L)) = contains(x, L)
</code>

**b)**
A -> D

**c)**
<code>
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))
</code>

==== Aufgabe 5 - Pseudo-Zufallszahlen ====
**a)**
<code java>
public static int f(int n) {
	if (n < 3)
		return n + 1;

	return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
}
</code>

**b)**

**Vorüberlegungen:**\\ 

<code java>
public static int f(int n) {
	return lin(1, 2, 3, n);
}
private static int lin(int a, int b, int c, int steps) { ...
</code>

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

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

Das Wichtige an dieser Aufgabe ist sich bewusst zu machen, wie die Werte im angegebenem Aufruf, mit den Basisfällen bzw. f(n-3), f(n-2), f(n-1) in der angegebenen Formel korrespondieren. Das Ziel ist ja diese Werte der Formel in Java-Code auszudrücken.

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)

<code java>
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);
}
</code>

**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)**
<code java>
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;
}
</code>


==== Aufgabe 6 - Suchbäume ====

**a)**
<code>
     27
    /  \
  23	42
 /     /  \
7     32  64
             \
             81
</code>

**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)

{{:pruefungen:bachelor:aud:ws08-6-c.png|:pruefungen:bachelor:aud:ws08-6-c.png}}

**d)**

{{:pruefungen:bachelor:aud:ws08-6-d.png|:pruefungen:bachelor:aud:ws08-6-d.png}}

  * Rotation an Knoten: 64

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

**e)**

{{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}}

==== Aufgabe 7 - Heap ====

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

**b)**
<code>
        13
      /     \
    6        9
  /   \     /
 2     5  8
</code>

**c)**
<code java>
public int leftChildIndex (int parentIndex) {
	return parentIndex * 2 + 1;
}
</code>
**d)**
<code java>
public int parentIndex (int childIndex) {
	return (childIndex % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2;
        //Oder auch einfach nur
        // return childIndex/2;
}
</code>

**e)**
<code java>
//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++;
}
</code>

**f)** O(log n)


==== Aufgabe 8 - wp-Kalkül ====

**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)
<code>
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
</code>

iii)
<code>
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
</code>