DokuWiki - fricklers.org

Trace:

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Last revisionBoth sides next revision
repds15:hausaufgaben_loes [2015/09/26 17:04] – [Rekursive Programmierung] 95.222.28.112repds15:hausaufgaben_loes [2015/10/04 16:24] – mario
Line 75: Line 75:
 lookupRek(int priority, int wo) lookupRek(int priority, int wo)
 { {
- if(2*wo <= n)+ if(wo <= n)
  {  {
- if (H[2*wo] == priority )+ if (H[wo] == priority )
  print priority  print priority
- else if (H[2*wo] >  priority )+ else if (H[wo] >  priority )
  lookupRek( priority, 2*wo);  lookupRek( priority, 2*wo);
- if (H[2*wo+1] == priority )+ if (H[wo+1] == priority )
  print priority  print priority
- else if (H[2*wo+1] > priority )+ else if (H[wo+1] > priority )
  lookupRek( priority, 2*wo+1);  lookupRek( priority, 2*wo+1);
  }  }
Line 89: Line 89:
 </code> </code>
   - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): Statt einem Feld ''Gewinner g'' speichert ein Knoten nun eine Zahl ''int gewinn''. Es gilt: ''gewinn'' > 0, wenn Alice gewinnt und ''gewinn'' < 0, wenn Bob gewinnt. Anfänglich sind nur die Blätter mit den ''gewinn''-Werten markiert. Für alle inneren Knoten ist ''gewinn = 0''. Wer gewinnt das Spiel und wie hoch ist der Gewinn, wenn jeder Spieler nach einem betragsmäßig großen Gewinn strebt?   - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): Statt einem Feld ''Gewinner g'' speichert ein Knoten nun eine Zahl ''int gewinn''. Es gilt: ''gewinn'' > 0, wenn Alice gewinnt und ''gewinn'' < 0, wenn Bob gewinnt. Anfänglich sind nur die Blätter mit den ''gewinn''-Werten markiert. Für alle inneren Knoten ist ''gewinn = 0''. Wer gewinnt das Spiel und wie hoch ist der Gewinn, wenn jeder Spieler nach einem betragsmäßig großen Gewinn strebt?
- +'' Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant?'' 
-<code> +**Antwort**: Der Name "MinMax-Algorithmus" stammt eigentlich aus diesem Modell. Die Frage, ob eine Gewinnstrategie existiert, ist nur ein Spezialfall. Interessant ist, dass man über die Gewinnfunktion für jeden Spieler den lokal optimalen Zug bestimmen kann und letztlich für denjenigen mit der Gewinnstrategie auch exakt angeben kann, welchen Zug er spielen soll, um möglichst hoch zu gewinnen.
-Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant? +
-</code>+
  
   - Erweitere die ''lookup(x)''-Funktion eines binären Suchbaums, sodass sie den Pfad von der Wurzel zum Schlüssel zurück gibt, sofern er existiert.   - Erweitere die ''lookup(x)''-Funktion eines binären Suchbaums, sodass sie den Pfad von der Wurzel zum Schlüssel zurück gibt, sofern er existiert.
Line 99: Line 97:
   - Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt.   - Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt.
   - Wir überlegen uns eine einfache Komprimierungsmöglichkeit: Wenn viele nebeneinander liegende Pixel die gleiche Farbe haben, dann genügt es, wenn nur einmal die Farbe und die Anzahl der betroffenen Pixel abgespeichert wird. So können wir Speicherplatz sparen. Der Zugriff auf ein Pixel ''p'' darf nun länger dauern, nämlich O(k), wobei k die Anzahl der Pixel links von ''p'' ist. Im besten Fall kann die Laufzeit auch geringer sein. **Tipp**: Was haben diese Aufgabe und ihr Vorgänger mit den Graph-Datenstrukturen aus der Vorlesung gemeinsam?   - Wir überlegen uns eine einfache Komprimierungsmöglichkeit: Wenn viele nebeneinander liegende Pixel die gleiche Farbe haben, dann genügt es, wenn nur einmal die Farbe und die Anzahl der betroffenen Pixel abgespeichert wird. So können wir Speicherplatz sparen. Der Zugriff auf ein Pixel ''p'' darf nun länger dauern, nämlich O(k), wobei k die Anzahl der Pixel links von ''p'' ist. Im besten Fall kann die Laufzeit auch geringer sein. **Tipp**: Was haben diese Aufgabe und ihr Vorgänger mit den Graph-Datenstrukturen aus der Vorlesung gemeinsam?
 +
 +''1) Bedarf an Speicherplatz: '' $O(n^2)$
 +
 +''2) Lauflängencodierung: Alle Zeilen werden separat codiert. Die Zeilen werden in einem Array verwaltet. Das Array enthält einen Zeiger auf einen Knoten mit dem Beginn der Zeile. Die Anzahl gleichfarbeiger Zellen wird in einem Knoten gespeichert. Weiße und schwarze Zellen wechseln einander ab. Die erste Codierung entspricht der Adjazenzmatix, die zweite der Adjazenzliste.''
 ===== Tag 1 ===== ===== Tag 1 =====
 ==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== ==== Mathematische Grundlagen, Asymptotik, Landau-Notation ====
Line 529: Line 531:
   * Was ist eine Kollision?   * Was ist eine Kollision?
   * Welche Laufzeit haben ''insert(x)'', ''remove(x)'' und ''lookup(x)'' im besten und im schlechtesten Fall?   * Welche Laufzeit haben ''insert(x)'', ''remove(x)'' und ''lookup(x)'' im besten und im schlechtesten Fall?
 +
 +**Insert**
 +
 +^ case:                | best | average | worst |  
 +^ mit Verkettung       | O(1) | O(1)+$\lambda$  | O(n)  |  
 +^ lineare Adressierung | O(1) | O(1)+$\lambda$  | O(n)  | 
 +^ doppeltes Hashing    | O(1) | O(1/1-$\lambda$)| O(n)  | 
 +
 +**Remove**
 +
 +^ case:                | best | average | worst |  
 +^ mit Verkettung       | O(1) | O(1)+$\lambda$  | O(n)  |  
 +^ lineare Adressierung | O(1) | O(1)+$\lambda$  | O(n)  | 
 +^ doppeltes Hashing    | O(1) | O(1/1-$\lambda$)| O(n)  | 
 +
 +**Lookup**
 +
 +^ case:                | best | average | worst |  
 +^ mit Verkettung       | O(1) | O(1)+$\lambda$    | O(n)  |  
 +^ lineare Adressierung | O(1) | O(1)    | O(1)  | 
 +^ doppeltes Hashing    | O(1) | O(1)    | O(1)  | 
 +
   * Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$.   * Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$.
   * Fülle eine Wertetabelle für $f(x) := 3x \mod 11$   * Fülle eine Wertetabelle für $f(x) := 3x \mod 11$
Line 588: Line 612:
     else      else 
         if (v.links == NULL und v.rechts == NULL)             if (v.links == NULL und v.rechts == NULL)    
-laufffähiger Code in C++ 
             // Basisfall: v ist ein Blatt             // Basisfall: v ist ein Blatt
             return 1                            return 1               
Line 681: Line 704:
 } }
 </code> </code>
 +
 +Der Code berücksichtigt nicht den Fall, daß es mehrere vollständige Teilbäume mit gleicher Knotenzahl geben kann. Hier wäre sinngemäß in der Rahmenprozedur zu ergänzen:
 +<code>
 +printMaxTree(Knoten)
 + if (Knoten == NULL) return
 + if (Knoten->links == NULL ) || (Knoten->rechts == NULL) return
 + else
 + if (zaehler = maximum)
 + printTree(Knoten)
 + else
 + printMaxTree(Knoten)
 +</code>
 +
 +
 ==== Datenstrukturen entwerfen ==== ==== Datenstrukturen entwerfen ====
   - Entwirf eine Wörterbuch-Datenstruktur, die für die gegebene Menge M := {0, 1,..., n-1} folgende Laufzeiten ermöglicht:   - Entwirf eine Wörterbuch-Datenstruktur, die für die gegebene Menge M := {0, 1,..., n-1} folgende Laufzeiten ermöglicht: