Anz.Mögl.Mengen(Kombinatorik) < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:20 Mi 18.07.2007 | | Autor: | kennydd |
| Aufgabe | Ich beobachte in einem Forum 9 verschiedene Pseudonyme (a,b,c,d,e,f,g,h,i). Diese können voneinander verschieden sein, aber auch zu ein und der selben Person gehören. Wieviele mögliche Kombinationen (Kombinatorik) für die Verkettung der Pseudonyme gibt es?
Durch langfristige Beobachtungen der Nutzeraktivitäten können folgende Aussagen zusätzlich getroffen werden.
Aussage1: a [mm] \not= [/mm] d [mm] \not= [/mm] f [mm] \not= [/mm] h
Aussage2: a [mm] \not= [/mm] b
Aussage3: g [mm] \not= [/mm] i
Aussage4: c = e
Für jede Aussage sinkt die Zahl möglicher Kombinationen! Wie sieht dies Mathematisch ausgedrückt aus, wenn alle Aussagen einbezogen werden?
|
=======ANSATZ================================
Grundaussage:
Menge={a,b,c,d,e,f,g,h,i} entspricht 9! Kombinationen bei Eintrittswahrscheinlichkeit von 1/9!
mit Aussage1:
durch Aufhebung möglicher Beziehungen zwischen a,d,f,h ergeben sich 4 mögliche Teilmengen
M1={a,b,c,e,g,i} zu 6! Möglichkeiten
M2={d,b,c,e,g,i} zu 6! Möglichkeiten
M3={f,b,c,e,g,i} zu 6! Möglichkeiten
M4={h,b,c,e,g,i} zu 6! Möglichkeiten
Damit reduzieren sich die Möglichkeiten von 9! auf 4*6!
mit Aussage2: (a ungleich b)
wird Menge M1 gesplittet in 2 Mögliche Untermengen
M1' ={a,c,e,g,i} zu 5! Möglichkeiten
M1''={b,c,e,g,i} zu 5! Möglichkeiten
damit wird die Gesamtzahl an Möglichen Kombinationen weiter gesenkt auf
2*5! + 3*6! RICHTIG ????
mit Aussage3 wird analog vorgegangen so das gilt:
4*4! + 6*5!
durch Aussage4:
c und e gehören zu einem Nutzer also c=e können wir diese Substituieren...
also c,e = ce und somit unsere Teilmengen um jeweils 1 Element reduzieren.
Dadurch komm ich auf folgendes Ergebnis
Kombinationen = 4*3! + 6*4! = 168
=> Unter Berücksichtigung der Aussagen gibt es statt 9! = 362880 Kombiationen für die Anordnung der Pseudonyme nur noch 168 mögliche Anordnungen... wobei jede dieser mit einer Wahscheinlichkeit von 1/168 Eintreten kann.
So das ist mein aktueller Lösungsansatz... ich bitte euch mir zu helfen und mal darüber zuschauen.
HINTERGRUND der Aufgabenstellung ist die Mathematische Hinterlegung der folgenden Aussage:
Kann ich über einen längeren Zeitraum das Nutzerverhalten anderer Pseudonyme in einer Online-Community beobachten, dann steigt mit jeder Beobachtung die Möglichkeit, um Bezihungen zwischen den Pseudonymen zu erkennen, da durch jede Beobachtung die Anzahl der Gesamtmöglichkeiten reduziert wird.
Dies soll Beweisen, dass allein die Reduzierung möglicher Beobachtungen zur Förderung der Anonymität in Online-Communitys führt.
Vielen Dank für euere Hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Mi 18.07.2007 | | Autor: | Sax |
Hi,
vielleicht hast Du bis jetzt noch keine Antwort erhalten, weil Deine Fragestellung zu unklar ist.
Zunächst schreibst Du von "9 verschiedenen Pseudonymen a, b, ...", um dann als Aussage 2 "a <> b" zu fordern. Das macht zunächst keinen Sinn.
Die Lösung 9! für die "Grundaussage" ist die Antwort auf folgende Fragestellung : "Wenn es zu diesen 9 Pseudonymen 9 Personen gibt, wie viele Möglichkeiten der Zuordnung zwischen diesen Personen und den Pseudonymen gibt es dann ?" Ist das die Fragestellung ? (Ich glaube nicht, weil ja andererseits darauf hingewiesen wird, dass es auch weniger als 9 Personen sein können.)
Wenn die Aussage 1 bedeuten soll, dass die Pseudonyme a, d, f und h von vier verschiedenen Personen benutzt werden, ist dann die Anzahl möglicher Zurdnungen von Personen zu Pseudonymen für die Fälle, dass es insgesamt 4 Personen, oder 5 Personen, ... , oder 9 Personen sind gesucht, oder was soll berechnet werden ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:40 Do 19.07.2007 | | Autor: | kennydd |
> Hi,
>
> vielleicht hast Du bis jetzt noch keine Antwort erhalten,
> weil Deine Fragestellung zu unklar ist.
>
> Zunächst schreibst Du von "9 verschiedenen Pseudonymen a,
> b, ...", um dann als Aussage 2 "a <> b" zu fordern. Das
> macht zunächst keinen Sinn.
===================================
- also Grundannahme des Angreifers 9 verschiedene Personen was zu 9! Möglichkeiten führt
- alle weiteren Annahmen erweitern das Wissen der Grundannahme Schrittweise.
1. Annahme 1 sagt, dass 4 bestimmte Pseudonyme nur voneinander verschieden auftreten dürfen wodurch die Gesamtzahl an Kombinationen sinkt
=> minimum von 4 und maximum von 9 Personen möglich über die Kombination berechnet wird
2. Annahme 2,3 sagt, dass weitere 2 Pseudonyme voneinander verschieden sind was wiederum die möglichen Gruppierungen senkt
Hier ist ein Wahrscheinlichkeitsbaum mit 4 Nutzern:
ohne Bebachtung / Annahme1 1ungleich2/ Annahme2 1ungleich3
---(1)(3,4) = 3! --- (1)(4) 2!
(1,2,3,4) = 24!-
---(2)(3,4) = 3!
also reduzieren sich bei diesem BSP die Konstellationen von 24! auf 2! + 3!
... das gleiche Prinzipt wollte ich an dem weitauskomplexeren BSP für den Beweis meiner Aussage herleiten
>
> Die Lösung 9! für die "Grundaussage" ist die Antwort auf
> folgende Fragestellung : "Wenn es zu diesen 9 Pseudonymen 9
> Personen gibt, wie viele Möglichkeiten der Zuordnung
> zwischen diesen Personen und den Pseudonymen gibt es dann
> ?" Ist das die Fragestellung ?
JA das ist die Grundfragestellung
> (Ich glaube nicht, weil ja
> andererseits darauf hingewiesen wird, dass es auch weniger
> als 9 Personen sein können.)
Richtig mit jeder Aussage ändern sich die Parameter wobei es unbekannt ist wieviele Personen zwischen 1 und 9 existieren... diese Werten durch die Aussagen ledigich eingegrenzt
>
> Wenn die Aussage 1 bedeuten soll, dass die Pseudonyme a, d,
> f und h von vier verschiedenen Personen benutzt werden, ist
> dann die Anzahl möglicher Zurdnungen von Personen zu
> Pseudonymen für die Fälle, dass es insgesamt 4 Personen,
> oder 5 Personen, ... , oder 9 Personen sind gesucht, oder
> was soll berechnet werden ?
Genau, dies ist der Punkt... wenn ich eine Aussage habe das 4 stck verschieden sind können es nur alle Kombinationen zwischen 4 und 9 Personen auftreten. Und dies wird durch die weiteren Aussagen gesenkt.
ZU BEACHTEN: 1 <> 2 und 1<>3 heißt nicht 2<>3 reduziert minmum anzahl lediglich auf 2 und nicht auf 3
Danke für den Tipp, hoffe das es nun etwas klarer ist...
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:02 Fr 20.07.2007 | | Autor: | kennydd |
| Aufgabe | Grundaussage:
- es sind 9 verschiedene Pseudonyme (a,b,c,d,e,f,g,h,i) bekannt
Fragestellung Teil1:
- Wieviele mögliche Kombinationen (Kombinatorik) für die Verkettung der Pseudonyme gibt es?
Zusatzbetrachtung und Fragestellung Teil2:
Wieviel Kombinationen gibt es wenn alle folgenden Bedingungen zusätzlich zur Grundaussage gelten ...
Aussage1: a [mm] \not= [/mm] d [mm] \not= [/mm] f [mm] \not= [/mm] h
Aussage2: a [mm] \not= [/mm] b
Aussage3: g [mm] \not= [/mm] i
Aussage4: c = e
Für jede Aussage sinkt die Zahl möglicher Kombinationen! Wie sieht dies Mathematisch ausgedrückt aus, wenn alle Aussagen einbezogen werden? |
=======ANSATZ=GRUNDAUSSAGE==============================
Fragestellung Teil1:
Menge={a,b,c,d,e,f,g,h,i} entspricht 9! Kombinationen bei Eintrittswahrscheinlichkeit von 1/9!
=======ANSATZ=AUSSAGE1=================================
a, d, f und h werden von vier verschiedenen Personen genutzt, damit reduziert sich die Betrachtung auf 5-9 Personen und 9 Pseudonymen zu denen die Kombinationen ermittelt werden müssen. Damit reduzieren sich die Möglichkeiten auf ...
4*6! bzw. 4!*5!
Mengennotation:
M1={a,b,c,e,g,i} / M2={d,b,c,e,g,i} / M3={f,b,c,e,g,i} / M4={h,b,c,e,g,i}
=======ANSATZ=AUSSAGE2=================================
sagt zusätzlich zu Aussage 1, dass die Person mit Pseudonym a auf keinen Fall das Pseudonym b nutzen kann und die Person mit Pseudonym b auf keinen Fall das Pseudonym a. Zu den Personen d,f,h kann b jedoch weiterhin zugeordnet werden. Damit senken sich mögliche Kombinationen auf ...
2*5! + 3*6!
Mengennotation: (Menge M1 wird in 2 Submengen geteilt)
M1'={a,c,e,g,i} / M1''={b,c,e,g,i} / M2={d,b,c,e,g,i} / M3={f,b,c,e,g,i} / M4={h,b,c,e,g,i}
=======ANSATZ=AUSSAGE3=================================
wird analog zu Aussage 3 gehandhabt...
Person mit Pseudonym g kann auf keinen Fall das Pseudonym i nutzen und Person mit Pseudonym i kann auf keinen Fall das Pseudonym g nutzen.
damit senken sich mögliche Kombinationen auf
4*4! + 6*5!
Mengennotation: (Menge M2, M3, M4 enthält je beide Elemente und wird in 2 Submengen geteilt)
M1'a={a,c,e,i} / M1''a={b,c,e,i} / M2a={d,b,c,e,i} / M3a={f,b,c,e,i} / M4a={h,b,c,e,i}
M1'b={a,c,e,g} / M1''b={b,c,e,g} / M2b={d,b,c,e,g} / M3b={f,b,c,e,g} / M4b={h,b,c,e,g}
=======ANSATZ=AUSSAGE4=================================
können 2 Pseudonym zu einer Person zugeordnet werden c = e reduzieren sich die Möglichen Elemente, um 1 Element. Dies geschieht indem c,e zu ce substituiert werden, so dass gilt
4*3! + 6*4! = 168
Mengennotation: (für jedes Vorkommen von c,e Substitution zu ce)
M1'a={a,ce,i} / M1''a={b,ce,i} / M2a={d,b,ce,i} / M3a={f,b,ce,i} / M4a={h,b,ce,i}
M1'b={a,ce,g} / M1''b={b,ce,g} / M2b={d,b,ce,g} / M3b={f,b,ce,g} / M4b={h,b,ce,g}
=> Unter Berücksichtigung aller Aussagen gibt es also statt 9! = 362880 Kombiationen für die Anordnung der Pseudonyme nur noch 4*3! + 6*4! = 168, wobei jede dieser mit einer Wahscheinlichkeit von 1/168 Eintreten kann.
Nun stellt sich die Frage ob die Rechnung korrekt ist
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:09 Fr 20.07.2007 | | Autor: | DirkG |
M.E. hat die Grundfragestellung nichts mit Anordnungsmöglichkeiten (Permutationen) der 9 Leute zu tun. Sondern ganz klar mit ![[]](/images/popup.gif) Mengenpartitionen, wie z.B.
[mm] $$\{ \{a,e,f\}, \{b\}, \{c,h\}, \{d\}, \{g,i\} \}$$
[/mm]
usw., jede der Mengen innerhalb dieser Partition (wie z.B. [mm] $\{c,h\}$ [/mm] entspricht dabei einer Person. Wie man die Anzahl solcher Partitionen bestimmt, ist dem verlinkten Wikipedia-Artikel zu entnehmen, konkret käme hier bei der Grundfragstellung (ohne die Zusatzannahmen) der Anzahlwert
[mm] $$B_9=21147$$
[/mm]
heraus.
Gruß,
Dirk
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:51 Mo 23.07.2007 | | Autor: | kennydd |
von Dirk folgt demnächst... ich Kämpfe noch damit die Bedingungen zu integrieren.. ich denke bis Mittwoch hab ich da einen Ansatz
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:28 Mo 23.07.2007 | | Autor: | rabilein1 |
Mein Gott, das ist ja ein richtig langer Thread mit vielen Irrungen und Verwirrungen.
Daher mein Tipp:
Fang doch erst mal klein an = also anstatt mit 9 (a - i) Teilnehmern, nimm zunächst mal 4 (a - d).
Und statt 4 Einschränkunen, untersuche wie sich 1 oder 2 auf das Ergebnis auswirken.
Schritt für Schritt vorwärts tasten. Dann kannst du die gesuchte Formel langsam aber stetig aufbauen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:35 Di 24.07.2007 | | Autor: | DirkG |
> von Dirk folgt demnächst...
Ich verstehe das mal als Aufforderung... 
Nun also zur Anzahl der Partitionen von {a,b,c,d,e,f,g,h,i}, die die Aussagen 1 bis 4 erfüllen. Gemäß Aussage 4 kann man sich auf die Partitionen von {a,b,c,d,f,g,h,i} konzentrieren, da e an c gekoppelt ist.
Seien nun
$A$ ... Menge aller Partitionen von {a,b,c,d,f,g,h,i}
[mm] $A_1$ [/mm] ... Menge der Partitionen mit a=d
[mm] $A_2$ [/mm] ... Menge der Partitionen mit a=f
[mm] $A_3$ [/mm] ... Menge der Partitionen mit a=h
[mm] $A_4$ [/mm] ... Menge der Partitionen mit d=f
[mm] $A_5$ [/mm] ... Menge der Partitionen mit d=h
[mm] $A_6$ [/mm] ... Menge der Partitionen mit f=h
[mm] $A_7$ [/mm] ... Menge der Partitionen mit a=b
[mm] $A_8$ [/mm] ... Menge der Partitionen mit g=i
Dann ist [mm] $N:=|A\setminus (A_1\cup A_2\cup A_3\cup A_4\cup A_5\cup A_6\cup A_7\cup A_8)|$ [/mm] gesucht. Gemäß Siebformel ist das
$$N = [mm] B_8 [/mm] - [mm] 8*B_7 [/mm] + [mm] 28*B_6 [/mm] - [mm] (4*B_6+52*B_5) [/mm] + [mm] (23*B_5+47*B_4) [/mm] - [mm] (6*B_5+34*B_4+16*B_3) [/mm] + [mm] (B_5+12*B_4+15*B_3) [/mm] - [mm] (2*B_4+6*B_3) [/mm] + [mm] B_3\; [/mm] ,$$
also
$$N = [mm] B_8 [/mm] - [mm] 8*B_7 [/mm] + [mm] 24*B_6 [/mm] - [mm] 34*B_5 [/mm] + [mm] 23*B_4 [/mm] - [mm] 6*B_3 [/mm] = 4140 - 8*877 + 24*203 - 34*52 + 23*15 - 6*5 = [mm] 543\; [/mm] .$$
Alles ohne Gewähr, man kann sich so leicht hier verzählen...
Gruß,
Dirk
|
|
|
| |
|
| Status: |
(Korrektur) oberflächlich richtig  | | Datum: | 17:56 Mo 13.08.2007 | | Autor: | kennydd |
Hallo Dirk,
vielen Dank für den Tipp mit der Bellschen Zahl und der Mengenpartitionierung...
Hab dazu zwar nicht im Bronstein gefunden, aber ich habe mich mit dem Wikipediaartikel auseinandergesetzt und mich draufhin mit einem Autor des Bronstein zusammengesetzt.
Mit diesem konnte ich die letzten unklarheiten beseitigen und habe nun eine passende, etwas länger Rechnung auf Basis von Aquivalenzrelation, Aquivalenzklassen, der Bellschen Zahl, Mengenpartitionierung und etwas Kombinatorik.
PS: evtl. findet sogar die Bellsche Zahl nun Einzug in das Buch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:17 Fr 20.07.2007 | | Autor: | DirkG |
Da gibt es ein kleines symbolische Missverständnis zu klären:
> Aussage1: a [mm]\not=[/mm] d [mm]\not=[/mm] f [mm]\not=[/mm] h
Diese Aussage bedeutet zunächst mal nur eine Zusammenfassung der drei Aussagen [mm] $a\neq [/mm] d$, [mm] $d\neq [/mm] f$ und [mm] $f\neq [/mm] h$.
Du scheinst sie aber so zu meinen, dass die vier Werte $a,d,f,h$ paarweise verschieden sind. Das wird durch diese Ungleichungskette nicht gesagt, da bei der z.B. sowas wie $a=f$ nicht ausgeschlossen wird!!!
Gruß,
Dirk
|
|
|
|
