Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen

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
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws11 [18.02.2013 13:51] – Dawodopruefungen:bachelor:aud:loesungws11 [16.03.2018 18:37] – Evren
Zeile 1: Zeile 1:
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
-FIXME - Bitte um Forenthreads erweitern!+  * [[https://fsi.informatik.uni-erlangen.de/forum/post/112045|https://fsi.informatik.uni-erlangen.de/forum/post/112045]] - Aufgabe 4
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 11: Zeile 11:
 **b)** Antwort RO ist richtig: Stark zusammenhängend **b)** Antwort RO ist richtig: Stark zusammenhängend
  
-**c)** 2. Antwort ist richtig: Preorder+**c)** 2. Antwort ist richtig: Preorder. Postorder müsste auch stimmen, denn die Reihenfolge, ob zuerst nach links oder rechts abgestiegen wird, ist nicht festgelegt. 
 + \\ 
 +Doch die Reihenfolge ist festgelegt: L-R-N (Links, Rechts, Mitte), siehe [[https://www2.cs.fau.de/teaching/WS2017/AuD/slides/secure/aud-12.pdf|WS 2017/2018 - Folie 12-52]] => nur Preorder ist richtig, so kommt man dann auch am Ende der Aufgabe auf die 10 Antworten = 10 Punkte.
  
 **d)** Richtig **d)** Richtig
Zeile 17: Zeile 19:
 **e)** Richtig, beispielsweise wenn sich die Werte für BucketSort eignen **e)** Richtig, beispielsweise wenn sich die Werte für BucketSort eignen
  
-**f)** (unsicher) +**f)** 
-  * f ist linear rekursiv +  * f ist linear rekursiv \\ 
-  * g ist iterativ+nach Definition ist eine Funktion genau dann linear rekursiv, wenn sie in jedem Zweig einer Fallunterscheidung höchstens einmal aufgerufen wird. \\ 
 +Bei Funktion f gilt:\\ 
 +Fall 1: Ist (x < = 0) ∨ (x % 2 = 0), also für die Zahlen (..., -3, -2, -1, 0, 2, 4, 6, ...), kommt es zu gar keinem rekursiven Funktionsaufruf. \\ 
 +Fall 2: Ist (x > 0) ∧ (x % 2 != 0) ∧ (x % 3 != 0), also für die Zahlen (1, 5, 7, 11, 13, ...) wird x um eins inkrementiert und der Schleiferumpf erneut ausgeführt. \\ 
 +Da jetzt mit Sicherheit Fall 1 vorliegt, kommt es ebenfalls zu keinem rekursiven Funktionsaufruf. \\ 
 +Fall 3: Ist (x > 0) ∧ (x % 2 != 0) ∧ (x % 3 == 0), also für die Zahlen (3, 9, 15, ...), kommt es zu einem rekursiven Aufruf f(x+1). Bei diesem Aufruf liegt mit Sicherheit Fall 1 \\ 
 +vor, weshalb x = x + 1 gilt. Anschließend wird x um eins inkrementiert und wir sind garantiert im Fall 2, bei dem es zu keinem rekursiven Funktionsaufruf kommt. 
 +Damit ist gezeigt, dass f linear rekursiv ist. 
 + 
 +  * g ist iterativ \\ 
 +nach Definition ist eine Funktion f nur genau dann rekursiv, wenn zur Berechnung von f diese Funktion f benutzt wird. 
  
 **g)** Antwort RO und LU sind richtig **g)** Antwort RO und LU sind richtig
Zeile 42: Zeile 54:
 ==Als Reihung== ==Als Reihung==
 ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ 13 ^  ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ 13 ^ 
-^ 6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 |+| 6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 |
  
 **b)** **b)**
Zeile 52: Zeile 64:
 **c)** **c)**
  
-Vorüberlegungen:\\+**Vorüberlegungen:**\\
 Die Aufgabenstellung ist das Färben eines Graphen mit den Farben **schwarz** und **grau**. Die Farbe **weiß** bedeutet lediglich, dass dieser Knoten noch gar nicht gefärbt wurde. Die Aufgabenstellung ist das Färben eines Graphen mit den Farben **schwarz** und **grau**. Die Farbe **weiß** bedeutet lediglich, dass dieser Knoten noch gar nicht gefärbt wurde.
 Bei dem Verfahren soll Breitensuche verwendet werden. Bei dem Verfahren soll Breitensuche verwendet werden.
  
-Eine elementare Erkenntnis hierbei ist: \\ +**Elementare Erkenntnis hierbei:** \\ 
-Hat ein Knoten zwei Nachbar, die verschiedene Farben haben, so kann der aktuelle Knoten nicht gefärbt werden, ohne die gleiche Farbe wie mindestens einer sein+Hat ein Knoten zwei (oder mehr) Nachbarn, die verschiedene Farben haben, so kann der aktuelle Knoten nicht gefärbt werden, ohne dass er die gleiche Farbe wie mindestens ein Nachbarknoten erhält. \\ 
 +Das bedeutet: Hat ein Knoten mindestens einen Nachbarn, der **grau** ist und mindestens einen, der **schwarz** ist, so lässt sich der Graph nicht färben und das Verfahren soll mit dem Rückgabewert "false" terminieren.
  
 <code java> <code java>
-while (!q.isEmpty()) { +boolean color(Node v) { 
- Node current = q.removeFirst(); + LinkedList<Node> q = new LinkedList<Node>(); 
- for (int i = 0; i < current.neighbors.size(); i++) { + v.color = BLACK; 
- if (current.neighbors.get(i).color == WHITE) { + q.addLast(v); 
- q.addLast(current.neighbors.get(i));+ 
 + // Solange es noch unbesuchte Knoten gibt 
 + while(!q.isEmpty()) { 
 + // Aktuellen Knoten aus der Queue entnehmen: 
 + // Dieser Knoten ist noch WHITE und soll nun korrekt gefärbt werden 
 + Node current = q.removeFirst(); 
 +  
 + // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) 
 + Color neighborColor = WHITE; 
 +  
 + // Gehe alle Nachbarknoten einmal durch 
 + for(Node n : neighbors) { 
 +  
 + // Ist der aktuelle Nachbar WHITE, dann wurde er noch nicht besucht 
 + // -> Füge ihn der Queue hinzu 
 + if(n.color == WHITE) { 
 + q.addLast(n); 
 +  
 + // Ist der aktuelle Nachbar nicht WHITE, dann wurde er schon besucht 
 + // und ist entweder BLACK oder GRAY 
 + } else { 
 + // Ist die Variable für die Farbe der Nachbarn noch nicht gesetzt 
 + // (d.h. WHITE), dann initialisiere sie anhand des aktuellen Nachbarn 
 + if(neighborColor == WHITE) 
 + neighborColor = n.color; 
 +  
 + // Hat der aktuelle Nachbar eine andere Farbe, als die bisher 
 + // betrachteten Nachbarknoten, dann ist der Graph nicht färbbar 
 + if(n.color != neighborColor) 
 + return false; 
 + }
  }  }
- } // for zuende 
  
- if (current.color == BLACK) { + // Färbe den Knoten korrekt ein und markiere ihn so als besucht 
- for (int i = 0; i < current.neighbors.size(); i++) { + // Die Farbe muss das Gegenteil der Farbe der Nachbarn sein! 
- if (current.neighbors.get(i).color == BLACK) + // Gab es keine Färbung der Nachbar, so wird der Knoten BLACK 
- return false; + current.color = (neighborColor == BLACK) ? GRAY : BLACK;
- if (current.neighbors.get(i).color == WHITE) +
- q.get(i).color = GRAY; +
- } // for zuende +
- } else { +
- for (int i = 0; i < current.neighbors.size(); i++) { +
- if (current.neighbors.get(i).color == GRAY) +
- return false; +
- if (current.neighbors.get(i).color == WHITE) +
- q.get(i).color = BLACK; +
- } // for zuende+
  }  }
  
-} // while zuende +// Die Schlange ist leer, alle Knoten wurden abgearbeitet, der Graph 
-return true; // gruesse Gaku :) +// wurde erfolgreich gefärbt. 
- +return true;
-// EDIT: Die Lösung stimmt nicht ganz, wenn jemand was besseres hat, +
-// kann er dashier gerne ersetzen!+
 </code> </code>
  
Zeile 101: Zeile 131:
 | | | **gd.g("YC")** | | |  | | | **gd.g("YC")** | | | 
 | | | GC | | | | | | GC | | |
 +
 +Anmerkungen:
 +  * Immer auf die Bindungstypen achten (statisch versus dynamisch)
 +  * Es kommen grundsätzlich nur die Attribute / Methoden in Frage, die der statische Typ kennt
 +  * Bei überladenen Methoden wird die spezifischte verwendet
  
 Programm zum selber Testen: {{:pruefungen:bachelor:aud:walkthrough.txt|Walkthrough.java}} Programm zum selber Testen: {{:pruefungen:bachelor:aud:walkthrough.txt|Walkthrough.java}}
  
 ==== Aufgabe 4 - Sortieren ==== ==== Aufgabe 4 - Sortieren ====
-[[https://fsi.informatik.uni-erlangen.de/forum/post/112045|Lösung]] von weißnix: 
  
 **a)** **a)**
 +
 <code java> <code java>
 private void versickern(Knoten k) { private void versickern(Knoten k) {
 + Knoten groesser = null;
  
-         Knoten groesser = null;+ if(links != null && rechts != null) { 
 + groesser = (links.wert > rechts.wert) ? links : rechts;
  
-         groesser = k.links; + } else if(links != null) { 
- + groesser = links;
-         if(k.rechts != null){ +
-               if(k.links != null && k.links.wert < k.rechts.wert || k.links == null) { +
-                                 groesser = k.rechts; +
-               } +
-        }+
  
 + } else if(rechts != null) {
 + groesser = rechts;
 + }
  
-        if(groesser == null) { + if(groesser == null) { 
-             return; + return; 
-        } + }
  
-        if(groesser.wert <k.wert) return; + if(k.wert > groesser.wert) 
- + return;
-        vertausche (groesser, k); +
- +
-         +
-        versickern(groesser);+
  
 + vertausche(k, groesser);        
 + versickern(groesser);
 } }
 </code> </code>
 **b)** **b)**
 +Nach dem Postorder-Prinzip:
 <code java> <code java>
 private void erzeugeHalde(Knoten k) { private void erzeugeHalde(Knoten k) {
 + if(k.left != null)
 + erzeugeHalde(k.left);
  
-       if(k.left != null){ + if(k.right != null) 
-           erzeugeHalde(k.left); + erzeugeHalde(k.right);
-       } +
- +
-       if(k.right !=null){ +
-           erzeugeHalde(k.right); +
-       } +
- +
-       versickern (k);+
  
 + versickern(k);
 }  } 
 </code> </code>
Zeile 155: Zeile 184:
 <code java> <code java>
 public Knoten inListeSortieren() { public Knoten inListeSortieren() {
-    // Kann leere Halde nicht sortieren + // Kann leere Halde nicht sortieren 
-    if (wurzel == null) + if (wurzel == null) 
-        return null;+ return null;
  
-    // Max-Heap-Eigenschaft herstellen + // Max-Heap-Eigenschaft herstellen 
-    erzeugeHalde(wurzel);+ erzeugeHalde(wurzel);
  
-    // Wurzel entnehmen und zum Kopf unserer Liste machen + // Wurzel entnehmen und zum Kopf unserer Liste machen 
-    Knoten kopf = entferneMax(); + Knoten kopf = entferneMax(); 
-    Knoten schlepp = kopf;+ Knoten schlepp = kopf;
  
-    // Wiederholt Wurzel entnehmen und an Liste anhängen + // Wiederholt Wurzel entnehmen und an Liste anhängen 
-    while(wurzel != null) { + while(wurzel != null) { 
-        Knoten tmp = entferneMax(); + schlepp.rechts = entferneMax(); 
-        schlepp.rechts = tmp; + schlepp = schlepp.rechts; 
-        schlepp = tmp; + }
-    }+
  
-    // Kopf unserer Liste zurückgeben + // Kopf unserer Liste zurückgeben 
-    return kopf; + return kopf; 
-} +}
 </code> </code>
 +
 ==== Aufgabe 5 - ADT ==== ==== Aufgabe 5 - ADT ====
 +
 **a)** **a)**
-<code java> 
-double letzte(String lort){ 
-   Table next = this; 
  
-   while(next.ort != lort){ +Alle Instanzen von **Tabelle** stellen eine verkettete Liste dar. Der älteste, also letzte Eintrag, dieser Liste ist "leer" und hat keinen Payload und sein Feld "naechster" zeigt auf null.
-      next = next.naechster; +
-   } +
-    +
-   if (next.ort == lort){ +
-      return next.wert; +
-   } +
-   return 0; +
-}'' +
-</code> +
-b)+
  
-''ops''+<code java> 
 +double letzte(String lort) { 
 + // Sind wir im letzten Element "leer" der Liste? 
 + if(naechster == null) 
 + return 0;
  
-''   meth:              -> Double''+ if(ort.equals(lort)) 
 + return wert;
  
-''axs''+ return naechster.letzte(lort); 
 +} 
 +</code>
  
-''   meth(leer) = 0''+**b)**
  
-''   meth(in(tab, ort, wert)) = meth(tab)+wert''+Die Methode **meth** summiert offenbar den Wert jedes Elements in der List auf.
  
-c)+<code> 
 +OPS: 
 + meth: Tabelle -> Double
  
-''ops''+AXS: 
 + meth(leer) = 0 
 + meth(in(tab, ort, wert)) = wert + meth(tab) 
 +</code>
  
-''   filter:   Tabelle x String   -> Tabelle''+**c)**
  
-''axs''+<code> 
 +OPS: 
 + filter: Tabelle x String -> Tabelle
  
-''   filter (leer, ort) = leer'' +AXS: 
- + filter(leer, ort) = leer 
-''   filter (in (tab, ort, wert), ort2) = entweder a oder b:'' + filter(in(tab, ort, wert), ort2) = in(filter(tab, ort2), ort, wert) falls equals(ort, ort2) 
- + = filter(tab, ort2) sonst 
-''a) filter (tab, ort2) für ort != ort2'' +</code>
- +
-''b) in (filter (tab, ort2), ort2, wert) sonst''+
  
 ==== Aufgabe 6 - UML ==== ==== Aufgabe 6 - UML ====
 **a)** **a)**
-Komposition+ 
 +  * 2. Antwort: Komposition
  
 **b)** **b)**
 <code java> <code java>
 class Buch { class Buch {
-    protected static int medienZaehler; + protected static int medienZaehler; 
-    public String name; + public String name; 
-    private String autor; + private String autor; 
-    public void Buch(String name, String autor) { } + public Buch(String name, String autor) { } 
-    public static int gibMedienZaehler() { } + public static int gibMedienZaehler() { } 
-    public String gibAutor() { }+ public String gibAutor() { }
 } }
 </code> </code>
 +
 +Hinweis: \\
 +Konstruktoren haben keinen Rückgabetyp, auch nicht void.
 +
 **c)** **c)**
-TODO+ 
 +{{:pruefungen:bachelor:aud:02-12-uml1.png|:pruefungen:bachelor:aud:02-12-uml1.png}} 
 + 
 +Dia-Sourcefile für etwaige Korrekturen: {{:pruefungen:bachelor:aud:02-12-uml1.dia.txt|:pruefungen:bachelor:aud:02-12-uml1.dia.txt}}
  
 **d)** **d)**
-TODO+ 
 +{{:pruefungen:bachelor:aud:02-12-uml2.png|:pruefungen:bachelor:aud:02-12-uml2.png}} 
 + 
 +Dia-Sourcefile für etwaige Korrekturen: {{:pruefungen:bachelor:aud:02-12-uml2.dia.txt|:pruefungen:bachelor:aud:02-12-uml2.dia.txt}}
  
 ==== Aufgabe 7 - Formale Verifikation ==== ==== Aufgabe 7 - Formale Verifikation ====
-a)  + 
-<code java> +**a)** 
-rechts oben:  +<code> 
-ret = Ω_i && i <= n +LO: Falsch 
-//gruesse Gaku :)+ i = 1; ret = 1; n ≥ 1 
 + i < n 
 + Für n = 1 nicht erfüllt 
 + 
 +RO: Richtig 
 + i = 1; ret = 1; n ≥ 1 
 + ret = Ω_i ∧ i ≤ n 
 + Ω_1 = 1 ∧ 1 ≤ n 
 + Immer erfüllt! 
 + 
 +LU: Falsch 
 + i = 1; ret = 1; n ≥ 1 
 + ret = Ω_n 
 + Offensichtlich nicht für jedes n erfüllt 
 + 
 +RU: Falsch 
 + i = 1; ret = 1; n ≥ 1 
 + indIter(n) = O(n^2) 
 + Offensichtlich völliger Quatsch
 </code> </code>
  
-b)  +**b)** 
-<code java> +<code> 
-P => I+Zu zeigen: P => I
  
-wp (" ret = 1; i = 1; " , ret = Ω_i && i < = n ) +wp("ret = 1; i = 1;", ret = Ω_i ∧ i ≤ n) = 
-= wp (" ret = 1; " , ret = Ω_1 && 1 < = n ) +(1 = Ω_1 ∧ 1 ≤ n) = 
-= (ret = 1 && 1 < = n) +(1 = (1 * (2 - 1) * (2 + 1)) / 3 ∧ 1 ≤ n) = 
-=> True +(1 = 3 / 3 ∧ 1 ≤ n) = 
-//gruesse Gaku :)+(1 ≤ n) 
 + 
 +P => I =  
 +(n ≥ 1) => (1 ≤ n) = 
 +(true)
 </code> </code>
  
-c) +**c)**
-<code java> +
-I & nicht b => Q+
  
-[ ret = Ω_i && i <= n ]  & ( i >= n)  +<code> 
-= [ ret = Ω_i && i = n ] +Zu zeigen: {I ∧ ¬b} => wp(A, Q) 
-= [ ret = Ω_n ] +Anmerkung: A beschreibt das Programmstück nach der Schleife, aber vor der Nachbedingung. Hier ist A "leer", daher gilt: wp(A, Q) = Q 
-= Q + 
-Bei der Lösung bin ich mir aber nicht 100% sicher. Inhaltlich stimmt sie schon, aber ob das auch so gefragt war? +{I ∧ ¬b} = 
-//gruesse Gaku :)+(ret = Ω_i ∧ i ≤ n ∧ ¬(i < n)) = 
 +(ret = Ω_i ∧ i ≤ n ∧ i ≥ n) = 
 +(ret = Ω_i ∧ i = n) = 
 +(ret = Ω_n) 
 + 
 +{I ∧ ¬b} => wp(A, Q) = 
 +{I ∧ ¬b} => Q = 
 +(ret = Ω_n) => Q = 
 +(ret = Ω_n) => (ret = Ω_n) = 
 +(true)
 </code> </code>
  
-d) +Folgender Abschnitt ist ein korrekter Beweis für die **nicht in der Klausur gestellte** Fragestellung: \\ 
-<code java> +"Weisen Sie formal mittels wp-Kalkül nach, dass I eine gültige Schleifeninvariante ist." 
-'V = - i + n' +<code> 
-Da i steigt => monotonfallend! +Zu zeigen: {I ∧ b} => wp(A, I) 
-Da i immer < = n ist = > ungleich null! + 
-//gruesse Gaku :)+wp(A, I) = 
 +wp("i = i + 1; ret = ret + 4 * i * i - 4 * i + 1;", ret = Ω_i ∧ i ≤ n) = 
 +wp("i = i + 1;", ret + 4 * i * i - 4 * i + 1 = Ω_i ∧ i ≤ n) = 
 +(ret + 4 * (i + 1) * (i + 1) - 4 * (i + 1) + 1 = Ω_(i + 1) ∧ (i + 1) ≤ n) = 
 +(ret + 4 * (i + 1)^2 - 4 * (i + 1) + 1 = Ω_(i + 1) ∧ i ≤ n - 1) 
 + 
 +Nebenrechnung: 
 +Ω_(i + 1) = 
 +Σ{from 1 to i + 1} (2k - 1)^2 = 
 +Σ{from 1 to i} (2k - 1)^2 + 2*((i + 1) - 1)^2 
 + 
 +Nebenrechnung: 
 +(ret + 4 * (i + 1)^2 - 4 * (i + 1) + 1) = 
 +binomische Formel (über Substituierung von (i + 1) eventuell leichter zu sehen) 
 +(ret + (2*(i + 1) - 1)^2) 
 + 
 +Daraus ergibt sich: 
 += (ret + (2*(i + 1) - 1)^2 = Σ{from 1 to i} (2k - 1)^2 + 2*((i + 1) - 1)^2 ∧ i ≤ n - 1) =  
 +(ret = Σ{from 1 to i} (2k - 1)^2 ∧ i ≤ n - 1) 
 + 
 +Und nach einem Blick auf die Definition von Ω_i ergibt sich: 
 +Σ{from 1 to i} (2k - 1)^2 = Ω_i 
 + 
 +Damit erhalten wir nun: 
 += (ret = Ω_i ∧ i ≤ n - 1) 
 + 
 + 
 +{I ∧ b} => wp(A, I) = 
 +{ret = Ω_i ∧ i ≤ n ∧ i < n} => wp(A, I) = 
 +¬{ret = Ω_i ∧ i ≤ n} ∨ wp(A, I) = 
 +(ret ≠ Ω_i) ∨ (i > n) ∨ wp(A, I) = 
 +(ret ≠ Ω_i) ∨ (i > n) ∨ (ret = Ω_i ∧ i ≤ n - 1) 
 + 
 +Sind (ret ≠ Ω_i) und (i > n) beide nicht gültig, dann gilt offensichtlich: 
 +(ret = Ω_i) und (i ≤ n) 
 +Gilt (i ≤ n), dann gilt natürlich auch (i ≤ n - 1) 
 + 
 +Damit können wir schlussfolgern: 
 +{I ∧ b} => wp(A, I) = (true)
 </code> </code>
 +
 +**d)**
 +<code>
 +V = n - i
 +
 +i wird stetig inkrementiert -> (-i) ist damit monoton fallend
 +
 +i = 1, i ≤ n und n ≥ 1 -> n - i ≥ 0
 +</code>
 +
 +**e)**
 +
 +**Induktionsanfang:**
 +<code>
 +IA_1 (n = 1): 
 +Ω_1 = (1 * (2 - 1) * (2 + 1)) / 3 = 3 / 3 = 1
 +indRec(1) = 1
 +</code>
 +
 +**Induktionsschritt:**\\
 +**Induktionsvorraussetzung:**\\
 +<code>
 +IV_(n-1) (n-1):
 +indRec(n-1) = Ω_(n-1) gilt für ein n ≥ 1
 +</code>
 +
 +Aus dem Programmfragment ist zu entnehmen:
 +<code>
 +indRec(n) = 4*n*n - 4*n + 1 + indRec(n-1) =
 +</code>
 +
 +über die obigen Induktionsvoraussetzungen kommt man auf:
 +<code>
 += 4*n^2 - 4*n + 1 + Ω_(n-1) =
 += (2n - 1)^2 + Ω_(n-1) =
 += Ω_(n-1) + (2n - 1)^2 =
 += Σ{from 1 to i-1} (2k - 1)^2 + (2n - 1)^2 =
 += Σ{from 1 to i} (2k - 1)^2 =
 += Ω_(n)
 +</code>
 +
 +q.e.d.