Loesungshinweise zur vierten Hausuebung

H-12. Jede Permutation laesst sich als Produkt (also
Hintereinanderausfuehrung) von Transpositionen schreiben. Nehmen wir
zum Beispiel die zyklische Vertauschung von 3 Elementen, also
0->1->2->0. Ausgehend von (0,1,2) bilden wir (1,0,2) und dann
(1,2,0). Wir haben also zwei Vertauschungen gebraucht. 

Entsteht also Wort v aus Wort u durch Permutation der Buchstaben, so
gibt es eine Folge von Woertern w0,w1,w2,...,wl wobei u=w0 und wl=v
und w(i+1) aus wi durch Transposition hervorgeht. Aufgrund von P-16
haben alle wi den gleichen Hashwert, somit auch u und v. 

Man kann aber auch ein direktes Argument wie in P-16 fuehren: 

h(a1...an) mod 255 = Summe(ai*256^i) mod 255 = Summe(ai) mod 255

(da 256^i mod 255 = 1^i mod 255 = 1)

Somit haengt der Hashwert nur von der Summe der Buchstabencodes ab. 

Grundsaetzlich ist eine Hashfunktion immer dann "schlecht", wenn die
Verteilung der Hashwerte nicht annaehernd uniform ist. Das kann hier
passieren, wenn die Schluessel nicht alle ASCII-Zeichen benutzen, denn
dann ist die Wahrscheinlichkeit, dass ein Schluessel Permutation eines
anderen ist ueberproportional gross. Das koennte also passieren,wenn
man etwa Telefonnummern oder Matrikelnummern als ASCII auffasst und
mit dieser Hashfunktion codiert, aber auch schon dann, wenn die
"seltenen" ASCII Zeichen, wie %^&* \n, etc nicht vorkommen. Ein
anderes Beispiel waeren Bezeichner in automatisch generierten
Programmen, etwa x13452, x13425,... welche auch oft eine kleine
Teilmenge der ASCII-Zeichen favorisieren.

H-13 k(61)=701, h(62)=319, h(63)=937, h(64)=555, h(65)=173

H-14 Fuer die mittlere Suchdauer bei erfolgreicher Suche gilt
(1-ln(1-alpha))/alpha wobei alpha der Lastfaktor ist. 

Wir haben also die Ungleichung 

(1-ln(1-alpha))/alpha <= 4,3

so gut wie moeglich zu loesen. Da fuer Gleichungen, die die Unbekannte
sowohl direkt, wie auch als Argument einer transzendenten Funktion
(hier ln) involvieren, keine symbolischen Verfahren (durch
"Aufloesen") existieren, muessen wir probieren. Hier ist ein
Transkript einer SML Sitzung. 

- fun f alpha = (1.0 -(Math.ln(1.0- alpha)))/alpha;
val f = fn : real -> real
- f 0.9;;
val it = 3.66953899222 : real
- f 0.95;
val it = 4.20603397216 : real
- f 0.97;
val it = 4.64593597662 : real
- f 0.96;
val it = 4.39466231757 : real
- f 0.955;
val it = 4.29433799917 : real
- f 0.957;
val it = 4.33286850918 : real
- f 0.956;
val it = 4.31335318521 : real
- f 0.9555;
val it = 4.30378450006 : real
- f 0.9552;
val it = 4.29810211428 : real
- f 0.9553;
val it = 4.29999139261 : real

Mit einem Lastfaktor von 0,9553 sind wir also gut bedient. Es ist 
auch noch f 0,3234 =~= 4,3 aber dieser Wert gilt nicht, da ja die
Formel nur eine obere Schranke fuer den wahren Erwartungswert
darstellt und dieser wahre Wert natuerlich monoton mit alpha waechst. 

H-15

Lineares Probieren: h(k,i)=((h'(k)+i) mod 11) + 1 fuer i=1..11. 
Die Werte werden an die Plaetze 2 3 1 7 8 9 10 4 11 gesetzt.

Quadratisches Probieren: h(k,i)=((h'(k)+i+3i^2) mod 11) + 1. 
Die Werte werden an die Plaetze 5 6 4 10 9 1 11 2 3 gesetzt.

Double Hashing: h(k,i)=((h'(k)+i*h2(k))) mod 11 + 1.
Die Werte werden an die Plaetze 2 5 4 11 1 6 10 9 3 gesetzt.

Der folgende SML code wurde von mir verwendet. 

fun h1 k = (k mod 11)+1
fun hlin k i = (h1 k + i) mod 11 + 1;
fun hquad k i = (h1 k + i + 3*i*i) mod 11 + 1;
fun h2 k = (k mod 10)+1
fun hdoub k i = (h1 k + i * h2 k) mod 11 +1;
val hash_tab = Array.array(11,0);;    
fun reset_hash_tab () = Array.modify (fn x=>0) hash_tab   
val keys = Array.fromList [10,22,31,4,15,28,17,88,59]
fun hash h k i = if i>9 then (0-1) else 
if Array.sub(hash_tab,h k i - 1) = 0 then
(Array.update(hash_tab,h k i - 1,1);h k i) else
hash h k (i+1)

val keys = Array.fromList [10,22,31,4,15,28,17,88,59]   
fun hash_from h j = if j>8 then () else (
 print (Int.toString (hash h (Array.sub(keys,j)) 1));
 print " ";
 hash_from h (j+1));

hash_from hlin 0;
reset_hash_tab();
hash_from hquad 0;
reset_hash_tab();
hash_from hdoub 0;


H-16: Bisher gibt es erst eine Loesung. Wie gesagt, auch die zwei
naechsten richtigen solchen werden mit einer Flasche "Corona"-Bier
ausgezeichnet.