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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws07 [14.02.2013 21:27] – Dawodo | pruefungen:bachelor:aud:loesungws07 [29.03.2016 15:02] (aktuell) – ADT korrigiert Marcel[Inf] | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==forum== | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
Zeile 10: | Zeile 10: | ||
* [[https:// | * [[https:// | ||
- | ====Lösungsversuch==== | + | ===== Lösungsversuch |
- | ===Aufgabe 1 - Binärsuche=== | + | ==== Aufgabe 1 - Binärsuche |
**a)** O(n) | **a)** O(n) | ||
Zeile 57: | Zeile 57: | ||
**c)** O(log n) | **c)** O(log n) | ||
- | ===Aufgabe 2 - Graphen=== | + | ==== Aufgabe 2 - Graphen |
**a)** | **a)** | ||
* **Ja** | * **Ja** | ||
Zeile 97: | Zeile 97: | ||
BD, BC, DG, BA, FI, GE, GI, FH | BD, BC, DG, BA, FI, GE, GI, FH | ||
- | ===Aufgabe 3 - Java=== | + | ==== Aufgabe 3 - Java ==== |
**a)** | **a)** | ||
Java Datei zum Ausprobieren: | Java Datei zum Ausprobieren: | ||
Zeile 125: | Zeile 125: | ||
Nein, eine Instanziierung von abstrakten Klassen ist nicht möglich. | 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)** | **a)** | ||
+ | Primärkonstruktoren: | ||
* number | * number | ||
* binop | * binop | ||
+ | |||
+ | Sekundärkonstruktoren (war nicht gefragt): | ||
* left | * left | ||
* right | * right | ||
* commutate | * commutate | ||
- | //Hinweis:// Konstruktoren sind Operationen, | + | Projektionen: |
+ | * numops | ||
**b)** | **b)** | ||
Zeile 149: | Zeile 157: | ||
binop(left(commutate(binop(4, | binop(left(commutate(binop(4, | ||
- | commutate | + | |
= binop(left(binop(7, | = binop(left(binop(7, | ||
- | right | + | |
= binop(left(binop(7, | = binop(left(binop(7, | ||
- | left | + | |
= binop(7, | = binop(7, | ||
Zeile 169: | Zeile 177: | ||
</ | </ | ||
- | === Aufgabe 6 - Rucksackproblem === | + | ==== Aufgabe 6 - Rucksackproblem |
**a)** | **a)** | ||
^ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ | ^ ^ 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)** |
- | 1,4,7 | + | Gesucht: Lösung für Rucksack der Größe 12 \\ |
- | In Tabelle | + | Elemente mit den Größen |
+ | 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)** | **c)** | ||
<code java> | <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 | + | |
- | | + | // 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) |
- | | + | // Das aktuelle Elemente gehört somit nicht zur Lösung -> OHNE |
- | } | + | if(tab[i |
- | } | + | 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), | ||
+ | // 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][j] = MIT; | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ | ||
+ | |||
+ | Vollständiges Programm: \\ | ||
+ | {{: | ||
**d)** | **d)** | ||
- | // | + | * **Ja** |
- | | + | * **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)** | + | **a)** |
Der Binärbaum muss eine totale Ordnung aufweisen: | 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 haben als der aktuelle Knoten. | + | Alle Knoten im linken Teilbaum müssen einen echt kleineren, alle im rechten Teilbaum einen echt größeren Wert als der aktuelle Knoten |
**b)** | **b)** | ||
Zeile 274: | Zeile 299: | ||
* **Nein**, man muss eines Tiefensuche vewenden | * **Nein**, man muss eines Tiefensuche vewenden | ||
- | === Aufgabe 8 - Binäre Bäume | + | ==== 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)** | **b)** | ||
Zeile 300: | Zeile 439: | ||
+ | ==== Aufgabe 9 - Aufwände, O-Kalkül ==== | ||
+ | **a)** | ||
+ | * **O(log n)** | ||
+ | * **O(n)**, da k * n/2 | ||
+ | * **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) ∧ 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) |