MINT üben

Den Huffman-Baum aufbauen

Zwei Abituraufgaben zum Aufbau von Huffman-Bäumen — mit Hinweisen und Erwartungshorizont.

Dein Fortschritt:
0 / 0 Aufgaben
1

ABRAKADABRA

AFB I–II

Das Wort ABRAKADABRA soll mit einem Huffman-Code übertragen werden. Konvention: Der Knoten mit der kleineren Häufigkeit hängt links, linke Kanten tragen die 0. Bei Gleichstand hängt der zusammengesetzte Knoten links, bei zwei Blättern das alphabetisch erste.

  1. Bestimmen Sie die Häufigkeiten der Zeichen.
  2. Zeichnen Sie den Huffman-Baum.
  3. Geben Sie die Codewörter und die Länge des codierten Wortes an.
  4. Begründen Sie, warum ein aus einem Baum abgelesener Code immer präfixfrei ist.

Hinweise

Hinweis zu Aufgabe a)
Strichliste; Probe über die Wortlänge.
Hinweis zu Aufgabe b)
Erster Schritt: die beiden Einsen. Danach gibt es drei Knoten mit Häufigkeit 2.
Hinweis zu Aufgabe c)
Weg von der Wurzel ablesen, dann \(\sum h\cdot l\).
Hinweis zu Aufgabe d)
Wo stehen die Zeichen im Baum?Begründen: Sachverhalte auf Regeln, Gesetzmäßigkeiten bzw. kausale Zusammenhänge zurückführen und mit Argumenten stützen.