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:loesungws10 [17.02.2013 13:04] – Dawodo
+++ pruefungen:bachelor:aud:loesungws10 [14.03.2022 08:29] (aktuell) – BobbyB
@@ Zeile 1: / Zeile 1: @@
-==forum==
+===== Forendiskussionen =====
    * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8074-Wissensfragen-24-02-2011]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8875-AK-24-2-11-Aufgabe-6-Graphen-Dijkstra-Stack]]
@@ Zeile 6: / Zeile 6: @@
-==== Lösungsversuch ====
+===== Lösungsversuch =====
-=== Aufgabe 1 - Wissensfragen (10P) ===
+==== Aufgabe 1 - Wissensfragen ====
 **a)** Falsch, alle Throwables können mit catch abgefangen werden, das heißt auch java.lang.Error und davon abgeleitete Klassen. \\
 Ob ein Abfangen sinnvoll ist oder unter Umständen fehlschlagen kann (beispielsweise bei einem OutOfMemoryError unter Umständen denkbar), ist an dieser Stelle nicht gefragt.
@@ Zeile 20: / Zeile 20: @@
   * f ∈ O(log n)
   * g ∈ O(n log n);
+Hinweis: Hier ist ein kleiner Fehler in der Aufgabenstellung: Die Variable k in Funktion f muss mit 1 initialisiert sein, dem neutralen Element der Multiplikation.
 **e)** Richtig, denn ohne wahlfreien Zugriff muss die verkettete Liste bis zum gesuchten Element durchlaufen werden. Dass sie sortiert ist, ändert daran nichts, da besser Suchverfahren wie Binary Search wahlfreien Zugriff voraussetzen.
@@ Zeile 34: / Zeile 35: @@
 Zusatzinfo: \\
-**Frage:** Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler?
+**Frage:** Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? \\
 **Antwort:** Man kann alle Methoden die der generische Typ hat Aufrufen. Im Fall von <T> waere das in der Tat nur Methoden von Object (weil in Java alle Klassen von Object automatisch erben). Hier steht aber <T extends Book>, d.h. es koennen auch Methoden der Klasse Book aufgerufen werden, da der generische Typ von Book erben muss.
-=== Aufgabe 2 - Bäume (20P) ===
+==== Aufgabe 2 - Bäume ====
 **a)**
@@ Zeile 68: / Zeile 69: @@
   X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r
   V = {A, B, C, D, E, F, G}
-  E = {(A,B), (A,G), (B,D), (B,E), (B,F), (D,C)}
+  E = {[A,B],[A,G], [B,D], [B,E], [B,F], [D,C]}
   r = A
 </code>
@@ Zeile 96: / Zeile 97: @@
 <code java>
 public boolean isUndirected(boolean[][] amx) {
-	for(int i = 0; i < amx.length; i++) {		// Zeilen
+	for(int i = 0; i < amx.length; i++) {          // Zeilen
-		for(int j = 0; j < i; j++) {		// Spalten
+                if(amx[i][i])                                        // bei ungerichtetem Graph,
+                        return false;                              // kein Pfeil auf sich selbst.
+		for(int j = 0; j < i; j++) {		  // Spalten
 			if(amx[i][j] != amx[j][i])
 				return false;
@@ Zeile 139: / Zeile 142: @@
 Programm zum selber Testen: {{:pruefungen:bachelor:aud:graph.java.txt|:pruefungen:bachelor:aud:graph.java.txt}}
-=== Aufgabe 3 ===
+==== Aufgabe 3 - Sortieren ====
 **a)** 96 oder kleiner
-**b)**
+**b)** 2. Antwort ist richtig: Von Hinten nach Vorne
-  * von Vorne nach Hinten: Falsch
-  * von Hinten nach Vorne: Richtig
 **c)**
-^ Stelle ^ Reihung ^^^^^
+^ Stelle ^ Reihung ^^^^^^
 | - | de | com | es | net | ch | ee |
 | 3 | de | es | ch | ee | com | net |
@@ Zeile 156: / Zeile 157: @@
 **d)**
 <code java>
-public static char getChar(String str, int pos){
+public static char getChar(String str, int pos) {
-		return (pos < str.length()) ? (str.charAt(pos)) : (char) 96;
+	return (pos < str.length()) ? (str.charAt(pos)) : (char) 96;
-	}
+}
-	public static void radixSort(String[] array){
+public static void radixSort(String[] array) {
-		ArrayList<String>[] buckets = (ArrayList<String> []) new ArrayList[27];
+	ArrayList<String>[] buckets = (ArrayList<String>[]) new ArrayList[27];
-		for(int i = 0; i < 3; ++i){
+	for(int i = 0; i < 3; i++) {			// Pro Stelle ein Durchgang
-			for(int j = 0; j < 27; ++j){
+		for(int j = 0; j < 27; j++) {
+			buckets[j] = new ArrayList<String>();
-				buckets[j] = new ArrayList<String>();
+		}
+		for(int j = 0; j < array.length; j++) {
+			int bucketNumber = (int) getChar(array[j], 2 - i) - 96;
+			buckets[bucketNumber].add(array[j]);
+		}
+		int k = 0;
+		for(int j = 0; j < 27; j++) {
+			for(String str : buckets[j]) {
+				array[k++] = str;
 			}
-			for(int j = 0; j < array.length; ++j){
+		}
-				buckets[(int)getChar(array[j],2-i) - 96].add(array[j]);
+	}
+}
+</code>
-			}
+Programm zum selber Testen: {{:pruefungen:bachelor:aud:radixsort.java.txt|:pruefungen:bachelor:aud:radixsort.java.txt}}
-			int k = 0;
-			for( int j = 0; j < 27; ++j){
-				for(String str : buckets[j]){
-					array[k++] = str;
-				}
+==== Aufgabe 4  - Rekursion ====
-			}
-		}
+**a)** Kaskadenartige Rekursion
+**b)**
+<code java>
+public static long[] pascalNiceRek(int n) {
+	long[] result = new long[n+1];
+	long[][] dd = new long[n+1][n+1];
+        // ^ eigentlich Speicherplatzverschwendung
+        // Besser: mit for-Schleife (mit i<=n): in dd[i] = new long[i+1];
+	for(int k = 0; k <= n; k++) {
+		result[k] = pascalNiceRekH(dd, n, k);
 	}
-</code>
+	return result;
+}
+</code>
-=== Aufgabe 4 ===
+<code java>
+private static long pascalNiceRekH(long[][] dd, int n, int k) {
+	if(n < 0 || k < 0 || k > n) {
+		return 0;
+	} else if(n == 0 && k == 0) {
+		return 1;
+	}
+	if(dd[n][k] == 0) {
+		dd[n][k] = pascalNiceRekH(dd, n - 1, k - 1) + pascalNiceRekH(dd, n - 1, k);
+	}
+	return dd[n][k];
+}
+</code>
-=== Aufgabe 5 - ADT (11 Punkte) ===
+**c)**
-**a)** getPublishDate(createPost("Hallo", 24.02.2011, false) = 24.02.2011 \\
+<code java>
-FIXME ist mit "vereinfachen" wirklich die Normalform (Ergebnis) gemeint?
+public static long[] pascalNextLine(long[] current) {
+	long[] result = new long[current.length + 1];
+	result[0] = 1;
+	result[result.length - 1] = 1;
+	for(int i = 1; i < result.length - 1; i++) {
+		result[i] = current[i - 1] + current[i];
+	}
+	return result;
+}
+</code>
-**b)** 01.01.1970
+Programm zum selber Testen: {{:pruefungen:bachelor:aud:pascal.java.txt|:pruefungen:bachelor:aud:pascal.java.txt}}
-**c)** createPost(s,d,v)
+==== Aufgabe 5 - ADT ====
-**d)** F4: getUrl(publish(P , id, F )) = getURL(F);
+**a)** Ergebnis: 24.02.2011 \\
+Regeln: P1
+**b)** Ergebnis: 01.01.1970 \\
+Regeln: F2, F2, F1, P2
+**c)** setSeen(createPost(s, d, b), v) = createPost(s, d, v)
+**d)** getUrl(publish(P, id, F)) = getURL(F);
 **e)**
 <code>
-					                 F		falls id1 == id2
+revoke(id_1, publish(P, id_2, F)) = revoke(id_1, F)			 falls id_1 = id_2
-F6: revoke(id1 , publish(P , id2 , F )) =
+				= publish(P, id_2, revoke(id_1, F))	sonst
-					                 publish(P,id2,revoke(id1, F)	sonst
 </code>
+Hinweis: getPost(id_1, revoke(id_1, F)) muss noPost liefern. \\
+Das bedeutet, dass alle Posts mit ID id_1 gelöscht werden müssen. Hat man einen Post mit gesuchter ID gefunden, darf man nach dessen Löschen nicht aufhören, sondern muss "weitersuchen".
 **f)**
 <code>
-					                   publish(setSeen(P,true), id2, F)    	falls id1 = id2
+markSeen(id_1, publish(P, id_2, F)) = publish(setSeen(P, true), id_2, F)	falls id_1 = id_2
-F8: markSeen(id1 , publish(P , id2 , F )) =
+				= publish(P, id_2, markSeen(id_1, F))		sonst
-					                   publish(P, id2, markSeen(id1,F))  	sonst
 </code>
-=== Aufgabe 6 ===
+==== Aufgabe 6 - Graphen ====
 **a)**
-A --> [B,9] --> [C,6]
-B --> A,9 --> E,3 --> C,21
+  [A] -> [B,9] -> [C,6]
-F --> E,4 --> K,2 --> G,10
+  [B] -> [A,9] -> [E,3] -> [C,21]
-Z --> H,5 --> K,3
+  [F] -> [E,4] -> [K,2] -> [G,10]
+  [Z] -> [H,5] -> [K,3]
 **b)**
-| A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ K ^ Z^
-^(0) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞|
+^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ K ^ Z ^
-^0 | 9 | (6) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞|
+| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
-^0 | 9 | 6 | ∞ | ∞ | ∞ | (9) | ∞ | ∞ | ∞|
+| 0 | 9 | [6] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
-^0 | (9) | 6 | 15| ∞ | 19| 9 | ∞ | ∞ | ∞|
+| 0 | 9 | 6 | ∞ | ∞ | ∞ | [9] | ∞ | ∞ | ∞ |
-^0 | 9 | 6 | 15| (12)| 19| 9 | ∞ | ∞ | ∞|
+| 0 | [9] | 6 | 15 | ∞ | 19 | 9 | ∞ | ∞ | ∞ |
-^0 | 9 | 6 | (15)| 12| 16| 9 | ∞ | ∞ | ∞|
+| 0 | 9 | 6 | 15 | [12] | 19 | 9 | ∞ | ∞ | ∞ |
-^0 | 9 | 6 | 15| 12| (16)| 9 | 17| ∞ | ∞|
+| 0 | 9 | 6 | [15] | 12 | 16 | 9 | ∞ | ∞ | ∞ |
-^0 | 9 | 6 | 15| 12| 16| 9 | (17)| 18| ∞|
+| 0 | 9 | 6 | 15 | 12 | [16] | 9 | 17 | ∞ | ∞ |
-^0 | 9 | 6 | 15| 12| 16| 9 | 17| (18)| 22|
+| 0 | 9 | 6 | 15 | 12 | 16 | 9 | [17] | 18 | ∞ |
-^0 | 9 | 6 | 15| 12| 16| 9 | 17| 18| 21|
+| 0 | 9 | 6 | 15 | 12 | 16 | 9 | 17 | [18] | 22 |
+| 0 | 9 | 6 | 15 | 12 | 16 | 9 | 17 | 18 | [21] |
+| 0 | 9 | 6 | 15 | 12 | 16 | 9 | 17 | 18 | 21 |
 **c)**
-//Für diese Aufgabe sollte man die angegebene Entfernungstabelle benutzen.// \\
-Lösung: D-H, F-K, B-E, C-G, K-Z, D-E, E-F, A-C, D-G\\
-Wie viele Meter Kabel werden verlegt? **33**
+Lösung: (D,H), (F,K), (B,E), (C,G), (K,Z), (D,E), (E,F), (A,C), (D,G)
+Wie viele Meter Kabel werden verlegt: **33**
-=== Aufgabe 7 ===
+==== Aufgabe 7 - wp-Kalkül====
+Anmerkung: \\
+Eine for-Schleife ist nicht direkt vom wp-Kalkül abgedeckt, lässt sich aber in eine äquivalente while-Schleife umformen:
+<code>
+for(int i = 0; i < n; i++) {
+	// Code
+}
+</code>
+entspricht
+<code>
+int i = 0;
+while(i < n) {
+	// Code
+	i++;
+}
+</code>
 **a)**
-Rechts oben ist richtig, da in der Schleife und aus der Schleife der Invariante die Nachbedingung sein muss
-Die Schleife berechnet die Summer der Betraege jedes a's es können nur die rechten sein, da die linken nur die Summe zum betrag berechnet.
-Rechts unten kann man direkt wegfallen lassen, da i irgendwann = n sein muss, da sonst die Schleife nie terminiert
+<code>
+LO: Falsch
+	Hier werden erst alle einzelnen Werte aufsummiert, dann der Betrag gebildet.
+RO: Richtig
+LU: Falsch
+	Hier werden erst alle einzelnen Werte aufsummiert, dann der Betrag gebildet.
+RU: Falsch
+	i < n darf nicht gelten, da sonst die Schleife nie terminieren würde
+</code>
 **b)**
 <code>
-s einsetzen, s = 0
+wp("n = a.length; s = 0; i = 0;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) =
-wp("n=a.length; s=0; i=0;I)
+(0 = ∑{from 0 to 0 - 1} |a_j| ∧ 0 ≤ a.length) =
-=|ai|^0<=n --> 0=0^0<=n  --> stimmt!
+(0 = 0 ∧ 0 ≤ a.length) =
+(true)
 </code>
 **c)**
 <code>
-I∧b --> wp(A,I)
+Zu zeigen: {I ∧ b} => wp(A, I)
-wp("if/else;i=i+1,I)  ---> [b∧wp(Ai,I)]...
--->[a[i]>0∧wp("s=s + a[i]", s=(Summenzeichen) ∧ c <=n)
-a[i] <= 0 ∧ wp("s = s-a[i], s = (Summenzeichen) ∧ i <= n)]
---> a[i] >0 s + a[i] = (Summenzeichen) |aj| ∧ 1+1| sn) ....
+wp(A, I) =
-kp wie das weiter funktioniert
+wp("if (a[i] > 0) {s = s + a[i];} else {s = s - a[i]} i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) =
-Ende: (ai > 0 ∧ s = (Summenzeichen)|ai| ∧ i + 1 <= n)) (umgedrehtes  ∧) (ai <= 0 0 ∧ s = (Summenzeichen)|ai| ∧ i + 1 <= n))
+[(a[i] > 0) ∧ wp("s = s + a[i]; i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n)] ∨ [(a[i] ≤ 0) ∧ wp("s = s - a[i]; i = i + 1;", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n)] =
+[(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i + 1 - 1} |a_j| ∧ i + 1 ≤ n)] ∨ [(a[i] ≤ 0) ∧ wp(s - a[i] = ∑{from 0 to i + 1 - 1} |a_j| ∧ i + 1 ≤ n)] =
+[(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] ∨ [(a[i] ≤ 0) ∧ (s - a[i] = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] =
-I ∧ b => wp(a,I)
+Überlegung:
-s = (Summenzeichen)|aj| ∧ i + 1 <= n ∧ i < n) --> s = (Summenzeichen)|aj| ∧ i + 1 <= n)
+(a[i] > 0) ∧ (s + a[i] = ∑{from 0 to i} |a_j|) -> ist a[i] positiv, dann wird a[i] auf s addiert
-daraus sieht man: A --> A  ist korrekt!
+(a[i] ≤ 0) ∧ (s - a[i] = ∑{from 0 to i} |a_j|) -> ist a[i] negativ, dann wird -a[i] auf s addiert, also der Betrag von a[i]
+Man kann somit vereinfachen:
+= (s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)
+{I ∧ b} => wp(A, I)
+{(s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) ∧ (i < n)} => wp(A, I) =
+¬(s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) ∨ ¬(i < n) ∨ wp(A, I) =
+(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i > n) ∨ (i ≥ n) ∨ wp(A, I) =
+(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ wp(A, I) =
+(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ [(s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i ≤ n - 1)] =
+Überlegung:
+(i ≥ n) und (i ≤ n - 1) decken für den Integer den Zahlenstrahl ab, das heißt:
+Ist (i ≥ n) nicht erfüllt, dann ist (i ≤ n - 1) erfüllt und umgekehrt
+(s + |a[i]| = ∑{from 0 to i} |a_j|) =
+(s = ∑{from 0 to i} |a_j| - |a[i]|) =
+(s = ∑{from 0 to i - 1} |a_j|)
+und dies ist das Komplement zu
+(s ≠ ∑{from 0 to i - 1} |a_j|)
+Somit kann man schlussfolgern, dass die Invariante erfüllt ist!
 </code>
-=== Aufgabe 8 ===
+**d)**
+<code>
+V = n - i
+i = 0; n = a.length;
+i++; in jedem Schleifendurchlauf
+</code>
+==== Aufgabe 8 - UML ====
 <code java>
-class Firma{
+class Firma {
 	String name;
 	Person geschaeftsfuehrer;
 	Person[] mitarbeiter;
-	Integer gibAnzahlMitarbeiter() { //Objekt vom Typ Integer, nicht der Datentyp int
+	Integer gibAnzahlMitarbeiter() {	// Achtung: Objekt vom Typ Integer, nicht der primitive Datentyp int
+		// ...
 	}
 }
 class Person {
 	String name;
 	Integer gebJahr;
@@ Zeile 291: / Zeile 412: @@
 	Person[] gibAlleUnterstelltenMitarbeiter() {
+		// ...
 	}
 }
 </code>