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

Decodieren

Bei der Codierung eines Textes aus vielen Zeichen möchte man keine 'Trennzeichen' verwenden, denn die machen die codierte Nachricht länger. Wie findet man dann das Ende der Codierung eines einzelnen Zeichens?

bei einer Codierung mit fester Länge ist das einfach: Bei ASCII-Codierung entsprechen z.B. einfach immer 8 Bit einem Zeichen.
bei Codierung mit variabler Länge muss man darauf achten, dass die Codierung eines Zeichens und der Anfang der Codierung eines anderen Zeichens nicht die Codierung eines weiteren Zeichens sind. Terminologie

Im zweiten Fall hilft ein Codierungsbaum.

Codierungsbäume

alles klar?

Mit t(z) bezeichnen wir die Tiefe des Blattes z im Codierungsbaum.

Die letzte Aufgabe hat gezeigt:
Kennt man in einem Text T die Häufigkeit h(z) eines jeden Zeichens z und dessen Tiefe t(z) im Codierungsbaum, so ist die Länge der codierten Nachricht

$L(T) = \sum_{z} t(z) \cdot h(z)$

die Aufgabe

Wenn man für einen gegebenen Text T also eine möglichst kurze Codierung haben möchte, so muss man folgende Aufgabe lösen:

Finde einen Codierungsbaum, für den L(T) minimal ist.

Die zugehörige Codierung nennt man Huffman-Code.

Huffman-Algorithmus

Und diese Aufgabe löst der folgende Algorithmus von Huffman mit einer gierigen Strategie:

Algorithmus:

erzeuge für jedes Zeichen z einen einblättrigen Codierungsbaum
    und gib ihm das 'Gewicht' h(z)
füge alle diese Codierungsbäume in eine Menge M ein [Bsp.]
solange M mehr als ein Element enthält
     entnehme aus M die beiden Bäume mit dem kleinsten
         und zweitkleinsten Gewicht [Bsp.]
     hänge diese beiden Bäume an eine neue Wurzel [Bsp.]
     gib dem neuen Baum als Gewicht die Summe
         der Gewichte der beiden Teilbäume
     füge den Baum in M ein [Bsp.]

Nach unten scrollen, bis die Schaltflächen sichtbar sind
Dank

Hier kannst du

den Ablauf des Algorithmus beobachten
Huffman-Codierungen für eigene oder vorgegebene (Knopf 'Zufallstext') Texte erstellen

Wir codieren nur die 26 'kleinen' Buchstaben des Alphabets. Großschreibung wird ignoriert, Umlaute, Satz- und Sonderzeichen werden nicht codiert.
Neu entstandene Bäume werden ihrem Gewicht entsprechend einsortiert.

Ein Codierungsbaum für die Zeichen

'b', 'e', 'g', 'i', 'n', 't', 'x'

slideshow1Element1

Die Codierung ergibt sich durch den Pfad von der Wurzel zum Zeichen:
nach links: 0, nach rechts: 1

slideshow1Element2

Das Zeichen 'e' wird codiert als 10

slideshow1Element3

Das Zeichen 'x' als 0110

slideshow1Element4

usw.

slideshow1Element5