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 ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws12 [29.07.2013 14:49] – Dawodo | pruefungen:bachelor:aud:loesungws12 [25.03.2015 18:08] – bor1 | ||
---|---|---|---|
Zeile 78: | Zeile 78: | ||
< | < | ||
## fld[0][0] ## ## fld[0][1] ## ## fld[0][2] ## | ## fld[0][0] ## ## fld[0][1] ## ## fld[0][2] ## | ||
- | 0,0 0,1 0,2 | + | 0,0 0,1 0,2 |
- | NPE null null | + | NPE null null |
+ | Grmbl | ||
## fld[1][0] ## ## fld[1][1] ## ## fld[1][2] ## | ## fld[1][0] ## ## fld[1][1] ## ## fld[1][2] ## | ||
- | 1,0 1,1 1,2 | + | 1,0 1,1 1,2 |
- | x x x | + | x x x |
- | icks | + | icks |
Mitte | Mitte | ||
## fld[2][0] ## ## fld[2][1] ## ## fld[2][2] ## | ## fld[2][0] ## ## fld[2][1] ## ## fld[2][2] ## | ||
- | 2,0 2,1 2,2 | + | 2,0 2,1 2,2 |
- | null Fertig | + | null Fertig |
</ | </ | ||
Zeile 99: | Zeile 99: | ||
==== Aufgabe 4 - Induktionsbeweis ==== | ==== Aufgabe 4 - Induktionsbeweis ==== | ||
- | {{: | + | {{: |
{{: | {{: | ||
Zeile 105: | Zeile 105: | ||
==== Aufgabe 5 - Rekursion ==== | ==== Aufgabe 5 - Rekursion ==== | ||
- | t.b.d. | + | Gesamter Sourcecode zum selber Testen: {{: |
+ | |||
+ | **a)** | ||
+ | <code java> | ||
+ | boolean isSolution(LinkedList< | ||
+ | int tmpRes = p.get(0).val; | ||
+ | for(int i = 1; i < p.size() - 1; i+= 2) { | ||
+ | Node op = p.get(i); Node v = p.get(i+1); | ||
+ | switch(op.type) { | ||
+ | case ADD: tmpRes += v.val; break; | ||
+ | case SUB: tmpRes -= v.val; break; | ||
+ | case MUL: tmpRes *= v.val; break; | ||
+ | case DIV: | ||
+ | if(tmpRes % v.val != 0) return false; | ||
+ | tmpRes /= v.val; break; | ||
+ | case EQ: | ||
+ | if(v.result && tmpRes == v.val) return true; | ||
+ | return false; | ||
+ | default: return false; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return false; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | <code java> | ||
+ | void allPaths(Node n, LinkedList< | ||
+ | if(n.visited) return; | ||
+ | n.visited = true; | ||
+ | |||
+ | if(n.result) { | ||
+ | p.addLast(n); | ||
+ | addList(p, | ||
+ | p.removeLast(); | ||
+ | n.visited = false; | ||
+ | } else { | ||
+ | p.addLast(n); | ||
+ | for(Node neighbour : n.neighbours) | ||
+ | allPaths(neighbour, | ||
+ | p.removeLast(); | ||
+ | n.visited = false; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | <code java> | ||
+ | LinkedList< | ||
+ | LinkedList< | ||
+ | allPaths(start, | ||
+ | |||
+ | LinkedList< | ||
+ | for(LinkedList< | ||
+ | if(isSolution(path)) { | ||
+ | if(best == null || path.size() < best.size()) | ||
+ | best = path; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return best; | ||
+ | } | ||
+ | </ | ||
Zeile 124: | Zeile 188: | ||
fib: Nat -> Nat | fib: Nat -> Nat | ||
axs: | axs: | ||
- | fib(zero) = zero | + | fib(zero) = succ(zero) |
fib(succ(zero)) = succ(zero) | fib(succ(zero)) = succ(zero) | ||
fib(succ(succ(n))) = add(fib(succ(n)), | fib(succ(succ(n))) = add(fib(succ(n)), | ||
Zeile 148: | Zeile 212: | ||
mult(succ(x), | mult(succ(x), | ||
</ | </ | ||
- | |||
==== Aufgabe 7 - Sortieren ==== | ==== Aufgabe 7 - Sortieren ==== | ||
- | t.b.d. | + | Vollständiger Sourcecode zum selber Testen: {{: |
+ | |||
+ | **a)** | ||
+ | |||
+ | <code java> | ||
+ | void prepareGroups(int left, int right) { | ||
+ | int lower = left; | ||
+ | while(lower <= right) { | ||
+ | int median = lower + 2; | ||
+ | int upper = lower + 4; | ||
+ | |||
+ | if(upper > right) { | ||
+ | upper = right; | ||
+ | median = lower + (upper - lower) / 2; | ||
+ | } | ||
+ | |||
+ | groupSort(lower, | ||
+ | swap(lower, | ||
+ | |||
+ | lower += 5; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | <code java> | ||
+ | void pivotFirst(int left, int right) { | ||
+ | if(left >= right) | ||
+ | return; | ||
+ | |||
+ | prepareGroups(left, | ||
+ | |||
+ | int nextMedianPos = left; | ||
+ | for(int i = left; i <= right; i+= 5) | ||
+ | swap(i, nextMedianPos++); | ||
+ | |||
+ | pivotFirst(left, | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | <code java> | ||
+ | void quickSortMedian(int left, int right) { | ||
+ | if(left < right) { | ||
+ | int indexOfPivot = left; | ||
+ | |||
+ | pivotFirst(left, | ||
+ | int index = partition(left, | ||
+ | |||
+ | quickSortMedian(left, | ||
+ | quickSortMedian(index + 1, right); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **d)** | ||
+ | Hierbei geht es nicht um obigen Algorithmus, | ||
+ | den Median alle betrachteten Werte untersucht. | ||
+ | |||
+ | Mit Master-Theorem: | ||
+ | < | ||
+ | T = 2 * T(n/2) + n | ||
+ | |||
+ | a = 2, b = 2, f(n) = n | ||
+ | |||
+ | Fall 2: | ||
+ | f(n) ∈ Θ(n^(log_b(a))) | ||
+ | n ∈ Θ(n^(log_2(2))) | ||
+ | n ∈ Θ(n^1) | ||
+ | n ∈ Θ(n) | ||
+ | true | ||
+ | |||
+ | Damit gilt: | ||
+ | T(n) ∈ Θ(n * log n) | ||
+ | </ | ||
+ | Lösung: O(n * log n) | ||
==== Aufgabe 8 - UML ==== | ==== Aufgabe 8 - UML ==== | ||
Zeile 163: | Zeile 303: | ||
==== Aufgabe 9 - Formale Verifikation ==== | ==== Aufgabe 9 - Formale Verifikation ==== | ||
- | t.b.d. | + | **a)** |
+ | < | ||
+ | LO: Falsch, r bleibt während der Abarbeitung der Schleife offensichtlich nicht konstant | ||
+ | RO: Richtig | ||
+ | LU: Falsch, ist vor der Schleife ungültig | ||
+ | |||
+ | RU: Falsch, ist zwar vor der Schleife erfüllt, stimmt während der Abarbeitung der Schleife nicht | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | < | ||
+ | Zu zeigen: P => wp(A, I) | ||
+ | |||
+ | wp(A, I) = wp("r = 1; t = e;", b^e = r * b^t) = | ||
+ | = (b^e = 1 * b^e) = (true) | ||
+ | |||
+ | (P => true) = (true) | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | < | ||
+ | Zu zeigen: {I ∧ b} => wp(S, I) | ||
+ | |||
+ | wp(S, I) = wp("r = r * b; t = t - 1;", b^e = r * b^t) = | ||
+ | = (b^e = r * b * b^(t-1)) = | ||
+ | = (b^e = r * b^t) = | ||
+ | |||
+ | {I ∧ b} => wp(S, I) = | ||
+ | (b^e = r * b^t ∧ t != 0) => (b^e = r * b^t) = | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | **d)** | ||
+ | |||
+ | < | ||
+ | Zu zeigen: {I ∧ ¬b} => wp(S, Q) // S leer | ||
+ | |||
+ | {I ∧ ¬b} => Q = | ||
+ | (b^e = r * b^t ∧ t = 0) => (b^e = r) = | ||
+ | true | ||
+ | </ | ||
+ | |||
+ | **e)** | ||
+ | |||
+ | < | ||
+ | V = t | ||
+ | </ |