Unabhängigkeit von zwei unabhängigen Hashfunktionen beweisen |
09.05.2016, 14:53 | lmilexi | Auf diesen Beitrag antworten » |
Unabhängigkeit von zwei unabhängigen Hashfunktionen beweisen 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 |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|