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 Überarbeitung | ||
pruefungen:bachelor:aud:loesungss09 [19.02.2013 13:00] – Dawodo | pruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez | ||
---|---|---|---|
Zeile 27: | Zeile 27: | ||
**h)** O(n²) | **h)** O(n²) | ||
- | **i)** | + | **i)** |
- | ==== Aufgabe 2 ==== | + | ==== Aufgabe 2 - UML==== |
**a)** | **a)** | ||
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 |
- | * WolleGebend extends Haustier | + | * WolleGebend |
- | * EierlegendeWollMilchSau implements EierLegend | + | * EierlegendeWollMilchSau |
- | * EierlegendeWollMilchSau implements WolleGebend | + | * EierlegendeWollMilchSau |
**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)** | ||
+ | |||
+ | < | ||
+ | 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) { | ||
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: | + | * Speicherbedarf: |
- | ==== Aufgabe 4 ==== | + | ==== Aufgabe 4 - Sortieren |
**a)** | **a)** | ||
Zeile 165: | Zeile 182: | ||
Anmerkung: | Anmerkung: | ||
- | Ich hab keine Ahnung, was bei sortPos mit " | + | Mit Angabe von " |
+ | |||
+ | Beispiel-Code | ||
<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< | + | LinkedList< |
- | for (int i = 0; i < buckets.length; | + | for (int i = 0; i < buckets.length; |
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], | int b = getDigit(array[i], | ||
buckets[b].addLast(array[i]); | buckets[b].addLast(array[i]); | ||
} | } | ||
- | LinkedList< | + | LinkedList< |
- | for (int i = 0; i < buckets.length; | + | for (int i = 0; i < buckets.length; |
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, | sortPos(array, | ||
} | } | ||
Zeile 198: | Zeile 217: | ||
</ | </ | ||
- | == 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: | **Kruskal: | ||
- | ==== 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 | + | Eine ungerade Zahl modulo eine gerade |
**c)** | **c)** | ||
+ | |||
+ | Primärkollision, | ||
+ | Sekundärkollision, | ||
+ | |||
^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)** | ||
+ | |||
< | < | ||
- | 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 ! | + | |
</ | </ |