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:loesungss15 [29.03.2016 12:22] – Marcel[Inf]pruefungen:bachelor:aud:loesungss15 [26.07.2017 13:17] – Verbesserung 1c ab21ajus
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). 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
 +
 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>