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:loesungss15 [29.03.2016 13:20] Marcel[Inf]pruefungen:bachelor:aud:loesungss15 [07.08.2019 12:55] (aktuell) TOKAMAK
Zeile 3: Zeile 3:
   * [[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 - **eingefügt!**   * [[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 **eingefügt!**   * [[https://fsi.cs.fau.de/forum/thread/13535-Vorschlag-fuer-Altklausur-SS-15-Aufgabe-7-Sorti]] Aufgabe 7 **eingefügt!**
  
Zeile 11: Zeile 11:
   * a) 1 und 4   * a) 1 und 4
   * b) 1 und 2   * b) 1 und 2
-  * c) 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 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) ====
 <code java>boolean eval(HashSet<String> tv) { <code java>boolean eval(HashSet<String> tv) {
Zeile 84: Zeile 117:
  fn = dp[n-1];  fn = dp[n-1];
  } else if (n >= 3) { // fn muss noch berechnet werden  } else if (n >= 3) { // fn muss noch berechnet werden
- fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1; 
  if (n <= dp.length) {  if (n <= dp.length) {
 + fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1;
  dp[n-1] = fn;  dp[n-1] = fn;
 + } else {
 + fn = f(n);
  }  }
  }  }