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
pruefungen:bachelor:aud:loesungss15 [29.03.2016 12:22] – Marcel[Inf]pruefungen:bachelor:aud:loesungss15 [07.08.2019 12:55] (aktuell) – TOKAMAK
Zeile 2: Zeile 2:
  
   * [[https://fsi.cs.fau.de/forum/thread/13555-Altklausur-SS15-2-Loesungsvorschlag-Baeume]] Aufgabe 2   * [[https://fsi.cs.fau.de/forum/thread/13555-Altklausur-SS15-2-Loesungsvorschlag-Baeume]] Aufgabe 2
-  * [[https://fsi.cs.fau.de/forum/thread/13531-Altklausur-SS15-5-DAG]] Aufgabe 5 +  * [[https://fsi.cs.fau.de/forum/thread/13531-Altklausur-SS15-5-DAG]] Aufgabe 5 - **eingefügt!** 
-  * [[https://fsi.cs.fau.de/forum/thread/13536-Vorschlag-fuer-Aufgabe-6-Dynamische-Programmierun]] Aufgabe 6 +  * [[https://fsi.cs.fau.de/forum/thread/13536-Vorschlag-fuer-Aufgabe-6-Dynamische-Programmierun]] Aufgabe 6 **eingefügt!** 
-  * [[https://fsi.cs.fau.de/forum/thread/13535-Vorschlag-fuer-Altklausur-SS-15-Aufgabe-7-Sorti]] Aufgabe 7+  * [[https://fsi.cs.fau.de/forum/thread/13535-Vorschlag-fuer-Altklausur-SS-15-Aufgabe-7-Sorti]] Aufgabe 7 **eingefügt!**
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 11: Zeile 11:
   * a) 1 und 4   * a) 1 und 4
   * b) 1 und 2   * b) 1 und 2
-  * c) 2 und 3 +  * c) 4 *Edit*(und 2) vgl. Vl 14 S. 85 *Edit* 
-  * d) 1 und 4 (unsicher!). Interfaces weder implementieren noch erben von Object => siehe JLS: http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2+  * Erneuter Edit von jemand anderem: 4 ist nicht richtig, der Laufzeitaufwand bei Prim ist O(n*log n + e). O(n + m) = O(max(n, m)), n*log(n) ist hier max, darum stimmt O(n*log(n)). Ausserdem ist 3 sehr wohl richtig: Das steht exakt so in der Vorlesung, Kruskal hat O(e*log e). 
 + 
 +  * d) 1 und 4 (zu 2: Interfaces weder implementieren noch erben von Object => siehe JLS: http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2)
   * e) 3 und 4   * e) 3 und 4
   * f) 1   * f) 1
-  * g) 2und 3+  * g) 2 und 3
   * h) 1 und 4   * h) 1 und 4
 ==== Aufgabe 2 - Bäume (9) ==== ==== Aufgabe 2 - Bäume (9) ====
 +
 +[[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html | Tool]]
 ==== Aufgabe 3 - Graphen (18) ==== ==== Aufgabe 3 - Graphen (18) ====
 +a) Endergebnis: 0,2,4,7,6,7 ---> Falsch: Von A nach F kommt man mit Pfad A->B->C->F mit Kosten 5, 7 kann also nicht stimmen. Lösung ist: 0,2,4,7,6,5)
 +
 b) A->B->C->F->E->D, Distanz 7. b) A->B->C->F->E->D, Distanz 7.
  
Zeile 45: Zeile 51:
  
 ==== Aufgabe 4 - Rekursion (11) ==== ==== Aufgabe 4 - Rekursion (11) ====
 +
 +Live auf ideone.com mit AuD-Beispiel: http://ideone.com/jr02d3
 +
 +<code java>static <T> List<List<T>> helfer(T[] s, int idx) {
 + // Rückgabe pms ist Potenzmenge von s ab index idx
 + List<List<T>> pms = new ArrayList<List<T>>();
 + if (idx >= s.length) {
 + // Basisfall
 + pms.add(new ArrayList<T>());
 + } else {
 + // aktuelles Kopfelement bestimmen
 + T kopf = s[idx];
 +
 + // Potenzmenge der Restliste bestimmen
 + List<List<T>> potRest = helfer(s, idx + 1);
 +
 + // Ergebnisse zusammenführen
 + for (List<T> ohneKopf : potRest) {
 + List<T> mitKopf = new ArrayList<>(ohneKopf); // *nocH* ohne Kopf
 + mitKopf.add(kopf);
 +
 + pms.add(ohneKopf);
 + pms.add(mitKopf);
 + }
 + }
 + return pms;
 +}</code>
 ==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ==== ==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ====
-==== Aufgabe 6 - Dynamische Programmierung (17) ====+<code java>boolean eval(HashSet<String> tv) { 
 +    if (this == BDD.TRUE) return true; 
 +    if (this == BDD.FALSE) return false; 
 +    return tv.contains(v) ? trueC.eval(tv) : falseC.eval(tv); 
 +} 
 + 
 +boolean isDAG(HashSet<BDD> p) { 
 +    if (p.contains(this)) return false; 
 +    p.add(this); 
 +    if (trueC != null && !trueC.isDAG(p)) { 
 +      return false; 
 +    } 
 +    if (falseC != null && !falseC.isDAG(p)) { 
 +      return false; 
 +    } 
 +    p.remove(this); 
 +    return true; 
 +}</code> 
 +==== Aufgabe 6 - Dynamische Programmierung (17) ====  
 +a) Verschachtelte Rekursion 
 + 
 +b, c) 
 +<code java> 
 +class DynProg { 
 + 
 + private int[] dp; 
 +  
 + public DynProg(int max) { 
 + dp = new int[max]; 
 + } 
 + 
 + int fDP(int n) { // Dynamische Programmierung 
 + int fn = 1; // Basisfall n < 3 trivial 
 +  
 + // fn schon einmal berechnet? 
 + if (n <= dp.length && dp[n-1] != 0) { 
 + fn = dp[n-1]; 
 + } else if (n >= 3) { // fn muss noch berechnet werden 
 + if (n <= dp.length) { 
 + fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1; 
 + dp[n-1] = fn; 
 + } else { 
 + fn = f(n); 
 + } 
 + } 
 + return fn; 
 + } 
 +} 
 +</code> 
 + 
 +d) 
 + 
 +Hier sind viele Varianten denkbar. 
 +<code java> 
 +public static int fIter(int n) { // Iterativ 
 + int k = 1; // Zähler 
 + int fk = 1; 
 +  
 + int z = 2; 
 + for (; k<=n; k++) { 
 + if (z == 0) { 
 + fk++; 
 + z = 2 * fk - 1; 
 + } 
 + else { 
 + z--; 
 + } 
 + } 
 +  
 + return fk; 
 +} 
 +</code>
 ==== Aufgabe 7 - Sortieren (16) ==== ==== Aufgabe 7 - Sortieren (16) ====
 +Mit System.out.println() Aufrufen zum Testen:
 +<code java>
 +public class MergeSortUsing4Lists {
 +     public static void mergeSortExtern(LinkedList<Integer> b) {
 +         assert b != null;
 +         assert b.size() > 0;
 +
 +         LinkedList<Integer> b0 = new LinkedList<>();
 +         LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
 +         LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
 +         LinkedList<Integer> b3 = new LinkedList<>();
 +
 +         merge(1, b0, b1, b2, b3);
 +
 +         b.clear();
 +         b.addAll(b0);
 +         b.addAll(b1);
 +     }
 +
 +     public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
 +             LinkedList<Integer> b3) {
 +         LinkedList<Integer> target = b0; // alternating between b0 and b3
 +
 +         do {
 +             System.out.println();
 +             System.out.println(b0);
 +             System.out.println(b1);
 +             System.out.println(b2);
 +             System.out.println(b3);
 +             System.out.println();
 +             int z1 = 0, z2 = 0; // counter for the already stored integers from
 +                                 // b1/b2 up to len
 +
 +             // if possible, store integers from b1 AND b2
 +             while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
 +                 // Wegen <= ist es stabil
 +                 if (b1.getFirst() <= b2.getFirst()) {
 +                     target.addLast(b1.removeFirst());
 +                     z1++;
 +                 } else {
 +                     target.add(b2.removeFirst());
 +                     z2++;
 +                 }
 +             }
 +
 +             // if there are still integers from b1
 +             while (!b1.isEmpty() && z1 < len) {
 +                 target.addLast(b1.removeFirst());
 +                 z1++;
 +             }
 +
 +             // if there are still integers from b2
 +
 +             while (!b2.isEmpty() && z2 < len) {
 +                 target.addLast(b2.removeFirst());
 +                 z2++;
 +             }
 +
 +             target = target == b0 ? b3 : b0;
 +
 +         } while (!b1.isEmpty() || !b2.isEmpty());
 +         // b3 is not empty => recursion call!
 +
 +         if (!b3.isEmpty()) {
 +             merge(2 * len, b1, b0, b3, b2);
 +         } else {
 +             System.out.println();
 +             System.out.println(b0);
 +             System.out.println(b1);
 +             System.out.println(b2);
 +             System.out.println(b3);
 +             System.out.println();
 +         }
 +     }
 +
 +     public static void main(String[] args) {
 +         LinkedList<Integer> a_empty = new LinkedList<Integer>();
 +    mergeSortExtern(a_empty);
 +
 +         LinkedList<Integer> a = new LinkedList<Integer>(
 +                 Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
 +
 +         mergeSortExtern(a);
 +
 +         // odd number of elements (added number 19)
 +         LinkedList<Integer> a_odd = new LinkedList<Integer>(
 +                 Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
 +
 +         mergeSortExtern(a_odd);
 +     }
 + }</code>
 ==== Aufgabe 8 - Backtracking (18) ==== ==== Aufgabe 8 - Backtracking (18) ====
 <code java> <code java>