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 ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws08 [21.07.2012 18:31] – Aufgabe 4 hinzugefügt matze_ | pruefungen:bachelor:aud:loesungws08 [11.05.2019 10:23] – SpeedyGonzalez | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==forum== | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
Zeile 7: | Zeile 7: | ||
* [[https:// | * [[https:// | ||
- | ====Lösungsversuch==== | + | ===== Lösungsversuch |
- | ==Aufgabe 1 - Wissensfragen== | + | ==== Aufgabe 1 - Wissensfragen |
- | **a)** | + | **a)** |
- | **b)** 3 - eine Schleife korrekt ist | + | **b)** |
- | **c)** | + | **c)** |
- | **d)** | + | **d)** |
**e)** Bucketsort, Mergesort | **e)** Bucketsort, Mergesort | ||
Zeile 24: | Zeile 24: | ||
**g)** 4 - O(n² * log n) | **g)** 4 - O(n² * log n) | ||
- | **h)** O(n*(log n)²) | + | **h)** |
**i)** 1 - kontextsensitiven Grammatiken | **i)** 1 - kontextsensitiven Grammatiken | ||
- | ==Aufgabe 2 - Graphen== | + | ==== Aufgabe 2 - Graphen ==== |
**a)** | **a)** | ||
^ A ^ B ^ C ^ D ^ E ^ F ^ Prioritäts-Warteschlange^ | ^ A ^ B ^ C ^ D ^ E ^ F ^ Prioritäts-Warteschlange^ | ||
Zeile 40: | Zeile 41: | ||
**b)** | **b)** | ||
+ | Pfade von Knoten A nach ... | ||
- | * nach B: 4 | + | ^ ... ^ Kosten ^ Pfad ^ |
- | * nach C: 5 | + | ^ B | 4 | A -> B | |
- | * nach D: 6 | + | ^ C | 5 | A -> C | |
- | * nach E: 5 | + | ^ D | 6 | A -> B -> E -> D | |
- | * nach F: 10 | + | ^ E | 5 | A -> B -> E | |
+ | ^ F | 10 | A -> B -> E -> F | | ||
+ | |||
+ | ==== Aufgabe 3 - Java ==== | ||
- | ==Aufgabe 3 - Java== | ||
**a)** | **a)** | ||
- | Java Datei zum selber testen: {{: | ||
^Zeile^Bildschirmausgabe bzw. keine Ausgabe^ | ^Zeile^Bildschirmausgabe bzw. keine Ausgabe^ | ||
^23 | BA | | ^23 | BA | | ||
Zeile 57: | Zeile 60: | ||
^38 | CC | | ^38 | CC | | ||
^39 | AA | | ^39 | AA | | ||
+ | |||
+ | Java-Datei zum selbst testen: \\ | ||
+ | {{: | ||
**b)** | **b)** | ||
^Zeile^Begrundung^ | ^Zeile^Begrundung^ | ||
- | ^7 |Compiler: | + | ^7 |Compiler: |
- | ^19| Compiler: | + | ^19| Compiler: |
- | ^34| Compiler: | + | ^21| Compiler: |
- | ^40| Compiler: | + | ^34| Compiler: Statischer Zugriff auf Instanzvariablen |
- | ^44| Compiler: g ist eine private-Methode. Darauf kann man nicht von i aus zugreifen| | + | ^40| Compiler: |
+ | ^44| Compiler: | ||
- | ==Aufgabe 4 - ADT== | + | Java-Datei zum selbst testen: \\ |
+ | {{: | ||
+ | |||
+ | ==== Aufgabe 4 - ADT ==== | ||
**a)** | **a)** | ||
- | A4: contains(x, create) = false | ||
< | < | ||
- | A5: contains(x, append(y,l))= 1+contains(x,l) //falls x=y | + | contains(x, create) = false |
- | contains(x,l) // | + | contains(x, append(x, L)) = true |
+ | contains(x, | ||
</ | </ | ||
+ | |||
**b)** | **b)** | ||
- | A -> D -> create | + | A -> D |
**c)** | **c)** | ||
- | //VORSICHT! nicht wirklich sicher! // | + | < |
+ | append(head(append(D, | ||
+ | A1 | ||
+ | = append(head(prepend(D, | ||
+ | A1 | ||
+ | = append(head(prepend(D, | ||
+ | A3 | ||
+ | = append(D, prepend(A, create)) = | ||
+ | A2 | ||
+ | = prepend(A, append(D, create)) = | ||
+ | A1 | ||
+ | = prepend(A, prepend(D, create)) | ||
+ | </code> | ||
- | A1: append(head(append(D, | + | ==== Aufgabe 5 - Pseudo-Zufallszahlen ==== |
+ | **a)** | ||
+ | <code java> | ||
+ | public static int f(int n) { | ||
+ | if (n < 3) | ||
+ | return n + 1; | ||
- | A1: append(head(prepend(D, create), prepend(A, create)) | + | return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100); |
+ | } | ||
+ | </ | ||
- | A3: append(D, prepend(A, create) | + | **b)** |
- | A2: prepend(A, append(D, create) | + | **Vorüberlegungen:**\\ |
- | A1: prepend(A, prepend(D, create) | + | <code java> |
+ | public static int f(int n) { | ||
+ | return lin(1, 2, 3, n); | ||
+ | } | ||
+ | private static int lin(int a, int b, int c, int steps) { ... | ||
+ | </ | ||
+ | Die Basisfälle der Funktion sind für n < 3 gegeben: \\ | ||
+ | f(0) = 1 \\ | ||
+ | f(1) = 2 \\ | ||
+ | f(2) = 3 \\ | ||
- | ==Aufgabe 7 - Heap== | + | Aus dem gegebenen Aufruf (mit 1, |
+ | a = 1 = f(0) | ||
+ | b = 2 = f(1) --> | ||
+ | c = 3 = f(2) --> | ||
- | a) Für jeden Knoten außer | + | Das Wichtige an dieser Aufgabe ist sich bewusst zu machen, wie die Werte im angegebenem Aufruf, mit den Basisfällen bzw. f(n-3), f(n-2), f(n-1) in der angegebenen Formel korrespondieren. Das Ziel ist ja diese Werte der Formel in Java-Code auszudrücken. |
- | b) | + | Somit wissen wir: \\ |
+ | lin(a, | ||
+ | |||
+ | Wir starten also am Basisfall n < 3 (=> Bottom-Up), weshalb nur noch der " | ||
+ | |||
+ | **Nächster " | ||
+ | |||
+ | lin(f(n - 2), f(n - 1), f(n), steps - 1) **(*)** | ||
+ | |||
+ | f(n - 2) und f(n - 1) sind bereits berechnet und müssen nur nach links geschoben werden.\\ | ||
+ | f(n) berechnet sich wie in Aufgabe a), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c: | ||
+ | |||
+ | f(n) = 1 + (((c - b) * a) % 100) **(* *)** | ||
+ | |||
+ | **(* *)** in **(*)** eingesetzt ergibt: | ||
+ | |||
+ | lin(b, c, 1 + (((c - b) * a) % 100), steps - 1) | ||
+ | |||
+ | <code java> | ||
+ | public static int f(int n) { | ||
+ | return lin(1, 2, 3, n); | ||
+ | } | ||
+ | |||
+ | private static int lin(int a, int b, int c, int steps) { | ||
+ | if (steps == 0) | ||
+ | return a; | ||
+ | |||
+ | return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **Warum steht das Ergebnis gerade in a?** | ||
+ | |||
+ | Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift: | ||
+ | f(0) = 1 \\ | ||
+ | f(0) = lin(1, 2, 3, 0) \\ | ||
+ | Das Ergebnis steht in Variable a. | ||
+ | |||
+ | |||
+ | **c)** | ||
+ | <code java> | ||
+ | public static int f(int n) { | ||
+ | int a = 1; | ||
+ | int b = 2; | ||
+ | int c = 3; | ||
+ | |||
+ | while(n > 0) { | ||
+ | int fn = 1 + (((c - b) * a) % 100); | ||
+ | a = b; | ||
+ | b = c; | ||
+ | c = fn; | ||
+ | n--; | ||
+ | } | ||
+ | |||
+ | return a; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Aufgabe 6 - Suchbäume ==== | ||
+ | |||
+ | **a)** | ||
< | < | ||
- | 13 | + | 27 |
- | | + | |
- | 2 5 8 | + | |
+ | / | ||
+ | 7 | ||
+ | \ | ||
+ | 81 | ||
</ | </ | ||
- | c) | + | |
+ | **b)** | ||
+ | \\ | ||
+ | Für die maximale Höhe müssen die Werte in auf- oder absteigend sortiert in den Baum eingefügt werden. \\ | ||
+ | Schlüsselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81 \\ | ||
+ | Kosten: O(n) | ||
+ | |||
+ | Für einen perfekt balancierten Baum fügt man immer das mittlere Element der sortierten Reihe ein, teil die Reihe in zwei Restreihen auf und fährt mit diesen genauso fort. \\ | ||
+ | Schlüsselfolge für minimale Höhe: 32, 23, 7, 27, 64, 42, 81 \\ | ||
+ | Kosten: O(log n) | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | Verwendete Definitionen: | ||
+ | * Höhe eines Blatts: 0 | ||
+ | * Daraus folgt die Höhe des leeren Baums: -1 | ||
+ | * Balancefaktor: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **d)** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * Rotation an Knoten: 64 | ||
+ | |||
+ | * **Einfachrotation** gegen der Uhrzeigersinn, | ||
+ | |||
+ | **e)** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | ==== Aufgabe 7 - Heap ==== | ||
+ | |||
+ | **a)** | ||
+ | Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein. | ||
+ | |||
+ | **b)** | ||
+ | < | ||
+ | 13 | ||
+ | / \ | ||
+ | 6 9 | ||
+ | / | ||
+ | | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
<code java> | <code java> | ||
public int leftChildIndex (int parentIndex) { | public int leftChildIndex (int parentIndex) { | ||
- | return parentIndex*2+1; | + | return parentIndex * 2 + 1; |
} | } | ||
</ | </ | ||
- | d) | + | **d)** |
<code java> | <code java> | ||
public int parentIndex (int childIndex) { | public int parentIndex (int childIndex) { | ||
- | return (childIndex-1)/ | + | return |
} | } | ||
</ | </ | ||
- | e) | + | **e)** |
<code java> | <code java> | ||
//keine garantie! | //keine garantie! | ||
public void add (int priority) { | public void add (int priority) { | ||
+ | array[n] = priority; | ||
+ | int p = parentIndex(n); | ||
- | array[n] = priority; | + | while(p >= 0 && array[p] < array[n]) { |
+ | // swap ohne temporäre Variable, da immer nur priority nach oben geswappt wird | ||
+ | array[n] = array[p]; | ||
+ | array[p] = priority; | ||
- | | + | n = p; |
+ | p = parentIndex(n); | ||
+ | } | ||
- | int i = n; | + | n++; |
- | int j = parentIndex(n); | + | } |
+ | </ | ||
- | if( priority > array[j] | + | **f)** O(log n) |
- | array[i] = array[j]; | + | |
- | array[j] = priority; | + | |
- | } else { | + | |
- | | + | |
- | } | + | |
- | } | + | |
- | n++; | + | |
- | } | + | ==== Aufgabe 8 - wp-Kalkül ==== |
+ | |||
+ | **a)** | ||
+ | wp("if (a > b - 5) {a = b++ - 4;}", a = b - 5) = | ||
+ | [(a > b - 5) ∧ wp("a = b++ - 4;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] = | ||
+ | [(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] = | ||
+ | [(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ (a = b - 5) = | ||
+ | [(a > b - 5) ∧ wp("a = b - 4;", a = b + 1 - 5)] ∨ (a = b - 5) = | ||
+ | [(a > b - 5) ∧ (b - 4 = b + 1 - 5)] ∨ (a = b - 5) = | ||
+ | [(a > b - 5) ∧ (b - 4 = b - 4)] ∨ (a = b - 5) = | ||
+ | [(a > b - 5) ∧ true] ∨ (a = b - 5) = | ||
+ | (a > b - 5) ∨ (a = b - 5) = | ||
+ | (a ≥ b - 5) | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | i) | ||
+ | Nummer 3: (x mod 2) = (i mod 2) ∧ y ≥ 0 | ||
+ | |||
+ | ii) | ||
+ | < | ||
+ | Zu zeigen: P => wp(A,I) | ||
+ | |||
+ | Nachweis: | ||
+ | wp(A,I) = | ||
+ | wp("x = i; y = 0; r = false;", | ||
+ | wp("x = i; y = 0;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = | ||
+ | wp("x = i;", (x mod 2) = (i mod 2) ∧ 0 ≥ 0) = | ||
+ | (i mod 2) = (i mod 2) ∧ 0 ≥ 0 = | ||
+ | true ∧ true = | ||
+ | true | ||
+ | |||
+ | P => wp(A,I) = | ||
+ | ((i ≥ 0) => true) = | ||
+ | (¬(i ≥ 0) ∨ true) = | ||
+ | true | ||
</ | </ | ||
- | f) O(log n) | + | iii) |
+ | < | ||
+ | Zu zeigen: {I ∧ b} => wp(A,I) | ||
+ | Nachweis: | ||
+ | wp(A,I) = | ||
+ | wp("x = x - 2; y = y + 1;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = | ||
+ | wp("x = x - 2;", (x mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = | ||
+ | (x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0 | ||
- | Aufgabe 8 (wp) | + | {I ∧ b} => wp(A,I) = |
+ | {(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} => ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = | ||
+ | ¬{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = | ||
+ | (x mod 2) != (i mod 2) ∨ (y < 0) ∨ (x ≤ 1) ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = | ||
- | a) a > b-5 && | + | (y + 1 ≥ 0) gilt immer, da y vor der Schleife immer 0 ist, und in der Schleife immer wieder inkrementiert wird. |
+ | (y < 0) ist aus selbigem Grund immer falsch. | ||
+ | |||
+ | (x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2) | ||
+ | |||
+ | Da das Axiom "a mod 2 = (a - 2) mod 2" für a ≥ 2 gilt: | ||
+ | aus ¬(x ≤ 1) | ||
+ | und daraus über das Axiom, dass | ||
+ | (x - 2 mod 2) = (i mod 2) = true | ||
+ | |||
+ | Das heißt: | ||
+ | (x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2) = | ||
+ | true | ||
+ | </ |