Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frage zu Klausur Herbst 2003 III-5 b)
Ist bei der b) p=1/2 richtig? Hat jemand eine genauere Loesung, irgendwie ist mir das noch nicht so ganz klar, wie s laeuft
ich hab mir das so gedacht:
pa ist die hoechte wahrscheinlichkeit und pd die kleinste.
wenn man den code konstruieren will, fasst man erst die zwei kleinsten zusammen (pd, pc). Im zweiten Schritt entscheidet sich dann was fuer ein Baum entsteht (2 2 2 2) oder (1 2 3 3).
pb ist auf jeden fall der kleinste und muss, damit es zum (1 2 3 3) Baum kommt, mit (pc pd) verdunden werden. Damit das passiert muss pa > pc + pd gelten. Grenzfall ist genau pa = pc + pd. Die Formeln einsetzen und nach p aufloesen.
Ergebnis find ich nicht mehr. 
Wir sollen Parameter p so bestimmen, dass 1pa + 2pb+ 3pc + 3pd auf den optimalen Huffmancode führt.
pa hat Wortlänge 1
pb hat Wortlänge 2
pc hat Wortlänge 3
pd hat Wortlänge 3
die Wortlängen errechnen sich wie folgt:
p² + 2p(1-p) + 3p(1-p) + 3(1-p)²
Der Huffmancode zeichnet sich dadurch aus, keine Redundanz mehr zu haben. Vier verschiedene Symbole kann man mit 2 Bits kodieren. Wie muss also das p gewählt werden, dass die mitllere Wortlänge 2 entspricht - wann ist also p² + 2p(1-p) + 3p(1-p) + 3(1-p)² <= 2
p² + 2p(1-p) + 3p(1-p) + 3(1-p)² <= 2
p+p² >= 1
da kommt raus p >= (-1 + √5) / 2 (und das ist, welch Überraschung der goldene Schnitt - 1)
PS.: Das war die Lösung die der Strehl uns präsentiert hatte. Ich wäre da auch nicht drauf gekommen.