W'keit von Kollisionen < stoch. Prozesse < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Nr. 20 (Hashing) Beim zufälligen Ablegen von Daten in einem Feld der Länge n können Mehrfachbelegungen (Kollisionen) vorkommen. Mit welcher Wahrscheinlichkeit? |
Allem voran habe ich keine Ahnung von Informatik, mein Interesse an dieser Aufgabe ist rein von der Stochastik her. Ich habe den Begriff Hashing mal gegoogelt und auch etwas gefunden, aber vor lauter Fachchinesich nichts kapiert. Also nehmt bitte Rücksicht auf meine Ahnungslosigkeit 
Erstmal ist mir nicht klar, wieviele Daten abgelegt werden sollen. Kann ich davon ausgehen, dass es bei n Fächern n Daten sind oder könnten es auch mehr oder weniger sein?
Mein Ansatz, der mich angesichts der Unklarheiten noch nicht weit bringt ist:
Beim 1. Ablegen sind noch alle Felder frei. Die W. für eine Kollision [mm] P_{1}(K) [/mm] ist 0.
Beim 2. Mal ist ein Feld belegt, n-1 Felder sind frei. [mm] P_{2}(K) [/mm] = 1/n
Muss ich nun im Fall einer Kollision ein anderes Feld wählen, oder kann ich zulassen, dass 2 Daten ein Feld belegen?
Ist eine Kollision nicht durchführbar, sind beim 3. Ablegen 2 Felder belegt und n-2 frei, [mm] P_{3}(K) [/mm] = 2/n
Geht es nach einer Kollision einfach weiter, können beim dritten Mal auch noch n-1 Felder frei sein...
Vielen Dank schonmal!
Julia
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 13.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
