Trace:
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| repds15:hausaufgaben_loes [2015/09/26 19:18] – [Hashing] 95.222.28.220 | repds15:hausaufgaben_loes [Unknown date] (current) – removed - external edit (Unknown date) 127.0.0.1 | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ===== Zusätzliche Fragen an Mario - von uns ;) ===== | ||
| - | ==== Fragen und Antworten ==== | ||
| - | |||
| - | Bitte nutzt die [[repds15: | ||
| - | ====== Hausaufgaben (mit Lösungen und Tipps) ====== | ||
| - | Diese Seite kann ohne Wiki-Account bearbeitet werden. Teilt eure Lösungen untereinander und korrigiert Fehler, wenn ihr sie findet. | ||
| - | |||
| - | ===== Neue Aufgaben ==== | ||
| - | |||
| - | ==== Rekursive Programmierung ==== | ||
| - | - Berechne die Tiefe eines Baums B, der in Kind-Geschwister-Darstellung gegeben ist. | ||
| - | |||
| - | Die Tiefe eines Baumes B (und nicht die Tiefe eines Knotens) meint die maximale Tiefe des Baumes B und die ist gleich der Höhe des Baumes. Das ist irritierend, | ||
| - | |||
| - | Ein rekursiver Algorithmus zur Ermittlung der Tiefe: | ||
| - | |||
| - | < | ||
| - | global im Baum: maximum = 0 | ||
| - | |||
| - | int getTiefe(p) | ||
| - | if (p == NULL) | ||
| - | return 0 | ||
| - | if (p→LKind == NULL) // p ist Blatt | ||
| - | return 0 | ||
| - | else | ||
| - | | ||
| - | </ | ||
| - | |||
| - | Die letzte Anweisung läßt sich noch genauer notieren: | ||
| - | |||
| - | < | ||
| - | max = 0 | ||
| - | for (q=p→LKind; | ||
| - | if (q-> | ||
| - | max = q->tiefe | ||
| - | return 1 + max | ||
| - | </ | ||
| - | |||
| - | Alternativ kann man den Algorithmus aus der Vorlesung (Folie 27 von 103 im 2. Foliensatz) | ||
| - | voraussetzen und alle Knoten mit ihrer Tiefe markieren: | ||
| - | |||
| - | < | ||
| - | tiefe(wurzel, | ||
| - | void tiefe (Knoten *p, int t) | ||
| - | { Knoten *q; t = t+1; | ||
| - | if (p != null) | ||
| - | { p→tiefe = t; | ||
| - | for (q=p→LKind; | ||
| - | | ||
| - | </ | ||
| - | |||
| - | Die Tiefe wird in einem Attribut des Knotens (hier Zugriff über p-> tiefe) gespeichert. | ||
| - | Der Baum habe ein globales Attribut maximum, das mit 0 initialiert ist und die maximale Tiefe | ||
| - | speichern soll. Nun genügt eine Traversierung durch den Baum, um das Maximum der Tiefe zu ermitteln. | ||
| - | |||
| - | < | ||
| - | void getTiefe (Knoten* p) | ||
| - | { | ||
| - | | ||
| - | if (p == NULL) | ||
| - | | ||
| - | for (q=p→LKind; | ||
| - | { | ||
| - | getTiefe(q) | ||
| - | if (q→tiefe > maximum) | ||
| - | maximum = q→tiefe | ||
| - | }} | ||
| - | </ | ||
| - | |||
| - | Was spricht für den einen, was für den anderen Weg? | ||
| - | |||
| - | - Gib eine rekursive Implementierung von '' | ||
| - | < | ||
| - | lookupRek(int priority, int wo) | ||
| - | { | ||
| - | if(2*wo <= n) | ||
| - | { | ||
| - | if (H[2*wo] == priority ) | ||
| - | print priority | ||
| - | else if (H[2*wo] > priority ) | ||
| - | lookupRek( priority, 2*wo); | ||
| - | if (H[2*wo+1] == priority ) | ||
| - | print priority | ||
| - | else if (H[2*wo+1] > priority ) | ||
| - | lookupRek( priority, 2*wo+1); | ||
| - | } | ||
| - | } | ||
| - | </ | ||
| - | - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | ||
| - | |||
| - | < | ||
| - | Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant? | ||
| - | </ | ||
| - | |||
| - | - Erweitere die '' | ||
| - | |||
| - | ==== Datenstrukturen entwerfen ==== | ||
| - | - 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: | ||
| - | ===== Tag 1 ===== | ||
| - | ==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== | ||
| - | |||
| - | - Welche Rechenregeln für Logarithmen gibt es? | ||
| - | - Vereinfache die folgenden Terme: | ||
| - | * $\log_2(8) = \log_2(2^3) = 3 \cdot \log(2) = 3 \cdot 1 = 3 \rightarrow \Theta(3) = \Theta(1)$ | ||
| - | * $\log_3(1) = 0$, da $x^0$ mit $x \in \mathbb{N}$ immer 1 ist $\rightarrow \Theta(1)$ | ||
| - | * $\log_2(n^4) = 4 \cdot log_2(n) \rightarrow \Theta(log \ n)$ | ||
| - | * $\log_{10}\left(\frac{1}{n^2}\right) = log_{10}(1) - log_{10}(n^2) = 0 - 2 \cdot log_{10}(n)$, | ||
| - | * $2^{\log_4(n)} = 2^{(log_4 2) \cdot (log_2 n)} = 2^{(log_2 n) \cdot (log_4 2)} = n^{log_4 2} = n^{1/2} = \sqrt n \rightarrow \Theta(\sqrt n)$ | ||
| - | * $\log_n(n) = 1 \rightarrow \Theta(1)$, da $\forall x \in \mathbb{N}: x^1=x$ | ||
| - | * $\log_a(b) \cdot \log_b(n)$ ist der Basiswechsel (siehe Formel) rückwärts, | ||
| - | * $\log_2(4n^3)=log_2(4)+log_2(n^3)=2+3\cdot log_2(n) \rightarrow \Theta (log \ n)$ | ||
| - | * $\log_2(\sqrt{n})=1/ | ||
| - | * $\log_2\left( \sum_{i=0}^n i \right) =\log_2\left( \frac{n\cdot(n+1)}{2} \right) = \log_2(n) + \log_2(n+1) - \log_2(2) = \Theta(\log(n)) $ | ||
| - | * $\log_3\left(\prod_{i=1}^n 3^i \right) = \sum_{i=1}^n \log_3\left(3^i \right) = \sum_{i=1}^n i \log_3(3) = \sum_{i=1}^n i = \frac{n\cdot(n+1)}{2}$ | ||
| - | * $\sum_{i=1}^n n \cdot i = n \cdot \sum_{i=1}^n i = n \cdot \frac{n \cdot(n+1)}{2} \rightarrow \Theta(n^3)$ | ||
| - | * $\sum_{k=0}^n 2^{-k} = 2- \frac{1}{2^n} \leq 2 = \Theta(1)$ | ||
| - | * $\sum_{k=1}^{\frac{n}{2}} 4^{-k} = (\sum_{k=0}^{\frac{n}{2}} 4^{-k}) - 1 = (\frac{1-(\frac{1}{4})^{(1+n/ | ||
| - | * $\sum_{i=1}^n \frac{2}{i} = O(log(n))$, da $\int \frac{1}{x} dx = \ln(x) + C$ | ||
| - | - Wahr oder falsch? Begründe deine Antwort. | ||
| - | * $1 = \Theta(3)$, wahr | ||
| - | * $2 = \Omega(1)$, wahr | ||
| - | * $3 = \omega(2)$, falsch | ||
| - | * $n = \omega(1)$, wahr, denn $\lim_{n\to \infty} \frac{n}{1} = \infty$. | ||
| - | * $f = \mathcal{O}(g)$ und $g = \mathcal{O}(f) \iff f = \Theta(g)$, wahr, siehe Definition | ||
| - | * $\sum_{k=0}^n 2^{-k} = \mathcal{O}(1)$, | ||
| - | * $\log_2(n) = \Theta(\log_8(n))$, | ||
| - | * $2^{\log_2(2n)} = \mathcal{O}(n^2)$, | ||
| - | * $f_1 = \Omega(g_1)$ und $f_2 = \Omega(g_2) \implies f_1 + f_2 = \Omega(g_1 + g_2)$, wahr, einfach in die Definition der Omega-Notation einsetzen. | ||
| - | * $f = o(g) \iff f = \mathcal{O}(g)$, | ||
| - | * $f(n) = g(\frac{n}{2}) \implies f = \Omega(g)$, falsch, Gegenbeispiel: | ||
| - | |||
| - | ==== Pseudocode und Laufzeitanalyse ==== | ||
| - | Welchen Wert hat k in Abhängigkeit von n nach der Ausführung des Programms? | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1,2,...,n | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1,2,...,n | ||
| - | k = k + 1 | ||
| - | for j=1, | ||
| - | k = k + 2 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1, | ||
| - | k = k + 2 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=n, | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1,2,...,n | ||
| - | k = k + i | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | while i < n | ||
| - | i = i + i | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | i = 0 | ||
| - | k = 0 | ||
| - | while i < n | ||
| - | i = i + k | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=sqrt(n), 2sqrt(n), | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | |||
| - | Umgekehrt: Schreibe Pseudocode mit den folgenden Laufzeiten: | ||
| - | - $\Theta(1)$ | ||
| - | - $\Theta(n)$ | ||
| - | - $\Theta(n^3)$ | ||
| - | - $\Theta(2^n)$, | ||
| - | - $\Theta(\sqrt{n})$ | ||
| - | < | ||
| - | i = 1 | ||
| - | k = 1 | ||
| - | while i <= n | ||
| - | i = i + k | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - $\Theta(\log{n})$ | ||
| - | - $\Theta(\log{n^3})$ | ||
| - | - $\Theta(n!)$, | ||
| - | |||
| - | **Billiglösung, | ||
| - | < | ||
| - | for i = 1, 2, ..., f(n) | ||
| - | print " | ||
| - | </ | ||
| - | |||
| - | Was tut der folgende Pseudocode? Angenommen $n = 2^k$ für ein beliebiges $k \in \mathbb{N}$. | ||
| - | < | ||
| - | function raetsel(Array A[0, | ||
| - | { | ||
| - | if l == r | ||
| - | { | ||
| - | return A[l] | ||
| - | } | ||
| - | else | ||
| - | { | ||
| - | grenze = floor( (l+r)/2 ) // untere Gaußklammer | ||
| - | m_l = raetsel(A, l, grenze) | ||
| - | m_r = raetsel(A, grenze + 1, r) | ||
| - | if m_l > m_r | ||
| - | { | ||
| - | return m_l | ||
| - | } | ||
| - | else | ||
| - | { | ||
| - | return m_r | ||
| - | } | ||
| - | } | ||
| - | } | ||
| - | </ | ||
| - | Welche Ausgabe liefert raetsel(A, 0, 7) für A = [1, | ||
| - | |||
| - | **Lösung: | ||
| - | {{: | ||
| - | |||
| - | ==== Rekursionsgleichungen aufstellen und lösen ==== | ||
| - | Aufstellen: | ||
| - | - < | ||
| - | def f(n): | ||
| - | if n == 1 | ||
| - | return 1 | ||
| - | else | ||
| - | return n + f(n-1) | ||
| - | </ | ||
| - | - < | ||
| - | def g(n): | ||
| - | if n > 1: | ||
| - | return g(n/2) | ||
| - | else | ||
| - | return 0 | ||
| - | </ | ||
| - | |||
| - | Lösen: | ||
| - | - $T(1) = 0$ und $T(n) = 2 T(\frac{n}{2}) + \frac{n}{2}$ für $n > 1$ | ||
| - | - $T(2) = 1$ und $T(n) = T(\frac{n}{2}) + n - 1$ für $n > 2$ | ||
| - | |||
| - | ==== Arrays ==== | ||
| - | * Was ist ein Array? | ||
| - | * Wie sieht ein Array im Arbeitsspeicher aus? | ||
| - | * Wie lang dauert ein Zugriff (lesen oder schreiben) auf das n. Element A[n]? Wieso? | ||
| - | * Schreibe ein Programm in Pseudocode, das ein gegebenes Array A[1,...,n] mit den Werten 2, 4,..., 2n befüllt. | ||
| - | < | ||
| - | for i = 1, 2, ..., n | ||
| - | A[i] = 2*i | ||
| - | </ | ||
| - | |||
| - | * Schreibe ein Programm in Pseudocode, das die Summe der Einträge dieses Arrays ausgibt. | ||
| - | < | ||
| - | sum = 0 | ||
| - | for(i = 1; i <= n; i++) | ||
| - | sum = sum + A[i] | ||
| - | return sum | ||
| - | </ | ||
| - | |||
| - | * Entwerfe eine Datenstruktur, | ||
| - | Idee: Das Intervall ist schon gegeben, d.h. es müssen keine " | ||
| - | < | ||
| - | def lookup(x): | ||
| - | return A[x] | ||
| - | | ||
| - | def insert(x): | ||
| - | A[x] = 1 | ||
| - | | ||
| - | def remove(x): | ||
| - | A[x] = 0 | ||
| - | </ | ||
| - | ==== Listen ==== | ||
| - | * Was ist eine Liste? | ||
| - | * Wie sieht eine Liste im Arbeitsspeicher aus? | ||
| - | * Wie unterscheiden sich Arrays und Listen? | ||
| - | * Welche Zeiger und Funktionen hat die Listen-Implementierung aus der Vorlesung zur Verfügung? | ||
| - | * Wie lange dauert es, das größte Element einer aufsteigend (absteigend) sortierten Liste zu finden? | ||
| - | **aufsteigend**: | ||
| - | **absteigend**: | ||
| - | < | ||
| - | L.movetofront() | ||
| - | return L.read() | ||
| - | </ | ||
| - | |||
| - | * Wie lange dauert das Einfügen der Zahl 7 in eine (un)sortierte Liste? | ||
| - | **unsortiert**: | ||
| - | |||
| - | * Wieso ist binäre Suche auf Listen keine gute Idee? | ||
| - | Wir können dort nicht " | ||
| - | |||
| - | * Schreibe ein Programm in Pseudocode, das beide Aufgaben (sortiert und unsortiert) erledigt. | ||
| - | **unsortiert**: | ||
| - | < | ||
| - | def insert_unsortiert(x): | ||
| - | L.insert(x) | ||
| - | </ | ||
| - | **sortiert (aufsteigend)**: | ||
| - | < | ||
| - | def insert_sortiert(x): | ||
| - | L.movetofront() | ||
| - | while not L.end(): | ||
| - | nachfolge_wert = L.read() | ||
| - | if nachfolge_wert >= x: | ||
| - | L.insert(x) | ||
| - | return; | ||
| - | else | ||
| - | L.next() | ||
| - | L.insert(x) | ||
| - | </ | ||
| - | |||
| - | * Die Datenstruktur Liste aus der Vorlesung ist eine einfach verkettete Liste, d.h. jedes Element hat nur einen Zeiger '' | ||
| - | ==== Stacks ==== | ||
| - | * Was ist ein Stack? | ||
| - | * Wie lange dauert ein Zugriff auf das oberste/ | ||
| - | * Beschreibe, wie mit einer Liste ein Stack implementiert werden kann. | ||
| - | < | ||
| - | def push(x): | ||
| - | L.movetofront() | ||
| - | L.insert(x) | ||
| - | | ||
| - | def pop(): | ||
| - | L.movetofront() | ||
| - | L.remove() | ||
| - | </ | ||
| - | |||
| - | * Schreibe ein Programm, das einen Stack A als Eingabe erhält und den Stack B ausgibt, wobei B die Elemente aus A in umgekehrter Reihenfolge enthält. | ||
| - | * Erweitere die Datenstruktur Stack um die Funktion '' | ||
| - | Benutze eine private Hilfsvariable '' | ||
| - | < | ||
| - | def push(x): | ||
| - | if S.empty(): | ||
| - | bot = x | ||
| - | push_alt(x) | ||
| - | | ||
| - | def bottom(): | ||
| - | if not S.empty(): | ||
| - | return bot | ||
| - | else | ||
| - | " | ||
| - | </ | ||
| - | |||
| - | * Bonusfrage: Wie werden Stacks in Programmiersprachen beim Aufruf von Funktionen verwendet? [[http:// | ||
| - | |||
| - | ==== Queues ==== | ||
| - | * Was ist eine Queue? | ||
| - | * Befolgen Queues das Prinzip LIFO oder FIFO? | ||
| - | FIFO (First in, first out). | ||
| - | |||
| - | * Beschreibe die Situation im Supermarkt an der Kasse mithilfe einer Queue. | ||
| - | * Wie würde sich das Einkaufen verändern, wenn Supermarkt-Kassen wie Stacks funktionieren würden? | ||
| - | Wenn eine neue Kasse geöffnet wird, dann sollte man sich möglichst ans Ende der Warteschlange anstellen, damit man als erste Person abkassiert wird. | ||
| - | |||
| - | * Welche Algorithmen aus der Vorlesung verwenden Queues? Wieso? | ||
| - | * Schreibe ein Programm in Pseudocode, das eine Liste L erhält und den Wert jedes Listenelements in eine Queue einfügt. | ||
| - | < | ||
| - | def list_to_queue(Liste L): | ||
| - | Q = new Queue() | ||
| - | L.movetofront() | ||
| - | while not L.empty(): | ||
| - | data = L.read() | ||
| - | Q.enqueue(data) | ||
| - | L.remove() | ||
| - | </ | ||
| - | |||
| - | * Lösche das jüngste Element aus einer Queue Q, ähnlich wie '' | ||
| - | < | ||
| - | H = new Queue() | ||
| - | while not Q.empty(): | ||
| - | data = Q.dequeue() | ||
| - | if not Q.empty(): | ||
| - | H.enqueue(data) | ||
| - | Q = H // statt alles wieder nach Q zu schaufeln, können wir auch einfach Q durch H ersetzen | ||
| - | </ | ||
| - | |||
| - | ---- | ||
| - | |||
| - | ===== Tag 2 ===== | ||
| - | ==== Bäume ==== | ||
| - | * Was ist ein Baum? | ||
| - | ein zusammenhängender Graph ohne einfache Kreise | ||
| - | |||
| - | * Was ist ein (vollständig) binärer, ternärer, k-ärer Baum? | ||
| - | Ein vollständiger binärer Baum der Tiefe t ist ein binärer Baum, in dem alle Blätter die Tiefe t besitzen und alle inneren Knoten wie auch die Wurzel den Aus-Grad genau 2 besitzen. | ||
| - | |||
| - | * Kann die Datenstruktur Liste auch als Baum aufgefasst werden? Ist ein Baum nur eine verzweigte Liste? | ||
| - | ja und ja, man kann beides so auffassen (je nach Implementierung) | ||
| - | |||
| - | * Welche Datenstrukturen für allgemeine Bäume kennen wir? | ||
| - | Eltern-Array, | ||
| - | |||
| - | * Entwerfe eine Datenstruktur für einen ternären Baum. Wieso sind Eltern-Arrays nicht geeignet? | ||
| - | |||
| - | < | ||
| - | struct Knoten | ||
| - | { schluesseltyp schluessel; | ||
| - | | ||
| - | | ||
| - | ... }; | ||
| - | </ | ||
| - | |||
| - | Eltern-Arrays: | ||
| - | die Ermitllung des kompletten Pfades von der Wurzel aus O(1). | ||
| - | |||
| - | * Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus? | ||
| - | Basisfall: Der Baum ist ein Blatt | ||
| - | Rekursionsfall: | ||
| - | ==== Graphen ==== | ||
| - | * Welche Datenstrukturen kennen wir für Graphen? | ||
| - | Adjazenzmatrix, | ||
| - | |||
| - | * Nenne Vor- und Nachteile dieser Datenstrukturen. | ||
| - | Tipp: Überlegt euch, wie lange es jeweils dauert, verschiedene Aufgaben zu lösen wie etwa "alle Nachbarn eines Knotens ausgeben", | ||
| - | ==== Tiefensuche, | ||
| - | * Führe Tiefen- und Breitensuche an einem selbst gewählten Beispiel aus. Dabei soll jeder Knoten seine Nachbarn in aufsteigender Reihenfolge speichern. | ||
| - | * Wieso müssen wir uns bei der Tiefen- und Breitensuche in allgemeinen Graphen merken, welche Knoten wir schon besucht haben? | ||
| - | * Führe Prä-/ | ||
| - | [[https:// | ||
| - | |||
| - | * Finde einen Baum, bei dem alle drei Traversierungen das gleiche Ergebnis liefern. | ||
| - | Der Baum ist ein Blatt. | ||
| - | |||
| - | * Gib eine rekursive Implementierung der Postorder-Traversierung an. Orientiere dich an Algorithmus 4.1 (S. 96 im Skript). | ||
| - | * Was hat die Tiefensuche auf Bäumen mit Prä-/ | ||
| - | * Welche Laufzeit hätten die Tiefen- und die Breitensuche, | ||
| - | Beim Besuch jedes Knotens müssen wir all seine Nachbarn überprüfen (wurden sie schon besucht?). Die Frage ist daher: Wie lange dauert es pro Knoten, all seine Nachbarn zu finden in der Adjazenzmatrix und in der Adjazenzliste? | ||
| - | Tipp: Mit dem Handshake-Lemma (doppeltes Abzählen) folgt dann, dass die Summe aller Knotengrade das doppelte der Kantenzahl ist: $\sum_{v \in V} \deg(v) = 2 \cdot |E|$ | ||
| - | |||
| - | * Benutzt die (nicht rekursive) Tiefensuche einen Stack oder eine Queue? Wie sieht es mit der Breitensuche aus? | ||
| - | Tiefensuche: | ||
| - | Breitensuche: | ||
| - | |||
| - | * Unter welchen Voraussetzungen kann ein Graph topologisch sortiert werden? | ||
| - | Wenn er keine Kreise hat. | ||
| - | |||
| - | * Ist diese Sortierung immer eindeutig? | ||
| - | nein. | ||
| - | * Gib eine topologische Sortierung an einem selbst gewählten Beispiel an. | ||
| - | |||
| - | ==== Heaps ==== | ||
| - | * Was ist ein Heap? | ||
| - | * Was ist der Unterschied zwischen Min- und Max-Heaps? | ||
| - | die Heap-Ordnung: | ||
| - | |||
| - | * In welcher Laufzeit kann bei einem Min-Heap (Max-Heap) auf das kleinste Element zugriffen werden? | ||
| - | O(1) durch '' | ||
| - | |||
| - | * Was ist die Heap-Ordnung? | ||
| - | * Richtig oder falsch: Ein Heap ist ein binärer Suchbaum? | ||
| - | Im Allgemeinen nein. | ||
| - | |||
| - | * Gib ein Beispiel für einen Heap an, der ein binärer Suchbaum ist. | ||
| - | Jeder Heap, der nur einen Knoten enthält ist ein binärer Suchbaum. Es gibt allerdings auch Min- und Max-Heaps mit zwei Knoten, die die Suchbaum-Eigenschaft erfüllen. | ||
| - | |||
| - | * Füge eine selbst gewählte Folge von acht Zahlen in einen Min-Heap ein. | ||
| - | * Entferne alle Zahlen mit '' | ||
| - | [[https:// | ||
| - | |||
| - | * Benutze diese Beobachtung für folgendes: Schreibe ein Programm in Pseudocode, das ein Array A[1,...,n] als Eingabe erhält und dessen Elemente in aufsteigender Reihenfolge ausgibt. | ||
| - | < | ||
| - | // Das ist Heap-Sort | ||
| - | |||
| - | H = new MinHeap() | ||
| - | for i=1,2,...,n | ||
| - | H.insert(A[i]) | ||
| - | for i=1,2,...,n | ||
| - | min = H.delete_min() | ||
| - | print min | ||
| - | </ | ||
| - | **Laufzeit-Analyse**: | ||
| - | |||
| - | * Wahr oder falsch: Wenn wir die Folge der einzufügenden Zahlen schon vorher kennen, kann das Einfügen aller Zahlen in den Heap in linearer Laufzeit realisiert werden. | ||
| - | wahr, mit der buildheap-Funktion | ||
| - | |||
| - | * Entwerfe einen Heap, der als ternärer Baum aufgefasst werden kann. | ||
| - | Speichere die Kinder von H[i] an den Positionen H[3i], H[3i+1], H[3i+2]. | ||
| - | ==== Binäre Suchbäume ==== | ||
| - | * Was ist ein binärer Suchbaum? | ||
| - | * Können auch Buchstaben in einem binären Suchbaum verwaltet werden? | ||
| - | * Welche Tiefe hat ein binärer Suchbaum mit n Schlüsseln im besten und im schlechtesten Fall? | ||
| - | * Was passiert bei '' | ||
| - | Nichts oder Fehlermeldung | ||
| - | * Was passiert bei '' | ||
| - | Nichts oder Fehlermeldung (Achtung: andere Implementierungen, | ||
| - | * Gib einen binären Suchbaum mit zehn Knoten an. | ||
| - | * Entferne die Wurzel. | ||
| - | * Entferne einen weiteren inneren Knoten | ||
| - | * mit einem Kind. | ||
| - | * mit zwei Kindern. | ||
| - | * Entferne ein Blatt. | ||
| - | * In welcher Laufzeit kann die Folge 1,2,...,n/2 in einen binären Suchbaum eingefügt werden? | ||
| - | Bei dieser Folge landet '' | ||
| - | * Gib eine Folge an, die in möglichst geringer Laufzeit eingefügt werden kann. Tipp: Breitensuche auf Bäumen. | ||
| - | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., 1: Jedes '' | ||
| - | ==== AVL-Bäume ==== | ||
| - | * Was ist ein AVL-Baum? | ||
| - | * Wahr oder falsch: Jeder AVL-Baum ist ein binärer Suchbaum. | ||
| - | * Wahr oder falsch: Jeder binäre Suchbaum ist ein AVL-Baum. | ||
| - | * Wozu dienen die Rotationen? | ||
| - | * Was ist die Tiefe eines AVL-Baums mit n Knoten im besten und im schlechtesten Fall? | ||
| - | * Welche Nachteile hat die Verwendung von AVL-Bäumen gegenüber üblichen binären Suchbäumen? | ||
| - | * Füge die Zahlen 1,2,...,15 in einen anfangs leeren AVL-Baum ein. Gib bei Balance-Grad-Verletzungen außerdem an, ob es sich um einen ZickZick, ZickZack, ZackZick oder ZackZack-Fall handelt. | ||
| - | |||
| - | ==== (a, | ||
| - | * Was ist ein (a,b)-Baum? | ||
| - | * Was bedeutet das a? | ||
| - | * Was bedeutet das b? | ||
| - | * Wie viele Kinder hat ein innerer Knoten, der 3 Schlüssel speichert? | ||
| - | * Füge die folgenden Zahlen in einen anfangs leeren (2,3)-Baum ein: 1, 4, 6, 9, 5, 11, 2, 3, 12, 10, 7, 8. Lösche anschließend wieder alle Schlüssel in der gleichen Reihenfolge. | ||
| - | |||
| - | ---- | ||
| - | |||
| - | ===== Tag 3 ===== | ||
| - | |||
| - | ==== Hashing ==== | ||
| - | * Was ist Hashing? | ||
| - | * Was ist eine Kollision? | ||
| - | * Welche Laufzeit haben '' | ||
| - | |||
| - | **Insert** | ||
| - | |||
| - | ^ case: | best | average | worst | | ||
| - | ^ mit Verkettung | ||
| - | ^ lineare Adressierung | O(1) | O(1)+$\lambda$ | ||
| - | ^ doppeltes Hashing | ||
| - | |||
| - | **Remove** | ||
| - | |||
| - | ^ case: | best | average | worst | | ||
| - | ^ mit Verkettung | ||
| - | ^ lineare Adressierung | O(1) | O(1)+$\lambda$ | ||
| - | ^ doppeltes Hashing | ||
| - | |||
| - | **Lookup** | ||
| - | |||
| - | ^ case: | best | average | worst | | ||
| - | ^ mit Verkettung | ||
| - | ^ lineare Adressierung | O(1) | O(1) | O(1) | | ||
| - | ^ doppeltes Hashing | ||
| - | |||
| - | * 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üge die Schlüssel 9, 20, 31, 42, 53 in eine Hash-Tabelle ein und gib jeweils die Reihenfolge der getesteten Zellen an: | ||
| - | * Hashing mit Verkettung | ||
| - | * Hashing mit linearem Austesten | ||
| - | * doppeltes Hashing mit $h(x) := f(x) + i\cdot g(x) \mod 11$, wobei $g(x) := 5 - (x \mod 5)$. | ||
| - | * Was ist der Auslastungfaktor $\lambda$ bei den beiden letzten Verfahren? Hängt er davon ob, ob linear ausgetestet oder doppelt gehasht wurde? | ||
| - | |||
| - | ^ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | ||
| - | ^ f(x)| | ||
| - | |||
| - | ^ x | 0 | 1 | 2 | 3 | 4 | | ||
| - | ^ g(x)| | ||
| - | |||
| - | ==== Rekursive Programmierung ==== | ||
| - | Löse die folgenden Aufgabenstellungen mit rekursiven Programmen. Was ist jeweils der Basisfall und was ist der Rekursionsfall? | ||
| - | |||
| - | - Maximum einer Liste finden | ||
| - | * Eingabe: Liste L | ||
| - | * Ausgabe: Wert eines größten Listenelements | ||
| - | * < | ||
| - | // Variante 1: | ||
| - | // Basisfall: Liste besteht nur aus einem einzigen Element | ||
| - | // Rekursionsfall: | ||
| - | |||
| - | def max1(Element e): | ||
| - | if(e.next == NULL) // Basisfall | ||
| - | return e.wert | ||
| - | else // Rekursion | ||
| - | max_restliste = max1(e.next) | ||
| - | if (e.wert > max_restliste) | ||
| - | return e.wert | ||
| - | else | ||
| - | return max_restliste | ||
| - | ------------------------------------------------ | ||
| - | | ||
| - | // Variante 2: | ||
| - | // Basisfall: leere Liste | ||
| - | // Rekursionsfall: | ||
| - | |||
| - | def max2(Element e): | ||
| - | if(e == NULL) // Basisfall | ||
| - | return -∞ | ||
| - | else // Rekursion | ||
| - | max_restliste = max1(e.next) | ||
| - | if (e.wert > max_restliste) | ||
| - | return e.wert | ||
| - | else | ||
| - | return max_restliste | ||
| - | </ | ||
| - | - Blätter eines Binärbaums zählen | ||
| - | * Eingabe: Zeiger root auf den Wurzelknoten eines Binärbaums | ||
| - | * Ausgabe: eine natürliche Zahl k > 0, wenn der Binärbaum k Blätter hat | ||
| - | * < | ||
| - | def count(Knoten v): | ||
| - | if (v == NULL) | ||
| - | return 0 | ||
| - | else | ||
| - | if (v.links == NULL und v.rechts == NULL) | ||
| - | laufffähiger Code in C++ | ||
| - | // Basisfall: v ist ein Blatt | ||
| - | return 1 | ||
| - | else | ||
| - | // Rekursionsfall: | ||
| - | return count(v.links) + count(v.rechts) | ||
| - | </ | ||
| - | - größte vollständige Teilbäume finden | ||
| - | * Eingabe: Zeiger root auf den Wurzelknoten eines Binärbaums | ||
| - | * Ausgabe: Zeiger auf einen Knoten, der die Wurzel eines vollständigen Binärbaums mit möglichst vielen Blättern ist | ||
| - | |||
| - | **Pseudocode** | ||
| - | < | ||
| - | im Baum: | ||
| - | im Knoten: | ||
| - | |||
| - | def maxFullBinTree() // | ||
| - | markFullBinTree(Wurzel des Binärbaums) | ||
| - | return maxnode = Zeiger auf den Knoten des größten vollständigen Teilbaums | ||
| - | |||
| - | def markFullBinTree(Knoten) | ||
| - | wenn Knoten leer | ||
| - | return | ||
| - | wenn Knoten ein Blatt | ||
| - | zaehler = 1 | ||
| - | wenn Knoten ein Halbblatt (nur ein Kind) | ||
| - | return | ||
| - | sonst hat der Knoten zwei Kinder | ||
| - | markFullBinTree(Knoten.links) | ||
| - | markFullBinTree(Knoten.rechts) | ||
| - | wenn beide Teilbäume gleich groß | ||
| - | zaehler = Knoten.links.zaehler + Knoten.rechts.zaehler + 1 | ||
| - | wenn zaehler > maximum | ||
| - | maximum = zaehler | ||
| - | maxNode = Knoten | ||
| - | return | ||
| - | </ | ||
| - | **laufffähiger Code in C++** | ||
| - | < | ||
| - | struct Knoten | ||
| - | { schluesseltyp schluessel; | ||
| - | | ||
| - | | ||
| - | | ||
| - | ... }; | ||
| - | |||
| - | class bsbaum | ||
| - | { | ||
| - | private: | ||
| - | Knoten* Kopf; // Wurzel | ||
| - | Knoten* maxNode; | ||
| - | int maximum; | ||
| - | ... }; | ||
| - | |||
| - | |||
| - | Knoten* bsbaum:: | ||
| - | { | ||
| - | Knoten* Zeiger = Kopf; | ||
| - | markFullBinTree(Zeiger); | ||
| - | cout << endl << " | ||
| - | return maxNode; | ||
| - | } | ||
| - | |||
| - | void bsbaum:: | ||
| - | { // in Variable count und ermittelt größten Teilbaum | ||
| - | if (Zeiger == NULL) // leerer Zeiger | ||
| - | return; | ||
| - | else if ((Zeiger-> | ||
| - | { // Blatt | ||
| - | Zeiger-> | ||
| - | return; | ||
| - | } | ||
| - | else if (!((Zeiger-> | ||
| - | { // HalbBlatt | ||
| - | return; | ||
| - | } // nichts zu tun | ||
| - | else // | ||
| - | { | ||
| - | markFullBinTree(Zeiger-> | ||
| - | markFullBinTree(Zeiger-> | ||
| - | int lb = Zeiger-> | ||
| - | int rb = Zeiger-> | ||
| - | if (lb == rb) // wenn Teilbäume gleich groß | ||
| - | Zeiger-> | ||
| - | if (Zeiger-> | ||
| - | { | ||
| - | maximum = Zeiger-> | ||
| - | maxNode = Zeiger; // Zeiger auf diesen | ||
| - | } | ||
| - | return; | ||
| - | } | ||
| - | } | ||
| - | </ | ||
| - | ==== Datenstrukturen entwerfen ==== | ||
| - | - Entwirf eine Wörterbuch-Datenstruktur, | ||
| - | * '' | ||
| - | * '' | ||
| - | * '' | ||
| - | - **Lösung**: | ||
| - | - Ein Projekt besteht aus einer geordneten Aufzählung von beliebig vielen Aufgaben. Jede Aufgabe hat eine Bearbeitungszeit. Die Bearbeitungszeit eines Projekts ist die Summe der Bearbeitungszeiten seiner Aufgaben. Entwirf eine Datenstruktur, | ||
| - | * '' | ||
| - | * '' | ||
| - | |||
| - | ==== Stichwörter: | ||
| - | |||
| - | === Arrays === | ||
| - | konstante Laufzeit O(1), vorgegebene Menge (feste Größe), Indizes, sortiert, Bitvektor, Array hat eine feste/fixe Größe, Matrix | ||
| - | |||
| - | === Listen === | ||
| - | variable Länge, beliebig lang, sortiert, O(n) Laufzeit, veränderliche/ | ||
| - | |||
| - | === Stacks === | ||
| - | push, pop, beides in O(1), LIFO (last in, first out), (Anwendungsbeispiel: | ||
| - | |||
| - | === Queue === | ||
| - | enqueue, dequeue, beides in O(1), FIFO (first in, first out), Warteschlange, | ||
| - | |||
| - | === Heaps === | ||
| - | Prioritätswarteschlange, | ||
| - | build_heap() in O(n) | ||
| - | |||
| - | === Graphen === | ||
| - | Adjazenz, Knoten, Kanten, Kreise, gerichtet, ungerichtet, | ||
| - | |||
| - | === Binäre Suchbäume === | ||
| - | Wörterbuch, | ||
| - | |||
| - | === AVL-Bäume === | ||
| - | Wörterbuch, | ||
| - | |||
| - | === (a, | ||
| - | Erweiterung von binären Suchbäumen, | ||
| - | |||
| - | === Hashing === | ||
| - | Wörterbuch, | ||