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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws12 [29.07.2013 15:04] – Dawodopruefungen:bachelor:aud:loesungws12 [25.03.2014 10:26] – Omage.xsify wird NIE aufgerufen (!) fharbe
Zeile 80: Zeile 80:
 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 +
  Mitte   Mitte
  
Zeile 105: Zeile 104:
 ==== 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 148: Zeile 211:
  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 215: Zeile 354:
 V = t V = t
 </code> </code>
-