Hashverfahren berechnen .

Question

1. Geben Sie eine Formel für die Wahrscheinlichkeit P(n) an, dass von n zufällig ausgewählten Personen mindestens zwei am gleichen Tag Geburtstag haben. Geben Sie ebenfalls die Herleitung Ihrer Lösung an bzw. begründen Sie deren Korrektheit. Sie  können annehmen, dass jedes Jahr 365 Tage hat (keine der Personen hat am 29. Februar Geburtstag) und dass die Geburtstage gleichverteilt sind (es gibt keine besonderen Ereignisse, die zu höheren Geburtenraten an bestimmten Tagen führen).

2. Bestimmen Sie die Werte P(10), P(23), P(35) und P(50) auf mindestens 3 Nachkommastellen genau. 

3. Was haben Sie in dieser Aufgabe, bezogen auf Hashverfahren, berechnet? 

Eine Wahrscheinlichkeit ist mathematisch eine reelle Zahl im Intervall [0, 1], die häufig aber auch in Prozent angegeben wird (multipliziert mit Faktor 100). Bestimmen Sie auf dem Weg zur Lösung die Anzahl der möglichen Kombinationen von Geburtstagen aller n Personen und die Anzahl der Kombinationen, bei denen alle Personen an unterschiedlichen Tagen Geburtstag haben. Ein hilfreicher Suchbegriff, um dann zum Ergebnis zu kommen, lautet ” Laplace-Formel“.

Ich komme mit dieser Aufgabe leider gar nicht klar :(((

Comments

https://lmgtfy.com/?q=Mindestens+zwei+personen+Geburtstag

Answer 1

Geben Sie eine Formel für die Wahrscheinlichkeit P(n) an, dass von n zufällig ausgewählten Personen mindestens zwei am gleichen Tag Geburtstag haben.

Diese Fragestellung firmiert auch unter der Bezeichnung "Geburtstagsproblem" (und damit verbunden das "Geburtstagsparadoxon"). Die Formel dafür lautet:

\(P(n)=1-\dfrac{365!}{(365-n)!\cdot 365^n}\)

Eine einfache Herleitung findest Du in dem folgenden Video:

Bestimmen Sie die Werte P(10), P(23), P(35) und P(50) auf mindestens 3 Nachkommastellen genau. 

Hierfür setzt Du lediglich in die oben angegebene Formel ein:

\(P(10) \approx0.117\)

\(P(23) \approx0.507\)

\(P(35) \approx 0.814\)

\(P(50) \approx 0.970\)

Was haben Sie in dieser Aufgabe, bezogen auf Hashverfahren, berechnet?

Die Kollisionswahrscheinlichkeit von Hashadressen. Allgemein gilt: Wenn eine Hashfunktion \(\sqrt{\pi\cdot\frac{n}{2}}\) Schlüssel auf eine Hashtable der Größe \(n\) abbildet, gibt es wahrscheinlich Adresskollisionen.

Nicht umsonst nennt man eine mögliche Angriffstechnik auf Hashfunktionen "Geburtstagsangriff" ;-)