===== Forendiskussionen =====
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8082-Klausur-25-02-2010]] 4c
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8048-Klausuren-Wissensfragen]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7128-Wissensfrage-25-02-2010]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7126-Klausur-25-02-2010-Haldeneigenschaft-herstellen]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7130-Verschieden-Klausur-fragen]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7068-WP-Kalkuel-25-Februar-2010]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8745-Suchbaeume]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8847-Klausur-vom-25-02-2010-A8]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8861-Klausur-25-02-2010-Aufgabe-7b-Dijkstra]]
  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9468-Klausur-25-02-2010]]
  * [[https://fsi.cs.fau.de/forum/thread/17186-Klausur-Ws2009-Frage-zu-ADTs-A8c]]

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

==== Aufgabe 1 - Wissensfragen ====

**a)** Richtig

**b)** [nicht mehr Stoff aktueller Semester]

**c)** 
  * O(n³)
  * O(√n)
  * O(√n*log2n)

**d)** 3. Antwort ist richtig

**e)** Falsch

**f)** Falsch

**g)** Bucketsort, Mergesort

**h)** Richtig, weil: \\
\\
Zusammenhänge für die Höhe h eines AVL-Baums mit n Knoten: \\
log<sub>2</sub>(n + 1) ≤ h < 1,441 * log<sub>2</sub>(n + 2) \\
\\
<=> O(log<sub>2</sub>(n + 1)) ≤ h < O(1,441 * log<sub>2</sub>(n + 2)) \\
<=> O(log<sub>2</sub>(n)) ≤ h < O(log<sub>2</sub>(n + 2)) \\
<=> O(log<sub>2</sub>(n)) ≤ h < O(log<sub>2</sub>(n)) \\
\\
=> h ∈ O(log<sub>2</sub>(n)) \\


**i)** Falsch; nur bei gerader Anzahl an Elementen. Naja es hängt in v.a. auch von der Wahl des Pivot-Elementes ab.

**j)** O(1)

**k)** O(n)


==== Aufgabe 2 - Streutabellen ====
**a)**
^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7  ^
|  | 3 | 6 | 1 | 12 | | 2 | 5 |
|  |  |  | 9 | 4 |  |  | |

**b)**
^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7  ^
| 1<sub>7</sub> | 3<sub>0</sub> | 6<sub>0</sub> | 9<sub>0</sub> | 4<sub>0</sub> | 12<sub>3</sub> | 2<sub>0</sub> | 5<sub>0</sub> |

**c)**

Die Anzahl der Buckets und die Schrittweite sollten teilerfremd sein, da sonst nicht alle Buckets abgedeckt werden können. \\
Ein Schlüssel kann so unter Umständen nicht der Hashtabelle hinzugefügt werden, obwohl noch Buckets frei wären.


==== Aufgabe 3 -Rekursion ====

**a)**
kaskadenartige Rekursion

**b)**
Die Implementierung ist ineffizient, weil viele Werte mehrfach berechnet werden.

c)
<code java>
private static long[][] b = new long[MAX][MAX];
// Vorinitialisierung des Felds b[][] mit -1
//Klausurfragestellung nicht ganz eindeutig, gefragt ist hier richtigerweise dynamische Programmierung mittels Memoization

private static long binom(int n, int k) { 
	if(k > n)
		return 0;
	
	if(k == 0 || k == n)
		return 1;

	if(b[n][k] == -1)
		b[n][k] = binom(n - 1, k - 1) + binom(n - 1, k);

	return b[n][k];
}
</code>


==== Aufgabe 4 - Suchbäume ====

**a)**

Ein binärer Suchbaum ist ein total geordneter Baum, bei dem für jeden Knoten gilt: \\
Jeder Knoten des linken Teilbaums ist echt kleiner, jeder des rechten Teilbaums echt größer als der aktuelle Knoten.

**b)**
  * Minimale Höhe ist O(log n)
  * Maximale Höhe ist O(n)

**c)**

Gesucht ist vom aktuellen Knoten ausgehend das linkeste Kind des rechten Teilbaums
Nicht der rechte Knoten von der Wurzel, sondern das linkeste Kind vom rechten Kind der Wurzel !
<code java>
static int getNext(BinTree r) {
	// Annahme der Aufgabenstellung, dass es einen nächsten Wert gibt
	r = r.right;

	while(r.left != null) {
		r = r.left;
	}

	return r.value;
}
</code>

**d)**
<code java>
static boolean insert(BinTree b, int value) {
	BinTree prev = null;		// Schleppzeiger (kann nie null bleiben, solange der Baum nicht leer ist)

	while(b != null) {
		if(b.value == value)
			return false;

		if(b.value < value) {
			prev = b;
			b = b.right;
		} else {
			prev = b;
			b = b.left;
		}
	}
	
	if(prev.value < value) {
		prev.right = new BinTree(value);
	} else {
		prev.left = new BinTree(value);
	}

	return true;
}
</code>

oder rekursive Version:

<code java>
static boolean insertRec(BinTree b, int value) {
        if (value > b.value) {
            if (b.right == null) {
                b.right = new BinTree(value);
                return true;
            }
            return insertRec(b.right, value);
        } else if (value < b.value) {
            if (b.left == null) {
                b.left = new BinTree(value);
                return true;
            }
            return insertRec(b.left, value);
        }
        return false;
    }
</code>


==== Aufgabe 5 - Halde ====
**a)**

<code java>
public static void haldenEigenschaftHerstellen(int[] feld) {
	for(int i = feld.length/2 - 1; i>= 0; i--) {
		versickern(feld, i, feld.length-1);
	}
}
</code>

**b)**
  * **O(n log n)**
Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!)

Ja O(n), in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm

**c)**
<code java>
public static void haldenSortierung(int[] feld) {
	haldenEigenschaftHerstellen(feld);
	
	for(int i = 0; i < feld.length; i++) {
		tausche(feld, 0, feld.length - 1 - i);

		// Annahme, dass versickern nur mit validen "von" und "bis" Werte aufgerufen werden darf
		if(i < feld.length - 1)
			versickern(feld, 0, feld.length - 2 - i);
	}
}
</code>

Das ginge meines Erachtens (bei anderer Angabe noch leichter), oder??:

<code java>

public static void haldenSortierung(int[] feld){
    haldenEigenschaftHerstellen(feld);
        
    for(int i = feld.length - 1; i > 0; i--){
        tausche(feld, 0, i);
        versickern(feld, 0, i - 1);
    }
}   
</code>

Programm zum selbst Testen: \\
{{:pruefungen:bachelor:aud:heapsort.java.txt|:pruefungen:bachelor:aud:heapsort.java.txt}}

**d)** 

  * versickern: **O(log n)**
  * haldenSortierung: **O(n log n)**

==== Aufgabe 6 - UML ====

{{:pruefungen:bachelor:aud:2010.02.25.aufgabe_6_uml_korrekt.png|:pruefungen:bachelor:aud:2010.02.25.aufgabe_6_uml_korrekt.png}}

==== Aufgabe 7 - Graphen ====

**a) Adjazenzmatrix**
^   ^ A ^ B ^ C ^ D ^ 
^ A | - | 4 | 2 | - | 
^ B | 4 | - | 1 | - | 
^ C | 2 | 1 | - | 5 | 
^ D | - | - | 5 | - | 

**b) Dijkstra**
^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^
| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 
| | 4<sub>A</sub> | [2<sub>A</sub>] | ∞ | ∞ | ∞ | ∞ | ∞ | 
| | [3<sub>C</sub>] | | 7<sub>C</sub> | ∞ | ∞ | ∞ | ∞ | 
| | | | 7<sub>C</sub> | ∞ | [4<sub>B</sub>] | ∞ | ∞ | 
| | | | 7<sub>C</sub> | [5<sub>F</sub>] | | ∞ | 8<sub>F</sub> |
| | | | [7<sub>C</sub>] | | | 10<sub>E</sub> | 8<sub>F</sub> |
| | | | | | | 10<sub>E</sub> | [8<sub>F</sub>] |
| | | | | | | [9<sub>H</sub>] | |  

[9<sub>H</sub>] -> [8<sub>F</sub>] -> [4<sub>B</sub>] -> [3<sub>C</sub>] -> [2<sub>A</sub>] -> [0]

=> A -> C -> B -> F -> H -> G

**c) Euler**

Eine von mehreren Möglichkeiten: \\

{{:pruefungen:bachelor:aud:aud-25-02-10-a7-c.png|:pruefungen:bachelor:aud:aud-25-02-10-a7-c.png}}

**d)**

  * Welche Kanten werden vom Algorithmus als nächstes in Betracht gezogen? \\ EG, HF, BA, CA, DC

  * Welche dieser Kanten fugt der Algorithmus im nächsten Schritt der Lösungsmenge hinzu? \\CA

Die Kante DC wird nicht genommen, da nur Kanten hinzugefügt werden, die zu einem noch nicht besuchten Knoten führen.


==== Aufgabe 8 – Abstrakte Datentypen ====
**a)**
<code>
contains(x, create) = false
contains(x, put(x, M)) = true
contains(x, put(y, M)) = contains(x, M);
</code>
oder
\\
<code>
axs
contains(s, create()) = FALSE
contains(s, put(a, m)) = { TRUE             falls s = a
                         { contains(s, m)   sonst
</code>
**b)**
<code>
count:	String x MultiSet   ->   Integer

count(x, create) = 0
count(x, put(x, M)) = 1 + count(x, M)
count(x, put(y, M)) = count(x, M)
</code>
oder
\\
<code>
ops
count:	String x MultiSet   ->   Integer

axs
count(s, create()) = 0
count(s, put(a, m)) = { 1 + count(s, m)  falls s = a
                      { count(s, m)      sonst
</code>

**c)**
<code>
purge:	String x MultiSet   ->   MultiSet

purge(x, create) = create
purge(x, put(x, M)) = purge(x, M)
purge(x, put(y, M)) = put(y, purge(x, M))
</code>
oder
\\
<code>
ops
purge:	String x MultiSet   ->   MultiSet

axs
purge(s, create()) = create()
purge(s, put(a, m)) = { purge(s, m)            falls s = a
                      { put(a, purge(s, m))    sonst
</code>

**d)**

Primärkonstruktoren: \\
create, put

==== Aufgabe 9 - wp-Kalkül ====
**a)**
<code>
wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) =
wp("a = a*3 - 1; b = 80 - a; b = b - 1;", b > 47) =
wp("a = a*3 - 1; b = 80 - a;", b - 1 > 47) =
wp("a = a*3 - 1;", 80 - a - 1 > 47) =
(80 - (a*3 - 1) - 1 > 47) =
(80 - a*3 + 1 - 1 > 47) =
(33 > a*3) =
(11  > a)
</code>

<code>
wp("if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}", x != 7) = 
[(x < 0 ∨ x > 7) ∧ wp("x = 7 - x;", x != 7)] ∨ [¬(x < 0 ∨ x > 7) ∧ wp("x = 8 + x;", x != 7)] = 
[(x < 0 ∨ x > 7) ∧ (7 - x != 7)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (8 + x != 7)] = 
[(x < 0 ∨ x > 7) ∧ (x != 0)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (x != -1)] = 

(x != 0) ist durch (x < 0 ∨ x > 7) schon abgedeckt
(x != -1) ist durch (x ≥ 0) ∧ (x ≤ 7) schon abgedeckt

(x < 0) ∨ (x > 7) ∨ ((x ≥ 0) ∧ (x ≤ 7)) = 
(x < 0) ∨ (x > 7) ∨ (0 ≤ x ≤ 7) = 
(true)
</code>

**b)**

i)
<code>
LO: falsch
	a = 1, i = n
	mf(n, i) = mf(n, n) = 0

RO: falsch
	a = 1, i = n
	mf(n, k) - mf(i, k) = mf(n, k) - mf(n, k) = 0

LU: korrekt
	a = 1, i = n
	(mf(n, k) / (mf(i, k) = (mf(n, k) / (mf(n, k) = 1
	
RU: falsch
	a = 1, i = n
	mf(n, i) - mf(k, i) = mf(n, n) - mf(k, n) = 0 - mf(k, n) = -mf(k, n) < 0
</code>

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

wp(A, I) = 
wp("a = a*i; i = i - k;", a = (mf(n, k)) / (mf(i, k)) ) = 
wp("a = a*i;", a = (mf(n, k)) / (mf(i - k, k)) ) = 
(a*i = (mf(n, k)) / (mf(i - k, k)) ) = 
(a = (mf(n, k)) / (mf(i - k, k) * i) ) = 
= (*) = (a = (mf(n, k)) / (mf(i, k)) )

(*) Nebenrechnung:
mf(i - k, k) = (i - k) * (i - 2k) * (i - 3k) * ... * 1
mf(i - k, k) * i = (i - k) * (i - 2k) * (i - 3k) * ... * 1 * i
und das entspricht
mf(i, k) * i = i* (i - k) * (i - 2k) * (i - 3k) * ... * 1

{I ∧ b} => wp(A, I)
{a = (mf(n, k)) / (mf(i, k)) ∧ i > 0)} => (a = (mf(n, k)) / (mf(i, k)) )
trivial, da die schwächste Vorbedingung nur restriktiver gemacht wurde
</code>

iii)

<code>
V = i
i = n, n > 0	-> V > 0 zu Beginn
i = i - k, k > 0	-> i ist monoton fallend
</code>