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 [21.07.2012 11:56] – matze_pruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez
Zeile 1: Zeile 1:
-=== Forum ===+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8871-Klausur-06-08-2009-Aufgabe-7]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8871-Klausur-06-08-2009-Aufgabe-7]]
  
-==== Lösungsversuch ====+===== Lösungsversuch =====
  
  
-=== Aufgabe 1 - Wissensfragen (13P) === +==== Aufgabe 1 - Wissensfragen ==== 
-**a)** [noch nicht in Vorlesung durchgenommen]+**a)** [Nicht mehr Stoff aktueller Semester]
  
 **b)**  **b)** 
-O (log2n) +(unsicher)
-O (n²)+
  
-O(2 hoch n)+  * O(log n) 
 +  * O(n²) 
 +  * O(2^n)
  
-**c)** falsch+**c)** Falsch, der Balancefaktor entspricht der **Differenz** der beiden Höhen
  
-**d)** falsch (geht nur andersherum)+**d)** Falsch, implizit (also automatisch) geht es nur in die andere Richtung (Ober o = new Unter();). Explizit mit Cast geht zur Compilezeit (Unter u = (Unter) new Ober();) auch, wirft aber eine ClassCastException zur Laufzeit.
  
-**e)** richtig+**e)** Richtig
  
-**f)** richtig+**f)** Richtig, beispielsweise oft beim Comparable Interface benutzt: LinkedList<Comparable>
  
-**g)** falsch+**g)** Falsch, HeapSort ist in-place
  
 **h)** O(n²) **h)** O(n²)
  
-**i)** [nicht in Vorlesung durchgenommen]+**i)** richtig, O(|v| + |E|)
  
  
-==Aufgabe 2==+==== Aufgabe 2 - UML====
 **a)** **a)**
 +
 +Anmerkung: \\
 +Bei dem gegebenen UML-Klassendiagramm wird keine grafische Unterscheidung zwischen "implements" und "extends" getroffen. \\
 +In Java gilt jedoch:
 +
 <code java> <code java>
-    abstract class EierLegend implements Haustier{ +Interface extends Interface // OK 
-                protected int eierSammeln(); +Interface implements Interface // Falsch 
-    }+Interface extends Class // Falsch 
 +Interface implements Class // Falsch 
 + 
 +Class extends Interface // Falsch 
 +Class implements Interface // OK 
 +Class extends Class // OK 
 +Class implements Class // Falsch 
 + 
 +// Wobei jede Class auch abstract sein kann 
 +</code> 
 + 
 +Daher sind die Pfeile immer eindeutig. 
 + 
 +<code java> 
 +abstract class EierLegend implements Haustier { 
 + protected int eierSammeln() { // ... } 
 +} 
 + 
 +class Schaf extends WolleGebend implements Schlachtvieh, MilchErzeugend { 
 + public static final int SCHWARZ = 1; 
 + private static int anzahl = 0;
            
-      + public float melken() { // ... } 
-    class Schaf extends WolleGebend implements Schlachtvieh, MilchErzeugend{ + public final void schlachten() { // ... } 
-                 public static final int SCHWARZ =1; + protected static int zaehlen() { // ... } 
-                 private static int anzahl=0; +} 
-      +
-                 public float melken(); +
-                 public final void schlachten(); +
-                 protected static int zaehlen(); +
-    } +
 </code> </code>
  
 **b)** **b)**
-java lässt keine mehrfachvererbung zu ( extends MilchErzeugend,Eierlegend,... n.a.)+ 
 +In Java ist (im Gegensatz zu manchen anderen Programmiersprachen) keine Mehrfachvererbung möglich. Die Klasse EierlegendeWollMilchSau erbt jedoch von den Klassen EierLegend, WolleGebend und Sau.
  
 **c)** **c)**
-???+ 
 +Die Klassen EierLegend und WolleGebend sollten als Interface implementiert werden, ebenso, wie MilchErzeugend und SchlachVieh bereits Interfaces sind. \\ 
 +"Eigenschaften" bzw. "Schnittstellen" sollte ohnehin eher als Interface, als abstrakte Klasse implementiert werden. 
 + 
 +Liste aller Änderungen: 
 +  * **interface** EierLegend 
 +  * **interface** WolleGebend 
 +  * Huhn **implements** EierLegend 
 +  * Schaf **implements** WolleGebend 
 +  * EierLegend **extends** Haustier 
 +  * WolleGebend **extends** Haustier 
 +  * EierlegendeWollMilchSau **implements** EierLegend 
 +  * EierlegendeWollMilchSau **implements** WolleGebend
  
 **d)** **d)**
-?? 
  
-== Aufgabe 3 ==+UML-Sequenzdiagramm
  
-**a)** Verschränkte Rekursion+==== Aufgabe 3 - Rekursion ==== 
 + 
 +**a)** 
 + 
 +Kaskadenartige, verschränkte Rekursion
  
 **b)** **b)**
 +
 <code java> <code java>
 public static int foo(int n) { public static int foo(int n) {
-    int ret;+ int ret;
  
-    if (n == 0) { + if (n == 0) { 
-        ret = 3; + ret = 3; 
-    } else if (n == 1) { + } else if (n == 1) { 
-        ret = 1; + ret = 1; 
-    } else { + } else { 
-        ret = foo(n - 1) + bar (n - 2); + ret = foo(n - 1) + bar (n - 2); 
-    }+ }
  
-    return ret;+ return ret;
 } }
 </code> </code>
  
 **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) {
-    int ret;+ int ret; 
 + 
 + if(fooTable[n] == UNKNOWN) {
  
-    if (fooTable[n] != UNKNOWN) { + // <Teilabschnitt von a)> 
-        return fooTable[n]; + if (n == 0) { 
-    } + ret = 3; 
-//...+ } else if (n == 1) { 
 + ret = 1; 
 + } else { 
 + ret = foo(n - 1) + bar (n - 2); 
 + } 
 + // </Teilabschnitt von a)>
  
-//... + fooTable[n] = ret; 
-    fooTable[n] = ret;+ }
  
-    return ret;+ ret = fooTable[n]; 
 + return ret;
 } }
 </code> </code>
  
 **e)** **e)**
-LZ: O(n²) 
-S-Pl: O(n) 
  
-== Aufgabe 4 == +  * 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 
-**a)** Von hinten nach vorne, also erst die letze stelle, dann die vorletzte usw.+  * 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 ==== 
 +**a)** 
 + 
 +Die Zahlen werden von hinten (rechts) nach vorne (links) sortiert, damit bspw. die Zahl "78" vor der Zahl "88" steht. Wichtig ist hierbei, dass das Verfahren unbedingt stabil sortieren muss.
  
 **b)** **b)**
 ^ Stelle ^ Reihung ^^^^^^ ^ Stelle ^ Reihung ^^^^^^
-|     |  420  | 234 | 142  |  123   | 432  |  230   ^ +^     |  420  | 234 | 142  |  123   | 432  |  230   ^ 
-|  3 |  420  | 230 | 142  |  432  | 123  |  234   ^ +^  3 |  420  | 230 | 142  |  432  | 123  |  234   ^ 
-|  2 |  420  | 123 | 230  |  432  |  234 |  142   ^ +^  2 |  420  | 123 | 230  |  432  |  234 |  142   ^ 
-|  1 |  123  | 142 | 230  |  234  | 420 |  432  |+^  1 |  123  | 142 | 230  |  234  | 420 |  432  |
  
 **c)** **c)**
  
-== Aufgabe 5 (Graphen)==+Anmerkung:\\ 
 +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]; //Für jede Ziifer 0-9 einen Bucket erstellen 
 +  
 + 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++) { //Buckets mit PLZs befüllen und sortieren 
 + int b = getDigit(array[i], pos); 
 + buckets[b].addLast(array[i]); 
 + } 
 +  
 + LinkedList<Integer> master = new LinkedList<>(); //Master Liste erstellen in die Werte sortiert kopiert werden können 
 +  
 + for (int i = 0; i < buckets.length; i++) { //In Master Liste einen Bucket nach dem anderen kopieren 
 + master.addAll(buckets[i]); 
 + } 
 +  
 + for(int i = from; i < to; i++) { //In ursprünglichen Array die Elemente aus Master Liste kopieren. 
 + array[i] = master.removeFirst(); 
 + } 
 +} 
 + 
 +public static void radixSort(int[] array) { 
 + for (int i = 5; i >=1; i--) { 
 + sortPos(array, 0, array.length, i); 
 + } 
 +} 
 +</code> 
 + 
 +==== Aufgabe 5 - Graphen ====
 **a)** **a)**
 ^ A ^ E ^ H4 ^ H7 ^ M ^ W ^ Warteschlange^ ^ A ^ E ^ H4 ^ H7 ^ M ^ W ^ Warteschlange^
-|∞ | ∞ | ∞ | ∞ | ∞ | [0] | W | +| ∞ | ∞ | ∞ | ∞ | ∞ | [0] | W | 
-|15 | ∞ | ∞ | ∞ | [2] | 0 | M, A | +| 15 | ∞ | ∞ | ∞ | [2] | 0 | A, M | 
-|15 | ∞ | 6 | [3] | 2 | 0 | H7, H4, A | +| 15 | ∞ | 6 | [3] | 2 | 0 | A, H4, H7 | 
-|15 | 21 | [6] | 3 | 2 | 0 | H4, A | +| 15 | 21 | [6] | 3 | 2 | 0 | A, H4, E | 
-|[14] | 20 | 6 | 3 | 2 | 0 | A, E | +| [14] | 20 | 6 | 3 | 2 | 0 | A, E | 
-|14 | [18] | 6 | 3 | 2 | 0 | E | +| 14 | [18] | 6 | 3 | 2 | 0 | E | 
-|14 | 18 | 6 | 3 | 2 | 0 | |+| 14 | 18 | 6 | 3 | 2 | 0 | |
  
 **b)** **b)**
- 
  
 {{:pruefungen:bachelor:aud:5-b-kruskal.png|:pruefungen:bachelor:aud:5-b-kruskal.png}} {{:pruefungen:bachelor:aud:5-b-kruskal.png|:pruefungen:bachelor:aud:5-b-kruskal.png}}
  
 **c)** **c)**
-Eulerpfad: Nein, da man mindestens eine Kante mehrmals benutzen müsste. Es weisen mehr als 2 Knoten einen ungeraden Grad auf. 
  
-Eulerzyklus: Nein, es haben nicht alle Knoten einen geraden Grad.+  * Eulerpfad: Nein, da man mindestens eine Kante mehrmals benutzen müsste. Es weisen mehr als 2 Knoten einen ungeraden Grad auf. 
 +  * Eulerzyklus: Nein, es haben nicht alle Knoten einen geraden Grad.
  
 **d)** **d)**
  
-**Dijkstra:** O((|V| + |E|)* log|V|)+Anmerkung: \\ 
 +Je nach Implementierung sind hier viele Möglichkeiten denkbar. 
  
-Gesamtaufwand mit Fibonacci Halde: O(|V| * log|V| + |E|)+**Dijkstra:** O(v log(v) + e) bei einer Implementierung mit Fibonacci-Heap
  
-**Kruskal:** O(|E| · log |V |)+**Kruskal:** O(e * log(e)) bei Implementierung mit Pfadkompression
  
-== Aufgabe 7 ==+==== Aufgabe 6 - Streutabellen ====
 **a)** **a)**
 +
 +^Bucket ^ Keys (LinkedList) ^
 +^ 0 | |
 +^ 1 | 27 -> 75 |
 +^ 2 | |
 +^ 3 | 44 -> 4 -> 0 |
 +^ 4 | |
 +^ 5 | 13 -> 65 -> 33 |
 +^ 6 | |
 +^ 7 | 46 -> 26 | 
 +
 +**b)**
 +
 +Die Hashfunktion mappt jeden Schlüssel garantiert auf einen Bucket mit ungerader Nummer. \\
 +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 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 | P |
 +^ 4 | 14 | D |
 +^ 5 | 6   | S |
 +^ 6 | 18 | D |
 +^ 7 | 5   | D |
 +^ 8 | 15 | P |
 +^ 9 | 9  | D |
 +
 +==== Aufgabe 7 - wp-Kalkül ====
 +**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>