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:loesungws10 [17.02.2013 15:11] Dawodopruefungen: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/8074-Wissensfragen-24-02-2011]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8875-AK-24-2-11-Aufgabe-6-Graphen-Dijkstra-Stack]]   * [[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. \\ **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. 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)   * f ∈ O(log n)
   * g ∈ O(n 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. **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: \\ 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. **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)** **a)**
Zeile 68: Zeile 69:
   X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r    X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r 
   V = {A, B, C, D, E, F, G}    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    r = A 
 </code> </code>
Zeile 96: Zeile 97:
 <code java> <code java>
 public boolean isUndirected(boolean[][] amx) { 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])  if(amx[i][j] != amx[j][i])
  return false;  return false;
Zeile 139: Zeile 142:
 Programm zum selber Testen: {{:pruefungen:bachelor:aud:graph.java.txt|:pruefungen:bachelor:aud:graph.java.txt}} 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 **a)** 96 oder kleiner
  
-**b)** +**b)** 2. Antwort ist richtigVon Hinten nach Vorne
-  * von Vorne nach HintenFalsch +
-  * von Hinten nach Vorne: Richtig+
  
 **c)** **c)**
Zeile 185: Zeile 186:
 Programm zum selber Testen: {{:pruefungen:bachelor:aud:radixsort.java.txt|:pruefungen:bachelor:aud:radixsort.java.txt}} Programm zum selber Testen: {{:pruefungen:bachelor:aud:radixsort.java.txt|:pruefungen:bachelor:aud:radixsort.java.txt}}
  
-=== Aufgabe 4 ===+==== Aufgabe 4  - Rekursion ====
  
 **a)** Kaskadenartige Rekursion **a)** Kaskadenartige Rekursion
Zeile 195: Zeile 196:
  long[] result = new long[n+1];   long[] result = new long[n+1];
  long[][] dd = new long[n+1][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++) {  for(int k = 0; k <= n; k++) {
Zeile 239: Zeile 242:
 Programm zum selber Testen: {{:pruefungen:bachelor:aud:pascal.java.txt|:pruefungen:bachelor:aud:pascal.java.txt}} Programm zum selber Testen: {{:pruefungen:bachelor:aud:pascal.java.txt|:pruefungen:bachelor:aud:pascal.java.txt}}
  
-=== Aufgabe 5 - ADT (11 Punkte) ===+==== Aufgabe 5 - ADT ====
  
-**a)** Ergebnis: 24.02.2011+**a)** Ergebnis: 24.02.2011 \\ 
 +Regeln: P1
  
-**b)** Ergebnis: 01.01.1970+**b)** Ergebnis: 01.01.1970 \\ 
 +Regeln: F2, F2, F1, P2
  
 **c)** setSeen(createPost(s, d, b), v) = createPost(s, d, v) **c)** setSeen(createPost(s, d, b), v) = createPost(s, d, v)
Zeile 252: Zeile 257:
  
 <code> <code>
-revoke(id_1, publish(P, id_2, F)) = publish(P, id_2, revoke(id_1, F)) +revoke(id_1, publish(P, id_2, F)) = revoke(id_1, F) falls id_1 = id_2 
-revoke(id_1, publish(P, id_1, F)) = F+ publish(P, id_2, revoke(id_1, F)) sonst
 </code> </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)**  **f)** 
  
 <code> <code>
-revoke(id_1, publish(P, id_2, F)) = publish(P, id_2, revoke(id_1, F)+markSeen(id_1, publish(P, id_2, F)) = publish(setSeen(P, true), id_2, F) falls id_1 = id_2 
-revoke(id_1publish(P, id_1, F)) = F+publish(P, id_2, markSeen(id_1, F)) sonst
 </code> </code>
  
-<code> +==== Aufgabe 6 - Graphen ====
-markSeen(id_1, publish(P, id_2, F)) publish(P, id_2, markSeen(id_1, F)) +
-markSeen(id_1, publish(P, id_1, F)) = publish(setSeen(P, true), id_1, F) +
-</code> +
- +
-=== Aufgabe 6 ===+
  
 **a)** **a)**
Zeile 299: Zeile 301:
  
  
-=== 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)** **a)**
Zeile 331: Zeile 349:
  
 wp(A, I) = wp(A, I) =
-wp("if (a[i] > 0) {s = s + a[i];} else {s = s - a[i]}", s = ∑{from 0 to i - 1} |a_j| ∧ i ≤ n) =+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) =
 [(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) ∧ 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 + 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)] =
Zeile 348: Zeile 366:
 (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) ∨ wp(A, I) =
-(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ [(s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i + 1 ≤ n)] = +(s ≠ ∑{from 0 to i - 1} |a_j|) ∨ (i ≥ n) ∨ [(s + |a[i]| = ∑{from 0 to i} |a_j|) ∧ (i ≤ n - 1)] =
-</code>+
  
-Alter Lösungsansatz+Überlegung
-<code> +(i ≥ n) und (≤ n - 1) decken für den Integer den Zahlenstrahl abdas heißt: 
-wp("if/else;i=i+1,I ---> [b∧wp(Ai,I)]... +Ist (i ≥ n) nicht erfülltdann ist (i ≤ - 1erfüllt und umgekehrt
--->[a[i]>0∧wp("s=s + a[i]", s=(Summenzeichen) ∧ c <=n) +
-a[i] <= 0 ∧ wp("s = s-a[i]s = (Summenzeichen) ∧ <= n)]+
  
---> a[i] >0 s + a[i] = (Summenzeichen) |aj∧ 1+1| sn.... +(s + |a[i]∑{from 0 to i} |a_j|) = 
-kp wie das weiter funktioniert +(s = ∑{from 0 to i} |a_j- |a[i]|) = 
-Ende: (ai > 0 ∧ s = (Summenzeichen)|ai∧ + 1 <n)) (umgedrehtes  ∧) (ai <= 0 0 ∧ s = (Summenzeichen)|ai∧ i + 1 <= n))+(∑{from to i - 1} |a_j|)
  
-I ∧ b => wp(a,I) +und dies ist das Komplement zu 
-= (Summenzeichen)|aj| ∧ <= n ∧ i < n) --> s = (Summenzeichen)|aj∧ i + 1 <= n+(s ≠ ∑{from 0 to 1|a_j|) 
-daraus sieht man: A --> A  ist korrekt!+ 
 +Somit kann man schlussfolgern, dass die Invariante erfüllt ist!
 </code> </code>
  
 **d)** **d)**
- 
-// unsicher 
  
 <code> <code>
Zeile 377: Zeile 391:
 </code> </code>
  
-=== Aufgabe 8 ===+==== Aufgabe 8 - UML ====
  
 <code java> <code java>