Ob eine Formel fehlerhaft ist oder nicht, erkennst du daran, dass am Ende des gesamten Ausdrucks auf jeden Fall "mod N_max", also ein Modulo stehen müsste. Dadurch ist garantiert, dass das Ergebnis zwischen 0 und N_max - 1 liegt, also immer ein möglicher Index raus kommt.TobiTobske hat geschrieben: Und nun nochmal zu meiner anderen Frage, die mir noch zum Verständnis sehr helfen würde: Angenommen, in der Klausur komme ich auf den Fall, dass ich auch nach dem zweiten Durchlauf der HashFunktion den Wert nicht einspeichern kann, weil sie eben nur endlich definiert ist. Kann ich dann davon ausgehen, dass ich mich verrechnet habe oder kann sowas in der Praxis durchaus vorkommen und der Wert wird dann einfach nicht gespeichert?
Ferienübungsblatt
Moderator: AI 2
Re: Ferienübungsblatt
-
- Mausschubser
- Beiträge: 58
- Registriert: 15. Jan 2014 20:50
Re: Ferienübungsblatt
Mmmh, aber in diesem Fall steht das doch bei der Gesamtfunktion F auf jeden Fall dabei?! F setzt sich ja aus F1 und F2 mit Linearfaktor zusammen. Und bei F steht ja ganz am Ende das mod Nmax. Mein Problem ist halt, dass ich ja auf einen sinnvollen Index (0-12) komme, der aber schon belegt ist und ich einen dritten Versuch starten müsste, um den Wert einzufügen.SophiaLi1 hat geschrieben: Ob eine Formel fehlerhaft ist oder nicht, erkennst du daran, dass am Ende des gesamten Ausdrucks auf jeden Fall "mod N_max", also ein Modulo stehen müsste.
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Beispiel (k=100000)
F2 = k + (k mod 13) => 100000 + 4 = 100004
Sagen wir es ist der 6. Versuch (i-1 = 5)
F = (4 + 5*100004) mod 13 = 5
Wo ist das Problem mit großen Zahlen?
F2 = k + (k mod 13) => 100000 + 4 = 100004
Sagen wir es ist der 6. Versuch (i-1 = 5)
F = (4 + 5*100004) mod 13 = 5
Wo ist das Problem mit großen Zahlen?
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Kannst du das etwas genauer ausführen, denn ich bin der Meinung es ist unmöglich einen ungültigen Index mit mod zu kriegen
Außerdem verstehe ich dein Problem mit der F2 nicht, denn dort kann etwas gegen Unendlich rauskommen das ist doch egal
Außerdem verstehe ich dein Problem mit der F2 nicht, denn dort kann etwas gegen Unendlich rauskommen das ist doch egal

- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Also beim ersten stimme ich dir vollkommen zu und damit wollte ich meine Argumentation machenSophiaLi1 hat geschrieben:
Es ist nur durch mod N_max sichergestellt, dass man als Index auch einen gültigen Index aus dem Bereich 0 bis (N_max - 1) erhält, das heißt, einen Index, der innerhalb des Arrays liegt. Würde man versuchen, auf einen Index zuzugreifen, der außerhalb dieses Bereichs liegt, so würde man eine IndexOutOfBounds Exception erhalten und das Programm würde abbrechen. (Also der Fall, in dem man auf einen "unendlich hohen" Index zugreifen will.)
Das ist nicht egal, da der Indexbereich für jeden Array endlich ist und ich keinen beliebig großen Index finden kann, sondern nur solche, die als Index für den Array in Frage kommen.

Die Funktion zur Bestimmung des Indexes setzt sich zusammen aus F = (IRGENDWAS) mod 13. F1 und F2 können meiner Meinung nach unendlich sein, denn wie du ja selbst gesagt hast stellt mod sicher dass der Index nicht überschritten wird. Das Ergebnis von F2 ist ja nur eine Hilfsfunktion, warum soll das denn eingeschränkt sein?
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Ok, ich glaube ich verstehe was du meinst, aber wo steht denn das F nur für i>2 benutzt wird. Ich habe das so verstanden, dass es die Funktion F
zur Index-Berechnung gibt und diese sich auch den anderen Funktionen zusammensetzt.
zur Index-Berechnung gibt und diese sich auch den anderen Funktionen zusammensetzt.
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Laut dem Aufgabenblatt hängt F nicht von einem Index ab
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Das mit dem Fi scheint mir sehr weit hergeholt. Wenn man sagt dass die Funktion Fi(i,nmax,k) ist
Dann müsste man auch so weitermachen, d.h. man bräuchte F3. F4 etc.
Aber das ganze ist unnötig denn wenn man einfach die Funktion F nimmt und brav die Werte aus den anderen Beiden Funktionen
einsetzt kommt man auch auf korrekte Indizes. Wo hast du denn das mit fk her? Und wo das mit i > 2? In den Vorlesungsfolien
steht nämlich immer F(...)
Dann müsste man auch so weitermachen, d.h. man bräuchte F3. F4 etc.
Aber das ganze ist unnötig denn wenn man einfach die Funktion F nimmt und brav die Werte aus den anderen Beiden Funktionen
einsetzt kommt man auch auf korrekte Indizes. Wo hast du denn das mit fk her? Und wo das mit i > 2? In den Vorlesungsfolien
steht nämlich immer F(...)
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Kann mir jemand bei Aufgabe 3 weiterhelfen ich verstehe nicht wie es nach der Merge-Operation von 100, 200, 400 weitergehen soll.
Re: Ferienübungsblatt
Wieso, was ist das Problem? Was würdest du denn vermuten, was richtig wäre, hast du überhaupt schon einen denkansatz?
Ich persönlich bin mir recht unsicher, meine Überlegung wäre wie folgt:
Merge 180,200,300 zur Wurzel. Jetzt das ganze dabei umlegen, dass es den Vorgaben entspricht, da die Knoten nie voll belegt sein dürfen, damit du ohne probleme einfügen könntest.
Nun wird die 500 gelöscht.
Reicht das als ansatz?
mfg jan
Ich persönlich bin mir recht unsicher, meine Überlegung wäre wie folgt:
Merge 180,200,300 zur Wurzel. Jetzt das ganze dabei umlegen, dass es den Vorgaben entspricht, da die Knoten nie voll belegt sein dürfen, damit du ohne probleme einfügen könntest.
Nun wird die 500 gelöscht.
Reicht das als ansatz?
mfg jan
- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Hi,
danke für die Antwort, aber wie hast du es hingekriegt dass 180,200 und 300 in der Wurzel stehen?
Ich frage mich sowieso warum das löschen der 500 so kompliziert ist und man nicht einfach eine Rotation anwenden darf
danke für die Antwort, aber wie hast du es hingekriegt dass 180,200 und 300 in der Wurzel stehen?
Ich frage mich sowieso warum das löschen der 500 so kompliziert ist und man nicht einfach eine Rotation anwenden darf
Re: Ferienübungsblatt
moin moin,
import java.noob schau vllt. nochmal die Videos und Folien an, habe da gestern auch nur
im Kopf gehabt und Sophia ihre kostbare Zeit gestohlen,
Nach einigen Wdh. der Videos hat es dann klick gemacht
An manchen Stellen überhört man so Tips wie: der Pointer kann nur auf Knoten zeigen die noch Werte entbehren könnten etc. wenn er minimal ist, musst du ihn vorher "umbauen". da ein Merge nach den Wurzel Mergen nicht mehr geht und auch wenig Sinnmachen würde, gibts laut Videos die Rotate-Funktion, die aus so einem Fall helfen kann. somit steht die 500 nicht mehr alleine da und kann gelöscht werden
MfG
Sven
PS:
Auf Seite 2 Findest du auch noch Tipps von Sophia als sie an mir verzweifelte xd^^
import java.noob schau vllt. nochmal die Videos und Folien an, habe da gestern auch nur


Nach einigen Wdh. der Videos hat es dann klick gemacht


An manchen Stellen überhört man so Tips wie: der Pointer kann nur auf Knoten zeigen die noch Werte entbehren könnten etc. wenn er minimal ist, musst du ihn vorher "umbauen". da ein Merge nach den Wurzel Mergen nicht mehr geht und auch wenig Sinnmachen würde, gibts laut Videos die Rotate-Funktion, die aus so einem Fall helfen kann. somit steht die 500 nicht mehr alleine da und kann gelöscht werden
MfG
Sven
PS:
Auf Seite 2 Findest du auch noch Tipps von Sophia als sie an mir verzweifelte xd^^

- import java.noob
- Windoof-User
- Beiträge: 25
- Registriert: 2. Mär 2014 12:28
Re: Ferienübungsblatt
Hi,
danke, aber man kann doch gleich die Rotate-Funktion anwenden. Was hält einen denn davon ab?
400
300/350 500
Funktion der Rotate funktion ist dass ich den oberen Wert mit dem Vorgänger/Nachfolger ersetze.
350 wäre der Vorgänger von 400, also nach oben
400 350
300 - 500
jetzt noch die 400 in den Rechten Knoten um rotate abzuschließen und dann die 500 löschen - fertig.
Wenn du mir nochmal einen Hinweis geben könntest wäre super ich stehe ziemlich auf dem Schlauch
danke, aber man kann doch gleich die Rotate-Funktion anwenden. Was hält einen denn davon ab?
400
300/350 500
Funktion der Rotate funktion ist dass ich den oberen Wert mit dem Vorgänger/Nachfolger ersetze.
350 wäre der Vorgänger von 400, also nach oben
400 350
300 - 500
jetzt noch die 400 in den Rechten Knoten um rotate abzuschließen und dann die 500 löschen - fertig.
Wenn du mir nochmal einen Hinweis geben könntest wäre super ich stehe ziemlich auf dem Schlauch

Re: Ferienübungsblatt
Mhm, ich muss gleich weg, aber ich versuchs. Wir haben folgende Situation:
- die Wurzel hat nur einen Key
- die beiden Nachfolger der Wurzel haben nur minimale Anzahl an Keys
- man kann also mit dem Pointer nicht auf einen ihrer Nachfolger zeigen
- in diesem Fall wendet man "Merge Root" an, siehe Foliensatz dazu
Re: Ferienübungsblatt
Sophia hat eben den Hauptdenkfehler angesprochen,
Ich dachte auch immer, dass ist so ein konstrukt, und egal wie ich wohin rotiere es passt wenn danach die logische Sichtweise passt. ABER das geht so nicht, weil du siehst den Baum als Visualisierung, und in REALITÄT kommt der Pointer ja von der Wurzel an und muss sich zum Wert durchschlagen, weshalb der Pointer nicht den ganzen komplexen baum kennt wie du der ihn sieht, sondern nur seinen weg. Dieser ist so definiert, dass er auf minimale Knoten beim löschen und auf maximale beim einfügen nicht zugreifen kann. ALSO musst du ihn erst so umbauen, dass der Pointer hindarf und die gewünschte Operation ausführen kann.
MfG
Ich dachte auch immer, dass ist so ein konstrukt, und egal wie ich wohin rotiere es passt wenn danach die logische Sichtweise passt. ABER das geht so nicht, weil du siehst den Baum als Visualisierung, und in REALITÄT kommt der Pointer ja von der Wurzel an und muss sich zum Wert durchschlagen, weshalb der Pointer nicht den ganzen komplexen baum kennt wie du der ihn sieht, sondern nur seinen weg. Dieser ist so definiert, dass er auf minimale Knoten beim löschen und auf maximale beim einfügen nicht zugreifen kann. ALSO musst du ihn erst so umbauen, dass der Pointer hindarf und die gewünschte Operation ausführen kann.
MfG