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

Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws12 [29.07.2013 14:47] – angelegt 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:eq1.png|:pruefungen:bachelor:aud:eq2.png}}+{{:pruefungen:bachelor:aud:eq2.png|:pruefungen:bachelor:aud:eq2.png}}
  
  
 ==== 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>