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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws11 [18.02.2013 14:09] – Dawodo | pruefungen:bachelor:aud:loesungws11 [16.03.2018 20:32] – Evren | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
===== Forendiskussionen ===== | ===== Forendiskussionen ===== | ||
- | FIXME - Bitte um Forenthreads erweitern! | + | * [[https:// |
===== 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, |
+ | \\ | ||
+ | Doch die Reihenfolge ist festgelegt: L-R-N (Links, Rechts, Mitte), siehe [[https:// | ||
**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)** | + | **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: | ||
{{: | {{: | ||
- | ==Als Reihung== | + | ==Als Reihung |
- | ^ 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: | ||
+ | | Array-Werte: | ||
**b)** | **b)** | ||
Zeile 61: | Zeile 75: | ||
<code java> | <code java> | ||
- | // Solange es noch unbesuchte Knoten gibt | + | boolean color(Node v) { |
- | while(!q.isEmpty()) { | + | LinkedList< |
- | // 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 | + | // Gehe alle Nachbarknoten |
- | // -> Füge ihn der Queue hinzu | + | for(Node n : neighbors) { |
- | if(n.color == WHITE) { | + | |
- | q.addLast(n); | + | |
- | // Ist der aktuelle | + | // 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 | + | |
- | if(neighborColor == WHITE) | + | // Ist der aktuelle |
- | neighborColor = GRAY; | + | // und ist entweder BLACK oder GRAY |
- | + | } else { | |
- | // Hat der aktuelle | + | // Ist die Variable für die Farbe der Nachbarn noch nicht gesetzt |
- | // betrachteten Nachbarknoten, | + | // (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 | ||
+ | // betrachteten Nachbarknoten, | ||
+ | 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, | ||
+ | // wurde erfolgreich gefärbt. | ||
+ | return true; | ||
</ | </ | ||
Zeile 110: | Zeile 133: | ||
| | | **gd.g(" | | | | **gd.g(" | ||
| | | 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: {{: | Programm zum selber Testen: {{: | ||
==== Aufgabe 4 - Sortieren ==== | ==== Aufgabe 4 - Sortieren ==== | ||
- | [[https:// | ||
**a)** | **a)** | ||
+ | |||
<code java> | <code java> | ||
private void versickern(Knoten k) { | private void versickern(Knoten k) { | ||
+ | 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){ | + | } else if(rechts != null) { |
- | if(k.links != null && k.links.wert < k.rechts.wert || k.links == null) { | + | groesser = rechts; |
- | groesser = k.rechts; | + | } |
- | } | + | |
- | | + | |
+ | if(groesser == null) { | ||
+ | return; | ||
+ | } | ||
- | | + | if(k.wert > groesser.wert) |
- | | + | return; |
- | } | + | |
- | + | ||
- | + | ||
- | if(groesser.wert <k.wert) return; | + | |
- | + | ||
- | vertausche (groesser, k); | + | |
- | + | ||
- | + | ||
- | versickern(groesser); | + | |
+ | vertausche(k, | ||
+ | versickern(groesser); | ||
} | } | ||
</ | </ | ||
**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.right != null) |
- | | + | erzeugeHalde(k.right); |
- | } | + | |
- | + | ||
- | if(k.right !=null){ | + | |
- | | + | |
- | } | + | |
- | + | ||
- | | + | |
+ | versickern(k); | ||
} | } | ||
</ | </ | ||
Zeile 164: | Zeile 186: | ||
<code java> | <code java> | ||
public Knoten inListeSortieren() { | public Knoten inListeSortieren() { | ||
- | | + | // Kann leere Halde nicht sortieren |
- | if (wurzel == null) | + | if (wurzel == null) |
- | return null; | + | return null; |
- | | + | // Max-Heap-Eigenschaft herstellen |
- | erzeugeHalde(wurzel); | + | erzeugeHalde(wurzel); |
- | | + | // 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 |
- | while(wurzel != null) { | + | while(wurzel != null) { |
- | | + | schlepp.rechts |
- | schlepp.rechts | + | schlepp = schlepp.rechts; |
- | | + | } |
- | } | + | |
- | | + | // Kopf unserer Liste zurückgeben |
- | return kopf; | + | return kopf; |
- | } | + | } |
</ | </ | ||
+ | |||
==== Aufgabe 5 - ADT ==== | ==== Aufgabe 5 - ADT ==== | ||
+ | |||
**a)** | **a)** | ||
- | <code java> | ||
- | double letzte(String lort){ | ||
- | Table next = this; | ||
- | | + | Alle Instanzen von **Tabelle** stellen eine verkettete Liste dar. Der älteste, also letzte Eintrag, dieser Liste ist " |
- | next = next.naechster; | + | |
- | } | + | |
- | + | ||
- | if (next.ort == lort){ | + | |
- | return next.wert; | + | |
- | } | + | |
- | | + | |
- | }'' | + | |
- | </ | + | |
- | b) | + | |
- | '' | + | <code java> |
+ | double letzte(String lort) { | ||
+ | // Sind wir im letzten Element " | ||
+ | if(naechster == null) | ||
+ | return 0; | ||
- | '' | + | if(ort.equals(lort)) |
+ | return wert; | ||
- | '' | + | return naechster.letzte(lort); |
+ | } | ||
+ | </ | ||
- | '' | + | **b)** |
- | '' | + | Die Methode **meth** summiert offenbar den Wert jedes Elements |
- | c) | + | < |
+ | OPS: | ||
+ | meth: Tabelle -> | ||
- | '' | + | AXS: |
+ | meth(leer) = 0 | ||
+ | meth(in(tab, | ||
+ | </ | ||
- | '' | + | **c)** |
- | '' | + | < |
+ | OPS: | ||
+ | filter: Tabelle x String -> | ||
- | '' | + | AXS: |
- | + | filter(leer, | |
- | '' | + | filter(in(tab, |
- | + | = filter(tab, ort2) sonst | |
- | '' | + | </ |
- | + | ||
- | '' | + | |
==== Aufgabe 6 - UML ==== | ==== Aufgabe 6 - UML ==== | ||
**a)** | **a)** | ||
- | Komposition | + | |
+ | * 2. Antwort: | ||
**b)** | **b)** | ||
<code java> | <code java> | ||
class Buch { | class Buch { | ||
- | | + | protected static int medienZaehler; |
- | public String name; | + | public String name; |
- | private String autor; | + | private String autor; |
- | public | + | public Buch(String name, String autor) { } |
- | public static int gibMedienZaehler() { } | + | public static int gibMedienZaehler() { } |
- | public String gibAutor() { } | + | public String gibAutor() { } |
} | } | ||
</ | </ | ||
+ | |||
+ | Hinweis: \\ | ||
+ | Konstruktoren haben keinen Rückgabetyp, | ||
+ | |||
**c)** | **c)** | ||
- | TODO | + | |
+ | {{: | ||
+ | |||
+ | Dia-Sourcefile für etwaige Korrekturen: | ||
**d)** | **d)** | ||
- | TODO | + | |
+ | {{: | ||
+ | |||
+ | Dia-Sourcefile für etwaige Korrekturen: | ||
==== Aufgabe 7 - Formale Verifikation ==== | ==== Aufgabe 7 - Formale Verifikation ==== | ||
- | a) | + | |
- | < | + | **a)** |
- | rechts oben: | + | < |
- | ret = Ω_i && | + | 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 | ||
</ | </ | ||
- | b) | + | **b)** |
- | < | + | < |
- | P => I | + | Zu zeigen: |
- | wp (" ret = 1; i = 1; " , ret = Ω_i && | + | wp(" |
- | = wp (" ret = 1; " , ret = Ω_1 && | + | (1 = Ω_1 ∧ 1 ≤ n) = |
- | = (ret = 1 && | + | (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) | ||
</ | </ | ||
- | c) | + | **c)** |
- | <code java> | + | |
- | I & nicht b => Q | + | |
- | [ ret = Ω_i && | + | < |
- | = [ ret = Ω_i && | + | 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 " |
- | = 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) | ||
</ | </ | ||
- | d) | + | Folgender Abschnitt ist ein korrekter Beweis für die **nicht in der Klausur gestellte** Fragestellung: |
- | < | + | " |
- | ' | + | < |
- | Da i steigt | + | 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) | ||
</ | </ | ||
+ | |||
+ | **d)** | ||
+ | < | ||
+ | V = n - i | ||
+ | |||
+ | i wird stetig inkrementiert -> (-i) ist damit monoton fallend | ||
+ | |||
+ | i = 1, i ≤ n und n ≥ 1 -> n - i ≥ 0 | ||
+ | </ | ||
+ | |||
+ | **e)** | ||
+ | |||
+ | **Induktionsanfang: | ||
+ | < | ||
+ | IA_1 (n = 1): | ||
+ | Ω_1 = (1 * (2 - 1) * (2 + 1)) / 3 = 3 / 3 = 1 | ||
+ | indRec(1) = 1 | ||
+ | </ | ||
+ | |||
+ | **Induktionsschritt: | ||
+ | **Induktionsvorraussetzung: | ||
+ | < | ||
+ | IV_(n-1) (n-1): | ||
+ | indRec(n-1) = Ω_(n-1) gilt für ein n ≥ 1 | ||
+ | </ | ||
+ | |||
+ | Aus dem Programmfragment ist zu entnehmen: | ||
+ | < | ||
+ | indRec(n) = 4*n*n - 4*n + 1 + indRec(n-1) = | ||
+ | </ | ||
+ | |||
+ | über die obigen Induktionsvoraussetzungen kommt man auf: | ||
+ | < | ||
+ | = 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) | ||
+ | </ | ||
+ | |||
+ | q.e.d. |