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

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungss09 [19.02.2013 13:00] – Dawodopruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez
Zeile 27: Zeile 27:
 **h)** O(n²) **h)** O(n²)
  
-**i)** [Nicht mehr Stoff aktueller Semester?]+**i)** richtig, O(|v| + |E|)
  
  
-==== Aufgabe 2 ====+==== Aufgabe 2 - UML====
 **a)** **a)**
  
Zeile 40: Zeile 40:
 Interface extends Interface // OK Interface extends Interface // OK
 Interface implements Interface // Falsch Interface implements Interface // Falsch
-Interface extends Class // Falsch+Interface extends Class // Falsch
 Interface implements Class // Falsch Interface implements Class // Falsch
  
-Class extends Interface // Falsch+Class extends Interface // Falsch
 Class implements Interface // OK Class implements Interface // OK
 Class extends Class // OK Class extends Class // OK
-Class implements Class // Falsch+Class implements Class // Falsch
  
 // Wobei jede Class auch abstract sein kann // Wobei jede Class auch abstract sein kann
Zeile 80: Zeile 80:
   * **interface** EierLegend   * **interface** EierLegend
   * **interface** WolleGebend   * **interface** WolleGebend
-  * Huhn implements EierLegend +  * Huhn **implements** EierLegend 
-  * Schaf implements WolleGebend +  * Schaf **implements** WolleGebend 
-  * EierLegend extends Haustier +  * EierLegend **extends** Haustier 
-  * WolleGebend extends Haustier +  * WolleGebend **extends** Haustier 
-  * EierlegendeWollMilchSau implements EierLegend +  * EierlegendeWollMilchSau **implements** EierLegend 
-  * EierlegendeWollMilchSau implements WolleGebend+  * EierlegendeWollMilchSau **implements** WolleGebend
  
 **d)** **d)**
Zeile 91: Zeile 91:
 UML-Sequenzdiagramm UML-Sequenzdiagramm
  
-==== Aufgabe 3 ====+==== Aufgabe 3 - Rekursion ====
  
 **a)** **a)**
Zeile 98: Zeile 98:
  
 **b)** **b)**
 +
 <code java> <code java>
 public static int foo(int n) { public static int foo(int n) {
Zeile 115: Zeile 116:
  
 **c)** **c)**
 +
 +<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)** **d)**
 +
 Es werden immer wieder die selben Wert neu berechnet z. b. foo(2). Es werden immer wieder die selben Wert neu berechnet z. b. foo(2).
 Optimierung durch dynamische Programmierung Optimierung durch dynamische Programmierung
  
 **e)** **e)**
 +
 <code java> <code java>
 public static int foo(int n) { public static int foo(int n) {
Zeile 148: 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   * 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 ====+==== Aufgabe 4 - Sortieren ====
 **a)** **a)**
  
Zeile 165: Zeile 182:
  
 Anmerkung:\\ 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> <code java>
 public static void sortPos(int array[], int from, int to, int pos) { 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();  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);  int b = getDigit(array[i], pos);
  buckets[b].addLast(array[i]);  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]);  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();  array[i] = master.removeFirst();
  }  }
Zeile 192: Zeile 211:
  
 public static void radixSort(int[] array) { 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);  sortPos(array, 0, array.length, i);
  }  }
Zeile 198: Zeile 217:
 </code> </code>
  
-== Aufgabe 5 (Graphen)==+==== Aufgabe 5 - Graphen ====
 **a)** **a)**
 ^ A ^ E ^ H4 ^ H7 ^ M ^ W ^ Warteschlange^ ^ A ^ E ^ H4 ^ H7 ^ M ^ W ^ Warteschlange^
Zeile 227: Zeile 246:
 **Kruskal:** O(e * log(e)) bei Implementierung mit Pfadkompression **Kruskal:** O(e * log(e)) bei Implementierung mit Pfadkompression
  
-==== Aufgabe 6 (Streutabellen) ====+==== Aufgabe 6 - Streutabellen ====
 **a)** **a)**
  
Zeile 245: Zeile 264:
 Begründung: \\ 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. \\ 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)** **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 ^ ^Bucket ^ Key ^ P, S oder D ^
 ^ 0 | 12 | S | ^ 0 | 12 | S |
 ^ 1 | 33 | D | ^ 1 | 33 | D |
 ^ 2 | 66 | S | ^ 2 | 66 | S |
-^ 3 | 28 | S |+^ 3 | 28 | P |
 ^ 4 | 14 | D | ^ 4 | 14 | D |
 ^ 5 | 6   | S | ^ 5 | 6   | S |
Zeile 260: Zeile 283:
 ^ 9 | 9  | D | ^ 9 | 9  | D |
  
-==== Aufgabe 7 ====+==== Aufgabe 7 - wp-Kalkül ====
 **a)** **a)**
 +
 <code> <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> </code>
  
-**b)** +**b)** 
 <code> <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> </code>
  
-**c) i)** +**c)** 
-Invariante I = e= (a!)/(a-e-1)! & d= (e-1) + 
 +i)
  
-**c) ii)** Invariante nachweisen: 
 <code> <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 
 + 1 ≤ 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> </code>