Verfasst am: Di Mai 18, 2004 7:24 pm Titel: Algorithmen
Tipp zu Blatt 4, Aufgabe 2 b) von Tutor M.Deelwater:
Zitat:
Es gibt offenbar einige Schwierigkeiten mit der Aufgabe 2b. Ich will
versuchen, etwas mehr Klarheit bezüglich des Algorithmus' zu schaffen
(Lösungen gibt's natürlich nicht):
Die "Deterministische Auswahl" wählt aus einer Menge von n Schlüsseln den k-größten, also den größten, den zweitgrößten, etc. aus. Dazu wird das gesamte Feld in Teilfelder einer festen Größe (in Aufgabenteil a sind das 5, in Teil b 2m-1) eingeteilt. Der genaue Algorithmus steht im Skript. Für uns ist zunächst nur wichtig, in welchem Zusammenhang die Zahlen im Skript mit der 5 bzw. mit 2m-1 stehen. Nachdem wir also die Teilmengen haben, wird von jeder einzelnen der Median berechnet. Das geht natürlich in konstanter Zeit, wenn m fest gewählt ist. Dann wird rekursiv der Median der Mediane, x, bestimmt. Das ist aber für uns vorerst nicht so wichtig. Entscheidend ist die Argumentation, die nun im Skript folgt: Mindestens die Hälfte aller Mediane ist größer als x. Nun müsst Ihr überlegen, ob das auch noch gilt, wenn ihr die Teilmengen größer macht (die Antwort ist sehr einfach). Wenn wir nun wissen, wie viele Mediane größer als x sind, überlegen wir, wie viele Elemente in den Teilmengen dann jeweils
größer sind als der Median der Teilmenge. Wenn wir eine Fünfermenge
betrachten, dann sind mindestens drei Elemente der Fünfermenge größer oder gleich dem Median. Wenn wir M Teilmengen haben, die jeweils 3 Elemente enthalten, die größer sind als ihr Median, und die Hälfte aller Mediane größer sind als x, dann haben wir mindestens 3*(M/2) Elemente, die größer sind als x. Was muss hier geändert werden, wenn wir 5 durch 2m-1 ersetzen? Wenn man den Algorithmus verstanden hat, ist das ganz einfach, keine Zauberei. Dann überlegt Ihr (analog zum Skript), wie viele Elemente bei der folgenden Rekursion übergeben werden. Am Ende packt Ihr das in die T(n)-Formel, die ja zwei Rekursionen enthält (einmal die zur Bestimmung des Medians der Mediane, und dann die eigentliche auf einem Teilfeld, das bei der Partitionierung entstanden ist). Wenn Ihr soweit seid, dann könnt Ihr weitermachen wie im Skript, nur eben mit Eurer Formel. Das heißt, ihr versucht zu zeigen, dass die Laufzeit linear wird, und schaut dann, unter welchen Bedingungen das klappt.
So, das mag jetzt für einige keine große Hilfe gewesen sein, aber es ist
vielleicht etwas verständlicher als das Skript.
_________________ "...from the faith that you release comes an atheist peace."
Blatt 7 Aufgabe 1:
Habe das mal soweit ich das verstanden hab nach dem Skript (diese 2-3-Stufen-Anleitung) gemacht, sieht eigentlich recht gut aus, habe die 2.Hashtabelle jetzt auch endlich auf ca. Größe 16 gebracht...Hat jemand was ähnliches raus?
2.Stufe: Auf jede Teilmenge nochmals Hashing (mit injektiver Hash-Fkt.) anwenden
Sei wi = {x € S : hk(x)=i}, bi = |wi| und mi:=2bi(bi-1)+1 (wie oben)
wähle ki mit hki(x) = ((ki*x) mod 127) mod mi so, dass hki injektiv für wi
h1(x)| hki(x)
------------------------------
1 | 0
2 | 0
3 | 0
4 | 0
5 | 0
7 | 0
8 | ((7*x) mod 127) mod 5
9 | ((4*x) mod 127) mod 5
h7(19)=((7*19) mod 127) mod 5 != h7(9)=((7*9) mod 127) mod 5
h4(93)=((4*93) mod 127) mod 5 != h4(103)=((4*103) mod 127) mod 5
3.Stufe: Sei si:=Summe(mi)
Dann speichere x € S in Tafelposition T[si + j]
wobei i=((k*x) mod 127) mod 10
und j=((ki*x) mod 127) mod mi
41: i=2, si=2, j=0, also T[2] // j=((0*41 mod 127) mod 1
85: i=3, si=3, j=0, also T[3] // j=((0*85 mod 127) mod 1
22: i=4, si=4, j=0, also T[4] // j=((0*22 mod 127) mod 1
64: i=1, si=1, j=0, also T[1] // j=((0*64 mod 127) mod 1
111: i=5, si=5, j=0, also T[5] // j=((0*111 mod 127) mod 1
19: i=8, si=8, j=1, also T[9] // j=((7*19 mod 127) mod 5
93: i=9, si=13, j=3, also T[16] // j=((4*93 mod 127) mod 5
9: i=8, si=8, j=3, also T[11] // j=((7*9 mod 127) mod 5
77: i=7, si=7, j=0, also T[7] // j=((0*77 mod 127) mod 1
103: i=9, si=13, j=1, also T[14] // j=((4*103 mod 127) mod 5
Also das mit der Beschränkung der sekundären Tabelle ist mir auch ein Rätsel....
Ist zwar nichts zur 1., aber ich kopier mal den Text, den meine Tutorin mir zur 4. geschickt hat, vielleicht hilft´s euch ja n bissl.
Zitat:
Hey ihr,
hier noch was zu Aufgabe 4, ich hoffe es bringt etwas.
Das Problem selbst kann als Graph dargestellt werden, der n Knoten hat und die Knoten untereinandern sind verbunden, also
Knoten1 mit Knoten2 bis n, Knoten 2 mit Knoten 3 bis Knoten n....
Ihr stellt dann eine Formel für die Wahrscheinlichkeit auf, dass in der i-ten Phase kein Fehler auftritt und eine Formel für die Kosten und versucht so die Kostenfunktion c_ij aufzustellen.
Es ist also alles rein formal.
Wenn ein Fehler gefunden wird entstehen natürlich keine weitern Kosten.
Arg viel mehr darf ich euch leider nicht mehr verraten, ich hoffe ihr kommt einigermaßen damit klar, lest die Aufgabe gut durch und streng eure grauen Zellen an :-)
Bis Dienstag dann und nicht vergessen, Abgabe Freitag bis 12 Uhr =)
Habe nochmal perfekt gehasht, jetzt passts glaub Habe es im oberen Beitrag editiert... _________________ "...from the faith that you release comes an atheist peace."
Du oder Robin solltest den dann für Ramiz und mich wahrscheinlich mitnehmen, da wir ja ab nächster Woche beide fort sind... _________________ "...from the faith that you release comes an atheist peace."
Ich werd garantiert nicht sofort hinrennen und den holen, wozu? Der läuft doch nicht weg. Hab grad auch genug zu tun und ab nächste Woche auch noch 2 Nebenjobs plus ne Wohnungsrenovierung und lernen auf Ti Vordiplom. Da interessiert mich Algo kein bisschen. Entweder wir haben den Schein oder nicht, wenn ja dann ist er auch in 10 Wochen noch da, wenn nein, dann ist es jetzt eh zu spät, wozu also Hektik.
Ganz locker bleiben, ich frag jemand anders, mir is es immer lieber, das Zeug is abgeholt. _________________ "...from the faith that you release comes an atheist peace."
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum nicht posten Du kannst Dateien in diesem Forum nicht herunterladen
Habe es im oberen Beitrag editiert...