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:loesungws08 [22.07.2012 10:17] – Aufgabe 5 c hinzugefügt matze_pruefungen:bachelor:aud:loesungws08 [11.05.2019 10:23] – 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+**a)** Falsch, es muss sortiert sein
  
-**b)** 3 - eine Schleife korrekt ist+**b)** Nummer 3: eine Schleife korrekt ist
  
-**c)** richtig+**c)** Richtig
  
-**d)** richtig+**d)** Richtig
  
 **e)** Bucketsort, Mergesort **e)** Bucketsort, Mergesort
Zeile 24: Zeile 24:
 **g)** 4 - O(n² * log n) **g)** 4 - O(n² * log n)
  
-**h)** O(n*(log n)²)+**h)** 2 - O(n*(log n)²)
  
 **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 40: Zeile 41:
  
 **b)** **b)**
 +Pfade von Knoten A nach ...
 +
 +^ ... ^ Kosten ^ Pfad ^ 
 +^ B | 4 | A -> B |
 +^ C | 5 | A -> C |
 +^ D | 6 | A -> B -> E -> D |
 +^ E | 5 | A -> B -> E |
 +^ F | 10 | A -> B -> E -> F |
  
-  * nach B: 4 +==== Aufgabe 3 - Java ====
-  * nach C: 5 +
-  * nach D: 6 +
-  * nach E: 5 +
-  * nach F: 10+
  
-==Aufgabe 3 - Java== 
 **a)** **a)**
-Java Datei zum selber testen: {{:pruefungen:bachelor:aud:test.java.txt|:pruefungen:bachelor:aud:test.java.txt}} 
 ^Zeile^Bildschirmausgabe bzw. keine Ausgabe^ ^Zeile^Bildschirmausgabe bzw. keine Ausgabe^
 ^23 | BA | ^23 | BA |
Zeile 57: Zeile 60:
 ^38 | CC | ^38 | CC |
 ^39 | AA | ^39 | AA |
 +
 +Java-Datei zum selbst testen: \\
 +{{:pruefungen:bachelor:aud:test.java.txt|:pruefungen:bachelor:aud:test.java.txt}}
  
 **b)** **b)**
 ^Zeile^Begrundung^ ^Zeile^Begrundung^
-^7 |Compiler: f implementiert nicht die Methode f des Interfaces| +^7 |Compiler: A implementiert die Methode f() des Interfaces I nicht (korrekt) | 
-^19| Compiler: keine cast von double auf int im return Statement | +^19| Compiler: fehlender Cast von double zu int im return-Statement | 
-^34| Compiler: Instanzvariablen können nicht über den statischen Typ angesprochen werden (nicht A sondern a)| +^21| Compiler: die Sichtbarkeit von A geerbte public Methode g() kann in der Unterklasse nicht eingeschränkt werden | 
-^40| Compiler: Man kann nicht von der Ober- auf die Unterklasse konvertieren, nur andersherum| +^34| Compiler: Statischer Zugriff auf Instanzvariablen (Beachte Unterschied: A <-> a) | 
-^44| Compiler: g ist eine private-Methode. Darauf kann man nicht von i aus zugreifen|+^40| Compiler: Cast von Ober- auf Unterklasse nicht möglich (andersherum jedoch schon) | 
 +^44| Compiler: Interface I definiert keine Methode g() |
  
-==Aufgabe 4 - ADT==+Java-Datei zum selbst testen: \\ 
 +{{:pruefungen:bachelor:aud:test-07-08_2.java.txt|:pruefungen:bachelor:aud:test-07-08_2.java.txt}} 
 + 
 +==== Aufgabe 4 - ADT ====
 **a)** **a)**
-A4: contains(x, create) = false 
 <code> <code>
-A5: contains(x, append(y,l))= 1+contains(x,l)       //falls x=y +contains(x, create) = false 
-                             contains(x,l)          //falls x!=y+contains(x, append(x, L)) = true 
 +contains(x, append(y, L)) = contains(x, L)
 </code> </code>
 +
 **b)** **b)**
-A -> D -> create +A -> D
  
 **c)** **c)**
-//VORSICHT! nicht wirklich sicher! // +<code> 
- +append(head(append(D, create), append(A, create)) =  
-A1: 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>
  
-A1: append(head(prepend(D, create), prepend(A, create)) +==== Aufgabe 5 - Pseudo-Zufallszahlen ====
- +
-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 95: Zeile 108:
  if (n < 3)  if (n < 3)
  return n + 1;  return n + 1;
- else + 
- return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);+ return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
 } }
 </code> </code>
  
 **b)** **b)**
 +
 +**Vorüberlegungen:**\\ 
 +
 <code java> <code java>
 public static int f(int n) { public static int f(int n) {
  return lin(1, 2, 3, n);  return lin(1, 2, 3, n);
 } }
 +private static int lin(int a, int b, int c, int steps) { ...
 +</code>
 +
 +Die Basisfälle der Funktion sind für n < 3 gegeben: \\
 +f(0) = 1 \\
 +f(1) = 2 \\
 +f(2) = 3 \\
 +
 +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**
 +
 +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), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c:
 +
 +f(n) = 1 + (((c - b) * a) % 100)  **(* *)**
 +
 +**(* *)** in **(*)** eingesetzt ergibt:
 +
 +lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)
 +
 +<code java>
 +public static int f(int n) {
 + return lin(1, 2, 3, n);
 +}
 +
 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 { + 
- return lin(b,c,1+(((c-b)*a)%100),steps-1); + return lin(b, c, 1 + (((c - b) * a) % 100), steps - 1);
- }+
 } }
 </code> </code>
 +
 +**Warum steht das Ergebnis gerade 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 134: Zeile 202:
     /  \     /  \
   23 42   23 42
- /      / \+ /     /  \
 7     32  64 7     32  64
-            \+             \
              81              81
 </code> </code>
  
 **b)** **b)**
-Schlusselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81 +\\ 
-Kosten: O (n²)+Für die maximale Höhe müssen die Werte in auf- oder absteigend sortiert in den Baum eingefügt werden. \\ 
 +Schlüsselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81 \\ 
 +Kosten: O(n)
  
-Schlusselfolge für minimale Höhe: 32, 64, 42, 81, 23, 7,  27 +Für einen perfekt balancierten Baum fügt man immer das mittlere Element der sortierten Reihe ein, teil die Reihe in zwei Restreihen auf und fährt mit diesen genauso fort. \\ 
-Kosten: O (n * log n)+Schlüsselfolge für minimale Höhe: 32, 23, 7, 27, 64, 42, 81 \\ 
 +Kosten: O(log n)
  
 **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 155: 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 81 und 64 links gedreht werden.+  * **Einfachrotation** gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind 
 + 
 +**e)**
  
 +{{:pruefungen:bachelor:aud:ws08-6-e.png|:pruefungen:bachelor:aud:ws08-6-e.png}}
  
-==Aufgabe 7 - Heap==+==== Aufgabe 7 - Heap ====
  
 **a)**  **a)** 
-Für jeden Knoten außer der Wurzel gilt A[Vater[i]] >= A[i]+Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte seiner Kinder sein.
  
 **b)** **b)**
 <code> <code>
-    13 +        13 
-  6    9 +      /     \ 
-2  5  8+    6        9 
 +  /   \     / 
 + 2     5  8
 </code> </code>
 +
 **c)** **c)**
 <code java> <code java>
 public int leftChildIndex (int parentIndex) { public int leftChildIndex (int parentIndex) {
-     return parentIndex*2+1;+ return parentIndex * 2 + 1;
 } }
 </code> </code>
Zeile 180: 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;
 } }
 </code> </code>
Zeile 188: Zeile 270:
 //keine garantie! //keine garantie!
 public void add (int priority) { public void add (int priority) {
 + array[n] = priority;
 + int p = parentIndex(n);
  
-   array[n] = priority;+ while(p >= 0 && array[p] < array[n]) { 
 + // swap ohne temporäre Variable, da immer nur priority nach oben geswappt wird 
 + array[n] = array[p]; 
 + array[p] = priority;
  
-   while( j !=0) { + n = p; 
- + p = parentIndex(n); 
-        int i = n; + }
-        int j = parentIndex(n);+
  
-        if( priority > array[j] ) { + n++;
-              array[i] = array[j]; +
-              array[j] = priority; +
-        } else { +
-             break; +
-        } +
-    } +
- +
-    n++;+
 } }
 </code> </code>
Zeile 211: Zeile 289:
  
  
-==Aufgabe 8 (wp)==+==== Aufgabe 8 - wp-Kalkül ====
  
 **a)** **a)**
-a > b-5 && true => a > b-5+  wp("if (a > b - 5) {a = b++ - 4;}", a = b - 5) = 
 +  [(a > b - 5) ∧ wp("a = b++ - 4;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] = 
 +  [(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] = 
 +  [(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ (a = b - 5) = 
 +  [(a > b - 5) ∧ wp("a = b - 4;", a = b + 1 - 5)] ∨ (a = b - 5) = 
 +  [(a > b - 5) ∧ (b - 4 = b + 1 - 5)] ∨ (a = b - 5) = 
 +  [(a > b - 5) ∧ (b - 4 = b - 4)] ∨ (a = b - 5) = 
 +  [(a > b - 5) ∧ true] ∨ (a = b - 5) = 
 +  (a > b - 5) ∨ (a = b - 5) = 
 +  (a ≥ b - 5) 
 + 
 +**b)** 
 + 
 +i) 
 +  Nummer 3: (x mod 2) = (i mod 2) ∧ y ≥ 0 
 + 
 +ii) 
 +<code> 
 +Zu zeigen: P => wp(A,I) 
 + 
 +Nachweis: 
 +wp(A,I) = 
 +wp("x = i; y = 0; r = false;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = 
 +wp("x = i; y = 0;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = 
 +wp("x = i;", (x mod 2) = (i mod 2) ∧ 0 ≥ 0) = 
 +(i mod 2) = (i mod 2) ∧ 0 ≥ 0 = 
 +true ∧ true = 
 +true 
 + 
 +P => wp(A,I) = 
 +((i ≥ 0) => true) = 
 +(¬(i ≥ 0) ∨ true) = 
 +true 
 +</code> 
 + 
 +iii) 
 +<code> 
 +Zu zeigen: {I ∧ b} => wp(A,I) 
 + 
 +Nachweis: 
 +wp(A,I) = 
 +wp("x = x - 2; y = y + 1;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = 
 +wp("x = x - 2;", (x mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = 
 +(x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0 
 + 
 +{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>