Beweis zu Hashfunktionen [Algorithmik]

15.06.2010, 20:02

MichaelZ.

Beweis zu Hashfunktionen [Algorithmik]

Hallo,

ich hoffe, dass dieses Thema mehr oder weniger in das Forum hier passt. Ich bin nämlich gerade bei einer Aufgabe komplett verloren, mir fehlt einfach der Ansatz.

Die Aufgabe:
Mit offener Adressierung sollen $\begin{eqnarray*} n \end{eqnarray*}$ Elemente in eine Hashtafel der Größe $\begin{eqnarray*} m \geq 2n \end{eqnarray*}$ eingefügt werden, wobei die Hashfunktion zufällig aus einer Menge $\begin{eqnarray*} \mathcal{H} \end{eqnarray*}$ uniformer Hashfunktionen $\begin{eqnarray*} h: U \Rightarrow \{0, ..., m-1\} \end{eqnarray*}$ ausgewählt werden soll.

Wie sollen jetzt zeigen, dass die Wahrscheinlichkeit, dass für $\begin{eqnarray*} i=1, 2, ..., n \end{eqnarray*}$ die $\begin{eqnarray*} i \end{eqnarray*}$ te Einfügeoperation echt mehr als k Versuche benötigt, höchstens $\begin{eqnarray*} 2^{-k} \end{eqnarray*}$ beträgt. Als Hinweis haben wir noch, dass $\begin{eqnarray*} \frac 1m \leq \frac12 \end{eqnarray*}$ .

Hättet ihr mir da vielleicht einen kleinen Ansatz? Ich habe keine Ahnung, wo ich da ansetzen soll...

Grüße,
Michael

17.06.2010, 01:19

Abakus

Auf diesen Beitrag antworten »

RE: Beweis zu Hashfunktionen [Algorithmik]
Hallo,

ein Versuch ist hier das Informatik-Board.

Kannst du erklären, was offene Adressierung, was eine uniforme Hashfunktion ist, und wie wir uns das Vorgehen mit den Hashfunktionen vorzustellen haben? Wird bei einer Kollision einfach die nächste benutzt oder wie geht das?

Grüße Abakus smile

17.06.2010, 01:29

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis zu Hashfunktionen [Algorithmik]

Zitat:

Original von Abakus
Hallo,

ein Versuch ist hier das Informatik-Board.

Klick: http://www.informatikerboard.de/index_start.php Augenzwinkern

Neue Frage »

Antworten »

Beweis zu Hashfunktionen [Algorithmik]

Verwandte Themen