Algorithmen

 
Neues Thema eröffnen   Neue Antwort erstellen    Trophäen-Jagd.de Foren-Übersicht -> Das ultimative Archiv
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Di Mai 18, 2004 7:24 pm    Titel: Algorithmen
Antworten mit Zitat

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."
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Di Jun 08, 2004 11:30 pm    Titel:
Antworten mit Zitat

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?

Code:

Aufgabe 1 (Perfektes Hashing)
-----------------------------------
Gegeben:
S={41,85,22,64,111,19,93,9,77,103}
U={0,1,...,126}
m=10

1.Stufe: Hashing mit Verkettung               

   hk(x) = (k*x mod 127) mod 10

   wir wählen k=2:

//  mi = 2bi(bi-1)+1
//  (bi entspricht Anzahl der Elemente mit gleichem Index i)

   h2(x) | x     | mi | Summe mi      
   -----------------------------      
    0      |         | 1  |  0
    1      |64        | 1  |  1
    2      |41       | 1  |  2
    3      |85        | 1  |  3
    4      |22       | 1  |  4
    5      |111       | 1  |  5
    6      |          | 1  |  6
    7      |77        | 1  |  7
    8      |19,9    | 5  |  8
    9      |93,103 | 5  |  13


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


Entgültige Hash-Tabelle:
------------------------

   h(x) | x   | h1(x)
   -----------------
   0    |       | 0
   -----------------
   1    |  64 | 1
   -----------------
   2    |  41 | 2
   -----------------
   3    |  85 | 3
   -----------------
   4    |  22 | 4
   -----------------
   5    | 111 | 5
   -----------------
   6    |        | 6
   -----------------
   7    |   77  | 7
   -----------------
   8    |       | 8
   9    |  19  | 8
   10   |       | 8
   11   |   9  | 8
   12   |       | 8
   -----------------
   13   |        | 9
   14   | 103 | 9
   15   |       | 9
   16   |   93  | 9
   17   |        | 9

_________________
"...from the faith that you release comes an atheist peace."


Zuletzt bearbeitet von Provokatiker am Mi Jun 09, 2004 10:18 am, insgesamt einmal bearbeitet
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
moonchild
macht sich gut
macht sich gut


Benutzer-Info
Alter: 40
Beiträge: 22
Wohnort: Hechingen

Karma: +0/-0


Keine Trophäen
BeitragVerfasst am: Mi Jun 09, 2004 9:01 am    Titel:
Antworten mit Zitat

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 =)

Grüßle Verena

Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Mi Jun 09, 2004 9:23 am    Titel:
Antworten mit Zitat

Mir is noch ein Fehler bei meiner Version der 1.Aufgabe aufgefallen, muss alles nochmal neu machen, hurraaaaa Twisted Evil

@moonchild: Danke für die Tipps Wink

_________________
"...from the faith that you release comes an atheist peace."
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Mi Jun 09, 2004 10:20 am    Titel:
Antworten mit Zitat

Habe nochmal perfekt gehasht, jetzt passts glaub Smile Habe es im oberen Beitrag editiert...
_________________
"...from the faith that you release comes an atheist peace."
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Sa Jul 24, 2004 9:01 am    Titel:
Antworten mit Zitat

Weiss jemand, wanns denn jetzt endlich die Scheine abzuholen gibt?
_________________
"...from the faith that you release comes an atheist peace."
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
Onkel Schnitzel
Gast


Benutzer-Info







Keine Trophäen
BeitragVerfasst am: Sa Jul 24, 2004 5:13 pm    Titel:
Antworten mit Zitat

wird sicher irgendwann auf der mailingliste bekannt gegeben, keine panik.
Nach oben
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Sa Jul 24, 2004 5:30 pm    Titel:
Antworten mit Zitat

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."
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
Onkel Schnitzel
Gast


Benutzer-Info







Keine Trophäen
BeitragVerfasst am: Sa Jul 24, 2004 5:37 pm    Titel:
Antworten mit Zitat

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.
Nach oben
Provokatiker
Administrator
Administrator


Benutzer-Info Geschlecht: Geschlecht:Männlein
Alter: 42
Beiträge: 7833
Wohnort: E-Town
Lieblingsband:
Bad Religion
Karma: +50/-47


Trophäen: 12
BeitragVerfasst am: Sa Jul 24, 2004 6:36 pm    Titel:
Antworten mit Zitat

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."
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen MSN Messenger
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Trophäen-Jagd.de Foren-Übersicht -> Das ultimative Archiv Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1


 
Gehe zu:  
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


Protected by phpBB Security © phpBB-Amod
phpBB Security hat 3,867 Exploit-Angriffe blockiert.
Powered by phpBB © 2001, 2005 phpBB Group

- Unread Post Information 2 Database V2 is inactive -