0 Daumen
285 Aufrufe

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

Avatar von

Jo das ist nicht fair, dass du die ganzen Fragen 1:1 hier aus dem Kurs postest - das sind keine Verständnisfragen mehr. Ich habe dich gemeldet.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community