Aufgabe:
Seien n, k с N Zweierpotenzen mit n=> k=>1. Wir betrachten die Menge X aller k-elementigen Teilmengen von {1,..,n}:
X = {X | X c {1,...,n}, |X| = k}:
In dieser Aufgabe beschäftigen wir uns mit Möglichkeiten, ein beliebiges Element von X mit möglichst wenig Bits darzustellen.
a) Beschreiben Sie eine Methode, wie man die verschiedenen Teilmengen X c X mit jeweils n Bits darstellen kann, so dass sich jedes X c X eindeutig identifizieren lässt.
b) Beschreiben Sie eine Methode, wie man die verschiedenen Teilmengen X c X mit jeweils k log n Bits darstellen kann, so dass sich jedes X c X eindeutig identifizieren lässt.
c) Beschreiben Sie eine Methode, wie man die verschiedenen Teilmengen X c X mit jeweils log(n/k) Bits darstellen kann, so dass sich jedes X c X eindeutig identifizieren lasst (hier kommt es hauptsächlich auf die Anzahl der Bits an, eine einfache Kodierung oder Dekodierung sind zweitrangig).
d) Vergleichen Sie die verschiedenen Methoden miteinander. Fur welche Werte von k ist welche Methode am besten geeignet? Verwenden Sie dazu die Abschätzung (n/k) <= (ne/k)^k
Problem/Ansatz:
Ich habe das Thema nicht verstanden, deswegen verstehe ich die Aufgabe gar nicht
