Hashwerte < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben:
h(k) = k mod 255
Diese Hashfunktion ist ungeeignet für Zeichenketten.
Zu zeigen:
a) Zwei Zeichenketten, die sich nur durch die Permutation von zwei Zeichen unterscheiden, etwa ABCDE und CBADE, erhalten den gleichen Hashwert.
b) Allgemein gilt: Jede Permutation einer Zeichenkette im 256er - ASCII-System erhält unter h(k) denselben Hashwert. |
Hallo Forum!
Wie kann ich hier a) und b) formal zeigen, ohne dass ich in der ACSII-Tabelle die Zahlen der einzelnen Buchstaben ermittle, und dann in h(k) einsetze? Weil das wäre ja kein richtiger mathematischer Beweisund wäre ja auch zu einfach. Ich versteh nicht ganz, wie sowas allgemein zeigen kann.
V.a. bei b): Kann mir bitte jemand helfen, wie man das allgemein zeigt.
Danke!
wetterfrosch
|
|
| |
|
Hallo frosch,
wenn Du die (a) schon hast, reicht es zu bemerken, dass jede Permutation darstellbar st als Verknüpfung von sogenannten Transpositionen -
Permutationen also, die nur zwei Elemente vertauschen.
Was ist denn der Hash-Wert einer Zeichenkette ? Das Produkt oder sowas von den Hash-Werten der Nummern der einzelnen Zeichen ?
Gruss,
Mathias
|
|
|
| |
|
Hallo,
also mit einer Zeichenkette meine ich die Aneinanderreihung von Buchstaben, z.b. wie ABC. Die müssen ja dann erstmal in Zahlen codiert werden mit Hilfe der ASCII-Tabelle.
Danke für den Tipp mit den Transpositionen, aber wie schreibe ich das mathematisch nieder? Doch nicht etwa wie in linearer Algebra mit den tausend Indizes und dem Tau...? 
Danke!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Do 08.06.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
