Hannes Stoppel, Benjamin Rott

Mit Bäumen Daten reduzieren

© Friedrich Verlag

Hannes Stoppel, Benjamin Rott

Die Huffman-Codierung

Bei „Codierung von Daten denkt man häufig ans Verschlüsseln auch im Kontext Schule (vgl. Stoppel/Rott 2016). Codierung spielt jedoch auch beim Komprimieren von Daten eine mindestens ebenso große Rolle, etwa bei Bildern im JPG- und Filmen im MPEG-Format. Diese Perspektive ist für die hier geschilderte Unterrichtssequenz maßgeblich.
Die Huffman-Codierung
Codierung und Kryptografie gehören zu den Standardthemen der Informatik in der Sekundarstufe (vgl. Hromkovic 2018). Ein Beispiel ist hier die Huffman-Codierung; sie ermöglicht eine effektive Komprimierung von Daten, weil häufig auftretende Zeichen einer Nachricht mit kürzeren Codes belegt werden als selten auftretende Zeichen. Dies wird oft genutzt, z.B. bei Bildern und Filmen (s.o.). Das spart auf dem Computer Speicherplatz und hilft bei der Übertragung.
Die Huffman-Codierung lässt sich gut in den Mathematikunterricht einbinden. Sie wird jedoch häufiger im Informatikunterricht der Sekundarstufe II behandelt (vgl. Hubwieser u. a. 2010 sowie Kempe/Grimm 2013), wobei der Schwerpunkt auf das Programmieren gelegt wird und die Mathematik manchmal etwas zu kurz kommt. Dies lässt sich umkehren: der Schwerpunkt der hier vorgestellten Unterrichtssequenz liegt auf der Mathematik und die Anwendung in der Informatik ist optional. Im Mathematikunterricht kann dieses Thema bereits gegen Ende der Sekundarstufe I behandelt werden. Eine Ergänzung durch Anwendung in der Informatik ist z.B. durch Exkurse immer noch möglich.
Der Einsatz im Unterricht
Das Ziel der Unterrichtssequenz ist die Einführung in die Huffman-Codierung. Dabei soll genauer auf den Algorithmus zur (De-)Codierung eingegangen werden.
Die Behandlung der Huffman-Codierung ermöglicht eine beispielgebundene Auseinandersetzung mit Algorithmen. Von Vorteil ist auch, dass für ein Verständnis des Verfahrens lediglich geringe Vorkenntnisse vonnöten sind. Schließlich spricht für dieses Thema, dass Schülerinnen und Schüler nach unserer Erfahrung großes Interesse an der Codierung sowie der Decodierung besitzen, da dieser Themenkomplex im täglichen Leben zunehmend an Bedeutung gewinnt; nicht zuletzt taucht es zunehmend in den Medien im Zusammenhang mit der Sicherheit von Computern auf.
Ein Reiz des Huffman-Algorithmus liegt darin, dass Algebra und Graphentheorie miteinander vereint werden. Mithilfe eines Baums stellt sich der eigentlich komplexe Algorithmus übersichtlich und verständlich dar. Für Schülerinnen und Schüler zeigt sich eine Kombination sonst voneinander getrennter Bereiche der Mathematik.
Die Unterrichtsreihe ist so geplant, dass Arbeitsblatt 1 und Arbeitsblatt 2 in je einer Unterrichtsstunde oder beide in einer Doppelstunde bearbeitet werden können. Lässt man die Lernenden in Kleingruppen arbeiten, können sie sich bei Schwierigkeiten gegenseitig helfen. Arbeitsblatt 3 kann auf eine oder zwei Unterrichtsstunden verteilt werden; je nachdem, wie umfangreich man die Lösungen der Aufgaben erwartet.
Stehen Computer zur Verfügung, ist eine Ausdehnung der Unterrichtssequenz möglich. Auch hier gibt es gute Möglichkeiten zur Binnendifferenzierung.
Aufgaben & Lösungswege
In der Einleitung von Aufgabe1 wird die Anwendung eines Algorithmus zur Codierung motiviert. Anschließend wird der erste notwendige Schritt der Huffman-Codierung durchgeführt: eine Sortierung der Zeichen der Nachricht nach ihrer absoluten Häufigkeit. Damit werden die Voraussetzungen für die Anwendung des Huffman-Algorithmus geschaffen. Die Lösung der Tabelle sieht wie in Tab.1 aus.
Um das Verfahren zu üben, wird es in Aufgabe 2 anhand einer anderen Nachricht wiederholt; die Ergebnisse aus Aufgabe 2 werden in den Aufgaben 4 und 8 wieder aufgegriffen.
In den Aufgaben 1 und 2 wurden die Voraussetzungen zur Durchführung des Huffman-Algorithmus geschaffen. Eine konkrete Umsetzung dieses Algorithmus wird beginnend mit Aufgabe 3 angeleitet. In eigenständiger Arbeit...

Friedrich+ Deutsch

Sie sind bereits Abonnent?

Jetzt anmelden und sofort lesen

Jetzt weiterlesen mit Friedrich+ Mathematik!

  • Digitaler Vollzugriff auf die Inhalte der Zeitschriften mathematik lehren und Mathematik 5–10
  • Intuitive Benutzeroberfläche mit thematischer Struktur und intelligenter Suche
  • Jährlich über 100 neue didaktische Beiträge, Unterrichtseinheiten, Arbeitsblätter, Bastelvorlagen, Bildmaterial, Methodenkarten, Aufgaben, Tests und vieles mehr

30 Tage kostenlos testen

Mehr Informationen zu Friedrich+ Mathematik

Fakten zum Artikel
aus: Mathematik lehren Nr. 219 / 2020

Codieren & Verschlüsseln

Friedrich+ Kennzeichnung Unterricht (> 90 Min) Schuljahr 9-13