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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws11 [18.02.2013 15:38] – Dawodopruefungen:bachelor:aud:loesungws11 [18.03.2018 19:33] – 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 129: Zeile 157:
  } else if(rechts != null) {  } else if(rechts != null) {
  groesser = rechts;  groesser = rechts;
 + }
  
- } else {+ if(groesser == null) {
  return;  return;
  }  }
Zeile 136: Zeile 165:
  if(k.wert > groesser.wert)  if(k.wert > groesser.wert)
  return;  return;
- 
- if(groesser == null) { 
- return; 
- } 
  
  vertausche(k, groesser);          vertausche(k, groesser);        
Zeile 146: Zeile 171:
 </code> </code>
 **b)** **b)**
 +Nach dem Postorder-Prinzip:
 <code java> <code java>
 private void erzeugeHalde(Knoten k) { private void erzeugeHalde(Knoten k) {
Zeile 173: Zeile 199:
  // 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;+
  }  }
  
Zeile 186: Zeile 211:
  
 **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 228:
  
 **b)** **b)**
 +
 +Die Methode **meth** summiert offenbar den Wert jedes Elements in der List auf.
 +
 <code> <code>
 OPS: OPS:
Zeile 212: Zeile 244:
 <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 311:
  
 **b)** **b)**
-<code java>+<code>
 Zu zeigen: P => I Zu zeigen: P => I
  
 wp("ret = 1; i = 1;", ret = Ω_i ∧ i ≤ n) = wp("ret = 1; i = 1;", ret = Ω_i ∧ i ≤ n) =
-(1= Ω_1 ∧ 1 ≤ n) = +(1 = Ω_1 ∧ 1 ≤ n) = 
-(1= (1 * (2 - 1) * (2 + 1) / (3) ∧ 1 ≤ n) = +(1 = (1 * (2 - 1) * (2 + 1)) / 3 ∧ 1 ≤ n) = 
-(1= 3 / 3 ∧ 1 ≤ n) =+(1 = 3 / 3 ∧ 1 ≤ n) =
 (1 ≤ n) (1 ≤ n)
  
Zeile 294: Zeile 326:
  
 **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 338: Zeile 390:
 </code> </code>
  
-d)+**d)**
 <code> <code>
 V = n - i V = n - i
Zeile 347: Zeile 399:
 </code> </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.
  
 +oder
  
 +{{:pruefungen:bachelor:aud:induction-1.png?400|}}