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:loesungws11 [18.02.2013 15:45] Dawodopruefungen:bachelor:aud:loesungws11 [24.01.2019 21:56] (aktuell) LasagneAlForno
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 | 
-^ A | +^ A | 
-^ B | +^ B | 
-^ C | +^ C | 
-^ D | +^ D | 
-^ E | |+^ E | |
  
 ==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)== 
-10 11 12 13  +| | | | | | | | S | S | A | A | B | C | D | D | 
-^ 6 10 11 12 14 |+| | S | A | B | C | D | E | A | B | C | D | D | E | C | E | 
 +| Array-Indizes:10 11 12 13  
 +| Array-Werte: ^ 6 10 11 12 14 ^
  
 **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) {+  
 + // Variable für die Farbe der Nachbarn, zunächst WHITE (d.h. uninitialisiert) 
 + Color neighborColor = WHITE;
   
- // Ist der aktuelle Nachbarknoten WHITE, dann wurde er noch nicht besucht + // Gehe alle Nachbarknoten einmal durch 
- // -> Füge ihn der Queue hinzu + for(Node : neighbors) {
- if(n.color == WHITE) { +
- q.addLast(n);+
   
- // 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 118: Zeile 146:
  
 <code java> <code java>
-private void versickern(Knoten k) { +private static void versickern(Knoten k) { 
- Knoten groesser = null;+ Knoten groesser = null;
  
- if(links != null && rechts != null) { + if (k.links != null && k.rechts != null) { 
- groesser = (links.wert > rechts.wert) links rechts;+ if (k.links.wert > k.rechts.wert) 
 + groesser = k.links
 + } else { 
 + groesser = k.rechts; 
 + }
  
- } else if(links != null) { + } else if (k.links != null) { // hier ist es wichtig, ein "else if" statt einem if zu verwenden! 
- groesser = links;+ groesser = k.links;
  
- } else if(rechts != null) { + } else if (k.rechts != null) { 
- groesser = rechts;+ groesser = k.rechts; 
 + }
  
- } else + if (groesser == null) 
- return; + return; 
- }+ }
  
- if(k.wert > groesser.wert) + if (k.wert > groesser.wert) { 
- return;+ return; // fertig :) 
 + }
  
- if(groesser == null{ + vertausche(k, groesser); 
- return; + versickern(groesser)// normalerweise würde man versickern(k) rekursiv aufrufen, aber die vertausche-Methode tauscht laut Aufgabenstellung nicht die Knoten, sondern nur deren Werte!
- }+
  
- vertausche(k, groesser);         + }
- versickern(groesser); +
-}+
 </code> </code>
 **b)** **b)**
 +Nach dem Postorder-Prinzip:
 <code java> <code java>
-private void erzeugeHalde(Knoten k) { +private static void erzeugeHalde(Knoten k) { 
- if(k.left != null) + if (k.links != null) 
- erzeugeHalde(k.left);+ erzeugeHalde(k.links);
  
- if(k.right != null) + if (k.rechts != null) 
- erzeugeHalde(k.right);+ erzeugeHalde(k.rechts);
  
- versickern(k); + versickern(k); 
-+}
 </code> </code>
 **c)** **c)**
 <code java> <code java>
-public Knoten inListeSortieren() { + public static 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 +  
- erzeugeHalde(wurzel);+ // Max-Heap-Eigenschaft herstellen 
 + 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 
 + return kopf;
  }  }
- 
- // Kopf unserer Liste zurückgeben 
- return kopf; 
-} 
 </code> </code>
  
Zeile 186: Zeile 218:
  
 **a)** **a)**
 +
 +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.
 +
 <code java> <code java>
 double letzte(String lort) { double letzte(String lort) {
- if(ort.equals(lort)) + // Sind wir im letzten Element "leer" der Liste?
- return wert; +
  if(naechster == null)  if(naechster == null)
  return 0;  return 0;
 +
 + if(ort.equals(lort))
 + return wert;
  
  return naechster.letzte(lort);  return naechster.letzte(lort);
Zeile 199: Zeile 235:
  
 **b)** **b)**
 +
 +Die Methode **meth** summiert offenbar den Wert jedes Elements in der List auf.
 +
 <code> <code>
 OPS: OPS:
Zeile 212: Zeile 251:
 <code> <code>
 OPS: OPS:
- meth: Tabelle x String -> Tabelle+ filter: Tabelle x String -> Tabelle
  
 AXS: AXS:
  filter(leer, ort) = leer  filter(leer, ort) = leer
- filter(in(tab, ort, wert), ort2) = in(filter(tab, ort2), ort1, wert) falls equals(ort1, ort2) + filter(in(tab, ort, wert), ort2) = in(filter(tab, ort2), ort, wert) falls equals(ort, ort2) 
- = filter(tab, ort2) sonst+  = filter(tab, ort2) sonst
 </code> </code>
  
Zeile 279: Zeile 318:
  
 **b)** **b)**
-<code java>+<code>
 Zu zeigen: P => I Zu zeigen: P => I
  
Zeile 294: Zeile 333:
  
 **c)** **c)**
 +
 +<code>
 +Zu zeigen: {I ∧ ¬b} => wp(A, Q)
 +Anmerkung: A beschreibt das Programmstück nach der Schleife, aber vor der Nachbedingung. Hier ist A "leer", daher gilt: wp(A, Q) = Q
 +
 +{I ∧ ¬b} =
 +(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>
 +
 +Folgender Abschnitt ist ein korrekter Beweis für die **nicht in der Klausur gestellte** Fragestellung: \\
 +"Weisen Sie formal mittels wp-Kalkül nach, dass I eine gültige Schleifeninvariante ist."
 <code> <code>
 Zu zeigen: {I ∧ b} => wp(A, I) Zu zeigen: {I ∧ b} => wp(A, I)
Zeile 360: Zeile 419:
 <code> <code>
 IV_(n-1) (n-1): IV_(n-1) (n-1):
-indRec(n-1) = Ω_(n-1)+indRec(n-1) = Ω_(n-1) gilt für ein n ≥ 1
 </code> </code>
  
Zeile 371: Zeile 430:
 <code> <code>
 = 4*n^2 - 4*n + 1 + Ω_(n-1) = = 4*n^2 - 4*n + 1 + Ω_(n-1) =
-2(- 1)^2 + Ω_(n-1) = += (2n - 1)^2 + Ω_(n-1) = 
-= Ω_(n-1) + 2(- 1)^2 = += Ω_(n-1) + (2n - 1)^2 = 
-= Σ{from 1 to i-1} (2k - 1)^2 + 2(- 1)^2 =+= Σ{from 1 to i-1} (2k - 1)^2 + (2n - 1)^2 =
 = Σ{from 1 to i} (2k - 1)^2 = = Σ{from 1 to i} (2k - 1)^2 =
 = Ω_(n) = Ω_(n)
Zeile 380: Zeile 439:
 q.e.d. q.e.d.
  
 +oder
 +
 +{{:pruefungen:bachelor:aud:induction-1.png?400|}}