Übung 10

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Übung 10

Beitrag von Stefan1992 »

Hallo,

in der Aufgabe soll ja erklärt werden, warum das Beispiel so nicht entstehen konnte.
Soll man den Algorithmus insert jetzt auf das schon vorhandene Array anwenden oder soll man von einem noch leeren Array ausgehen?
Wenn man dieses schon vorhandene Array verwenden soll, sehe ich kein Argument, warum die Folge nicht korrekt sein sollte. Geht man jetzt von einem leeren Array aus, das durch die Werte gefüllt werden soll und im Endeffekt so aussehen sollte, wie das gegebene Array, sehe ich eine einzige Stelle, die so nicht funktionieren könnte. (Weiß jetzt nicht, ob ich die Stelle nennen darf/kann/soll?!?)

Und darüber hinaus, welche Invariante soll dann verifiziert werden? Die des Algorithmus' insert oder die der Hashtable?

Gruß, Stefan

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: Übung 10

Beitrag von R_Egert »

Soll man den Algorithmus insert jetzt auf das schon vorhandene Array anwenden oder soll man von einem noch leeren Array ausgehen?
Der Umgang von Insert mit bereits korrekt eingefügten Keys sollte diese Frage egtl. klären :D
...Weiß jetzt nicht, ob ich die Stelle nennen darf/kann/soll?!?)
In Ihrem Testat sollen Sie diese Stelle durchaus nennen ^^. Hier im Forum allerdings nicht ;)
Und darüber hinaus, welche Invariante soll dann verifiziert werden? Die des Algorithmus' insert oder die der Hashtable?
Da es sich um eine gegebene Hashtable handelt, die Invariante der Hashtable ;)

Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Anica
Neuling
Neuling
Beiträge: 3
Registriert: 16. Apr 2012 16:38

Re: Übung 10

Beitrag von Anica »

Hallo,
ich hab nur eine kurze Frage:
Fängt man bei den Hash Funktionen mit i=0 oder mit i=1 an?
Ich bin mir nämlich nicht mehr sicher, ob wir hier in der Vorlesung die 0 zu den natürlichen Zahlen hinzugenommen haben oder nicht?

Stefan1992
Mausschubser
Mausschubser
Beiträge: 45
Registriert: 20. Okt 2011 22:38

Re: Übung 10

Beitrag von Stefan1992 »

Hey,
ich habs mit 0 ausprobiert. Da funktioniert es zumindest ganz gut :)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 10

Beitrag von Prof. Karsten Weihe »

Anica hat geschrieben: Fängt man bei den Hash Funktionen mit i=0 oder mit i=1 an?
Mit 0, um die Modulorechnung einfach zu halten.

Anica hat geschrieben: Ich bin mir nämlich nicht mehr sicher, ob wir hier in der Vorlesung die 0 zu den natürlichen Zahlen hinzugenommen haben oder nicht?
Hatten wir. Aber im Wiki hätten Sie es auch gefunden. 8)

KW

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Übung 10

Beitrag von aileen »

Prof. Karsten Weihe hat geschrieben:
Anica hat geschrieben: Fängt man bei den Hash Funktionen mit i=0 oder mit i=1 an?
Mit 0, um die Modulorechnung einfach zu halten.
Müsste es dann aber im Wiki in der Implementationsinvariante des Hashsets im 5. Punkt nicht heißen, dass es für jedes K ein i aus N0 gibt, sodass die zwei nachfolgenden Punkte erfüllt sind und bei 5.2 die Positionen F(0, Nmax, K), ... , F(i-1, Nmax, K) sind belegt, falls i > 0?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 10

Beitrag von Prof. Karsten Weihe »

aileen hat geschrieben: Müsste es dann aber im Wiki in der Implementationsinvariante des Hashsets im 5. Punkt nicht heißen, dass es für jedes K ein i aus N0 gibt
Nein, das \(i\) ist ja kein Arrayindex, sondern der Zähler dafür, der wievielte Versuch das jetzt war, eine leere Stelle zu finden (schlechtes Deutsch, ich weiß...).

KW

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Übung 10

Beitrag von aileen »

Prof. Karsten Weihe hat geschrieben: Nein, das \(i\) ist ja kein Arrayindex, sondern der Zähler dafür, der wievielte Versuch das jetzt war, eine leere Stelle zu finden (schlechtes Deutsch, ich weiß...).

KW
Dass das i die Anzahl der Versuche, eine leere Stelle zu finden, ist, war mir schon klar(so wie ich das gerade sehe, fängt man aber trotzdem unpraktischerweise bei Null an zu zählen), aber die Frage
Anica hat geschrieben: Fängt man bei den Hash Funktionen mit i=0 oder mit i=1 an?
bezieht sich doch gerade darauf, welcher Wert für i in F(i, Nmax,K) als erstes eingesetzt werden soll, nämlich die Null.
Wenn der Wert F(0, Nmax, K) eine Position im Array bezeichnet, die nicht void ist, kann ich K an dieser Position einfügen & das i, von dem in Punkt 5 die Rede ist, ist gleich Null. Oder übersehe ich hier irgendetwas?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 10

Beitrag von Prof. Karsten Weihe »

aileen hat geschrieben:(so wie ich das gerade sehe, fängt man aber trotzdem unpraktischerweise bei Null an zu zählen)
Auf welche Stelle beziehen Sie sich?

KW

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Übung 10

Beitrag von aileen »

Prof. Karsten Weihe hat geschrieben: Auf welche Stelle beziehen Sie sich?

KW
Darauf, dass Sie gesagt haben, wir fangen mit i = 0, also mit F(0, Nmax, K) an. Dies wäre dann zwar der erster Versuch, aber die Nummerierung beginnt bei 0.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 10

Beitrag von Prof. Karsten Weihe »

aileen hat geschrieben:
Prof. Karsten Weihe hat geschrieben: Auf welche Stelle beziehen Sie sich?
Darauf, dass Sie gesagt haben, wir fangen mit i = 0
Wann/wo habe ich das gesagt? :roll:

KW

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Übung 10

Beitrag von aileen »

Prof. Karsten Weihe hat geschrieben:
Anica hat geschrieben: Fängt man bei den Hash Funktionen mit i=0 oder mit i=1 an?
Mit 0, um die Modulorechnung einfach zu halten.

KW

SchottCh
Mausschubser
Mausschubser
Beiträge: 74
Registriert: 4. Okt 2010 16:39

Re: Übung 10

Beitrag von SchottCh »

Hallo,
im Wiki Artikel Hashtabel wird unter Punkt 5 gesagt das i ein Element der natürlichen Zahlen ohne 0 ist.
https://hermes.algo.informatik.tu-darms ... /Hashtable

Also i bei 1 startet.
Gruß

aileen
Erstie
Erstie
Beiträge: 20
Registriert: 26. Apr 2012 13:28

Re: Übung 10

Beitrag von aileen »

SchottCh hat geschrieben:Hallo,
im Wiki Artikel Hashtabel wird unter Punkt 5 gesagt das i ein Element der natürlichen Zahlen ohne 0 ist.
https://hermes.algo.informatik.tu-darms ... /Hashtable

Also i bei 1 startet.
Gruß
& genau darum geht es mir ja gerade..Dass der Eintrag im Wiki nicht dazu passt, dass hier gesagt wurde, wir sollen mit i=0 beginnen.

SchottCh
Mausschubser
Mausschubser
Beiträge: 74
Registriert: 4. Okt 2010 16:39

Re: Übung 10

Beitrag von SchottCh »

Mhh das würde mich jetzt aber auch interressieren. Wenn man das Start i = 0 wählt, würde es glaube ich für das Übungsblatt stimmen, so würde man zumindest auf die position von 17 und 29 kommen, also habe jetzt nur mal die beiden mit i = 0 gerechnent, da ich schon alles mit i = 1 gerechnet habe.

Antworten

Zurück zu „Archiv“