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 [16.02.2013 22:57] – gakupruefungen: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)** //Da die Klasse AssertionError eine Unterklasse von java.lang.Error ist, können Ausnahmen dieser Art nicht abgefangen und daher nicht behandelt werden.//+**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.
  
-**falsch**: Alle Fehlertypen, auch java.lang.Error und davon abgeleitete können mit catch abgefangen werden, obwohl das u.U. nicht immer sinnvoll ist; Fehler die von java.lang.Error abgeleitet sind, haben meist ein schwerwiegendes Problem als Ursache, so dass es sinnvoller sein kann, das Programm zu beenden als unter unklaren Bedingungen zu versuchen weiterzuarbeiten.+**b)** Richtig, das Argument für die VM lautet "-ea" (für "enable assertions").
  
-**b)** //Ein AssertionError tritt in einer seiteneffektfreien assert-Anweisung auf, wenn die +**c)** Richtig, Beweis siehe Vorlesung.
-Zusicherung während der Programmausführung nicht erfüllt ist, jedoch nur, falls das Prüfen von Zusicherungen durch die Java-VM beim Programmstart aktiviert wurde.// +
- +
-**wahr**. +
- +
-**c)** //Es kann kein Sortierverfahren für n Schlüssel existieren, das auf Vergleichen von Schlüsselpaaren beruht und dessen Laufzeitkomplexität besser als O(n · log<sub>2</sub> n) ist.// +
- +
-**wahr**. Ich (dario) würde sagen, dass da log<sub>2</sub> steht, prüft einfach nochmal ab, ob dem Prüfling klar ist dass O(log<sub>2</sub> n) = O(log_a n) = O(log n) +
- +
-**d)** FIXME: code eintragen +
-f ∈ O(log n); g ∈ O(n log n); +
- +
-**e)** //Die Suche nach einem Element in einer sortierten doppelt-verketteten Liste der Länge n ohne wahlfreien Zugriff hat eine Laufzeitkomplexität von O(n).// +
- +
-**wahr**: "ohne wahlfreien Zugriff" => man muss die Liste entlanglaufen, bis man das gesuchte Element gefunden hat, die Tatsache dass die Liste sortiert ist, hilft in demt Moment nicht allzuviel. +
- +
-**f)** //Verwendet man zum Einfügen in einen Streuspeicher (Tabellenlänge n) das sogenannte quadratische Sondieren, so hat die Operation eine Laufzeitkomplexität von O(log(n)).// +
- +
-**falsch**: Die Reihenfolge wie die Felder der Streutabelle sondiert werden, ist zwar unterschiedlich, insgesamt werden im worst case aber trotzdem alle Felder einmal besucht, also ist die Komplexität O(n). +
- +
-**g)** //In einem gerichteten Graphen G = (V, E) repräsentiert der Ausgangsgrad eines Knotens n ∈ V die Anzahl aller Knoten m ∈ V , für die es eine Kante (n, m) ∈ E gibt.// +
- +
-**wahr**.+
  
 +**d)**
 +  * 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.
  
-**h)** //Mehrfachvererbung von mehreren nicht-abstrakten Oberklassen ist in UML-Klassendia- +**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.
-grammen (genau wie in Java) verboten.//+
  
-**falsch**: Da UML nicht Java-spezifisch ist, und z.B. in C++ Mehrfachvererbung möglich ist, ist auch in UML Mehrfachvererbung erlaubt.+**f)** Falsch, im worst-case werden alle Felder nur genau einmal besucht, die Komplexität liegt also in O(n)
  
 +**g)** Richtig
  
-**i)** //Folgender Code verwendet Generics korrekt im Sinne der Sprache Java und ist daher +**h)** Falsch, UML ist nicht Java-spezifisch. In andere Programmiersprachen wie beispielsweise C++ ist die Mehrfachvererbung möglich.
-gültig und ubersetzbar:// FIXME: add code+
  
-**wahr** (ich (dario) kann keinen fehler erkennen ;)+**i)** Richtig
  
-**Frage:** Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? (Dank an dario für die guten Erklärungen)+Datei zum selber Testen: {{:pruefungen:bachelor:aud:rack.java.txt|:pruefungen:bachelor:aud:rack.java.txt}}
  
 +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? \\
 **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)**
  
 ==Adjazenzmatrix== ==Adjazenzmatrix==
-|     ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^+^     ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^
 ^ A |   -  |  + |   -  |   -  |   -  |  -  |  + | ^ A |   -  |  + |   -  |   -  |   -  |  -  |  + |
 ^ B |  +  |  -  |   -  |  +  | +  |  + |  -  | ^ B |  +  |  -  |   -  |  +  | +  |  + |  -  |
Zeile 74: Zeile 58:
  
 **b)** **b)**
-//Geben Sie zu jedem Knoten des neuen Baums X dessen Höhe in X an://+
 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^
 |  0  |  1  |  3  |  2  |  2   | 2  |  1  | |  0  |  1  |  3  |  2  |  2   | 2  |  1  |
- 
  
 **c)** **c)**
-//Betrachten Sie den neuen Baum X als sogenannten Out-Tree“ (bei dem die Kanten gerichtet von der Wurzel ausgehen) und geben Sie ihn in Mengenschreibweise an:// 
  
-**Mengenschreibweise** +<code> 
-X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r \\ +  Mengenschreibweise: 
-V = {A, B, C, D, E, F, G} \\ + 
-E = {{AB}, {AG}, {BD}, {BE}, {BF}, {DC}} \\ +  X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r  
-r = A \\+  V = {A, B, C, D, E, F, G}  
 +  E = {[A,B],[A,G], [B,D], [B,E], [B,F], [D,C]}  
 +  r = A  
 +</code>
  
 **d)** **d)**
-//Schreiben Sie eine Methode isUndirected, die feststellt ob eine Adjazenzmatrix amx 
-einen ungerichteten Graphen darstellt.// 
  
-Zunächst einmal muss man sich klar machen, dass ein Graph genau dann ungerichtet ist, wenn die Adjazenzmatrix sowohl einen Eintrag (AB) als auch einen Eintrag (BA) hat.+Zunächst einmal muss man sich klar machen, dass ein Graph genau dann ungerichtet ist, wenn die Adjazenzmatrix sowohl den Eintrag (A,B) als auch einen Eintrag (B,A) aufweist. Das heißt: Die Adjazenzmatrix ist an der Diagonale symmetrisch (vergleiche Adjazenzmatrix oben). 
 + 
 +Grundlegende Idee für die Funktion ''isUndirected'': \\ 
 +Die Matrix komplett durchgehen und überprüfen, ob jeder Eintrag matrix[i][j] mit dem an der Diagonale gespiegeltem Wert matrix[j][i] identisch ist. Sollte das nicht der Fall sein, ist der zugehörige Graph gerichtet.
  
 <code java> <code java>
-/** 
- * die idee is, einfach die ganze adjazenzmatrix durch zu gehen 
- * und zu schaun ob alle einträge mit ihren "gegenüberliegenden" 
- * - also an der diagonale gespiegelten (indices vertauscht) - 
- * übereinstimmen. falls nicht, ist der graph gerichtet. 
- **/ 
 public boolean isUndirected(boolean[][] amx) { public boolean isUndirected(boolean[][] amx) {
- for(int i= 0; i < amx.length; i++) { + for(int i = 0; i < amx.length; i++) { // Zeilen 
- for(int j= 0; j < amx[0].length; j++) { + for(int j = 0; j < amx[0].length; j++) { // Spalten 
- if(amx[i][j] != amx[j][i]) {+ if(amx[i][j] != amx[j][i])
  return false;  return false;
- } 
  }  }
  }  }
 +
  return true;  return true;
 } }
 </code> </code>
  
-(dario): ich geb zu, es is nicht der effizienteste code (wer will kann den mal dazuschreiben), aber in der klausur kommts erstmal drauf an, dass der code tut was er soll, und nicht ob er dass in O(n) oder O(n<sup>2</sup>) tut (abgesehen davon, dass es selbst wenn man nur die hälfte vergleicht noch O(n<sup>2</sup>) bleibt).+Geringfügig optimierte Version, die nur eine Dreiecksmatrix durchiteriert:
  
-**e)** TODO 
 <code java> <code java>
- public static boolean allReach(boolean[][] ug, int node){ +public boolean isUndirected(boolean[][] amx) { 
- boolean schonGehabt[] = new boolean[ug[node].length]; + for(int i = 0; i < amx.length; i++) {          // Zeilen 
-  +                if(amx[i][i])                                        // bei ungerichtetem Graph, 
- help(ug, node, schonGehabt); +                        return false;                              // kein Pfeil auf sich selbst.  
-  + for(int j = 0; j < i; j++) {   // Spalten 
- for (int i=0; i<schonGehabt.length; i++){ + if(amx[i][j] != amx[j][i])
- if (schonGehabt[i] == false){+
  return false;  return false;
- } 
  }  }
- return true; 
  }  }
 +
 + return true;
 +}
 +</code>
 +
 +Programm zum selber Testen: {{:pruefungen:bachelor:aud:graph.java.txt|:pruefungen:bachelor:aud:graph.java.txt}}
 +
 +**e)**
 +<code java>
 +public static boolean allReachable(boolean[][] ug, int node) {
 + boolean[] visited = new boolean[ug.length];
   
 + visited[node] = true;
 + visitAll(ug, visited, node);
   
- public static void help(boolean[][] ug, int node, boolean[] schonGehabt){ + for(int i = 0; i < visited.length; i++) { 
- schonGehabt[node] = true; + if(!visited[i]) 
-  + return false; 
- for (int i=0; i<ug[node].length; i++){ + } 
- if (schonGehabt[i] == false && ug[node][i] == true){ +  
- help(ug, i, schonGehabt);+ return true; 
 +} 
 + 
 +private static void visitAll(boolean[][] ug, boolean[] visited, int node) { 
 + for(int i = 0; i < ug.length; i++) { 
 + if(ug[node][i]) { 
 + if(!visited[i]) { 
 + visited[i] = true; 
 + visitAll(ug, visited, i);
  }  }
  }  }
- } //Gruesse Gaku :)+ } 
 +}
 </code> </code>
  
-=== Aufgabe 3 === +Programm zum selber Testen: {{:pruefungen:bachelor:aud:graph.java.txt|:pruefungen:bachelor:aud:graph.java.txt}}
-**a)** 96+
  
-**b)** von hinten nach vorne+==== Aufgabe 3 - Sortieren ==== 
 +**a)** 96 oder kleiner 
 + 
 +**b)** 2. Antwort ist richtig: Von Hinten nach Vorne
  
 **c)** **c)**
  
-^ Stelle ^ Reihung ^ +^ Stelle ^ Reihung ^^^^^^ 
-|  -  |  de  |  com  |  es  |  net   | ch  |  ee   ^ +| - | de | com | es | net | ch | ee | 
-|  3 |  de  |  es  |  ch   |  ee   | com  |  net   ^ +| 3 | de | es | ch | ee | com | net | 
-|  2 |  de  |  ee  |  net   |ch   |  com  | es     ^ +| 2 | de | ee | net | ch | com | es | 
-|  1 |  ch  | com | de  |  ee  | es |  net  |+| 1 | ch | com | de | ee | es | net |
  
 **d)** **d)**
 <code java> <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)** 
  
-**e)**  
 <code> <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> </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>
-                    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> </code>
-=== Aufgabe 6 ===+ 
 +==== Aufgabe 6 - Graphen ==== 
 **a)** **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)** **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)** **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)** **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)** **b)**
 +
 <code> <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) = 
-0=|ai|^0<=n --> 0=0^0<=n  --> stimmt!+(0 = 0 ∧ 0 ≤ a.length) = 
 +(true)
 </code> </code>
  
 **c)** **c)**
 +
 <code> <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> </code>
-=== Aufgabe 8 ===+ 
 +**d)** 
 + 
 +<code> 
 +V = n - i 
 + 
 +i = 0; n = a.length; 
 +i++; in jedem Schleifendurchlauf 
 +</code> 
 + 
 +==== Aufgabe 8 - UML ==== 
 <code java> <code java>
-class Firma{ +class Firma {
- +
  String name;  String name;
  Person geschaeftsfuehrer;  Person geschaeftsfuehrer;
  Person[] mitarbeiter;  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 { class Person {
-  
  String name;  String name;
  Integer gebJahr;   Integer gebJahr; 
Zeile 290: Zeile 412:
   
  Person[] gibAlleUnterstelltenMitarbeiter() {  Person[] gibAlleUnterstelltenMitarbeiter() {
 + // ...
  }  }
-  
 } }
 </code> </code>