Algorithmen und Programmierung 3, WS 2003/2004 — 7. Übungsblatt

Abgabe bis Donnerstag, 8. Januar 2004

41. (7 Punkte) Versuchen Sie, den Huffman-Algorithmus zur Konstruktion eines optimalen Kodes auf ein ternäres Kodealphabet (ein Alphabet mit drei Buchstaben) zu verallgemeinern. Konstruieren Sie einen optimalen ternären Kode für n = 8 Quellsymbole mit relativen Häufigkeiten (p_{1}, …, p_{8}) = (\frac{2}{56}, \frac{3}{56}, \frac{4}{56}, \frac{6}{56}, \frac{7}{56}, \frac{10}{56}, \frac{11}{56}, \frac{13}{56}).

42. (7 Punkte) Eine stückweise konstante Funktionen f: (u, v] → ℝ ist durch eine zusammenhängende Folge von Intervallen mit entsprechenden Werten f(x) = a gegeben, z. B.

f(x) = \begin{cases}1, & für −1 < x ≤ 0 \\ −1, & für 0 < x ≤ 2 \\ 6, & für 2 < x ≤ 4 \end{cases}

Spezifizieren Sie eine Datenstruktur zur Darstellung solcher Funktionen. Nehmen Sie an, dass alle Intervalle halboffen sind, und zwar links offen und rechts abgeschlossen, wie im obigen Beispiel. Die Datenstruktur soll zumindest folgende Operationen erlauben:

(a) Berechnung des Wertes einer solche Funktion f(x) an einer gegebenen Stelle x. Falls x nicht im Definitionsbereich liegt, soll der Wert 0 zurückgegeben werden.

(b) Addition und Multiplikation zweier stückweise konstanter Funktionen. Entscheiden

Sie selbst, was der Definitionsbereich von f + g beziehungsweise fg sein soll.

43. (6 Punkte) Leiten Sie aus der algebraischen Spezifikation für Mengen

istenthalten(x, leer) = falsch  (1)
istenthalten(x, einfüge(x, M)) = wahr  (2)
istenthalten(x, einfüge(y, M)) = istenthalten(x, M), für x ≠ y (3)
istenthalten(x, lösche(x, M)) = falsch  (4)
istenthalten(x, lösche(y, M)) = istenthalten(x, M),  für x ≠ y  (5)

durch Umformungen folgende Identität her:

istenthalten(u, einfüge(x, lösche(x, M))) = istenthalten(u, einfüge(x, M)).

Geben Sie dabei in jedem Beweisschritt die Nummer der Gleichung an, die Sie verwenden.

44. (0 Punkte) Gegeben sei eine Funktion f: {0, …, n − 1} → {0, …, n − 1}, die einen großen (aber endlichen) Bereich in sich selbst abbildet, zum Beispiel

f(x) = x^{3} + 2x^{2} + 7 mod 10^{6}.

Wir betrachten die Folge a_{0} = 0, a_{i+1} = f(a_{i}). Da der Bereich endlich ist, muss die Folge Wiederholungen enthalten. Wie kann man in O(n) Zeit mit konstantem Speicher ein doppeltes Element finden? Wie kann man das kleinste i und das kleinste j finden, sodass a_{i} = a_{i+j} ist?^{1}

45. (0 Punkte) Der Weihnachtsmann ist mit seinem Rentierschlitten in die Mitte eines kreisförmigen Sees mit Umfang 100 m gefallen. Am Rande des Sees befindes sich ein Grinch, der nicht schwimmen, aber 4,5-mal so schnell laufen kann wie die Rentiere den Schlitten im Wasser ziehen können. Auf dem Land ist der Rentierschlitten jedoch schneller als der Grinch. Kann der Weihnachtsmann die Rentiere so lenken, dass die Weihnachtsgeschenke nicht dem Grinch in die Hände fallen und er die Pakete noch rechtzeitig abliefern kann? Wenn ja, welchen Mindestabstand vom Grinch kann der Weihnachtsmann erreichen, wenn er das rettende Land erreicht? Der Einfachheit halber stelle man sich Grinch und Rentierschlitten jeweils punktförmig vor.^{2}

1Diese Aufgabe dient nur zur Erbauung und hat mit dem Stoff der Vorlesung nicht direkt etwas zu tun.

Lösungshinweise (für alle, die nicht selbst daraufkommen wollen) finden Sie auf der Netzseite der Vorlesung.

2Mit etwas Kreativität kann man diese Aufgabe auch mit Hilfe eines Computers lösen. Die weihnachtliche Einkleidung dieses Rätsels habe ich teilweise von http://www.fzt86.de/Adventskalender/ übernommen.