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
pruefungen:bachelor:aud:loesungws08 [15.02.2013 19:29] – Dawodopruefungen:bachelor:aud:loesungws08 [11.05.2019 12:09] (aktuell) – SpeedyGonzalez
Zeile 1: Zeile 1:
-==forum==+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7553-Frage-zur-Klausur-vom-19-02-2009-Aufgabe-8b]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7553-Frage-zur-Klausur-vom-19-02-2009-Aufgabe-8b]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7085-19-02-2009-Aufgabe-1]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7085-19-02-2009-Aufgabe-1]]
Zeile 7: Zeile 7:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung]]
  
-====Lösungsversuch====+===== Lösungsversuch =====
  
-==Aufgabe 1 - Wissensfragen==+==== Aufgabe 1 - Wissensfragen ====
 **a)** Falsch, es muss sortiert sein **a)** Falsch, es muss sortiert sein
  
-**b)** 3 - eine Schleife korrekt ist+**b)** Nummer 3: eine Schleife korrekt ist
  
 **c)** Richtig **c)** Richtig
Zeile 28: Zeile 28:
 **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 49: Zeile 50:
 ^ F | 10 | A -> B -> E -> F | ^ F | 10 | A -> B -> E -> F |
  
-==Aufgabe 3 - Java==+==== Aufgabe 3 - Java ====
  
 **a)** **a)**
Zeile 75: Zeile 76:
 {{:pruefungen:bachelor:aud:test-07-08_2.java.txt|:pruefungen:bachelor:aud:test-07-08_2.java.txt}} {{:pruefungen:bachelor:aud:test-07-08_2.java.txt|:pruefungen:bachelor:aud:test-07-08_2.java.txt}}
  
-==Aufgabe 4 - ADT==+==== Aufgabe 4 - ADT ====
 **a)** **a)**
-  contains(x, create) = false +<code> 
-  contains(x, append(x, L)) = 1 + contains(x, L) +contains(x, create) = false 
-  contains(x, append(y, L)) = contains(x, L)+contains(x, append(x, L)) = true 
 +contains(x, append(y, L)) = contains(x, L) 
 +</code>
  
 **b)** **b)**
-A -> D -> create +A -> D
  
 **c)** **c)**
 +<code>
 +append(head(append(D, create), append(A, create)) = 
 +A1
 += append(head(prepend(D, create), append(A, create)) = 
 +A1
 += append(head(prepend(D, create), prepend(A, create)) = 
 +A3
 += append(D, prepend(A, create)) = 
 +A2
 += prepend(A, append(D, create)) = 
 +A1
 += prepend(A, prepend(D, create))
 +</code>
  
-  append(head(append(D, create), append(A, create)) =  +==== Aufgabe 5 - Pseudo-Zufallszahlen ====
-  A1 +
-  = append(head(prepend(D, create), append(A, create)) =  +
-  A1 +
-  = append(head(prepend(D, create), prepend(A, create)) =  +
-  A3 +
-  = append(D, prepend(A, create)) =  +
-  A2 +
-  = prepend(A, append(D, create)) =  +
-  A1 +
-  = prepend(A, prepend(D, create)) +
- +
- +
-==Aufgabe 5 - Pseudo-Zufallszahlen==+
 **a)** **a)**
 <code java> <code java>
Zeile 114: Zeile 117:
 **Vorüberlegungen:**\\  **Vorüberlegungen:**\\ 
  
-f(n - 1) ^= c, da f(2) = 2 + 1 = 3 ist; analog:\\  +<code java> 
-f(n - 2) ^= b\\  +public static int f(int n) { 
-f(n - 3) ^= a+ return lin(1, 2, 3, n); 
 +} 
 +private static int lin(int a, int b, int c, int steps) { ... 
 +</code>
  
-lin (a, b, c) ^= lin (f(n - 3), f(n - 2), f(n - 1), steps)+Die Basisfälle der Funktion sind für n < 3 gegeben: \\ 
 +f(0) = 1 \\ 
 +f(1) = 2 \\ 
 +f(2) = 3 \\
  
-Wir starten also am Basisfall n < 3 ( => Bottom-Up ), weshalb nur noch der "sonst"-Teil beachtet werden muss. +Aus dem gegebenen Aufruf (mit 1,2,3)  und dieser Basisfälle lässt sich schließen: \\ 
 +a = 1 = f(0)  -->  entspricht f(n - 3) \\ 
 +b = 2 = f(1)  -->  entspricht f(n - 2) \\ 
 +c = 3 = f(2)  -->  entspricht f(n - 1) \\ 
 + 
 +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. 
 + 
 +Somit wissen wir: \\ 
 +lin(a, b, c, steps) -> lin(f(n - 3), f(n - 2), f(n - 1), steps) 
 + 
 +Wir starten also am Basisfall n < 3 (=> Bottom-Up), weshalb nur noch der "sonst"-Teil beachtet werden muss.
  
 **Nächster "step": n + 1** **Nächster "step": n + 1**
  
-lin (f(n - 2), f(n - 1), f(n), steps - 1)  **(*)**+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) und sieht mit a, b, c dann so aus:+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)+f(n) = 1 + (((c - b) * a) % 100)   **(* *)**
  
-Das in **(*)** eingesetzt ergibt dann+**(* *)** in **(*)** eingesetzt ergibt:
  
 lin(b, c, 1 + (((c - b) * a) % 100), steps - 1) lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)
Zeile 140: Zeile 160:
  
 private static int lin(int a, int b, int c, int steps) { private static int lin(int a, int b, int c, int steps) {
-    if (steps == 0) { + if (steps == 0) 
-        return a; + return a; 
-    } else { + 
-        lin(b, c, 1 + (((c - b) * a) % 100), steps - 1); + return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
-    }+
 } }
 </code> </code>
Zeile 150: Zeile 169:
 **Warum steht das Ergebnis gerade in a?** **Warum steht das Ergebnis gerade in a?**
  
-Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift: f(0) = lin(1, 2, 3, 0). Da n = 0 < 3, greift der sonst-Fall und das Ergebnis muss n + 1 = 0 + 1 = 1 sein. Und die 1 steht 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)** **c)**
 <code java> <code java>
 public static int f(int n) { public static int f(int n) {
- int a = 1, b = 2, c = 3; + int a = 1; 
- while (n > 0) { + int b = 2; 
- int tmp = a;+ int c = 3; 
 + 
 + while(n > 0) { 
 + int fn = 1 + (((c - b) * a) % 100);
  a = b;  a = b;
  b = c;  b = c;
- c = 1 + (((b-a)*tmp)%100);+ c = fn;
  n--;  n--;
  }  }
 +
  return a;  return a;
 } }
 </code> </code>
-==Aufgabe 6 - Suchbäume==+ 
 + 
 +==== Aufgabe 6 - Suchbäume ==== 
 **a)** **a)**
 <code> <code>
Zeile 172: Zeile 202:
     /  \     /  \
   23 42   23 42
- /      / \+ /     /  \
 7     32  64 7     32  64
-            \+             \
              81              81
 </code> </code>
Zeile 189: Zeile 219:
  
 **c)** **c)**
 +
 +Verwendete Definitionen:\\
 +  * Höhe eines Blatts: 0
 +  * Daraus folgt die Höhe des leeren Baums: -1
 +  * Balancefaktor: (Höhe des linken Teilbaums) - (Höhe des rechten Teilbaums)
  
 {{:pruefungen:bachelor:aud:ws08-6-c.png|:pruefungen:bachelor:aud:ws08-6-c.png}} {{:pruefungen:bachelor:aud:ws08-6-c.png|:pruefungen:bachelor:aud:ws08-6-c.png}}
Zeile 196: Zeile 231:
 {{:pruefungen:bachelor:aud:ws08-6-d.png|:pruefungen:bachelor:aud:ws08-6-d.png}} {{:pruefungen:bachelor:aud:ws08-6-d.png|:pruefungen:bachelor:aud:ws08-6-d.png}}
  
-  * Rotation an: 64+  * Rotation an Knoten: 64
  
-  * **Einfachrotation**, da die Vorzeichen der Balancewerte von 81 und 64 gleich sind+  * **Einfachrotation** gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind
  
 **e)** **e)**
-... 
  
-==Aufgabe 7 - Heap==+{{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}} 
 + 
 +==== Aufgabe 7 - Heap ====
  
 **a)**  **a)** 
-Der Wert jedes Knotens muss größer, als der seiner Kinder sein.+Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein.
  
 **b)** **b)**
Zeile 226: Zeile 262:
 <code java> <code java>
 public int parentIndex (int childIndex) { public int parentIndex (int childIndex) {
- return (childIndex - 1) / 2;+ return (childIndex % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2; 
 +        //Oder auch einfach nur 
 +        // return childIndex/2;
 } }
 </code> </code>
Zeile 253: Zeile 291:
  
  
-==Aufgabe 8 (wp)==+==== Aufgabe 8 - wp-Kalkül ====
  
 **a)** **a)**
Zeile 270: Zeile 308:
  
 i) i)
-  Nummer 3 - (x mod 2) = (i mod 2) ∧ y ≥ 0+  Nummer 3: (x mod 2) = (i mod 2) ∧ y ≥ 0
  
 ii) ii)
Zeile 301: Zeile 339:
 (x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0 (x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0
  
-{I ∧ b} => wp(A,I) = ... +{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) =
- +
- +
- +
- +
  
 +(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)   folgt   (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
 </code> </code>