ich habe folgendes Problem, bei dem ich irgendwie den Wald nicht vor Bäumen sehe. Das Problem ist natürlich "übersetzt", d. h. eigentlich handelt es sich nur um ein analoges Problem (Werte in Datenbank-Tabellen, die entlang von bestimmten Pfad das Laden weiterer Werte triggern). Allerdings wird es so, wie ich es dir formuliere wahrscheinlich verständlicher:
Bälle mit verschiedenen Attributen, z. B. Farbe, Gewicht, Oberfläche usw. fallen durch eine Reihe von „Sieben“. Das erste Sieb filtert rote Bälle aus, das zweite Sieb filtert Bälle aus, die schwerer als 100 Gramm sind, das dritte Sieb filtert Bälle aus, die flauschig sind.
Statistisch sind uns die Schnittmengen bekannt: wir wissen z. B., 10 Prozent aller roten Bälle sind flauschig, 50 Prozent aller roten Bälle wiegen mehr als 100 Gramm, 40 Prozent aller Bälle die weniger oder gerade 100 Gramm wiegen sind flauschig.
Außerdem wissen wir, dass beim ersten Sieb 100 rote Bälle durch gekommen sind, wovon nur 50 Bälle das zweite Sieb passieren konnten (eben nach der Statistik:50 Prozent aller roten Bälle wiegen mehr als 100 Gramm).
Bei Sieb 3 kommen also 50 Bälle an. Wir wissen, dass diese Bälle alle weniger oder gleich 100 Gramm wiegen. Nach der Statistik wären hiervon 20 Bälle flauschig (40 Prozent der 50 ankommenden Bälle). Auf der anderen Seite wissen wir, dass alle Bälle rot sind. Nach der Statistik wären also nur 5 Bälle flauschig (10 Prozent der ankommenden roten Bälle).
Welche richtige Statistik muß angewendet werden? Wie kann man richtig berechnen (mit dem Wissen, dass wir haben), wie viele der ankommenden Bälle flauschig sind?
vielleicht kann mir jemand einen Tip geben, in welche Richtung ich denken muß.
Vielen lieben dank schon mal im voraus und euch allen noch frohe Ostern
- Chris
bm
11.04.2004, 15:33
Hallo Leute,
ich habe folgendes Problem, bei dem ich irgendwie den Wald nicht vor Bäumen sehe. Das Problem ist natürlich "übersetzt", d. h. eigentlich handelt es sich nur um ein analoges Problem (Werte in Datenbank-Tabellen, die entlang von bestimmten Pfad das Laden weiterer Werte triggern). Allerdings wird es so, wie ich es dir formuliere wahrscheinlich verständlicher:
Bälle mit verschiedenen Attributen, z. B. Farbe, Gewicht, Oberfläche usw. fallen durch eine Reihe von „Sieben“. Das erste Sieb filtert rote Bälle aus, das zweite Sieb filtert Bälle aus, die schwerer als 100 Gramm sind, das dritte Sieb filtert Bälle aus, die flauschig sind.
Statistisch sind uns die Schnittmengen bekannt: wir wissen z. B., 10 Prozent aller roten Bälle sind flauschig, 50 Prozent aller roten Bälle wiegen mehr als 100 Gramm, 40 Prozent aller Bälle die weniger oder gerade 100 Gramm wiegen sind flauschig.
Außerdem wissen wir, dass beim ersten Sieb 100 rote Bälle durch gekommen sind, wovon nur 50 Bälle das zweite Sieb passieren konnten (eben nach der Statistik:50 Prozent aller roten Bälle wiegen mehr als 100 Gramm).
Bei Sieb 3 kommen also 50 Bälle an. Wir wissen, dass diese Bälle alle weniger oder gleich 100 Gramm wiegen. Nach der Statistik wären hiervon 20 Bälle flauschig (40 Prozent der 50 ankommenden Bälle). Auf der anderen Seite wissen wir, dass alle Bälle rot sind. Nach der Statistik wären also nur 5 Bälle flauschig (10 Prozent der ankommenden roten Bälle).
Welche richtige Statistik muß angewendet werden? Wie kann man richtig berechnen (mit dem Wissen, dass wir haben), wie viele der ankommenden Bälle flauschig sind?
vielleicht kann mir jemand einen Tip geben, in welche Richtung ich denken muß.
Vielen lieben dank schon mal im voraus und euch allen noch frohe Ostern
- Chris
Widerspruch in sich. Überarbeite das nochmal.
nobody
11.04.2004, 15:54
ja, vielleicht ein bißchen mißverständlich formuliert.
Das erste Sieb läßt nur rote Bälle durch, alle anderen Bälle werden "verworfen". Durch dieses Sieb kommen 100 Bälle durch (wieviel bei diesem Sieb zunächst ankommen, ist doch unerheblich, oder irre ich mich?). Diese 100 Bälle landen dann bei Sieb 2, das "schwere" Bälle "verwirft" und leichte Bälle passieren läßt. 50% werden verworfen und 50% kommen durch, also kommen bei Sieb 3 noch 50 Bälle an. Diese sind rot und leicht.
Die Statistik sagt: zum einen sind alle Bälle rot und 10% aller roten Bälle sind flauschig. Deswegen müßten 5 Bälle Sieb 3 passieren können. Zum anderen sind 40% aller leichten Bälle flauschig, also müßten 20 Bälle Sieb 3 passieren können.
Wieviele Bälle passieren Sieb 3 tatsächlich?
Mein Ansatz war übrigens: in Sieb 2 wurden ja bereits einige rote, flauschige Bälle verworfen, weil sie schwer waren. Aber wieviele? Und wie ändert das die "wirksame" Statistik?
bm
11.04.2004, 18:03
Die Aufgabe ist so nicht eindeutig lösbar :
Annahme 1
Sieb 1 : 100 rote Bälle, davon (10 schwer und flauschig), (40 schwer und glatt), (50 leicht und glatt)
Sieb 2 : (50 leicht und glatt) kommen durch
Sieb 3 : es kommen keine flauschigen an
Annahme 2
Sieb 1 : 100 rote Bälle, davon 50 schwer und glatt, 10 leicht und flauschig, 40 leicht und glatt
Sieb 2 : (10 leicht und flauschig), (40 leicht und glatt) kommen durch
Sieb 3 : (10 leicht und flauschig) kommen durch
Sieb 3 lässt also 0 - 10 Bälle passieren.
Orange markierte Zahlen getauscht.
nobody
12.04.2004, 16:54
Die Aufgabe ist so nicht eindeutig lösbar :
...
Sieb 3 lässt also 0 - 10 Bälle passieren.
hhhmmm... eine solche Worst-Case-Abschätzung hilft ja auch schon mal weiter. Aber andererseits: welche statistischen Daten wären erforderlich, um das Problem vollständig zu lösen?
Allerdings verstehe ich gerade auf Anhieb nicht genau, wie du auf die Annahmen gekommen bist. Kannst du nochmal erklären, wie sich die Zahlen zusammensetzen? (Eigentlich bin ich ja net so doof, aber hier stehe ich auf dem Schlauch...)
übrigens vielen vielen dank schon mal für die Hilfe! Super...
liebe Grüße und schöne Rest-Ostern
- Chris
bm
12.04.2004, 17:23
Die Annahmen sind einfach so konstruiert, dass sie den maximalen Spielraum abdecken, ohne in Widerspruch zu den Vorgaben zu stehen.
Um die Aufgabe eineindeutig zu machen, müsste noch die statistische Gleichverteilung der Eigenschaften Masse und Oberfläche gegeben sein.
Wenn dem so wäre
Die Statistik sagt: zum einen sind alle Bälle rot und 10% aller roten Bälle sind flauschig.
würde die Aussage
Deswegen müßten 5 Bälle Sieb 3 passieren können.
stimmen.
Scheintoter
12.04.2004, 18:30
Am besten presst man das alles in Formeln:
f:= flauschig
s:= schwer
r:= rot
P(x):= Relativer Anteil an Bällen die x sind
N(x):= Anzahl an Bällen die x sind
N() = Anzahl aller Bälle
+ := logisches und
- := logisches nicht
Daraus folgt: N(x) = N()*P(x)
Wir wissen:
10 Prozent aller roten Bälle sind flauschig
Das macht: 0,1 = P(f+r)/P(r) = N(f+r)/N(r)
50 Prozent aller roten Bälle wiegen mehr als 100 Gramm
0,5 = P(s+r)/P(r) = N(s+r)/N(r)
40 Prozent aller Bälle die weniger oder gerade 100 Gramm wiegen sind flauschig
0,4 = P(f+-s)/P(-s) = (P(f)-P(f+s))/(1-P(s)) = (N(f)-N(f+s))/(N()-N(s))
ersten Sieb 100 rote Bälle durch gekommen
100 = N(r)
Wenn man das oben umformt erhält man:
N(r) = 100
N(f+r) = 0,1 * N(r) = 10
N(s+r) = 0,5 * N(r) = 50
2,5*N(f) + N(s) = N()+ 2,5*N(f+s)
Jetzt kann man sich beliebige Werte für die Gleichungen aussuchen, solange dür jedes möglich x und y gilt: N(x+y) ≤ N(x)
Insbesondere heißt das: N(s+f+r) ist kleiner als jeder andere Wert also kleiner als 10.
Dazu muss man annehmen, dass die Anzahl eine Natürliche Zahl ist.
Ich hoffe ich habe keinen Rechenfehler gemacht habe und die Rechnung so richtig ist.
nobody
12.04.2004, 20:03
Die Annahmen sind einfach so konstruiert, dass sie den maximalen Spielraum abdecken, ohne in Widerspruch zu den Vorgaben zu stehen.
klar... die Frage ist, ob es irgendeinen algorithmischen Weg gibt, solche Annahmen zu treffen, die zum Worst-Case-Ergebnis führen, und das allgemein, also nicht nur für *diese* statistischen Werte, sondern allgemein.
Das sieht dann so aus: wir haben eine Reihe von Filtern f_1 bis f_n, wobei diese hintereinander geschaltet sind.
I→f_1→f_2...f_{n-1}→f_n→O
Den Filtern f_i (1≤i≤n) sind Mengen M_i zugeordnet. Die Filter haben als Eingabe eine Menge und liefern als Ausgabe die Schnittmenge zwischen der Eingabe-Menge und der dem Filter assoziierten Menge.
Wir kennen die Mächtigkeiten der Schnittmengen sich jeweils zwei Filter-Mengen (|M_i∩M_j|; 1≤i,j≤n) untereinander und die Mächtigkeit der einzelnen Mengen |M_i|. Allerdings kennen wir nicht die Mächtigkeit von Schnittmengen von mehr als zwei Grundmengen, d. h. |M_i∩M_j∩M_k|; 1≤i,j,k≤n ist schon unbekannt.
Außerdem kennen wir die Mächtigkeit der Ausgabe-Mengen aller Filter d. h. |f_1(I)|, |f_2(f_1(I))|... die Mächtigkeit von I kennen wir allerdings nicht.
Um die Aufgabe eineindeutig zu machen, müsste noch die statistische Gleichverteilung der Eigenschaften Masse und Oberfläche gegeben sein.
Wenn dem so wäre (Die Statistik sagt: zum einen sind alle Bälle rot und 10% aller roten Bälle sind flauschig.), würde die Aussage (Deswegen müßten 5 Bälle Sieb 3 passieren können. )stimmen.
Warum gerade diese Ausgabe und nicht die andere?
Liebe Grüße
- Chris
bm
12.04.2004, 20:34
40 Prozent aller Bälle die weniger oder gerade 100 Gramm wiegen sind flauschig.
Ich nehme an, Du meinst diese Aussage.
Sie bezieht sich auf alle Farben und ist daher nur für die roten nicht anwendbar. Es sei denn, ...müsste noch die statistische Gleichverteilung der Eigenschaften..., s.o.
klar... die Frage ist, ob es irgendeinen algorithmischen Weg gibt, solche Annahmen zu treffen, die zum Worst-Case-Ergebnis führen, und das allgemein, also nicht nur für *diese* statistischen Werte, sondern allgemein.
Gibt es sicher, ich habe einfach über das Problem nachgedacht und bin empirisch zu diesem Ergebniss gekommen.
Scheintoter
12.04.2004, 21:54
Wenn nur |Mi∩Mj| und |Mi| gegeben ist, dann ist die einzige Aussage die man über |M1∩M2∩M3∩...| treffen kann:
|M1∩M2∩M3∩...| ≤ |Mi∩Mj|, wobei i und j die selben Indizes wie der gesuchte Schnitt annehmen kann.
nobody
12.04.2004, 22:26
Wenn nur |Mi∩Mj| und |Mi| gegeben ist, dann ist die einzige Aussage die man über |M1∩M2∩M3∩...| treffen kann:
|M1∩M2∩M3∩...| ≤ |Mi∩Mj|, wobei i und j die selben Indizes wie der gesuchte Schnitt annehmen kann.
super! Hört sich auf den ersten Blick einleuchtend an.
Kann man das beweisen?
Und: wenn ich mehr statistische Daten hätte, kann ich dann noch genauer abschätzen (außer statistische Daten über "3er-Schnitte", "4er-Schnitte" usw., das scheint klar zu sein). Gibt es auch eine untere Schranke? Last but not least: kann man irgendwie einen Erwartungswert (Average-Case-Analyse) für |O| berechnen?