Informationstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:28 Mi 10.12.2008 | | Autor: | alkan |
Hinweis:
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.matheboard.de/thread.php?threadid=383707
http://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=113363
Ich suche Hinweise, Tipps, Lösungsansätze zu einem informationstheoretischen Problem, das sich schlecht einem bestimmten mathematischen Gebiet zuordnen lässt und auch etwas unüblich erscheint. Dies ist wohl auch der Grund, weshalb mir in den beiden Foren, wo ich die Frage bereits gestellt habe, bislang niemand geantwortet hat.
Ich wäre bereits sehr dankbar, wenn mir nur schon jemand mitteilen könnte, ob das Problem so eigentlich verständlich ist und ob es überhaupt lösbar ist.
Praktische Problembeschreibung:
-------------------------------------------------------
Gegeben ist ein Bestand von n gleich grossen Datenblöcken a, b, c, ...
Von diesem Bestand können wir die Blöcke sowohl einzeln als auch beliebige XOR-Verknüpfungen davon entnehmen. Beispielsweise können wir uns von einem Hosting-Server a xor b aber auch b xor c xor z zusenden lassen. Egal aus wie vielen Originalblöcken sich eine Kombination zusammensetzt, sie weist immer die Grösse der Originalblöcke auf.
Uns steht aber nur ein limitiertes Datenvolumen zur Verfügung (bzw. wir möchten dieses so niedrig wie möglich halten), so dass wir danach bestrebt sind, möglichst wenige Blockkombinationen anzufordern.
Das Ziel ist nun, einen Algorithmus zu finden, der uns für eine vorgegebene Anzahl Blockdownloads Vorschläge präsentiert, welche Blockkombinationen wir anfordern sollten, damit folgende Voraussetzungen erfüllt werden:
1) Durch XOR-Verknüpfung der erhaltenen Blockkombinationen untereinander lassen sich möglichst viele verschiedene neue Blockkombinationen generieren, die sich aus nicht mehr als aus einer vorgebenen Anzahl (z.B. 0.1*n) von Ursprungsblöcken zusammen setzen.
(Wenn der Gesamtbestand bspe. die Blöcke a, b, c und d enthält und wir die Kombinationen a xor d sowie b xor c xor d erhalten, können daraus den Block a xor b xor c bilden, welcher ja eine Verknüpfung von 75% der im Ursprungsbestand enthaltenen Blöcke ist. Das Ziel ist nun, diese Prozentzahl zu minimieren.)
2) Die so generierten Blockkombinationen müssen jeweils einer zufälligen Kombination der Originalblöcke entsprechen; d.h. jeder Originalblock soll darin im Durchschnitt mit der gleichen Häufigkeit vorkommen. Es sollte also eine natürliche Häufigkeitsverteilung (Gauss) resultieren. Zudem sollten die gebildeten Kombinationen unabhängig voneinander sein und aussehen, als wären sie jeweils durch zufällige Ziehung von höchstens 0.1n Original-Blöcken entstanden.
Mein Ziel ist es, die angegebenen Kritierien möglichst gut zu erfüllen, da ich bezweifle, dass es eine perfekte Lösung gibt.
Beispiel für eine schlechte Lösung:
--------------------------------------------
1) Wir entnehmen dem Bestand k Kombinationen, die die XOR-Verknüfung von jeweils n/2 zufällig Blöcken darstellen.
Ist k genügend gross gewählt, so lassen sich durch (zufällige) Verknüpfung der Kombinationen eine immense Zahl von neuen, ebenfalls zufällig aussehenden, Kombinationen bilden.
Das Problem dieses Ansatzes ist aber, dass die resultierenden Kombinationen im Durchschnitt ebenfalls n/2 Blöcke enthalten wird.
Auch wenn wir nicht immer n/2 Blöcke entnehmen, sondern die Anzahl der in der Kombination verwendeten Blöcke variieren, kommen wir dem Ziel nicht näher.
Es ist klar, dass eine Lösung nur dann erreicht werden kann, wenn die entommenen Blockkombinationen auf welche Art auch immer von einander abhängen. Diese Abhängigkeit sollte dann aber in den resultierenden Blockkombinationen wieder möglichst verschwinden.
"Versuch" einer mathematischen Beschreibung (leider ohne Formeleditor)
--------------------------------------------------------------------------------------------------
Zur Terminologie:
- ¦M¦ steht für die Mächtigkeit der Menge M resp. für die Anzahl ihrer Elemente
- e bedeutet "Element von"
- ^ steht für "und"
- P(A) ist die Potenzmenge von A
- A c B bedeutet "A ist Teilmenge von B"
- xor(X, Y) steht für die symmetrische Differenz zwischen den Mengen X und Y.
- XOR(M) bezeichnet die symmetrische Differenz sämtlicher Elemente (die selber auch wieder Mengen sind) von M.
Allgemeines:
- D ist eine Menge von allen möglichen Datenblöcken der Grösse g
- A c D ist eine bestimmte Menge von Datenblöcken und dient als Eingabegrösse für den gesuchten Algorithums Ag
- c1, c2 sind vorgegebene Systemparameter von Ag
- ¦R¦ ist ein Wert, der für die Güte der Lösung steht, die unser Algorithmus Ag im konkreten Fall (d.h. für eine bestimmte Menge A)liefert. Je grösser ¦R¦, desto besser ist unser Algorithums.
Gesucht ist nun ein Algorithmus (resp. Funktion) Ag: D -> P(D);
Ag(A, c1, c2) ¦-> T mit folgenden Eigenschaften:
1) T c P(A)
2) ¦T¦ < c1
3) ¦R¦ = max.
4) Die Elemente von R sehen gesamthaft betrachtet aus, als wären sie jeweils durch zufällige Ziehung von höchstens c2 Elementen von A entstanden. M.a.W.: die üblichen Tests für Pseudozufallsgeneratoren müssen erfolgreich angewendet werden können.
wobei:
R c Y
Y = {y¦(y e X)^(¦y¦ <= c2)}
X = {XOR(I1), XOR(I2), ..., XOR(In)}, wobei I1..In
die durchnummerierten Elemente der Menge P(T) darstellen. (maximale
Indexmenge?)
-----------------------------------
hier noch in umgekehrter Reihenfolge, in Worten, und hoffentlich etwas klarer:
Wir betrachten zunächst die Menge P(T) und bezeichnen ihre (sämtlichen) Elemente mit I1 bis In.
(I ist dann also die maximale Indexmenge von P(T), oder nicht?).
Dann bilden wir die Menge X = {XOR(I1), XOR(I2), ..., XOR(In)} und betrachten schliesslich die Menge Y = {y¦(y e X)^(¦y¦ <= c2)}, also eine Teilmenge von X, deren Elemente (ihrerseits ja Mengen) aus höchstens c2 Elementen bestehen.
Die Eigenschaft, die es zu maximieren gilt, ist nun die Grösse der Teilmenge ¦R¦, wobei R eine solche Teilmenge von Y ist, deren Elemente (ihrerseits Mengen) nach einer Serie von Zufallsziehungen von nicht mehr als c2 Elementen von A aussehen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Do 25.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
