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 [20.02.2013 12:17] – 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: \\ 
 +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: \\
 +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. \\
 +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)
  
-**d)** 2. Antwort ist richtig: "kommt mit O(1) zusätzlichem Speicher aus."+**d)** 2. Antwort ist richtig
  
 **e)** 1. Antwort ist richtig: "Überlädt meth aus C", da beide Methoden gleich heißen, aber andere Parameter erwarten **e)** 1. Antwort ist richtig: "Überlädt meth aus C", da beide Methoden gleich heißen, aber andere Parameter erwarten
Zeile 23: Zeile 31:
 **f)** 2. und 3. Antwort sind richtig **f)** 2. und 3. Antwort sind richtig
  
-**g)** false, denn der "=="-Operator vergleicht die Referenzen, nicht den Inhalt der Objekte+**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: \\ 
 +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 (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 42: Zeile 56:
  
 <code java>  <code java> 
-boolean isSearchTree(){ +boolean isSearchTree() { 
- return isSearchTreeAux(null, null); + if(left != null) { 
-} + if(getMax(left.data) >= data || !left.isSearchTree()) 
- + return false; 
-boolean isSearchTreeAux(Integer min, Integer max){ + } 
- if(min != null && data < min) +  
- return false; + if(right != null) { 
- + if(getMin(right) <= data || !right.isSearchTree()) 
- if(max != null && data > max) + return false; 
- return false; + }
- +
- if(left != null && !left.isSearchTreeAux(min, value -1)) +
- return false; +
- +
- if(right != null && !right.isSearchTreeAux(value + 1, max)) +
- return false;+
  
  return true;  return true;
 } }
 </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)**
-  * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer, als sein eigener Wert sein. +  * 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: +  * 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) +    * In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y) 
  
 **d)** **d)**
Zeile 73: Zeile 109:
  int smallest = getSmallest();  int smallest = getSmallest();
  
- // aktueller Knoten nicht der kleinste -> versickern lassen + // aktueller Knoten der kleinste -> fertig 
- if(data > smallest) { + if(data == smallest) 
- if(right.data == smallest) { + return; 
- swap(this, right); + 
- right.sanitize(); + if(left != null && left.data == smallest) { 
- } else { + swap(this, left); 
- swap(this, left); + left.sanitize(); 
- left.sanitize(); + } else { 
- }+ swap(this, right); 
 + right.sanitize();
  }  }
 } }
Zeile 88: Zeile 125:
 **e)** **e)**
  
-Ein AVL-Baum ist ein binärer Suchbaum, bei dem für jeden Knoten gilt: Die Höhe der beiden Teilbäume unterscheidet sich maximal um eins.+Ein AVL-Baum ist ein binärer Suchbaum, bei dem für jeden Knoten gilt: Die Höhe seiner beiden Teilbäume unterscheidet sich maximal um eins.
  
 **f)** **f)**
Zeile 110: Zeile 147:
 <code java> <code java>
 void getInOrderHelper(ArrayList<Integer> a){ void getInOrderHelper(ArrayList<Integer> a){
- if (left != null)+ if(left != null)
  left.getInOrderHelper(a);  left.getInOrderHelper(a);
  
  a.add(data);  a.add(data);
  
- if (right != null)+ if(right != null)
  right.getInOrderHelper(a);  right.getInOrderHelper(a);
 } }
Zeile 122: Zeile 159:
 **h)** **h)**
  
-2. und 3. Antwort sind richtig.+2. und 3. Antwort sind richtig
  
 ==== Aufgabe 3 - Streutabellen ==== ==== Aufgabe 3 - Streutabellen ====
Zeile 150: Zeile 187:
 } }
 </code> </code>
 +
 +Alternativ:
 +
 +<code java>
 +int getIndex(String url, ArrayList<String> urlList) {
 + return urlList.indexOf(url);
 +}
 +</code>
 +
 +Bemerkung: \\
 +Der Parameter urlList ist eigentlich überflüssig, da man mit Hilfe der url und der Hashfunktion die korrekt urlList selbstständig identifizieren kann.
  
 **c)** **c)**
Zeile 161: Zeile 209:
  
  ArrayList<String> bucket = urls.get(h);  ArrayList<String> bucket = urls.get(h);
- 
  int index = getIndex(url, bucket);  int index = getIndex(url, bucket);
 +
  if(index == -1)  if(index == -1)
  throw new UnknownHostException();  throw new UnknownHostException();
Zeile 174: Zeile 222:
 <code java> <code java>
 void resize(int h) { void resize(int h) {
- int newBuckets = h + 1 - urls.size(); + while(urls.size() <= h) {
- +
- for (int i = 0; i < newBuckets; i++) {+
  urls.add(new ArrayList<String>());  urls.add(new ArrayList<String>());
  ips.add(new ArrayList<String>());  ips.add(new ArrayList<String>());
  }     }   
 }    }   
 +</code>
 +alternativ:
 +\\
 +<code java>
 +void resize(int h) {
 + urls.ensureCapacity(h);
 + ips.ensureCapacity(h);
 +}
 </code> </code>
  
Zeile 189: Zeile 243:
  int h = hash(url);  int h = hash(url);
  
- // Hashtabelle vergrößern, sofern notwendig + // Hashtabelle vergrößern (resize verändert nichts, wenn ein Vergrößern nicht notwendig ist) 
- if(urls.size() <= h) + resize(h);
- resize(h);+
  
  int index = getIndex(url, urls.get(h));  int index = getIndex(url, urls.get(h));
   
- // die URL ist bereits vorhanden, es muss nur die IP aktualisiert werden + // URL wurde nicht gefunden -> URL und IP neu hinzufügen 
- if(index != -1) { + if(index == -1) {
- ips.get(h).set(index, ip); +
- +
- // die URL wurde nicht gefunden, URL und IP müssen neu eingefügt werden +
- } else {+
  urls.get(h).add(url);  urls.get(h).add(url);
  ips.get(h).add(ip);  ips.get(h).add(ip);
 +
 + // URL ist bereits vorhanden -> aktualisiere IP
 + } else {
 + ips.get(h).set(index, ip);
  }  }
 }    }   
Zeile 208: Zeile 261:
  
 Bemerkung: \\ Bemerkung: \\
-Die Aufgabe baut auf der Annahme auf, dass es sich praktisch um zwei eigenständige, aber gleichzeitig verwaltete Hashtabellen handelt. \\+Die Aufgabe baut auf der Annahme auf, dass es sich praktisch um zwei eigenständige, aber gleichzeitig (!) verwaltete Hashtabellen handelt. \\
 Nur aufgrund diese Annahme funktionieren die obigen Funktionen korrekt. Nur aufgrund diese Annahme funktionieren die obigen Funktionen korrekt.
  
Zeile 232: 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 265: 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 282: 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 294: 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 327: 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 379: 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 402: 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