Dreißig Übungen zu Lauflänge, Huffman und Übertragung: rechnen, Bäume prüfen und Verfahren beurteilen.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen in gemischter Reihenfolge — du klickst, ziehst, ordnest, rechnest und knobelst. Jede Übung gibt dir sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fährst du über ein unterstrichenes Arbeitswort, siehst du, was es genau von dir verlangt.
A1
Läufe zählen und notieren
AFB I
Stelle die Lauflängencodierung der Zeichenfolge iiiiiaaaaooooooooxx in der Notation Anzahl-Wert dar und fülle die Felder aus.
Fülle alle Felder aus und prüfe dann auf einmal. Enter prüft ebenfalls.
Die Folge hat Läufe, der längste Lauf hat die Länge . Die vollständige Codierung lautet und besteht aus Zeichen.
Die Folge besteht aus 5 i, 4 a, 8 o und 2 x: vier Läufe. Anzahl vor Wert ergibt 5i4a8o2x, das sind 8 Zeichen statt 19.
Jeder Wechsel zu einem anderen Zeichen beginnt einen neuen Lauf: Zähle zuerst die Läufe und dann ihre Längen.
Schreibe für jeden Lauf zuerst die Anzahl und dann das Zeichen, ohne Leerzeichen hintereinander. Die Zeichen der Codierung zählst du am Ende.
A2
Verschlüsseln und komprimieren
AFB IIMix
Untersuche, wie sich Verschlüsselung und Kompression beeinflussen: Entscheide bei jeder Aussage, ob sie stimmt.
6 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 6
Caesar ändert nur, welcher Buchstabe wofür steht: Häufigkeiten und Läufe bleiben erhalten. Vigenère zerstört Läufe, weil der Schlüssel wechselt. Ohne Codetabelle ist ein Huffman-Bitstrom nicht lesbar.
Überlege bei jeder Aussage, was die Verschlüsselung ändert: die Buchstaben selbst oder ihre Häufigkeiten und ihre Reihenfolge.
Caesar ordnet jedem Buchstaben immer denselben Geheimbuchstaben zu, Vigenère wechselt mit jeder Stelle des Schlüsselworts.
A3
Ein Baum mit vertauschten Blättern
AFB III
Für ein Wort mit den Häufigkeiten A 10, B 6, C 4, D 3 und E 1 hat ein Schüler diesen Codebaum gezeichnet (links 0, rechts 1; neben jedem Zeichen steht seine Häufigkeit). Durch genau einen Tausch zweier Blätter wird der Baum optimal. Bewerte ihn an der Gesamtbitzahl: Klicke zuerst das Zeichen an, das häufig vorkommt, aber ein zu langes Codewort hat, und dann das Zeichen, mit dem es getauscht werden muss.
Klicke die gesuchte Stelle an. Mit der Tastatur: Tab oder Pfeiltasten zum Wandern, Enter zum Auswählen.
A (10×) liegt mit 3 Bit tief im Baum, C (4×) mit nur 1 Bit direkt unter der Wurzel. Der Tausch senkt die Gesamtbitzahl von 10·3 + 6·2 + 4·1 + 3·4 + 1·4 = 62 auf 10·1 + 6·2 + 4·3 + 3·4 + 1·4 = 50 Bit, und das ist die Huffman-Länge. Ein Tausch von A mit B ergäbe 58 Bit.
Das häufigste Zeichen gehört so nah wie möglich an die Wurzel: Suche zuerst, wo A steht und wie viele Bit sein Codewort hat.
Das Blatt direkt unter der Wurzel hat das kürzeste Codewort (1 Bit), trägt hier aber nur die kleine Häufigkeit 4. Tausche A dorthin und prüfe die Summe der Produkte Häufigkeit · Codelänge.
