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

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws07 [14.02.2013 21:27] – Dawodopruefungen: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/7567-Frage-Klausur-21-Februar-2008]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7104-WP-kalkuel-21-02-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]]   * [[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) **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: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}} Java Datei zum Ausprobieren: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}}
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)**
   * number   * number
Zeile 133: Zeile 137:
   * commutate   * commutate
  
-//Hinweis:// Konstruktoren sind Operationen, die Datenobjekte des Typs erzeugen.+//Hinweis:// Konstruktoren sind alle Operationen, die Datenobjekte des Typs erzeugen.
  
 **b)** **b)**
Zeile 149: Zeile 153:
  
   binop(left(commutate(binop(4,+,7))),*,right(binop(binop(1,-,1),+,binop(3,*,4)))) =    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)))) =    = binop(left(binop(7,+,4)),*,right(binop(binop(1,-,1),+,binop(3,*,4)))) = 
-  right +  //right// 
   = binop(left(binop(7,+,4)),*,binop(3,*,4)) =    = binop(left(binop(7,+,4)),*,binop(3,*,4)) = 
-  left +  //left// 
   = binop(7,*,binop(3,*,4))    = binop(7,*,binop(3,*,4)) 
  
Zeile 169: Zeile 173:
 </code> </code>
  
-=== 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 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)** **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 +  
-            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> </code>
 +
 +Vollständiges Programm: \\
 +{{:pruefungen:bachelor:aud:rucksack.java.txt|:pruefungen:bachelor:aud:rucksack.java.txt}}
  
 **d)** **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)**+**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 haben.
  
 **b)** **b)**
Zeile 274: Zeile 295:
   * **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 435:
  
  
 +==== 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) =
 +  [(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)