Gierige Methoden | MathePrisma

Gierige Methoden

Huffman-Codes

Sudokus

Wechselgeld

Allgemein

Codes

Arbeitsblatt

Aufgabe 1

a) Wir betrachten einen Münzsatz mit 5 Münzen mit den Werten

w(1) = 16, w(2) = 8, w(3) = 4, w(4) = 2, w(5) = 1.
Zeige, dass die gierige Strategie für das Wechselgeldproblem hier stets eine minimale Zahl von Münzen ergibt.
b) Verallgemeinere die Untersuchung von a) für den Fall, dass n Münzen mit den Werten

$w(1) = b^{n-1}, w(2) = b^{n-2}, ..., w(n-1) = b^{1}, w(n) = b^{0}$

vorliegen. Dabei ist $b$ eine ganze Zahl $\geq 2$ .

Aufgabe 2

Man kann jeden Bruch $\displaystyle \frac{p}{q}$ mit $1\leq p \leq q$ als sog. ägyptischen Bruch darstellen, d.h.

$\frac{p}{q} = \frac{1}{q_1} + \frac{1}{q_2} + ... + \frac{1}{q_n}.$

Dabei sind die Nenner $q_i$ paarweise verschiedene natürliche Zahlen. Die Anzahl $n$ der Glieder hängt von $p$ und $q$ ab.
a) Beschreibe einen auf einer gierigen Strategie beruhenden Algorithmus, welcher für gegebenes $p$ und $q$ die Nenner $q_i$ in der Darstellung als ägyptischer Bruch bestimmt.
b) Wie lauten hier die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur?

Aufgabe 3

Auf einer sehr langen Autofahrt (z.B. von Wuppertal nach Wladiwostok) soll möglichst selten zum Tanken angehalten werden. Die Tankstellen entlang der Strecke sind mit T(i) durchnummeriert. Folgendes ist bekannt:

Das Auto besitzt den konstanten Benzinverbrauch v.
Tankstelle T(i) befindet sich an Streckenkilometer d(i)..
Der Tank besitzt einen Inhalt I.

a) Beschreibe eine gierige Strategie zur Lösung dieser Aufgabe.
b) Wie lauten hier die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur?

Aufgabe 4

a) Führe alle Schritte des Huffman-Algorithmus für den nachstehenden Zeichensatz mit den angegebenen Häufigkeiten aus:

	Zeichen z	a	i	o	l	k	n	t
	h(z)	11	6	5	9	3	4	4

b) Gib mit dem in a) berechneten Codierungsbaum die Codierungen für die Wörter "koala", "aioli" und "koalition" an.

c) Wie groß ist die gewichtete externe Pfadlänge des Codierungsbaums aus a)?

Aufgabe 5

Beim Nachweis der Eigenschaft der gierigen Wahl auf der Seite Huffman-Codes 4 hatten wir einen optimalen Codierungsbaum so umgebaut, dass die Zeichen z1 und z2 Geschwister in maximaler Tiefe wurden. Wenn sie das nicht schon vor dem Umbau waren, müssen einige Zeichen mit genau den gleichen Häufigkeiten wie z1 und z2 vorkommen. Welche (Blätter in dem angegebenen Codierungsbaum) sind das?

Drucken

jetzt geht's richtig los

Wir beginnen mit der Eigenschaft der gierigen Wahl. Im Huffman-Algorithmus fügt man immer die beiden Knoten mit dem kleinsten Gewicht an einen gemeinsamen Vater.

gierige Wahl

Es gilt: Es gibt einen optimalen Codierungsbaum, in welchem die beiden Zeichen mit der kleinsten und zweitkleinsten Häufigkeit Geschwister sind.

Und das beweisen wir jetzt, indem wir einen optimalen Codierungsbaum erforderlichenfalls so umbauen, dass er immer noch optimal ist.

zum Beweis

Fazit

Die externe Pfadlänge des neuen Baumes hat sich gegenüber dem ursprünglichen Baum verkleinert oder sie ist gleich geblieben. Weil der ursprüngliche Baum optimal war, kann sie sich nicht verkleinert haben. Der neue Baum hat dieselbe minimale externe Pfadlänge; er ist auch optimal.

Im neuen Baum sind z1 und z2 Geschwister.

optimale Teilstruktur

Jetzt fehlt noch die Eigenschaft der optimalen Teilstruktur.
Dazu:

Zwei Zeichen a,b seien Geschwister in einem optimalen Codierungsbaum.
Wir ersetzen sie durch ein neues Zeichen z, dessen Häufigkeit die Summe der Häufigkeiten der beiden ersetzten Zeichen ist.
Ersetzen wir im Codierungsbaum den Vater der beiden Zeichen durch z, so ist der resultierende Codierungsbaum optimal für den modifizierten Zeichensatz.
Umgekehrt führt jeder optimale Codierungsbaum für den modifizierten Zeichensatz zu einem optimalen Codierungsbaum für den ursprünglichen Zeichensatz, wenn man in ihm z durch einen Vater mit den beiden Söhnen a und b ersetzt.

	T sei ein optimaler Codierungsbaum für die Zeichen z1 ... zn mit Häufigkeiten h1 ... hn. Wir ersetzen zwei Zeichen mit demselben Vater (hier: z3 und z4) ...
	... durch ein neues Zeichen z mit Häufigkeit h3+h4. Im Codierungsbaum ersetzen wir den Vater durch ein Blatt für das Zeichen z. Im neuen Baum T' ist L(T') = L(T)-h3-h4. T' ist optimal für den neuen Zeichensatz. Denn:
	Wäre T'' ein Codierungsbaum für den neuen Zeichensatz mit L(T'') < L(T'), so würde nach Ersetzen von z durch einen Vater von z3 und z4 ...
	... ein Codierungsbaum T''' für den ursprünglichen Zeichensatz entstehen mit L(T''') = L(T'') + h3+h4 < L(T') + h3+h4 = L(T). Das ist unmöglich, da T optimal war.

T sei (irgendein) optimaler Codierungsbaum.

slideshow2Element5

Das Zeichen z1 habe die kleinste, z2 die zweitkleinste Häufigkeit.

slideshow2Element1

Zusätzlich haben wir zwei Geschwister maximaler Tiefe, m1 und m2, blau markiert.

slideshow2Element2

Vertauschen wir z1 und m1, so ändert sich die externe Pfadlänge um

$\begin{align*} h(z1)\cdot(t(m1)-t(z1))+h(m1)\cdot(t(z1)-t(m1))\\ = \underbrace{( h(m1)-h(z1) )}_{\geq 0} \cdot \underbrace{(t(z1)-t(m1))}_{\leq 0} \leq 0 \end{align*}$

slideshow2Element3

Vertauschen wir noch z2 und m2, so ändert sich die externe Pfadlänge weiter um

$\begin{align*} h(z2)\cdot(t(m2)-t(z2))+h(m2)\cdot(t(z2)-t(m2))\\ = \underbrace{( h(m2)-h(z2) )}_{\geq 0} \cdot \underbrace{(t(z2)-t(m2))}_{\leq 0} \leq 0 \end{align*}$

slideshow2Element4

slideshow3optstruct0

slideshow3optstruct1

slideshow3optstruct2

slideshow3optstruct3