Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen

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
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss11 [20.03.2018 21:07] – Evrenpruefungen:bachelor:aud:loesungss11 [21.03.2018 12:00] – Evren
Zeile 68: Zeile 68:
 </code> </code>
  
-**c)** 
-  * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer als sein eigener Wert sein. 
-  * Mathematisch: Ein partiell geordneter Baum ist ein knotenmarkierter Binärbaum, in dem für jeden Teilbaum T' mit Wurzel x gilt: 
-    * In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y)  
- 
-**d)** 
-<code java> 
-void sanitize() { 
- int smallest = getSmallest(); 
- 
- // aktueller Knoten der kleinste -> fertig 
- if(data == smallest) 
- return; 
- 
- if(left != null && left.data == smallest) { 
- swap(this, left); 
- left.sanitize(); 
- } else { 
- swap(this, right); 
- right.sanitize(); 
- } 
-} 
-</code> 
 ?? oder vielleicht so: ?? ?? oder vielleicht so: ??
 \\ \\
-<code java >+<code java>
 boolean isSearchTree() { boolean isSearchTree() {
     if (this.left == null && this.right == null) {     if (this.left == null && this.right == null) {
Zeile 117: Zeile 94:
  
 Zum Testen: https://pastebin.com/T6DbJ4iU Zum Testen: https://pastebin.com/T6DbJ4iU
 +
 +
 +**c)**
 +  * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer als sein eigener Wert sein.
 +  * Mathematisch: Ein partiell geordneter Baum ist ein knotenmarkierter Binärbaum, in dem für jeden Teilbaum T' mit Wurzel x gilt:
 +    * In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y) 
 +
 +**d)**
 +<code java>
 +void sanitize() {
 + int smallest = getSmallest();
 +
 + // aktueller Knoten der kleinste -> fertig
 + if(data == smallest)
 + return;
 +
 + if(left != null && left.data == smallest) {
 + swap(this, left);
 + left.sanitize();
 + } else {
 + swap(this, right);
 + right.sanitize();
 + }
 +}
 +</code>
  
 **e)** **e)**
Zeile 222: Zeile 224:
  }     }   
 }    }   
 +</code>
 +alternativ:
 +\\
 +<code java>
 +void resize(int h) {
 + urls.ensureCapacity(h);
 + ips.ensureCapacity(h);
 +}
 </code> </code>
  
Zeile 272: Zeile 282:
  
 <code java> <code java>
-public static long getPrimeDPHelper(int n, long primes[]) { +public static long getPrimeDPHelper(int n, long primes[]) throws ArrayIndexOutOfBoundsException  { 
- if(n <= 0)+ // ArrayIndexOutOfBoundsException detection (falls getPrimeDPHelper(..) falsch aufgerufen wird) 
 + if (n >= primes.length) { 
 + throw new ArrayIndexOutOfBoundsException("Uebergebenes Array zum Speichern der berechneten Primzahlen ist zu klein!"); 
 + } 
 +         
 +        if (n <= 0)
  return 2;  return 2;
  
  // Geforderte Primzahl wurde noch nicht berechnet  // Geforderte Primzahl wurde noch nicht berechnet
- if(primes[n] == 0) {+ if (primes[n] == 0) {
  // Berechne den vorherige Primzahl  // Berechne den vorherige Primzahl
  long p = getPrimeDPHelper(n - 1, primes);  long p = getPrimeDPHelper(n - 1, primes);
Zeile 308: Zeile 323:
 | 0 | 11 | 16 | 3 | 7 | 7 | [17] | | 0 | 11 | 16 | 3 | 7 | 7 | [17] |
 | 0 | 11 | 16 | 3 | 7 | 7 | 17 | | 0 | 11 | 16 | 3 | 7 | 7 | 17 |
 +
 +alternativ:
 +
 +^ Kara ^ A ^ B ^ C ^D ^E ^ Klee ^
 +| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
 +| | ∞ | 18<sub>Klara</sub> | [3<sub>Klara</sub>] | 7<sub>Klara</sub> | 9<sub>Klara</sub> | ∞ |
 +| | 13<sub>C</sub> | 18<sub>Klara</sub> | | 7<sub>Klara</sub> | [7<sub>C</sub>] | ∞ |
 +| | 11<sub>E</sub> | 18<sub>Klara</sub> | | [7<sub>Klara</sub>] | | ∞ |
 +| | [11<sub>E</sub>] | 18<sub>Klara</sub> | | | | 19<sub>D</sub> |
 +| | | [16<sub>A</sub>] | | | | 17<sub>A</sub> |
 +| | | | | | | [17<sub>A</sub>] |
 +| | | | | | | |
 +
 +Indizes rückwärts (von unten nach oben) durchgehen : [17<sub>A</sub>] -> [11<sub>E</sub>] -> [7<sub>C</sub>] -> [3<sub>Klara</sub>] -> [0]
 +
 +=> umdrehen: Klara -> C -> E -> A -> Klee
  
 **b)** **b)**
Zeile 446: Zeile 477:
 Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein. Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein.
 Die Invariante ist somit gültig. Die Invariante ist somit gültig.
 +</code>
 +
 +einfacher:
 +<code>
 +Zu zeigen: (I ∧ b) => wp(B, I)
 +
 +I: p = 2^(n - k - 1) ∧ k ≥ 0
 +b: (k > 0)
 +B: "p *= 2; k--" <=> "p = p * 2; k = k - 1;"
 +
 +(I ∧ b):
 +    p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0
 +    <=> p = 2^(n - k - 1) ∧ k > 0      (weil: (k ≥ 0 ∧ k > 0) <=> (k > 0))
 +
 +wp(B, I):
 +    wp("p = p * 2; k = k - 1;", p = 2^(n - k - 1) ∧ k ≥ 0)
 +    <=> wp("p = p * 2;", p = 2^(n - (k - 1) - 1) ∧ k - 1 ≥ 0)
 +    <=> wp("p = p * 2;", p = 2^(n - k) ∧ k ≥ 1)
 +    <=> wp(" ", p * 2 = 2^(n - k) ∧ k ≥ 1)
 +    <=> p * 2 = 2^(n - k) ∧ k ≥ 1
 +    <=> p = (1/2) * 2^(n - k) ∧ k ≥ 1
 +    <=> p = 2^(n - k) * (1/2) ∧ k ≥ 1
 +    <=> p = 2^(n - k) * 2^(-1) ∧ k ≥ 1      (weil: (1/2) = 2^(-1))
 +    <=> p = 2^(n - k - 1) ∧ k ≥ 1      (weil: 2^(n - k) * 2^(-1) = 2^(n - k - 1))
 +
 +(I ∧ b) => wp(B, I):
 +    p = (2^(n - k - 1) ∧ k > 0)   =>   (p = 2^(n - k - 1) ∧ k ≥ 1)
 +      -> wahr, weil k > 0 <=> k ≥ 1, da k vom Datentyp "long" und damit ganzzahlig (..., -2, -1, 0, 1, 2, ...)
 +
 +fertig
 </code> </code>