Aufgabe:
Text erkannt:
Sei \( A \) ein beliebiges Alphabet mit \( |A|>2 . \) Definieren Sie die in den folgenden Teilaufgaben die in natürlicher Sprache spezifizierten Dinge formal korrekt. Nutzen sie hierfür keine natürliche Sprache, mit Ausnahme folgender Begriffe: ,"für alle \( ^{\prime \prime} \quad \),es gibt (ein) \( ^{\prime \prime} \), bzw. , gibt es (ein) \( ^{\prime \prime} \)
a) Für ein Wort \( w \in A^{*} \) definieren wir das von \( w \) induzierte Teilalphabet \( A_{w} \) als die Menge aller Zeichen die sowohl in \( A \) als auch in \( w \) enthalten sind. Definieren Sie \( A_{w} \)
b) Eine Verallgemeinerung der Zeichenhäufigkeitsfunktion \( N_{x}(w) \) auf ganze Mengen \( M \), sodass \( N_{M}(w) \) die gesamte Häufigkeit aller Zeichen \( M \) in \( w \) ergibt. Definieren Sie \( N_{M}(w) \).
c) Für zwei beliebige Mengen von Zeichen, die in \( w \) enthalten sind, gilt, dass die Elemente der größeren Menge insgesamt häufiger in \( w \) vorkommen. Definieren Sie diesen Zusammenhang für entsprechende Mengen aus \( A_{w} \).
d) Sei \( A \) ein beliebiges Alphabet, \( w \in A^{*} \) ein Wort und \( H(w) \) eine Huffman-Codierung von \( w . \) Geben Sie eine geschlossene Formel zur Berechnung von \( |H(w)| \) ohne Verwendung von \( w(i) \) - oder einer äquivalenten Funktion an.
Sei im Folgenden \( w \in A^{*} \) ein Wort, dass die in Aufgabenteil c) spezifizierte Bedingung erfüllt und \( H \) eine Huffman-Codierung von \( w \).
e) Gilt für alle \( x_{1}, x_{2} \in A_{w}:\left|\bar{H}\left(x_{1}\right)\right|=\left|H\left(x_{2}\right)\right| \) ?
- Falls ja: Beweisen Sie.
- Falls nein: Fügen Sie weitere Bedingungen zu \( w \) hinzu, sodass die Behauptung gilt. Formulieren Sie die Bedingungen ebenfalls nach den Kriterien aus a) - \( c \) ). Beweisen Sie, dass die Behauptung aus der Gesamtmenge aller Bedingungen folgt.
Hinweis: Überlegen Sie sich, wie ein Huffman-Baum aussehen muss, damit die Behauptung erfüllt ist.
Problem/Ansatz: Es geht um die Aufgabe d), ist markiert
Ich vermute, dass es wahr ist, weil in einer Menge jedes Zeichen ja maximal 1x vorkommen darf. Das bedeutet, ja, dass jedes Zeichen nur 1 Bit besitzen kann und somit jedes Zeichen eine Kardinalität von 1 hat.
Oder verstehe ich etwas falsch?
Ansonsten würde ich mich über einen Lösungsansatz freuen
Liebe Grüße
