Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in KOD-AQ

Beantwortet: Fehler

Wed, 10 Feb 2016 16:45:43 +0000

Hallo ugemt!

Falls deine Huffman-Codierung die gleiche Länge wie die in der Musterlösung hat, dann ist auch deine Lösung korrekt!

Um ein gegebenes Wort dekodieren zu können, musst du aber wissen, wie die verwendete Codierung genau aussieht (bildlich gesprochen: ob bei der Erstellung der Huffman-Codierung die Nullen oder die Einsen links oder rechts an die Pfeile geschrieben wurden). Siehe dazu auch : http://info2.aifb.kit.edu/qa/index.php?qa=4122&qa_1=fehler-verst%C3%A4ndnis

Eine solche Aufgabe (Huffman-Codierung aus gegebener Wahrscheinlichkeitsverteilung für ein Eingabealphabet bestimmen und anschließend ein gegebenes kodiertes Wort dekodieren) kann somit in der Klausur nicht drankommen, da sie nur die Studenten richtig lösen könnten, die zufällig genau die Huffman-Codierung wie in der Musterlösung erstellt haben.

Es kann aber durchaus sein, dass ihr mit eurem eigenen Huffman-Code verschiedene Wörter codieren müsst!

Viele Grüße,
Janine (Tutorin)

Beantwortet: Fehler Verständnis

Wed, 10 Feb 2016 14:42:12 +0000

Hallo ugemt,

Huffman-Kodierungen sind nicht eindeutig, d.h. es gibt durchaus mehrere richtige Lösungen. Wichtig ist nur, dass die Kodierung minimal ist und die Fano-Bedingung erfüllt ist. Du könntest aber z.B. alle 0er und 1er in deiner Kodierung tauschen und hättest trotzdem eine gültige Huffman-Kodierung.

Wenn du nun aber ein Wort dekodieren möchtest, musst du das mit der gleichen Huffman-Kodierung machen, mit der du das Wort kodiert hast.

Folglich musst du bei dieser Aufgabe für den b)-Teil die Kodierung aus a) aus der Musterlösung verwenden.

Viele Grüße,

Tim (Tutor)

Beantwortet: Wäre Aufgabe mit Codierung&Decodierung so in Klausur ?

Thu, 13 Nov 2014 16:07:49 +0000

Zunächst mal zum Thema:

"Sprich alle Blätter oben und die Wurzel unten"

Der Algorithmus sagt doch nichts darüber aus, wohin man die Wurzel malt. Die Bäume mit Wurzel oben sind absolut äquivalent zu denen mit Wurzel unten. Wir haben uns entschieden, im Pool die Wurzel nach oben zu malen, weil die Bäume dann übersichtlicher gezeichnet werden können. Ich hoffe, Sie lassen sich davon nicht verwirren!

Ansonsten haben Sie aber recht, so eine Aufgabe wäre in der Klausur nicht denkbar, da man eine spezielle Lösung des a-Teils braucht, um den b-Teil korrekt zu lösen. (Auch im Pool finde ich das jetzt, wo Sie es sagen, nicht ganz optimal...)

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: Warum werden die Bits beim decodieren gekippt?

Thu, 13 Nov 2014 16:03:53 +0000

Oh ja, da haben Sie auch wieder recht, das ist immer noch fehlerhaft! (Man muss da nichts kippen...)

Sie beziehen sich auf den b-Teil, oder? Dort ist die Änderung an der Kodierung aus dem a-Teil offenbar noch nicht angepasst. Wir werden das am Montag korrigieren. (Der a-Teil ist meines Erachtens korrekt, und K ist dort auch richtig mit 01 kodiert.)

Aber:

Wir stellen gerade fest, dass bei der Diskussion hier etwas durcheinander geraten ist. Um weitere Verwirrung zu vermeiden, jetzt nochmal klipp und klar: Theoretisch wäre die Lösung mit dem Kippen auch ok, da es aber nicht explizit in der Aufgabenstellung steht, haben wir diesen Gedankengang gelöscht.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Kommentiert: Invertieren zum decodieren - Fehler in Lösung?

Thu, 13 Nov 2014 15:59:39 +0000

Sie haben recht, wir werden den Teil b anpassen.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König