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

--- pruefungen:bachelor:aud:loesungss15 [29.03.2016 13:16] – DP a, b, c, hinzugefügt Marcel[Inf]
+++ pruefungen:bachelor:aud:loesungss15 [26.07.2017 14:16] – ab21ajus
@@ 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/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!**
@@ Zeile 11: / Zeile 11: @@
   * a) 1 und 4
   * 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
   * f) 1
-  * g) 2und 3
+  * g) 2 und 3
   * h) 1 und 4
 ==== Aufgabe 2 - Bäume (9) ====
+[[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html | Tool]]
 ==== 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.
@@ Zeile 45: / Zeile 51: @@
 ==== 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) ====
 <code java>boolean eval(HashSet<String> tv) {
@@ Zeile 84: / Zeile 117: @@
 			fn = dp[n-1];
 		} else if (n >= 3) { // fn muss noch berechnet werden
-			fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1;
 			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>