Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss09 [21.07.2012 11:53] – Aufgabe 5 hinzugefügt matze_ | pruefungen:bachelor:aud:loesungss09 [15.05.2019 06:26] – SpeedyGonzalez | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | === Forum === | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
- | ==== Lösungsversuch ==== | + | ===== Lösungsversuch |
- | === Aufgabe 1 - Wissensfragen | + | ==== 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)** | + | **c)** |
- | **d)** | + | **d)** |
- | **e)** | + | **e)** |
- | **f)** | + | **f)** |
- | **g)** | + | **g)** |
**h)** O(n²) | **h)** O(n²) | ||
- | **i)** | + | **i)** |
- | ==Aufgabe 2== | + | ==== Aufgabe 2 - UML==== |
**a)** | **a)** | ||
+ | |||
+ | Anmerkung: \\ | ||
+ | Bei dem gegebenen UML-Klassendiagramm wird keine grafische Unterscheidung zwischen " | ||
+ | In Java gilt jedoch: | ||
+ | |||
<code java> | <code java> | ||
- | | + | Interface extends Interface // |
- | protected int eierSammeln(); | + | Interface implements Interface // |
- | } | + | Interface extends Class // Falsch |
+ | Interface implements Class // Falsch | ||
+ | |||
+ | Class extends Interface // | ||
+ | Class implements Interface // | ||
+ | Class extends Class // OK | ||
+ | Class implements Class // Falsch | ||
+ | |||
+ | // Wobei jede Class auch abstract sein kann | ||
+ | </ | ||
+ | |||
+ | Daher sind die Pfeile immer eindeutig. | ||
+ | |||
+ | <code java> | ||
+ | abstract class EierLegend implements Haustier { | ||
+ | protected int eierSammeln() | ||
+ | } | ||
+ | |||
+ | class Schaf extends WolleGebend implements Schlachtvieh, | ||
+ | public static final int SCHWARZ = 1; | ||
+ | private static int anzahl = 0; | ||
- | + | public float melken() | |
- | class Schaf extends WolleGebend implements Schlachtvieh, | + | public final void schlachten() |
- | | + | protected static int zaehlen() |
- | | + | } |
- | + | ||
- | public float melken(); | + | |
- | | + | |
- | | + | |
- | } | + | |
</ | </ | ||
**b)** | **b)** | ||
- | java lässt | + | |
+ | In Java ist (im Gegensatz zu manchen anderen Programmiersprachen) | ||
**c)** | **c)** | ||
- | ??? | + | |
+ | Die Klassen EierLegend und WolleGebend sollten als Interface implementiert werden, ebenso, wie MilchErzeugend und SchlachVieh bereits Interfaces sind. \\ | ||
+ | " | ||
+ | |||
+ | 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)** | + | ==== Aufgabe 3 - Rekursion ==== |
+ | |||
+ | **a)** | ||
+ | |||
+ | Kaskadenartige, | ||
**b)** | **b)** | ||
+ | |||
<code java> | <code java> | ||
public static int foo(int n) { | public static int foo(int n) { | ||
- | | + | int ret; |
- | | + | 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; |
} | } | ||
</ | </ | ||
**c)** | **c)** | ||
+ | |||
+ | < | ||
+ | bar(3) | ||
+ | ---> foo(3) | ||
+ | ---> | ||
+ | | ||
+ | | ||
+ | ---> | ||
+ | ---> bar(2) | ||
+ | ---> | ||
+ | | ||
+ | | ||
+ | ---> | ||
+ | </ | ||
**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; |
+ | |||
+ | if(fooTable[n] == UNKNOWN) { | ||
- | | + | // < |
- | | + | if (n == 0) { |
- | } | + | ret = 3; |
- | //... | + | } else if (n == 1) { |
+ | ret = 1; | ||
+ | } else { | ||
+ | ret = foo(n - 1) + bar (n - 2); | ||
+ | } | ||
+ | // </ | ||
- | //... | + | fooTable[n] = ret; |
- | | + | } |
- | | + | ret = fooTable[n]; |
+ | return ret; | ||
} | } | ||
</ | </ | ||
**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)** | + | * Speicherbedarf: |
+ | |||
+ | ==== Aufgabe 4 - Sortieren ==== | ||
+ | **a)** | ||
+ | |||
+ | Die Zahlen werden von hinten | ||
**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 | + | Anmerkung: |
+ | Mit Angabe von " | ||
+ | Beispiel-Code zur Aufgabe: https:// | ||
+ | |||
+ | <code java> | ||
+ | public static void sortPos(int array[], int from, int to, int pos) { | ||
+ | LinkedList< | ||
+ | |||
+ | for (int i = 0; i < buckets.length; | ||
+ | buckets[i] = new LinkedList(); | ||
+ | } | ||
+ | |||
+ | for (int i = from; i < to; i++) { //Buckets mit PLZs befüllen und sortieren | ||
+ | int b = getDigit(array[i], | ||
+ | buckets[b].addLast(array[i]); | ||
+ | } | ||
+ | |||
+ | LinkedList< | ||
+ | |||
+ | for (int i = 0; i < buckets.length; | ||
+ | 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, | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== 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)** | ||
- | |||
{{: | {{: | ||
**c)** | **c)** | ||
- | Eulerpfad: Nein, da man mindestens eine Kante mehrmals benutzen müsste. Es weisen mehr als 2 Knoten einen ungeraden Grad auf. | ||
- | Eulerzyklus: | + | * Eulerpfad: Nein, da man mindestens eine Kante mehrmals benutzen müsste. Es weisen mehr als 2 Knoten einen ungeraden Grad auf. |
+ | * Eulerzyklus: | ||
**d)** | **d)** | ||
- | Dijkstra: O(V log(V) + E) ??? | + | Anmerkung: \\ |
+ | Je nach Implementierung sind hier viele Möglichkeiten denkbar. | ||
- | Kruskal: O(|E| · log |V |) | + | **Dijkstra:** O(v log(v) + e) bei einer Implementierung mit Fibonacci-Heap |
- | == Aufgabe | + | **Kruskal: |
+ | |||
+ | ==== Aufgabe | ||
**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, | ||
+ | Sekundärkollision, | ||
+ | |||
+ | ^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)** | ||
+ | |||
< | < | ||
- | wp('a+= ++b -2; ' | + | 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) | ||
</ | </ | ||
- | **b)** | + | **b)** |
< | < | ||
- | [(b & wp(A,Q)] | [ ab & wp (A,Q)] | + | wp("if (a > -2*b && |
- | [(a > -2b & b> | + | [(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> | + | |
- | => [a+2b > 0 & b> | + | bereits in der a) berechnet: |
- | => b> | + | wp("a += ++b - 2;", a + b > 0) = (a + 2 * b > 0) |
- | => b> | + | |
- | => 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) | ||
</ | </ | ||
- | **c) i)** | + | **c)** |
- | Invariante I = e= (a!)/ | + | |
+ | i) | ||
- | **c) ii)** Invariante nachweisen: | ||
< | < | ||
- | Formel | + | 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 | ||
+ | </ | ||
+ | |||
+ | ii) | ||
+ | |||
+ | Invariante nachweisen: | ||
+ | < | ||
+ | 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(' | + | Damit ist die Invariante gültig. |
- | wp(' | + | |
- | wp(' | + | |
- | 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 ! | + | |
</ | </ |