Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:bachelor:aud:loesungws08 [23.07.2012 13:43] – Erläuterungen zur Linearisierung in Aufgabe 5 b) Damon
+++ pruefungen:bachelor:aud:loesungws08 [11.05.2019 10:23] – SpeedyGonzalez
@@ Zeile 1: / Zeile 1: @@
-==forum==
+===== 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]]
@@ Zeile 7: / Zeile 7: @@
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung]]
-====Lösungsversuch====
+===== Lösungsversuch =====
-==Aufgabe 1 - Wissensfragen==
+==== Aufgabe 1 - Wissensfragen ====
-**a)** falsch
+**a)** Falsch, es muss sortiert sein
-**b)** 3 - eine Schleife korrekt ist
+**b)** Nummer 3: eine Schleife korrekt ist
-**c)** richtig
+**c)** Richtig
-**d)** richtig
+**d)** Richtig
 **e)** Bucketsort, Mergesort
@@ Zeile 24: / Zeile 24: @@
 **g)** 4 - O(n² * log n)
-**h)** O(n*(log n)²)
+**h)** 2 - O(n*(log n)²)
 **i)** 1 - kontextsensitiven Grammatiken
-==Aufgabe 2 - Graphen==
+==== Aufgabe 2 - Graphen ====
 **a)**
 ^ A ^ B ^ C ^ D ^ E ^ F ^ Prioritäts-Warteschlange^
@@ Zeile 40: / Zeile 41: @@
 **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 |
-  * nach B: 4
+==== Aufgabe 3 - Java ====
-  * nach C: 5
-  * nach D: 6
-  * nach E: 5
-  * nach F: 10
-==Aufgabe 3 - Java==
 **a)**
-Java Datei zum selber testen: {{:pruefungen:bachelor:aud:test.java.txt|:pruefungen:bachelor:aud:test.java.txt}}
 ^Zeile^Bildschirmausgabe bzw. keine Ausgabe^
 ^23 | BA |
@@ Zeile 57: / Zeile 60: @@
 ^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: f implementiert nicht die Methode f des Interfaces|
+^7 |Compiler: A implementiert die Methode f() des Interfaces I nicht (korrekt) |
-^19| Compiler: keine cast von double auf int im return Statement |
+^19| Compiler: fehlender Cast von double zu int im return-Statement |
-^34| Compiler: Instanzvariablen können nicht über den statischen Typ angesprochen werden (nicht A sondern a)|
+^21| Compiler: die Sichtbarkeit von A geerbte public Methode g() kann in der Unterklasse nicht eingeschränkt werden |
-^40| Compiler: Man kann nicht von der Ober- auf die Unterklasse konvertieren, nur andersherum|
+^34| Compiler: Statischer Zugriff auf Instanzvariablen (Beachte Unterschied: A <-> a) |
-^44| Compiler: g ist eine private-Methode. Darauf kann man nicht von i aus zugreifen|
+^40| Compiler: Cast von Ober- auf Unterklasse nicht möglich (andersherum jedoch schon) |
+^44| Compiler: Interface I definiert keine Methode g() |
-==Aufgabe 4 - ADT==
+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)**
-A4: contains(x, create) = false
 <code>
-A5: contains(x, append(y,l))= 1+contains(x,l)       //falls x=y
+contains(x, create) = false
-                             contains(x,l)          //falls x!=y
+contains(x, append(x, L)) = true
+contains(x, append(y, L)) = contains(x, L)
 </code>
 **b)**
-A -> D -> create
+A -> D
 **c)**
-//VORSICHT! nicht wirklich sicher! //
+<code>
+append(head(append(D, create), append(A, create)) =
-A1: 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))
+A1
+= append(head(prepend(D, create), prepend(A, create)) =
-A3: append(D, prepend(A, create)
+A3
+= append(D, prepend(A, create)) =
+A2
+= prepend(A, append(D, create)) =
+A1
+= prepend(A, prepend(D, create))
+</code>
-A2: prepend(A, append(D, create)
+==== Aufgabe 5 - Pseudo-Zufallszahlen ====
-A1: prepend(A, prepend(D, create)
-==Aufgabe 5 - Pseudo-Zufallszahlen==
 **a)**
 <code java>
@@ Zeile 95: / Zeile 108: @@
 	if (n < 3)
 		return n + 1;
-	else
-		return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
+	return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
 }
 </code>
@@ Zeile 104: / Zeile 117: @@
 **Vorüberlegungen:**\\
-f(n - 1) ^= c, da f(2) = 2 + 1 = 3 ist; analog:\\
+<code java>
-f(n - 2) ^= b\\
+public static int f(int n) {
-f(n - 3) ^= a
+	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.
-lin (a, b, c) ^= lin (f(n - 3), f(n - 2), f(n - 1), steps)
+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.
+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)  	**(*)**
+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) und sieht mit a, b, c dann so aus:
+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)
+f(n) = 1 + (((c - b) * a) % 100)  	**(* *)**
-Das in **(*)** eingesetzt ergibt dann
+**(* *)** in **(*)** eingesetzt ergibt:
 lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)
@@ Zeile 130: / Zeile 160: @@
 private static int lin(int a, int b, int c, int steps) {
-    if (steps == 0) {
+	if (steps == 0)
-        return a;
+		return a;
-    } else {
-        lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
+	return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
-    }
 }
 </code>
@@ Zeile 140: / Zeile 169: @@
 **Warum steht das Ergebnis gerade in a?**
-Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift: f(0) = lin(1, 2, 3, 0). Da n = 0 < 3, greift der sonst-Fall und das Ergebnis muss n + 1 = 0 + 1 = 1 sein. Und die 1 steht 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, b = 2, c = 3;
+	int a = 1;
-	while (n > 0) {
+	int b = 2;
-		int tmp = a;
+	int c = 3;
+	while(n > 0) {
+		int fn = 1 + (((c - b) * a) % 100);
 		a = b;
 		b = c;
-		c = 1 + (((b-a)*tmp)%100);
+		c = fn;
 		n--;
 	}
 	return a;
 }
 </code>
-==Aufgabe 6 - Suchbäume==
+==== Aufgabe 6 - Suchbäume ====
 **a)**
 <code>
@@ Zeile 162: / Zeile 202: @@
     /  \
 	42
- /      / \
+ /     /  \
      32  64
-            \
+             \
 </code>
 **b)**
-Schlusselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81
+\\
-Kosten: O (n²)
+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)
-Schlusselfolge für minimale Höhe: 32, 64, 42, 81, 23, 7,  27
+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. \\
-Kosten: O (n * log n)
+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}}
@@ Zeile 183: / Zeile 231: @@
 {{:pruefungen:bachelor:aud:ws08-6-d.png|:pruefungen:bachelor:aud:ws08-6-d.png}}
-Rotation an: 64
+  * Rotation an Knoten: 64
-Einfachrotation, da 81 und 64 links gedreht werden.
+  * **Einfachrotation** gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind
+**e)**
-==Aufgabe 7 - Heap==
+{{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}}
+==== Aufgabe 7 - Heap ====
 **a)**
-Für jeden Knoten außer der Wurzel gilt A[Vater[i]] >= A[i]
+Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein.
 **b)**
 <code>
-    9
+      /     \
-  5  8
+        9
+  /   \     /
+     5  8
 </code>
 **c)**
 <code java>
 public int leftChildIndex (int parentIndex) {
-     return parentIndex*2+1;
+	return parentIndex * 2 + 1;
 }
 </code>
@@ Zeile 208: / Zeile 262: @@
 <code java>
 public int parentIndex (int childIndex) {
-     return (childIndex-1)/2;
+	return (childIndex % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2;
 }
 </code>
@@ Zeile 216: / Zeile 270: @@
 //keine garantie!
 public void add (int priority) {
+	array[n] = priority;
+	int p = parentIndex(n);
-   array[n] = priority;
+	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;
-   while( j !=0) {
+		n = p;
+		p = parentIndex(n);
-        int i = n;
+	}
-        int j = parentIndex(n);
-        if( priority > array[j] ) {
+	n++;
-              array[i] = array[j];
-              array[j] = priority;
-        } else {
-             break;
-        }
-    }
-    n++;
 }
 </code>
@@ Zeile 239: / Zeile 289: @@
-==Aufgabe 8 (wp)==
+==== Aufgabe 8 - wp-Kalkül ====
 **a)**
-a > b-5 && true => a > b-5
+  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>