Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

3 Pluspunkte 0 Minuspunkte
172 Aufrufe

Hallo,

heute wurde im Tut erwähnt, wie wichtig es ist, die Pfeile bei dem Huffman Baum einzuzeichnen und dass es dort schnell zu Punktabzug kommen kann.

Nun bin ich mir aber nicht sicher in welche Richtung die Pfeile hier gezeichnet werden müssen. In der Lösung zu der entsprechenden Aufgabe zeigen die Pfeile quasi von der Wurzel zu den Blättern (so wie man auch den Code ablesen würde), im Skript bei der Beispielaufgabe zeigen die Pfeile jedoch gerade in die entgegengesetzte Richtung (Siehe Bild). Welche Art der Zeichnung wird in der Klausur als korrekt gewertet?

Vielen Dank

in KOD-AE von updrr updrr Eins-Komma-Null-Anwärter(in) (4.7k Punkte)  
0 0
Was die Richtung der Pfeile angeht, haben Sie recht, dass wir dabei nicht konsistent waren. Herr Schmeck zeichnet die Pfeile so, wie sie in der Originalarbeit von Huffman gezeichnet wurden, nämlich von den Blättern zur Wurzel (entsprechend dem Aufbau des Baums). Bei der Implementierung des XWizards habe ich allerdings nicht so tief recherchiert, sondern fand es einfach intuitiver, wie Sie sagen, die Pfeile in der Richtung zu zeichnen, wie die Wörter abgelesen werden. Vielleicht werde ich das noch ändern, ich weiß aber nicht, ob es eher Verwirrung oder Einsicht stiften würde.

In der Klausur dürfen Sie die Pfeile jedenfalls beliebig setzen (natürlich aber alle in derselben Richtung bitte).

2 Antworten

1 Pluspunkt 0 Minuspunkte

In welche Richtung die Pfeile zeigen, ist uns egal - was der Tutor oder die Tutorin vermutlich meinte, ist, dass es sehr wichtig ist, in welche Richtung die Code-Wörter abgelesen werden. Das ist eigentlich das einzige, was relativ oft beim Huffman falsch gemacht wird. 

Man liest die Codewörter immer von der Wurzel zu den Blättern hin ab. In Ihrem Beispiel wäre das Wort anders herum abgelesen dasselbe, aber das ist im Allgemeinen nicht der Fall! Wenn Sie die Wörter von den Blättern zur Wurzel ablesen, ist die Fano-Bedingung nicht erfüllt, und dafür bekommen Sie sehr empfindliche Punktabzüge.

Das ist also ein sehr unnötiger Fehler, den man leicht vermeiden kann.

von Dozent (10.1m Punkte)  
0 Pluspunkte 0 Minuspunkte
Hallo updrr,

waehrend in den Tutorien und im Uebungsbuch die Pfeilrichtung wie richtig angegeben von der Wurzel in Richtung Blatt geht, so dass wirklich ein binaerer Baum entsteht ist hier der entgegengesetzte weg gewaehlt worden, um die Richtung der Konstruktion und Addition von Wahrscheinlichkeiten anzuzeigen. Der gestrichelte rote Pfeil zeigt ja die Ableserichtung.

Wenn Du bei der Huffmann-Kodierung die Pfeile von der Wurzel zum Blatt anbringst (sodass ein binaerer Baum entsteht), dann ist das sicherlich richtig (und wird auch so gewertet) und auch meine Empfehlung um Missverstaendnissen vorzubeugen. Ggf. gibt es noch genauere Infos.

Marvin (Tutor)
von ucdxg ucdxg Tutor(in) (104k Punkte)  
...