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 [27.07.2013 16:09] – Dawodopruefungen: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 13: Zeile 14:
 **a)** E + Unterklassen von E **a)** E + Unterklassen von E
  
-**b)** O(|n|) +**b)** O(|n|) \\ 
-Begründung:+Begründung: \\
 Nach einmaliger Abarbeitung der inneren Schleife gilt "n == 0". Dadurch ergibt die Auswertung des Schleifenkopfs der äußeren Schleife "false" und die Funktion endet. Nach einmaliger Abarbeitung der inneren Schleife gilt "n == 0". Dadurch ergibt die Auswertung des Schleifenkopfs der äußeren Schleife "false" und die Funktion endet.
  
 **c)** O(n) **c)** O(n)
-Begründung: +Begründung: \\ 
-Im ersten Durchgang der Schleife werden alle drei Unterfunktionen einmal aufgerufen, das heißt: O(log n) + O(n) + O(1) = O(n) für die erste Iteration. +Im ersten Durchgang der Schleife werden alle drei Unterfunktionen einmal aufgerufen, das heißt: O(log n) + O(n) + O(1) = O(n) für die erste Iteration. \\ 
-In allen weiteren Durchläufen wird nur mehr "doSomethingInO(1)" ausgeführt, das heißt O(1) für alle weiteren Iterationen. +In allen weiteren Durchläufen wird nur mehr "doSomethingInO(1)" ausgeführt, das heißt O(1) für alle weiteren Iterationen. \\ 
-Da es insgesamt n-1 weitere Iterationen gibt, lautet der Gesamtaufwand der weiteren Iterationen O(n)+Da es insgesamt n-1 weitere Iterationen gibt, lautet der Gesamtaufwand der weiteren Iterationen O(n) \\
 Insgesamt ergibt sich damit: O(n) + O(n) = O(n) Insgesamt ergibt sich damit: O(n) + O(n) = O(n)
  
Zeile 32: Zeile 33:
 **g)** false, denn der "=="-Operator vergleicht die Referenzen, nicht den Inhalt der Objekte (das wäre equals()) **g)** false, denn der "=="-Operator vergleicht die Referenzen, nicht den Inhalt der Objekte (das wäre equals())
  
-**h)** O(log n) +**h)** O(log n) \\ 
-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 156: Zeile 188:
 </code> </code>
  
-Alternativ (Unbekannt, ob Ausnutzung der API an dieser Stelle erlaubt):+Alternativ:
  
 <code java> <code java>
Zeile 164: Zeile 196:
 </code> </code>
  
-Bemerkung:+Bemerkung: \\
 Der Parameter urlList ist eigentlich überflüssig, da man mit Hilfe der url und der Hashfunktion die korrekt urlList selbstständig identifizieren kann. Der Parameter urlList ist eigentlich überflüssig, da man mit Hilfe der url und der Hashfunktion die korrekt urlList selbstständig identifizieren kann.
  
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;
-  + 
- if(primes[n] == 0) {+ // Geforderte Primzahl wurde noch nicht berechnet 
 + if (primes[n] == 0) { 
 + // Berechne den vorherige Primzahl
  long p = getPrimeDPHelper(n - 1, primes);  long p = getPrimeDPHelper(n - 1, primes);
   
 + // Berechne ausgehend von der vorherigen, die aktuelle Primzahl
  do {  do {
  p++;  p++;
Zeile 278: 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)**
  
-Kürzester Pfad: Kara -> C -> E -> A -> Klee+Kürzester Pfad: \\ 
 +Kara -> C -> E -> A -> Klee
  
 **c)** **c)**
Zeile 295: Zeile 360:
 <code> <code>
 IA_0 (n = 0):  IA_0 (n = 0): 
-C0 = (0 + 2) * 2^(0 - 1) = 2 * 2^(-1) = 2 / 2 = 1  +C_0 = (0 + 2) * 2^(0 - 1) = 2 * 2^(-1) = 2 / 2 = 1  
-cpRec(0) = 1+cpRec(0) = 1 (Basisfall)
  
 IA_1 (n = 1):  IA_1 (n = 1): 
-C1 = (1 + 2) * 2^(1 - 1) = 3*2^0 = 3 * 1 = 3  +C_1 = (1 + 2) * 2^(1 - 1) = 3*2^0 = 3 * 1 = 3  
-cpRec(1) = 3+cpRec(1) = 3 (Basisfall)
 </code> </code>
  
Zeile 307: Zeile 372:
 <code> <code>
 IV_(n-2) (n-2): IV_(n-2) (n-2):
-cpRec(n-2) = C_(n-2)+cpRec(n-2) = C_(n-2) gilt für ein n ∈ N_0
    
 IV_(n-1) (n-1): IV_(n-1) (n-1):
-cpRec(n-1) = C_(n-1)+cpRec(n-1) = C_(n-1) gilt für ein n ∈ N_0
 </code> </code>
  
 Aus dem Programmfragment ist zu entnehmen: Aus dem Programmfragment ist zu entnehmen:
 <code> <code>
-cpRec(n) = 4 * cpRec(n-1) - 4 * cpRec(n-2) =+cpRec(n) = 4 * cpRec(n-1) - 4 * cpRec(n-2) = ...
 </code> </code>
  
-über die obigen Induktionsvoraussetzungen kommt man auf:+Über die obigen Induktionsvoraussetzungen kommt man auf:
 <code> <code>
-= 4 * C_(n-1) - 4 * C_(n-2) = +... = 4 * C_(n-1) - 4 * C_(n-2) = 
 = 4 * [((n - 1) + 2) * 2^((n - 1) - 1)] - 4 * [((n - 2) + 2) * 2^((n - 2) - 1)] =  = 4 * [((n - 1) + 2) * 2^((n - 1) - 1)] - 4 * [((n - 2) + 2) * 2^((n - 2) - 1)] = 
 = 4 * [(n + 1) * 2^(n - 2)] - 4 * [n * 2^(n - 3)] =  = 4 * [(n + 1) * 2^(n - 2)] - 4 * [n * 2^(n - 3)] = 
Zeile 340: Zeile 405:
 <code> <code>
 LO: Falsch LO: Falsch
- n ≥ 0; a = 1; k = n - 1; p = 1; + n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) 
- a = (n + 2) * 2^(n - 1)+ (a = (n + 2) * 2^(n - 1)) = (1 = (n + 2) * 2^(n - 1))
  -> kann nicht für jedes n ≥ 0 gelten  -> kann nicht für jedes n ≥ 0 gelten
  
 RO: Falsch RO: Falsch
- n ≥ 0; a = 1; k = n - 1; p = 1; + n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) 
- p = 2^(n - k) = 2^(n - (n - 1)) = 2^1 = 2+ (p = 2^(n - k)) = (1 = 2^(n - (n - 1))) =  
 + (1 = 2^1) = (1 = 2)
  -> stimmt nicht  -> stimmt nicht
  
 LU: Richtig LU: Richtig
- n ≥ 0; a = 1; k = n - 1; p = 1; + n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) 
- (p = 2^(n - k - 1) ∧ k ≥ 0) = (p = 2^(n - (n - 1) - 1) ∧ n - 1 ≥ 0) = + (p = 2^(n - k - 1) ∧ k ≥ 0) = (1 = 2^(n - (n - 1) - 1) ∧ n - 1 ≥ 0) = 
- (p = 2^0 ∧ n - 1 ≥ 0) = (p = 1 ∧ n - 1 ≥ 0)+ (1 = 2^0 ∧ n - 1 ≥ 0) = (1 = 1 ∧ n - 1 ≥ 0) 
 + Falls n eine Ganzzahl ist, folgt: (n > 0) ∧ (n - 1 ≥ 0) = true
  -> stimmt  -> stimmt
  
 RU: Falsch RU: Falsch
- n ≥ 0; a = 1; k = n - 1; p = 1; + n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) 
- C_k = (k + 2) * p -> p = 2^(k - 1)+ (C_k = (k + 2) * p) = (C_(n-1) = (n + 1) * 1) = 
 + (C_(n-1) = n + 1) 
  -> kann nicht für jedes n ≥ 0 gelten  -> kann nicht für jedes n ≥ 0 gelten
 </code> </code>
Zeile 392: Zeile 460:
  
 (p * 2 = 2^(n - k) ∧ k > 0) (p * 2 = 2^(n - k) ∧ k > 0)
- 
  
 {I ∧ b} => wp(A, I) = {I ∧ b} => wp(A, I) =
Zeile 415: Zeile 482:
 </code> </code>
  
-**e)**+einfacher: 
 +<code> 
 +Zu zeigen: (I ∧ b) => wp(B, I)
  
-(unsicher)+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> 
 + 
 +**e)**
  
 V := k V := k