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:loesungss09 [19.02.2013 13:03] – Dawodo
+++ pruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez
@@ Zeile 27: / Zeile 27: @@
 **h)** O(n²)
-**i)** [Nicht mehr Stoff aktueller Semester?]
+**i)** richtig, O(|v| + |E|)
@@ Zeile 117: / Zeile 117: @@
 **c)**
-FIXME - Aufrufgraph
+<code>
+bar(3)
+    ---> foo(3)
+              --->foo(2)
+                       --->foo(1)
+                       --->bar(0)
+              --->bar(1)
+    ---> bar(2)
+              --->foo(2)
+                       --->foo(1)
+                       --->bar(0)
+              --->bar(1)
+</code>
 **d)**
@@ Zeile 153: / Zeile 165: @@
   * 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) benötigt (je eins für DP von foo und von bar)
+  * Speicherbedarf: O(n), da man zwei Arrays der Größe (n + 1) beneq05oqabötigt (je eins für DP von foo und von bar)
 ==== Aufgabe 4 - Sortieren ====
@@ Zeile 170: / Zeile 182: @@
 Anmerkung:\\
-Ich hab keine Ahnung, was bei sortPos mit "from" und "to" gemeint ist. Eventuell ist das auch einfach zur Verwirrung da.
+Mit Angabe von "from" und "to" wird eine Teilsortierung moeglich.
+Beispiel-Code zur Aufgabe: https://fsi.cs.fau.de/forum/post/160481;nocount
 <code java>
 public static void sortPos(int array[], int from, int to, int pos) {
-	LinkedList<Integer>[] buckets = new LinkedList[10];
+	LinkedList<Integer>[] buckets = new LinkedList[10]; //Für jede Ziifer 0-9 einen Bucket erstellen
-	for (int i = 0; i < buckets.length; i++) {
+	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++) {
+	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<>();
+	LinkedList<Integer> master = new LinkedList<>(); //Master Liste erstellen in die Werte sortiert kopiert werden können
-	for (int i = 0; i < buckets.length; i++) {
+	for (int i = 0; i < buckets.length; i++) { //In Master Liste einen Bucket nach dem anderen kopieren
 		master.addAll(buckets[i]);
 	}
-	for(int i = 0; i < array.length; i++) {
+	for(int i = from; i < to; i++) { //In ursprünglichen Array die Elemente aus Master Liste kopieren.
 		array[i] = master.removeFirst();
 	}
@@ Zeile 197: / Zeile 211: @@
 public static void radixSort(int[] array) {
-	for (int i = 0; i < 5; i++) {
+	for (int i = 5; i >=1; i--) {
 		sortPos(array, 0, array.length, i);
 	}
@@ Zeile 232: / Zeile 246: @@
 **Kruskal:** O(e * log(e)) bei Implementierung mit Pfadkompression
-==== Aufgabe 6 -Streutabellen ====
+==== Aufgabe 6 - Streutabellen ====
 **a)**
@@ Zeile 250: / Zeile 264: @@
 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 ungerade Zahl ergibt wiederum 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.
 ^Bucket ^ Key ^ P, S oder D ^
 ^ 0 | 12 | S |
 ^ 1 | 33 | D |
 ^ 2 | 66 | S |
-^ 3 | 28 | S |
+^ 3 | 28 | P |
 ^ 4 | 14 | D |
 ^ 5 | 6   | S |
@@ Zeile 267: / Zeile 285: @@
 ==== Aufgabe 7 - wp-Kalkül ====
 **a)**
 <code>
-wp('a+= ++b -2; ' , a+b>0)
+wp("a += ++b - 2;", a + b > 0) =
-wp('b=b+1;a=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)
+wp("b = b + 1;", (a + b - 2) + b > 0) =
-wp(",a+(b+1) - 2+(b+1) >0)
+((a + (b + 1) - 2) + (b + 1) > 0) =
-=a+b+b+1+1-2 = a+2b >0
+(a + b - 1 + b + 1 > 0) =
+(a + 2 * b > 0)
 </code>
 **b)**
 <code>
-[(b & wp(A,Q)] | [ ab & wp (A,Q)]
+wp("if (a > -2*b && b > 0) {a += ++b - 2;} else {b -= --a;}", a + b > 0) =
-[(a > -2b & b>0) & wp("a+=++b-2", a+b>0)] | [( ! (a>-2b & b>0) & wp( " b-= --a", a+b > 0)]	// wp("a+=++b-2", a+b>0) wurde bei a) schon berechnet
+[(a > -2*b ∧ b > 0) ∧ wp("a += ++b - 2;", a + b > 0)] ∨ [(¬(a > -2*b ∧ b > 0) ∧ wp("b -= --a;", a + b > 0)] =
-=> [(a > -2b & b>0) & a+2b>0)] | [( ! (a>-2b & b>0) & a+b > 0)]
-=> [a+2b > 0 & b>0)] | [ a<= -2b & b>0]
+bereits in der a) berechnet:
-=> b>0 & (a+2b > = | a <=-2b)
+wp("a += ++b - 2;", a + b > 0) = (a + 2 * b > 0)
-=> b>0 & (a+2b > 0 | a+2b<=0)
-=> 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)
 </code>
-**c) i)**
+**c)**
-Invariante I = e= (a!)/(a-e-1)! & d= (e-1)
+i)
-**c) ii)** Invariante nachweisen:
 <code>
-Formel : I & b => wp (A,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
+≤ c ≤ a! - b!
+	(1 ≤ c ≤ a! - b!) = (1 ≤ 1 ≤ a! - b!)
+	Kann offensichtlich nicht für jedes a und b gelten
+</code>
+ii)
+Invariante nachweisen:
+<code>
+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
-wp('c=c*(a-e+1),d=de,e=e+1',I)
+Damit ist die Invariante gültig.
-wp('c=c*(a-e+1),d = de', c =(a!) /(a-(e+1)+1)! & d= ((e+1)-1)!
-wp('c=c*(a-e+1)',c= (a!) / (a-e)! & de= e!
-wp (", c(a-e+1)= (a!)/ (a-e)! & de-e!			// de = e! ==> d= (e-1)!
-c= (a!) / (a-e+1) & d = (e-1)!
-I & b => I	= immer wahr !
 </code>