universelles Hashing- Familie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:22 Do 12.06.2008 | | Autor: | gmh |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Aufgabe:
Betrachten Sie die beiden Hasfunktionen h1 und h2 der Größe 3 auf dem Universum U = {I; n; f; o; 1}
h1(k) = k mod 3
h2(k) = [3((k/7)mod 1) )] (abrunden)
(a) übersetzen Sie das Universum nach dem ASCII-Standard in ganze, nichtnegative
Zahlen und erstellen Sie die Hashtabelle für h1 und h2.
(b) Geben Sie eine Hashfunktion h3 an, so dass die Familie H = {h1; h2; h3} von
Hashfunktionen auf U universell ist.
(c) Wieviele Funktionen kann eine universelle Familie H von Hashfunktionen der
Größe 3 auf eine Universum U von 5 Elementen maximal enthalten, wenn man
zusätzlich fordert, dass gilt:
für alle x,y U : |{h H| h(x) = h(y)}|<= 1:
Wieviele Funktionen muss sie mindestens enthalten? |
Mir geht es vor allem um Teilaufgabe c.
Ich würde mich sehr freuen, wenn mir jemand die c ausführlich erklären kann.
Vielen Dank für jede Hilfe
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Fr 13.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
