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
pruefungen:bachelor:aud:loesungws12 [29.07.2013 15:04] – Dawodopruefungen:bachelor:aud:loesungws12 [28.03.2022 08:00] (aktuell) – Warnung vor Quatsch BobbyB
Zeile 80: Zeile 80:
 0,0 0,1 0,2 0,0 0,1 0,2
 NPE null null NPE null null
 + Grmbl
  
  
Zeile 86: Zeile 86:
 1,0 1,1 1,2 1,0 1,1 1,2
 x x x x x x
- icks + icks
  Mitte   Mitte
  
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 160: Zeile 300:
  
 Dia-Sourcefile für etwaige Korrekturen: {{:pruefungen:bachelor:aud:21-02-2013-8.dia.txt|:pruefungen:bachelor:aud:21-02-2013-8.dia.txt}} Dia-Sourcefile für etwaige Korrekturen: {{:pruefungen:bachelor:aud:21-02-2013-8.dia.txt|:pruefungen:bachelor:aud:21-02-2013-8.dia.txt}}
 +
 +Vorsicht, dieses Diagramm ist falsch. Erstens müssen bremsanlage und tasten nicht mit in Kabinensteuerung, sondern nur als Beziehung eingetragen werden. Außerdem sollte die implements Beziehung zwischen den Tasten und dem Interface gestrichelt sein.
  
 ==== Aufgabe 9 - Formale Verifikation ==== ==== Aufgabe 9 - Formale Verifikation ====
Zeile 215: Zeile 357:
 V = t V = t
 </code> </code>
-