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

--- pruefungen:bachelor:aud:loesungws07 [15.02.2013 07:07] – Dawodo
+++ pruefungen:bachelor:aud:loesungws07 [27.05.2014 23:10] – yef
@@ 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 126: / Zeile 126: @@
-=== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ===
+==== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ====
 (nicht mehr Stoff aktueller Semester)
-===Aufgabe 5 - ADT===
+==== Aufgabe 5 - ADT ====
 **a)**
   * number
@@ Zeile 173: / 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)**
+**b)** \\
-,4,7
+Gesucht: Lösung für Rucksack der Größe 12 \\
-In Tabelle von a) mittels [] eingekreist.
+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 i = 1; i < n; i++) {			// Zeilen
-    for(int j = 0; j < m + 1; j++) {    // Spalten
+	for(int j = 0; j <= m; 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.
+		// Fall P(n - 1, K): Gibt es in der Zelle direkt darüber eine Lösung,
-            if(j + k[i+1] <= m)
+		// dann ist P(n, K) = P(n - 1, K)
-                tab[i+1][j+k[i+1]] = MIT;
+		// 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)**
-//unsicher!
+  * **Ja**
-  * nein
+  * **Ja**
-  * ja
+  * **Ja**, durch sukzessives Ausprobieren für Kapazitäten < m
-  * nein
+  * **Nein**, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu
-  * ja
-=== Aufgabe 7 - Binäre Bäume ===
+==== Aufgabe 7 - Binäre Bäume ====
 **a)**
 Der Binärbaum muss eine totale Ordnung aufweisen:\\
@@ Zeile 278: / Zeile 295: @@
   * **Nein**, man muss eines Tiefensuche vewenden
-=== Aufgabe 8 - Sortieren ===
+==== Aufgabe 8 - Sortieren ====
-∨∧
 **a)**
-^ | | | | | | ∨ |
+| | | | | | | ∨ |
-^ [35] | 70 | 42 | 11 | 99 | 1 | 20 |
+| [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)**
@@ Zeile 309: / Zeile 435: @@
-=== Aufgabe 9 - Aufwände, O-Kalkül ===
+==== Aufgabe 9 - Aufwände, O-Kalkül ====
 **a)**
   * **O(log n)**
-  * **O(n²)**
+  * **O(n)**, da k * n/2
   * **O(n²)**
   * **O(n)**
@@ Zeile 318: / Zeile 444: @@
 **b)**
-  * **Ja**
+  * **Ja**, Logarithmen zu verschiedenen Basen unterscheiden sich nur durch konstanten Faktor
-  * **Ja**
+  * **Ja**, gültige Regel
-  * **Nein**
+  * **Nein**, für Subtraktion und Division gibt es keine Sonderregeln
-  * **Nein**
+  * **Nein**, O(n log n) steigt stärker
 === Aufgabe 10 - WP-Kalkül ===
@@ Zeile 356: / Zeile 482: @@
 **d)**
-  * **Nein**
+  * **Nein**, gilt nur vor der Schleife, nicht im Schleifenrumpf
-  * **Ja**
+  * **Ja**, gilt vor der Schleife nicht, jedoch: {I ∧ b} => wp(A, I)
-  * **Nein**
+  * **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)