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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws12 [29.07.2013 14:49] – Dawodopruefungen:bachelor:aud:loesungws12 [25.03.2015 18:08] – bor1
Zeile 78: Zeile 78:
 <code> <code>
 ## 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
  
 </code> </code>
Zeile 99: Zeile 99:
  
 ==== Aufgabe 4 - Induktionsbeweis ==== ==== Aufgabe 4 - Induktionsbeweis ====
-{{:pruefungen:bachelor:aud:eq1.png|:pruefungen:bachelor:aud:eq1.png}}+{{:pruefungen:bachelor:aud:eq1.png|:pruefungen:bachelor:aud:eq1.png}} \\
 {{:pruefungen:bachelor:aud:eq2.png|:pruefungen:bachelor:aud:eq2.png}} {{:pruefungen:bachelor:aud:eq2.png|:pruefungen:bachelor:aud:eq2.png}}
  
Zeile 105: Zeile 105:
 ==== Aufgabe 5 - Rekursion ==== ==== Aufgabe 5 - Rekursion ====
  
-t.b.d.+Gesamter Sourcecode zum selber Testen: {{:pruefungen:bachelor:aud:riddle.java.txt|:pruefungen:bachelor:aud:riddle.java.txt}} 
 + 
 +**a)** 
 +<code java> 
 +boolean isSolution(LinkedList<Node> p) { 
 + 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; 
 +} 
 +</code> 
 + 
 +**b)** 
 +<code java> 
 +void allPaths(Node n, LinkedList<Node> p, LinkedList<LinkedList<Node>> s) { 
 + if(n.visited) return; 
 + n.visited = true; 
 +  
 + if(n.result) { 
 + p.addLast(n); 
 + addList(p, s); 
 + p.removeLast(); 
 + n.visited = false; 
 + } else { 
 + p.addLast(n); 
 + for(Node neighbour : n.neighbours) 
 + allPaths(neighbour, p, s); 
 + p.removeLast(); 
 + n.visited = false; 
 + } 
 +} 
 +</code> 
 + 
 +**c)** 
 +<code java> 
 +LinkedList<Node> solve(Node start) { 
 + LinkedList<LinkedList<Node>> s = new LinkedList<>(); 
 + allPaths(start, new LinkedList<Node>(), s); 
 +  
 + LinkedList<Node> best = null; 
 + for(LinkedList<Node> path : s) { 
 + if(isSolution(path)) { 
 + if(best == null || path.size() < best.size()) 
 + best = path; 
 + } 
 + } 
 +  
 + return best; 
 +} 
 +</code> 
  
  
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(n))  fib(succ(succ(n))) = add(fib(succ(n)), fib(n))
Zeile 148: Zeile 212:
  mult(succ(x), y) = add(mult(x,y), y)  mult(succ(x), y) = add(mult(x,y), y)
 </code> </code>
- 
  
 ==== Aufgabe 7 - Sortieren ==== ==== Aufgabe 7 - Sortieren ====
  
-t.b.d.+Vollständiger Sourcecode zum selber Testen: {{:pruefungen:bachelor:aud:sort.java.txt|:pruefungen:bachelor:aud:sort.java.txt}} 
 + 
 +**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, upper); 
 + swap(lower, median); 
 +  
 + lower += 5; 
 + } 
 +} 
 +</code> 
 + 
 +**b)** 
 + 
 +<code java> 
 +void pivotFirst(int left, int right) { 
 + if(left >= right) 
 + return; 
 +  
 + prepareGroups(left, right); 
 +  
 + int nextMedianPos = left; 
 + for(int i = left; i <= right; i+= 5) 
 + swap(i, nextMedianPos++); 
 +  
 + pivotFirst(left, nextMedianPos - 1); 
 +} 
 +</code> 
 + 
 +**c)** 
 + 
 +<code java> 
 +void quickSortMedian(int left, int right) { 
 + if(left < right) { 
 + int indexOfPivot = left; 
 +  
 + pivotFirst(left, right);  
 + int index = partition(left, right, left); 
 +  
 + quickSortMedian(left, index - 1); 
 + quickSortMedian(index + 1, right); 
 + } 
 +} 
 +</code> 
 + 
 +**d)** 
 +Hierbei geht es nicht um obigen Algorithmus, sondern allgemein um einen Quicksort-Algorithmus, der vor jeder Partitionierung \\ 
 +den Median alle betrachteten Werte untersucht. 
 + 
 +Mit Master-Theorem: 
 +<code> 
 +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) 
 +</code>
  
 +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)**
  
 +<code>
 +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
 +</code>
 +
 +**b)**
 +
 +<code>
 +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)
 +</code>
 +
 +**c)**
 +
 +<code>
 +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
 +</code>
 +
 +**d)**
 +
 +<code>
 +Zu zeigen: {I ∧ ¬b} => wp(S, Q) // S leer
 +
 +{I ∧ ¬b} => Q = 
 +(b^e = r * b^t ∧ t = 0) => (b^e = r) = 
 +true
 +</code>
 +
 +**e)**
 +
 +<code>
 +V = t
 +</code>