Unabhängigkeit von zwei unabhängigen Hashfunktionen beweisen

Neue Frage »

lmilexi Auf diesen Beitrag antworten »
Unabhängigkeit von zwei unabhängigen Hashfunktionen beweisen
Meine Frage:
so meine Aufgabe ist: zwei hashfunktionen h, h' : K-> 1,.., m heißen unabhängig, falls für zwei zufällig gewählte Schlüssel x, y element K gilt:
Pr 2(h (x) = h (y)) = 1/m , pr 1(h '(x) = h'(y)) = 1/m
Pr1 und pr2 = 1/m^2
Geben Sie K der Größe m^2 an, sowie ein Paar h, h' von unabhängigen hashfunktionen an. Mit m beliebig groß
Mit 1 < m < | K|

Meine Ideen:
Also, ich bitte um Rücksicht, da ich eine Biologin bin und für mein wahlpflichtfach einen kurs in der Informatik gewählt habe.
Ich hätte mit m = 3 und K = 9 gestartet. Da P (A)* P (B) = P(A^B) gelten muss hätte ich das jetzt einfache eingesetzt:
1/3 * 1/3 = 1/9 = 1/3 ^2 = 1/m^2
Mir ist bewusst, dass beweisen eigentlich anders geht. Aber das einzige was ich bis jetzt beweisen kann ist O notation
Ich bitfe euch um einen Ansatz oder um Hilfe wie ich da ran gehen muss
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »