Aufgabenblock — AFB III
Begründen statt nur rechnen: widerlegen, verallgemeinern und beurteilen. Formulieren Sie Ihre Antwort zuerst selbst in ganzen Sätzen, bevor Sie die Musterlösung aufklappen.
Widerlegen Sie die Behauptung: „Ein gutes verlustfreies Verfahren macht jede Datei kleiner.“
Hinweis: Zählen statt rechnen.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Es gibt \(2^{n}\) Dateien mit genau \(n\) Bit, aber nur \(2^{0}+2^{1}+\dots+2^{n-1}=2^{n}-1\) kürzere Bitfolgen. Ein verlustfreies Verfahren muss verschiedene Dateien auf verschiedene Ergebnisse abbilden, sonst ließe es sich nicht umkehren. Also bleibt mindestens eine Datei übrig, die nicht kürzer wird — die Behauptung ist falsch.
Beurteilen Sie, ob sich Lauflängencodierung für Farbfotos eignet.
Hinweis: Denken Sie an benachbarte Pixel eines Fotos.
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: In Fotos unterscheiden sich benachbarte Pixel fast immer leicht (Rauschen, Verläufe). Es entstehen fast nur Läufe der Länge 1; jedes Paar kostet dann Anzahl-Bits plus 24 Bit Farbe — mehr als das Original. Lauflänge eignet sich für Grafiken mit großen einfarbigen Flächen, nicht für Fotos.
Begründen Sie, warum jeder aus einem Codebaum abgelesene Code präfixfrei ist.
Hinweis: Wo stehen die Zeichen?
Musterlösung anzeigen (zählt als erledigt)
Musterlösung: Wäre Codewort \(u\) Präfix von \(v\), läge der Knoten von \(u\) auf dem Weg von der Wurzel zu \(v\). Dann hätte er Kinder, wäre also kein Blatt. Zeichen stehen aber nur in Blättern — Widerspruch. Also ist kein Codewort Anfang eines anderen.