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:loesungss11 [23.03.2014 13:33] – *indexOf war in API-Auszug enthalten -> erlaubt Anonapruefungen:bachelor:aud:loesungss11 [20.06.2020 12:12] (aktuell) BierBaron69
Zeile 1: Zeile 1:
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
 +  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8856-Klausur-11-08-2011-Wissensfragen]] Aufgabe 1
 +  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8878-Klausur-11-08-2011]] Aufgabe 4
 +  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8833-Induktion]] Aufgabe 6
 +  * [[https://fsi.cs.fau.de/forum/thread/13564-WP-Kalkuel-SS-2011]] Aufgabe 6
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8821-Klausur-11-08-2011-Aufgabe-6-c-wp]] Aufgabe 6   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8821-Klausur-11-08-2011-Aufgabe-6-c-wp]] Aufgabe 6
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8783-UML]] Aufgabe 7   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8783-UML]] Aufgabe 7
-  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8833-Induktion]] 
-  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8856-Klausur-11-08-2011-Wissensfragen]] Aufgabe 1 
-  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8878-Klausur-11-08-2011]] 4 
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 35: Zeile 36:
 Begründung: \\ Begründung: \\
 Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\ Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\
-Um zu prüfen, ob es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht.+Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht
 + 
 +Anmerkung: 
 +Es geht ja um den worst case. Ich denke, man kann ein Szenario konstruieren, in dem die Laufzeit O(n) beträgt. Wenn z.B. die gesamte Reihung nur aus diesem Element besteht, muss man nach Auffinden des ersten Eintrags, die gesamte Liste durchgehen, um alle Vorkommen zu finden und zu zählen.
  
 **i)** 2. Antwort ist richtig **i)** 2. Antwort ist richtig
Zeile 54: Zeile 58:
 boolean isSearchTree() { boolean isSearchTree() {
  if(left != null) {  if(left != null) {
- if(left.data > data || !left.isSearchTree())+ if(getMax(left.data>data || !left.isSearchTree())
  return false;  return false;
  }  }
   
  if(right != null) {  if(right != null) {
- if(right.data < data || !right.isSearchTree())+ if(getMin(right<data || !right.isSearchTree())
  return false;  return false;
  }  }
Zeile 66: Zeile 70:
 } }
 </code> </code>
 +
 +?? oder vielleicht so: ??
 +\\
 +<code java>
 +boolean isSearchTree() {
 +    if (this.left == null && this.right == null) {
 +        return true;
 +    } else if (this.left == null) {
 +        if (this.right.getMin() > this.data) {
 +            return this.right.isSearchTree();
 +        }
 +        return false;
 +    } else if (this.right == null) {
 +        if (this.left.getMax() < this.data) {
 +            return this.left.isSearchTree();
 +        }
 +        return false;
 +    } else  {
 +        if (this.left.getMax() < this.data && this.right.getMin() > this.data) {
 +            return this.left.isSearchTree() && this.right.isSearchTree();
 +        }
 +        return false;
 +    }
 +}
 +</code>
 +
 +Zum Testen: https://pastebin.com/T6DbJ4iU
 +
  
 **c)** **c)**
Zeile 195: Zeile 227:
  }     }   
 }    }   
 +</code>
 +alternativ:
 +\\
 +<code java>
 +void resize(int h) {
 + urls.ensureCapacity(h);
 + ips.ensureCapacity(h);
 +}
 </code> </code>
  
Zeile 245: Zeile 285:
  
 <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 281: Zeile 326:
 | 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 419: Zeile 480:
 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>