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

--- pruefungen:bachelor:aud:loesungws07 [14.02.2013 20:41] – Dawodo
+++ pruefungen:bachelor:aud:loesungws07 [25.09.2013 14:46] – elli
@@ Zeile 1: / Zeile 1: @@
-==forum==
+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7567-Frage-Klausur-21-Februar-2008]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7104-WP-kalkuel-21-02-2008]]
@@ Zeile 10: / Zeile 10: @@
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8877-Klausur-21-2-2008-A10-d-e]]
-====Lösungsversuch====
+===== Lösungsversuch =====
-===Aufgabe 1 - Binärsuche===
+==== Aufgabe 1 - Binärsuche ====
 **a)** O(n)
@@ Zeile 57: / Zeile 57: @@
 **c)** O(log n)
-===Aufgabe 2 - Graphen===
+==== Aufgabe 2 - Graphen ====
 **a)**
   * **Ja**
@@ Zeile 97: / Zeile 97: @@
 BD, BC, DG, BA, FI, GE, GI, FH
-===Aufgabe 3 - Java===
+==== Aufgabe 3 - Java ====
 **a)**
 Java Datei zum Ausprobieren: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}}
 ^ Zeile ^ Fehler bzw. Ausgabe ^
-^ 32 | 5 |
+^ 32 | 6 |
 ^ 33 | 13 |
 ^ 34 | 6 |
@@ Zeile 120: / Zeile 120: @@
 ^ 12 | Variable "i" hier nicht deklariert |
 ^ 14 | Zuweisung ("=") statt Vergleich ("==") für booleschen Ausdruck |
-^ 16 | fehlende "}" am Ende der if |
+^ 15 | überzähliges "{" am Ende der if-Bedingung |
 **c)**
 Nein, eine Instanziierung von abstrakten Klassen ist nicht möglich.
-===Aufgabe 5 - ADT===
+==== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ====
+(nicht mehr Stoff aktueller Semester)
+==== Aufgabe 5 - ADT ====
 **a)**
   * number
@@ Zeile 133: / Zeile 137: @@
   * commutate
-//Hinweis:// Konstruktoren sind Operationen, die Datenobjekte des Typs erzeugen.
+//Hinweis:// Konstruktoren sind alle Operationen, die Datenobjekte des Typs erzeugen.
 **b)**
@@ Zeile 149: / Zeile 153: @@
   binop(left(commutate(binop(4,+,7))),*,right(binop(binop(1,-,1),+,binop(3,*,4)))) =
-  commutate
+  //commutate//
   = binop(left(binop(7,+,4)),*,right(binop(binop(1,-,1),+,binop(3,*,4)))) =
-  right
+  //right//
   = binop(left(binop(7,+,4)),*,binop(3,*,4)) =
-  left
+  //left//
   = binop(7,*,binop(3,*,4))
 **e)**
-<code>
+<code java>
 double left = left.evaluate();
 double right = right.evaluate();
@@ Zeile 169: / Zeile 173: @@
 </code>
-=== Aufgabe 6 - Rucksackproblem ===
+==== Aufgabe 6 - Rucksackproblem ====
 **a)**
 ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^
-^ 1 |  -  |[+] | /  |  / |  /  | /  |  / |  /  |  /  |  /  |   /   |  /  |  /  |
+^ 1 |  -  | [+] | /  |  / |  /  | /  |  / |  /  |  /  |  /  |   /   |  /  |  /  |
-^ 3 |  -  |  -  | /  | + |[+] | /  |  / |  /  |  /  |  /  |   /   |  /  |  /  |
+^ 3 |  -  |  [-]  | /  | + | + | /  |  / |  /  |  /  |  /  |   /   |  /  |  /  |
-^ 4 |  -  |  -  | /  |  - |  -  | + |  / | +  | +  |  /  |   /   |  /  |  /  |
+^ 4 |  -  |  -  | /  |  - |  -  | [+] |  / | +  | +  |  /  |   /   |  /  |  /  |
-^ 7 |  -  |  -  | /  |  - |  -  |  - |  / | [-] |  -  |  /  |  +   |  + |  + |
+^ 7 |  -  |  -  | /  |  - |  -  |  - |  / | - |  -  |  /  |  +   |  + |  [+] |
-^ 8 |  -  |  -  | /  |  - |  -  |  - |  / |  -  |  -  |  + |   -   |  -  |  -  |
+^ 8 |  -  |  -  | /  |  - |  -  |  - |  / |  -  |  -  |  + |   -   |  -  |  [-]  |
+**b)** \\
+Gesucht: Lösung für Rucksack der Größe 12 \\
+Elemente mit den Größen 1, 4, 7 (Pfad mit eckigen Klammern in der Tabelle aus a) markiert) \\
+  Algorithmus:
+  P(5, 12) -> k_5 = 8 gehört nicht rein -> P(4, 12)
+  P(4, 12) -> k_4 = 7 gehört rein -> P(3, 12 - 7)
+  P(3, 5) -> k_3 = 4 gehört rein -> P(2, 5 - 4)
+  P(2, 1) -> k_2 = 3 gehört nicht rein -> P(1, 1)
+  P(1, 1) -> k_1 = 1 gehört rein -> Rucksack vollständig gefüllt
+**c)**
+<code java>
+for(int i = 1; i < n; i++) {			// Zeilen
+	for(int j = 0; j <= m; j++) {		// Spalten
+		// Fall P(n - 1, K): Gibt es in der Zelle direkt darüber eine Lösung,
+		// dann ist P(n, K) = P(n - 1, K)
+		// Das aktuelle Elemente gehört somit nicht zur Lösung -> OHNE
+		if(tab[i - 1][j] != UNMOEGLICH) {
+			tab[i][j] = OHNE;
+		// Fall P(n - 1, K - k_n): Gibt es in der Zeile darüber, nach links versetzt
+		// eine Lösung (Achtung: ArrayIndexOutOfBoundsException), dann ist
+		// P(n, K) = P(n - 1, K) + k_n
+		// Das aktuelle element gehört somit zur Lösung -> MIT
+		} else if(elements[i] <= j && tab[i - 1][j - elements[i]] != UNMOEGLICH) {
+			tab[i][j] = MIT;
+		}
+	}
+}
+</code>
+Vollständiges Programm: \\
+{{:pruefungen:bachelor:aud:rucksack.java.txt|:pruefungen:bachelor:aud:rucksack.java.txt}}
+**d)**
+  * **Ja**
+  * **Ja**
+  * **Ja**, durch sukzessives Ausprobieren für Kapazitäten < m
+  * **Nein**, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu
+==== Aufgabe 7 - Binäre Bäume ====
+**a)**
+Der Binärbaum muss eine totale Ordnung aufweisen:\\
+Alle Knoten im linken Teilbaum müssen einen echt kleineren, alle im rechten Teilbaum einen echt größeren Wert als der aktuelle Knoten haben.
 **b)**
-,4,7
+<code java>
-In Tabelle von a) mittels [] eingekreist.
+public class BB {
+	...
+	public void einfuegen(int schluessel) {
+		if(this.schluessel == schluessel)
+			return;
+		if(schluessel < this.schluessel) {
+			if(left != null) {
+				left.einfuegen(schluessel);
+			} else {
+				left = new BB(schluessel);
+			}
+		} else {
+			if(right != null) {
+				right.einfuegen(schluessel);
+			} else {
+				right = new BB(schluessel);
+			}
+		}
+	}
+}
+</code>
 **c)**
 <code java>
-for(int i = 1; i < n; i++) {            // Zeilen
+public class BB {
-    for(int j = 0; j < m + 1; j++) {    // Spalten
+	...
-        if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht
-            tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben.
+	public int maximum() {
-            if(j + k[i+1] <= m)
+		if(right != null)
-                tab[i+1][j+k[i+1]] = MIT;
+			return right.maximum();
-        }
-    }
+		return schluessel;
+	}
 }
 </code>
 **d)**
-//unsicher!
+Der Wert eines Knotes in einem Max-Heap muss größer sein als der seiner Kinder.
-  * nein
-  * ja
+**e)**
-  * nein
+<code java>
-  * ja
+public class Heap {
+	...
+	public int maximum() {
+		return schluessel;
+	}
+}
+</code>
+**f)**
+Suchbaum: \\
+{{:pruefungen:bachelor:aud:02-2008-7f1.png|:pruefungen:bachelor:aud:02-2008-7f1.png}}
+\\
+Max-Heap: \\
+{{:pruefungen:bachelor:aud:02-2008-7f2.png|:pruefungen:bachelor:aud:02-2008-7f2.png}}
+**g)**
+  * **Nein**
+  * **Nein**
+  * **Ja**, wenn es sich um einen Min-Heap handelt
+  * **Nein**, man muss eines Tiefensuche vewenden
+==== Aufgabe 8 - Sortieren ====
+**a)**
+| | | | | | | ∨ |
+| [35] | 70 | 42 | 11 | 99 | 1 | 20 |
+| ∧ | | | | | | |
+| | | | | | | ∨ |
+| [35] | 70 | 42 | 11 | 99 | 1 | 20 |
+| | ∧ | | | | | |
+| | | | | | | ∨ |
+| [35] | 20 | 42 | 11 | 99 | 1 | 70 |
+| | ∧ | | | | | |
+| | | | | | ∨ | |
+| [35] | 20 | 42 | 11 | 99 | 1 | 70 |
+| | ∧ | | | | | |
+| | | | | | ∨ | |
+| [35] | 20 | 42 | 11 | 99 | 1 | 70 |
+| | | ∧ | | | | |
+| | | | | | ∨ | |
+| [35] | 20 | 1 | 11 | 99 | 42 | 70 |
+| | | ∧ | | | | |
+| | | | | ∨ | | |
+| [35] | 20 | 1 | 11 | 99 | 42 | 70 |
+| | | ∧ | | | | |
+| | | | ∨ | | | |
+| [35] | 20 | 1 | 11 | 99 | 42 | 70 |
+| | | ∧ | | | | |
+| | | | ∨ | | | |
+| [35] | 20 | 1 | 11 | 99 | 42 | 70 |
+| | | | ∧ | | | |
+| | | | ∨ | | | |
+| 11 | 20 | 1 | 35 | 99 | 42 | 70 |
+| | | | ∧ | | | |
+Linkes Teil-Array:
+| | | ∨ |
+| [11] | 20 | 1 |
+| ∧ | | |
+| | | ∨ |
+| [11] | 20 | 1 |
+| | ∧ | |
+| | | ∨ |
+| [11] | 1 | 20 |
+| | ∧ | |
+| | ∨ | |
+| [11] | 1 | 20 |
+| | ∧ | |
+| | ∨ | |
+| 1 | 11 | 20 |
+| | ∧ | |
+Linkes Teil-Array:
+| ∨ |
+| [1] |
+| ∧ |
+Rechtes Teil-Array:
+| ∨ |
+| [20] |
+| ∧ |
+Rechtes Teil-Array:
+| | | ∨ |
+| [99] | 42 | 70 |
+| ∧ | | |
+| | | ∨ |
+| [99] | 42 | 70 |
+| | ∧ | |
+| | | ∨ |
+| [99] | 42 | 70 |
+| | | ∧ |
+| | | ∨ |
+| 70 | 42 | 99 |
+| | | ∧ |
+| | | ∨ |
+| 70 | 42 | 99 |
+| | | ∧ |
+Linkes Teil-Array:
+| | ∨ |
+| [70] | 42 |
+| ∧ | |
+| | ∨ |
+| [70] | 42 |
+| | ∧ |
+| | ∨ |
+| 42 | 70 |
+| | ∧ |
+Linkes Teil-Array:
+| ∨ |
+| [42] |
+| ∧ |
+Sortierte Folge:
+| 1 | 11 | 20| 35| 42| 70| 99 |
+**b)**
+<code java>
+MyArray sort(MyArray a) {
+	int len = a.getLength();
+	int halfLen = len / 2;
+	if(len <= 1)
+		return a;
+	MyArray left = sort(getLeftSideSplit(halfLen));
+	MyArray right = sort(getRightSideSplit(halfLen));
+	return merge(left, right);
+}
+</code>
+**c)**
+^ / ^ mittlere Laufzeit ^ schlechteste Laufzeit ^ beste Laufzeit ^
+^ QuickSort | O(n log n) | O(n²) | O(n log n) |
+^ MergeSort| O(n log n) | O(n log n) | O(n log n) |
+^ BubbleSort | O(n²) | O(n²) | O(n) |
+==== Aufgabe 9 - Aufwände, O-Kalkül ====
+**a)**
+  * **O(log n)**
+  * **O(1)**, da k eine Konstante ist
+  * **O(n²)**
+  * **O(n)**
+  * **O(n³)**
+**b)**
+  * **Ja**, Logarithmen zu verschiedenen Basen unterscheiden sich nur durch konstanten Faktor
+  * **Ja**, gültige Regel
+  * **Nein**, für Subtraktion und Division gibt es keine Sonderregeln
+  * **Nein**, O(n log n) steigt stärker
+=== Aufgabe 10 - WP-Kalkül ===
+**a)**
+  wp("b = 5*a - 3; c = 2*a; b = b + 3 * c;", b = 8) =
+  wp("b = 5*a - 3; c = 2*a;", b + 3*c = 8) =
+  wp("b = 5*a - 3;", b + 3*(2*a) = 8) =
+  ((5*a - 3) + 3*(2*a) = 8) =
+  (5*a - 3 + 6*a = 8) =
+  (11*a = 11) =
+  (a = 1)
+**b)**
+  wp("b = 2*a + 1; c = a*a; a = c + b*b;", a >= 0) =
+  wp("b = 2*a + 1; c = a*a;", c + b*b >= 0) =
+  wp("b = 2*a + 1;", a*a + b*b >= 0) =
+  (a*a + (2*a + 1)*(2*a + 1) >= 0) =
+  (a² + 4*a² + 4*a + 1 >= 0) =
+  (5* a² + 4*a + 1 >= 0) =
+  (true)
+**c)**
+  wp("if (a == b) then a = 2*a; b = 2*b; else a = a + 1; b = b + 1; endif;", a = b) =
+  [(a == b) ∧ wp("a = 2*a; b = 2*b;", a = b)] ∨ [(a != b) ∧ wp("a = a + 1; b = b + 1;", a = b)] =
+  [(a == b) ∧ wp("a = 2*a;", a = 2*b)] ∨ [(a != b) ∧ wp("a = a + 1; b = b + 1;", a = b)] =
+  [(a == b) ∧ (2*a = 2*b)] ∨ [(a != b) ∧ wp("a = a + 1; b = b + 1;", a = b)] =
+  [(a == b) ∧ (2*a = 2*b)] ∨ [(a != b) ∧ wp("a = a + 1;", a = b + 1)] =
+  [(a == b) ∧ (2*a = 2*b)] ∨ [(a != b) ∧ (a + 1 = b + 1)] =
+  [(a == b) ∧ (a = b)] ∨ [(a != b) ∧ (a + 1 = b + 1)] =
+  (true) ∨ [(a != b) ∧ (a + 1 = b + 1)] =
+  (true) ∨ (false) =
+  (true)
+**d)**
+  * **Nein**, gilt nur vor der Schleife, nicht im Schleifenrumpf
+  * **Ja**, gilt vor der Schleife nicht, jedoch: {I ∧ b} => wp(A, I)
+  * **Nein**, gilt nur vor der Schleife, nicht im Schleifenrumpf
+  * **Ja**, true ist immer Schleifeninvariante
+**e)**
+  Invariante
+  (y - y0) / (x - x0) = m
+  Es gilt:
+  x = x0; y = y0;
+  x = x + 1; y = y + m;
+  m unverändert
+  ((y - y0) / (x - x0) = m) =
+  ((y + m - y0) / (x + 1 - x0) = m) =
+  ((y0 + m - y0) / (x0 + 1 - x0) = m) =
+  (m / 1 = m) =
+  (m = m) =
+  (true)