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 14:16] – Dawodopruefungen:bachelor:aud:loesungws11 [16.03.2018 20:32] – Evren
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 29: Zeile 41:
 ==Adjazenzmatrix== ==Adjazenzmatrix==
 ^  ^ S ^ A ^ B ^ C ^ D ^ E ^ ^  ^ S ^ A ^ B ^ C ^ D ^ E ^
-^ S | - | + | + | - | - | - | +^ S | 0 | 1 | 1 | 0 | 0 | 0 | 
-^ A | - | - | - | + | + | - | +^ A | 0 | 0 | 0 | 1 | 1 | 0 | 
-^ B | - | - | - | - | + | - | +^ B | 0 | 0 | 0 | 0 | 1 | 0 | 
-^ C | - | - | - | - | - | + | +^ C | 0 | 0 | 0 | 0 | 0 | 1 | 
-^ D | - | - | - | + | - | + | +^ D | 0 | 0 | 0 | 1 | 0 | 1 | 
-^ E | - | - | - | - | - | - |+^ E | 0 | 0 | 0 | 0 | 0 | 0 |
  
 ==Graphische Darstellung== ==Graphische Darstellung==
Zeile 40: Zeile 52:
 {{:pruefungen:bachelor:aud:02-12-graph.png|:pruefungen:bachelor:aud:02-12-graph.png}} {{:pruefungen:bachelor:aud:02-12-graph.png|:pruefungen:bachelor:aud:02-12-graph.png}}
  
-==Als Reihung== +==Als Reihung (eingebettet in Array; auch Adjazenzfeld genannt)== 
-^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ 13 ^  +| | | | | | | | S | S | A | A | B | C | D | D | 
-^ 6 | 8 | 10 | 11 | 12 | 14 | 1 | 2 | 3 | 4 | 4 | 5 | 3 | 5 |+| | S | A | B | C | D | E | A | B | C | D | D | E | C | E | 
 +| Array-Indizes: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |  
 +| Array-Werte: ^ 6 ^ 8 ^ 10 ^ 11 ^ 12 ^ 14 ^ 1 ^ 2 ^ 3 ^ 4 ^ 4 ^ 5 ^ 3 ^ 5 ^
  
 **b)** **b)**
Zeile 61: Zeile 75:
  
 <code java> <code java>
-// Solange es noch unbesuchte Knoten gibt +boolean color(Node v) { 
-while(!q.isEmpty()) { + LinkedList<Node> q = new LinkedList<Node>(); 
- // Aktuellen Knoten aus der Queue entnehmen: + v.color = BLACK; 
- // Dieser Knoten ist noch WHITE und soll nun korrekt gefärbt werden + q.addLast(v); 
- Node current = q.removeFirst(); + 
-  + // Solange es noch unbesuchte Knoten gibt 
- // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) + while(!q.isEmpty()) { 
- Color neighborColor = WHITE; + // Aktuellen Knoten aus der Queue entnehmen: 
-  + // Dieser Knoten ist noch WHITE und soll nun korrekt gefärbt werden 
- // Gehe alle Nachbarknoten einmal durch + Node current = q.removeFirst();
- for(Node n : neighbors) {+
   
- // Ist der aktuelle Nachbarknoten WHITE, dann wurde er noch nicht besucht + // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) 
- // -> Füge ihn der Queue hinzu + Color neighborColor = WHITE; 
- if(n.color == WHITE) { +  
- q.addLast(n);+ // Gehe alle Nachbarknoten einmal durch 
 + for(Node n : neighbors) {
   
- // Ist der aktuelle Knoten nicht WHITE, dann wurde er schon besucht + // Ist der aktuelle Nachbar WHITE, dann wurde er noch nicht besucht 
- // und ist entweder BLACK oder GRAY + // -> Füge ihn der Queue hinzu 
- } else { + if(n.color == WHITE) { 
- // Ist die Variable für die Farbe der Nachbarn noch nicht + q.addLast(n); 
- // gesetzt (d.h. WHITE), dann initialisiere sie +  
- if(neighborColor == WHITE) + // Ist der aktuelle Nachbar nicht WHITE, dann wurde er schon besucht 
- neighborColor = GRAY; + // und ist entweder BLACK oder GRAY 
- + } else { 
- // Hat der aktuelle Knoten eine andere Farbe, als die bisher + // Ist die Variable für die Farbe der Nachbarn noch nicht gesetzt 
- // betrachteten Nachbarknoten, dann ist der Graph nicht färbbar + // (d.h. WHITE), dann initialisiere sie anhand des aktuellen Nachbarn 
- if(n.color != neighborColor) + if(neighborColor == WHITE) 
- return false;+ 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; 
 + }
  }  }
- +
  // Färbe den Knoten korrekt ein und markiere ihn so als besucht  // Färbe den Knoten korrekt ein und markiere ihn so als besucht
  // Die Farbe muss das Gegenteil der Farbe der Nachbarn sein!  // Die Farbe muss das Gegenteil der Farbe der Nachbarn sein!
Zeile 97: Zeile 117:
  current.color = (neighborColor == BLACK) ? GRAY : BLACK;  current.color = (neighborColor == BLACK) ? GRAY : BLACK;
  }  }
-}+ 
 +// Die Schlange ist leer, alle Knoten wurden abgearbeitet, der Graph 
 +// wurde erfolgreich gefärbt. 
 +return true;
 </code> </code>
  
Zeile 110: Zeile 133:
 | | | **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}}
Zeile 121: Zeile 149:
  Knoten groesser = null;  Knoten groesser = null;
  
- if(links == null && rechts == null) + if(links != null && rechts != null) {
- return; +
- +
- if(links != null && rechts != null)+
  groesser = (links.wert > rechts.wert) ? links : rechts;  groesser = (links.wert > rechts.wert) ? links : rechts;
  
- if(links != null) {+ } else if(links != null) {
  groesser = links;  groesser = links;
- } else {+ 
 + } else if(rechts != null) {
  groesser = rechts;  groesser = rechts;
  }  }
- 
- if(k.wert > groesser.wert) 
- return; 
  
  if(groesser == null) {  if(groesser == null) {
  return;  return;
  }  }
 +
 + if(k.wert > groesser.wert)
 + return;
  
  vertausche(k, groesser);          vertausche(k, groesser);        
Zeile 145: Zeile 171:
 </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 163: Zeile 186:
 <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) = 
 +(1 = Ω_1 ∧ 1 ≤ n) = 
 +(1 = (1 * (2 - 1) * (2 + 1)) / 3 ∧ 1 ≤ n) = 
 +(1 = 3 / 3 ∧ 1 ≤ n) = 
 +(1 ≤ n)
  
-wp (" ret = 1; i = 1; " , ret = Ω_i && i < = n ) +P => I =  
-= wp (" ret = 1; " , ret = Ω_1 && 1 < = n ) +(n ≥ 1) => (1 ≤ n) = 
-= (ret = 1 && 1 < = n) +(true)
-=> True +
-//gruesse Gaku :)+
 </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.