Hashing < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:30 Di 03.06.2008 | | Autor: | Wimme |
| Aufgabe | Wir betrachten geschlossenes Hashing mit Arraygröße [mm] M=2^k [/mm] für ein k [mm] \in \mathbb [/mm] N, k [mm] \geq [/mm] 1.
Betrachten Sie für eine gegebene Hashfunktion h^* die wie folgt definierte Sondierungsfolge:
[mm] h_0(x),h_1(x)...
[/mm]
[mm] h_0(x)=h^{\star}(x) [/mm] mod M
[mm] h_i(x)=(h_{i-1}(x)+i) [/mm] mod M
Zeigen Sie: Für jedes einzufügende Element x wird mit M Sondierungsschritten die ganze Hashtabelle durchsucht. |
Hallo!
Wie macht man das?
Muss ich zeigen, dass [mm] \summe_{i=0}^{2^k-1}{h_i(x)}=h_0(x) [/mm] ist?
Also ich brauche ja M Sondierungsschritte, deswegen gehe ich bis [mm] M-1=2^k-1. [/mm] In jedem Schritt mache ich das nächste [mm] h_i. [/mm] In den Anfangsplatz [mm] (h_0(x)) [/mm] will ich zurück, weil ich da gestartet bin, und....hm...ne ist eigentlich quatsch, ne? Ich muss ja nicht die ganze Tabelle durchsucht haben, um wieder im gleichen Platz zu landen..
Irgendwelche Tipps?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:04 Mi 04.06.2008 | | Autor: | rainerS |
Hallo!
> Wir betrachten geschlossenes Hashing mit Arraygröße [mm]M=2^k[/mm]
> für ein k [mm]\in \mathbb[/mm] N, k [mm]\geq[/mm] 1.
> Betrachten Sie für eine gegebene Hashfunktion h^* die wie
> folgt definierte Sondierungsfolge:
> [mm]h_0(x),h_1(x)...[/mm]
>
> [mm]h_0(x)=h^{\star}(x)[/mm] mod M
> [mm]h_i(x)=(h_{i-1}(x)+i)[/mm] mod M
>
> Zeigen Sie: Für jedes einzufügende Element x wird mit M
> Sondierungsschritten die ganze Hashtabelle durchsucht.
> Hallo!
>
> Wie macht man das?
>
> Muss ich zeigen, dass [mm]\summe_{i=0}^{2^k-1}{h_i(x)}=h_0(x)[/mm]
> ist?
>
> Also ich brauche ja M Sondierungsschritte, deswegen gehe
> ich bis [mm]M-1=2^k-1.[/mm] In jedem Schritt mache ich das nächste
> [mm]h_i.[/mm] In den Anfangsplatz [mm](h_0(x))[/mm] will ich zurück, weil ich
> da gestartet bin, und....hm...ne ist eigentlich quatsch,
> ne? Ich muss ja nicht die ganze Tabelle durchsucht haben,
> um wieder im gleichen Platz zu landen..
Du hast eine Tabelle mit M Einträgen. Wenn du irgendeine (andere als die gegebene) Sondierungsfolge nimmst, könnte es doch sein, dass du mehrmals denselben Tabelleneintrag anschaust. Du musst also zeigen, dass in den M Schritten nie zweimal dasselbe Tabellenelement angeschaut wird, dass also die Folge
[mm] h_0(x),h_1(x)...[/mm]
alle Zahlen von 0 bis M-1 enthält.
Bedenke, dass [mm] $h^{\star}$ [/mm] zwar beliebig ist, aber nur einmal (für [mm] $h_0$) [/mm] berechnet wird!
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:33 Mi 04.06.2008 | | Autor: | Wimme |
genau, darauf bin ich gestern abend dann auch noch gekommen!
Aber wie zum Geier zeige ich, dass in einer Summe alle Summenglieder verschieden sind, bzw. dass alle Indizes auftauchen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:44 Mi 04.06.2008 | | Autor: | rainerS |
Hallo!
> genau, darauf bin ich gestern abend dann auch noch
> gekommen!
>
> Aber wie zum Geier zeige ich, dass in einer Summe alle
> Summenglieder verschieden sind, bzw. dass alle Indizes
> auftauchen?
Du kannst doch den n-ten Schritt, also [mm] $h_n(x)$ [/mm] direkt als Summe (mod M) schreiben. Für diese Summe gibt es eine Formel.
Außerdem kannst du schließen, dass die Hälfte der [mm] $h_n(x)$ [/mm] gerade und die andere Hälfte ungerade ist. Dann überlege dir, dass die Hälfte der geraden Werte durch 4 teilbar ist, usw.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:17 Mi 04.06.2008 | | Autor: | Wimme |
hallo Rainer!
mir fehlt immer noch der finale Schritt. Immerhin glaube ich jetzt die geschlossene Formel gefunden zu haben:
[mm] h_n(x)=(h^{\star}+\frac{n(n+1)}{2}) [/mm] mod M
damit kann ich jetzt also den n-ten Schritt ausdrücken.
Ich möchte zeigen, dass alle Zahlen von 0 bis M-1 rauskommen, wenn die die Folge [mm] h_0 [/mm] .. [mm] h_{M-1} [/mm] anwende. Offensichtlich unterschieden sich die [mm] h_i(x) [/mm] nur in [mm] \frac{n(n+1)}{2} [/mm] was ich sicher irgendwie ausnutzen muss, bestimmt im Zusammenhang, dass M eine Zweierpotenz ist.
Hmmm...ich komm noch nicht drauf!! Mit deinem Tipp von Hälfte ungerade Hälfte gerade kann ich auch nicht richtig etwas anfangen :((
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:32 Fr 06.06.2008 | | Autor: | rainerS |
Hallo!
> mir fehlt immer noch der finale Schritt. Immerhin glaube
> ich jetzt die geschlossene Formel gefunden zu haben:
>
> [mm]h_n(x)=(h^{\star}+\frac{n(n+1)}{2})[/mm] mod M
>
> damit kann ich jetzt also den n-ten Schritt ausdrücken.
> Ich möchte zeigen, dass alle Zahlen von 0 bis M-1
> rauskommen, wenn die die Folge [mm]h_0[/mm] .. [mm]h_{M-1}[/mm] anwende.
> Offensichtlich unterschieden sich die [mm]h_i(x)[/mm] nur in
> [mm]\frac{n(n+1)}{2}[/mm] was ich sicher irgendwie ausnutzen muss,
> bestimmt im Zusammenhang, dass M eine Zweierpotenz ist.
Ja. Der Wert von [mm] $h^{\star}$ [/mm] spielt für die Überlegung keine Rolle.
> Hmmm...ich komm noch nicht drauf!! Mit deinem Tipp von
> Hälfte ungerade Hälfte gerade kann ich auch nicht richtig
> etwas anfangen :((
Ich meine, du müsstest das Problem durch Bisektion lösen können. Die Menge der möglichen Werte zerfällt in zwei gleich große Teile, eine mit allen geraden, die andere mit allen ungeraden Werten. Dann betrachtest du jeden Teil für sich, aber mit $M/2$ statt M.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:12 Fr 06.06.2008 | | Autor: | Wimme |
hallo Rainer!
hmm..also im Prinzip betrachte ich jetzt nur:
[mm] (\frac{n(n+1)}{2})mod 2^k
[/mm]
Und betrachte alle geraden Zahlen von n(n+1)/2 im Intervall [mm] 0..2^k-1 [/mm] und alle ungeraden separat. Ok..
Aber mir ist nicht ganz klar, wieso ich dann [mm] M(=2^k) [/mm] einfach halbieren darf. Dadurch verfälsche ich doch die Ergebnisse des Modulo?
z.B. 4 mod 8 = 4 aber 4 mod 4 = 0
:-(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:12 Fr 06.06.2008 | | Autor: | rainerS |
Hallo!
> hallo Rainer!
>
> hmm..also im Prinzip betrachte ich jetzt nur:
>
> [mm](\frac{n(n+1)}{2})mod 2^k[/mm]
>
> Und betrachte alle geraden Zahlen von n(n+1)/2 im Intervall
> [mm]0..2^k-1[/mm] und alle ungeraden separat. Ok..
>
> Aber mir ist nicht ganz klar, wieso ich dann [mm]M(=2^k)[/mm]
> einfach halbieren darf. Dadurch verfälsche ich doch die
> Ergebnisse des Modulo?
> z.B. 4 mod 8 = 4 aber 4 mod 4 = 0
Nein, ich meinte, du nimmst alle geraden Zahlen teilst sie alle durch zwei. Und statt mod M machst du dann die Betrachtung mod (M/2).
Für die ungeraden Zahlen ziehst du 1 ab und halbierst und betrachtest wieder alle Zahlen mod (M/2).
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:09 Fr 06.06.2008 | | Autor: | Wimme |
sorry, ich verstehe nicht inwiefern mir das helfen soll.
Bin anscheinend etwas begriffsstutzig bei dieser Aufgabe.
Könntest du es vielleicht mal teilweise vorführen und erklären, warum es mich bei der Lösung vorwärts bringt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:44 Fr 06.06.2008 | | Autor: | rainerS |
Hallo!
> sorry, ich verstehe nicht inwiefern mir das helfen soll.
>
> Bin anscheinend etwas begriffsstutzig bei dieser Aufgabe.
>
> Könntest du es vielleicht mal teilweise vorführen und
> erklären, warum es mich bei der Lösung vorwärts bringt?
Fortgesetzte Bisektion: wenn du die geraden Zahlen alle halbierst, müssen diese neuen Zahlen die Menge aller Zahlen von 0 bis M/2-1 sein, sonst ist die Aussage falsch. Analoges gilt für die ungeraden.
Damit hast du das Problem halbiert. Das machst du k mal.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:04 Sa 07.06.2008 | | Autor: | Wimme |
hallo Rainer!
Naja, dann versuche ich jetzt mal selbst ein Beispiel vorzuführen:
Nehmen wir an, ich betrachte die Ergebnismenge 0..7
So, jetzt nehme ich mir alle geraden Zahlen heraus, also 0,2,4,6 und alle ungeraden 1,3,5,7
So, wenn ich dich richtig verstehe, meinst du man könnte das dann einfach halbieren, so dass ich die Zahlen
0,1,2,3 hätte. Wenn mein Modulo vorher also 8 war, soll ich also Modulo 4 betrachten?
Das ist mir jetzt denke ich klarer geworden. Denn wenn etwas vorher den Rest 0-3 erzeugt hat bei Modulo 8, muss es das auch bei Mod 4 noch tun.
Ok, das läuft darauf hinaus, dass ich am Ende mod [mm] (2^0) [/mm] betrachte und 0 herausbekommen möchte, was ja auch stimmt. Aber wieso beweist das nun, dass das für allgemeine ks funktioniert? Aus einer falschen Annahme, kann ich doch im Prinzip alles folgern, oder nicht?
Bei dem Prinzip fließt ja auch gar nicht wirklich meine aufgestellte Formel ein. Das könnte ich ja so mit jedem Modulo [mm] 2^k [/mm] machen.
Nehmen wir auch mal [mm] 2^k [/mm] für k=1. Ich muss also die Reste 0 und 1 erzeugen.Dafür steht mir [mm] h_0 [/mm] und [mm] h_1 [/mm] zur Verfügung, also einmal
[mm] (h^{\star}+0) [/mm] mod [mm] 2^1 [/mm] und [mm] (h^{\star}+2) [/mm] mod [mm] 2^1. [/mm] Folgt daraus nicht, dass [mm] h^{\star} [/mm] ungerade sein muss?
Ich weiß, man soll ja keine Erwartungshaltung haben..aber kannst du es nicht einfach mal zumindest teilweise vorführen? Ich bemühe mich ja auch. Es ist irgendwie ziemlich frustrierent, nicht zu verstehen, warum es das tut, was es soll, wie das genau funktionieren soll und mich deine Hilfestellungen leider nicht weiter bringen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:37 Sa 07.06.2008 | | Autor: | rainerS |
Hallo!
> hallo Rainer!
>
> Naja, dann versuche ich jetzt mal selbst ein Beispiel
> vorzuführen:
> Nehmen wir an, ich betrachte die Ergebnismenge 0..7
> So, jetzt nehme ich mir alle geraden Zahlen heraus, also
> 0,2,4,6 und alle ungeraden 1,3,5,7
>
> So, wenn ich dich richtig verstehe, meinst du man könnte
> das dann einfach halbieren, so dass ich die Zahlen
> 0,1,2,3 hätte. Wenn mein Modulo vorher also 8 war, soll
> ich also Modulo 4 betrachten?
> Das ist mir jetzt denke ich klarer geworden. Denn wenn
> etwas vorher den Rest 0-3 erzeugt hat bei Modulo 8, muss es
> das auch bei Mod 4 noch tun.
>
> Ok, das läuft darauf hinaus, dass ich am Ende mod [mm](2^0)[/mm]
> betrachte und 0 herausbekommen möchte, was ja auch stimmt.
> Aber wieso beweist das nun, dass das für allgemeine ks
> funktioniert? Aus einer falschen Annahme, kann ich doch im
> Prinzip alles folgern, oder nicht?
>
> Bei dem Prinzip fließt ja auch gar nicht wirklich meine
> aufgestellte Formel ein. Das könnte ich ja so mit jedem
> Modulo [mm]2^k[/mm] machen.
Nein, du brauchst die Formel, um die Aussage in jedem Schritt zu beweisen. Die Sache funktioniert ja nur, weil im ersten Schritt die Hälfte der Zahlen gerade, und die andere Hälfte ungerade sind. Und das liegt daran, dass
[mm] \bruch{n(n+1)}{2} [/mm] gerade [mm] \gdw [/mm] n ist durch 4 teilbar oder (n+1) ist durch 4 teilbar.
und
[mm] \bruch{n(n+1)}{2} [/mm] ungerade [mm] \gdw [/mm] (n+2) ist durch 4 teilbar oder (n+3) ist durch 4 teilbar.
Da n alle Werte von 0 bis [mm] $2^k-1$ [/mm] annehmen kann, ergeben sich [mm] $2^{k-1}$ [/mm] gerade und [mm] $2^{k-1}$ [/mm] ungerade Werte für [mm] \bruch{n(n+1)}{2} [/mm].
Im zweiten Schritt zeigst du, dass die [mm] $2^{k-1}$ [/mm] geraden Werte bestehen aus [mm] $2^{k-2}$ [/mm] Zahlen, die durch 4 zeilbar sind, und [mm] $2^{k-2}$ [/mm] Zahlen, die nicht durch 4 teilbar sind. Ebenso zeigst du, dass die [mm] $2^{k-1}$ [/mm] ungeraden Werte zur Hälfte von der Form $4m+1$ und zur anderen Hälfte von der Form $4m+3$ sind.
Nach m Schritten hast du die Menge [mm] $\{0,\dots,2^{k}-1\}$ [/mm] in [mm] $2^m$ [/mm] gleich große Teile zerlegt, und für jeden Teil hast du eine andere Teilbarkeitsregel:
n ist durch [mm] $2^{m+1}$ [/mm] teilbar oder n+1 ist durch [mm] $2^{m+1}+1$ [/mm] teilbar
n+2 ist durch [mm] $2^{m+1}$ [/mm] teilbar oder n+3 ist durch [mm] $2^{m+1}$ [/mm] teilbar
[mm] $\dots$
[/mm]
[mm] $n+2^{m+1}-2$ [/mm] ist durch [mm] $2^{m+1}$ [/mm] teilbar oder [mm] $n+2^{m+1}-1$ [/mm] ist durch [mm] $2^{m+1}$ [/mm] teilbar
Viele Grüße
Rainer
|
|
|
|
