Blatt 05 - HackMD

--- tags: Assignments --- # Blatt 05 |Kurs |Semester |Team | |--- |--- |--- | |Algorithmen und Datenstrukturen |SS 2020 |Carlo Mohl & Noah Nuebling | --- ## Aufgabe 1 ### a) 18 36 99 17 35 10 14 32 98  ### b) a = 2 c = 3  ## Aufgabe 2 ### a) Wir skalieren den Eingabebereich auf den Ausgabebereich und runden dann ab. ``` h(u) = L ((u - 1) / |U|) * p ⅃ ``` Der Abstand zwischen Ausgabewerten ist direkt proportional zum Abstand der zugehörigen Engabewerte. Bei gleichmäßiger Verteilung der Eingabewerte sollten die Ausgabewerte also auch gleichmäßig verteilt sein. Wir können die Verteilung der Ausgabewerte mit den Formeln für zufällige Hashfunktionen aus der Vorlesung abschätzen: ``` m = |U| n = p Kollisionen abschätzen: E(X) = (n(n-1))/2m = (p(p-1))/2*|U| Leerfelder abschätzen: E(X) = m * e^(-(n/m)) = |U| * e^(-(p/|U|)) ``` ### b) Vorraussetzungen: h(u) = 3u mod p p ist eine Primzahl u < p Wir unterteilen die Eingabewerte `u` in 3 Gruppen: ``` 1. u < 1/3 p 2. 1/3 p <= u < 2/3p 3. 2/3p <= u < p ``` Wir Unterteilen die Ausgabewerte `h(u)` in entsprechende Mengen: ``` 1. H1 = {h(u) | u < 1/3 p} 2. H2 = {h(u) | 1/3p <= u < 2/3p} 3. H3 = {h(u) | 2/3p <= u < p} ``` Für die 3 Bildmengen lässt sich festhalten: ``` 1. Für alle Funktionswerte h(u) aus H1 gilt: h(u) = 3u mod p = 3u (da 3u < p) 2. Für alle Funktionswerte h(u) aus H2 gilt: h(u) = 3u mod p = (3u-p + p) mod p = (3u-p mod p + p mod p) mod p = 3u-p mod p = 3u-p (da 3u-p < p) 3. Für alle Funktionswerte h(u) aus H3 gilt: h(u) = 3u mod p = (Rechenweg analog zu 2.) = 3u-2p ``` -> Daraus lässt sich erkennen, dass es innerhalb der Bildmengen keine "Überschneidung" gibt. Oder formaler – für zwei beliebige `u1` und `u2` aus der _gleichen_ Gruppe gilt: Wenn `u1 != u2 -> h(u1) != h(u2)` Zwischen den Bildmengen besteht auch keine "Überschneidung". Das können wir so zeigen: ``` 1. Für alle Funktionswerte h(u) aus H1 gilt: h(u) mod 3 = 3u mod 3 = 0 2. Für alle Funktionswerte h(u) aus H2 gilt h(u) mod 3 =: xa = (3u - p) mod 3 = ((3u mod 3) - (p mod 3)) mod 3 = (0 - (p mod 3)) mod 3 = -p mod 3 = 1 oder 2 (da p eine Primzahl ist) 3. Für alle Funktionswerte h(u) aus H3 gilt h(u) mod 3 =: xb = (3u - 2p) mod 3 = ((3u mod 3) - (2p mod 3)) mod 3 = (0 - (2p mod 3)) mod 3 = -2p mod 3 = (-p mod 3 * 2 mod 3) mod 3 = (xa * 2 mod 3) mod 3 1. Wenn xa = 1, dann gilt: xb = (xa * 2 mod 3) mod 3 = 2 mod 3 = 2 2. Wenn xa = 2, dann gilt: xb = (xa * 2 mod 3) mod 3 = 4 mod 3 = 1 ``` - Für alle beliebigen `a` aus `H1`, `b` aus `H2`, `c` aus `H3` gilt also `a mod 3 != b mod 3 != c mod 3` - Damit können wir nun also für alle `u1`, `u2` aus `U` schließen: wenn `u1 != u2 -> h(u1) != h(u2)`. ## Aufgabe 3 ### a) Problem der Hashfunktion ist das zum Bespiel `h'(8) = 8`. In diesem Fall würden wir beim Sondieren nur 2 unterschiedliche Zahlen finden ähnlich mit 4 oder 12 (da würden wur nur 4 finden) etc... . Forderung: `h'(u)` soll keine (Vielfache von) Teiler(n) von 16 und als Ergebnis haben. Also 16 und `h'(u)` sollen Teilerfremd sein. Ersatz: `h'(u) = (2u mod 8) + 1` ### b) Das Problem kann in beiden Fällen auftreten: Lineares Sondieren: `H_i(u) = (h(u) + i * 16) mod 16` Quadratisches Sondieren: `H_i(u) = (h(u) + i * 16 + i^2 * 16) mod 16` ## Aufgabe 4 RAKETE und ASTERIX ### a) | | e | R | A | K | E | T | E | | ---- | ---- | --- | --- | --- | --- | --- | --- | | e |__0__ | __0__|0 |0 |0 | 0 |0 | | A | 0 | 0 |__1__ | 1 | 1 | 1| 1 | | S | 0 | 0 |__1__ | __1__ |__1__ | 1| 1 | | T | 0 | 0 | 1 | 1 | 1 | __2__ | 2 | | E | 0 | 0 | 1 | 1 |2 |2 |__3__ | | R | 0 | 1 | 1 | 1 | 2 | 2 | __3__ | | I | 0 | 1 | 1 | 1 | 2 | 2 | __3__ | | X | 0 | 1 | 1 | 1 | 2 | 2 | __3__ | LGTS: `ATE` ### b) | | e | R | A | K | E | T | E | | ---- | ---- | --- | --- | --- | --- | --- | --- | | e | __0__ | 1 | 2 | 3 | 4 | 5 | 6 | | A | 1 | __1__ | 1 | 2 | 3 | 4 | 5 | | S | 2 | 2 | __2__ | 2 | 3 | 4 | 5 | | T | 3 | 3 | 3 | __3__ | 3 | 3 | 4 | | E | 4 | 4 | 4 | 4 | __3__ | 4 | 3 | | R | 5 | 4 | 5 | 5 | __4__ | 4 | 4 | | I | 6 | 5 | 5 | 6 | 5 | __5__ | 5 | | X | 7 | 6 | 6 | 6 | 6 | 6 | __6__ | Optimale Umformung gemäß Tabelle: ``` RAKETE 6. Ersetze E mit X RAKETX 5. Ersetze T mit I RAKEIX 4. Füge R nach E ein RAKERIX 3. Ersetze K durch T RATERIX 2. Ersetze A durch S RSTERIX 1. Ersetze R durch A ASTERIX ```