Double Hashing Verständnis + Taschenrechner + Schwierigkeit

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Double Hashing Verständnis + Taschenrechner + Schwierigkeit

Beitrag von Nullmann »

Hallo zusammen,
ich sitze gerade verzweifelt vor der Double-Hashing-Aufgabe. Ich weiß nicht, wie man auf das Ergebnis kommt. F1 und F2 ausrechnen funktioniert gut, die finale Position aber nicht. Bei dem Beispiel unten komme ich auf:
(F1+(i-1)*F2) mod 14 = (13+0*26) mod 14 = 338 mod 14 = 2
und nicht, wie das Ergebnis richtig lauten sollte, 13.
Was mache ich falsch? Wo habe ich einen Denkfehler?

Außerdem wollte ich nachfragen, ob man im Testat dann einen Taschenrechner benutzen darf? Bei der schieren Masse an Berechnungen, die man bei der Aufgabe machen muss wäre es wahrscheinlich nicht schaffbar, im Testat mehre als einen Versuch hin zu bekommen. Zumal dann sehr einfach Flüchtigkeitsfehler rein kommen können, besonders auch bei den Größen der Zahlen.

Desweiteren: Ich habe mich zwar noch nicht an die B-Tree-Aufgabe gemacht, aber diese scheint ja noch schwerer bzw. aufwändiger zu sein als das Double Hashing. Wären dann nicht beide Aufgabentypen zusammen in einem Testat etwas zu viel?
Dateianhänge
Double Hashing.png
Double Hashing.png (46.39 KiB) 998 mal betrachtet

hololol2
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 27. Apr 2015 14:13

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von hololol2 »

Ganz einfacher Fehler:
13+0*26=13+0=13

Nein einen Taschenrechner darf man meines Wissens nicht benutzen

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von KaeferZuechter »

Double Hashing ist IMHO eine der einfachsten Aufgaben.

Tipp:
Rechenregeln für Kongruenzen
http://www.mathe-schule.de/download/pdf ... chnung.pdf

Das erspart die unnötig großen Zahlen und reduziert die Augabe im Wesentlichen auf das kleine Einmaleins.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von Nullmann »

Ah, da hab ich doch einfach das Plus und das Mal vertauscht.. Und beim X-ten mal drauf schauen merkt man sowas schon gar nicht mehr.
Danke euch beiden.

hololol2
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 27. Apr 2015 14:13

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von hololol2 »

Ja. Das sind so Fehler, die man selber niemals findet

kaeru
Neuling
Neuling
Beiträge: 2
Registriert: 22. Apr 2015 20:42

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von kaeru »

KaeferZuechter hat geschrieben:Double Hashing ist IMHO eine der einfachsten Aufgaben.

Tipp:
Rechenregeln für Kongruenzen
http://www.mathe-schule.de/download/pdf ... chnung.pdf

Das erspart die unnötig großen Zahlen und reduziert die Augabe im Wesentlichen auf das kleine Einmaleins.
Ich versteh nicht ganz wie mir die Rechenregeln helfen sollen :/ Kann mir vlt jemand ein Beispiel zeigen bei dem diese sich gut anwenden lassen? Schon mal Danke im Voraus :)

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von Nullmann »

Hallo zusammen, ich nochmal. Mittlerweile habe ich den Algo zwar verstanden, aber empfinde diese Aufgabe immer noch als sehr schwierig, da sehr rechenintensiv. Dies wirkt sich zum einen sehr stark auf die Zeit und auf die Fehleranfälligkeit aus. Zudem sind hier die Unterschiede in den Schwierigkeitsgraden noch extremer als bei den Algorithmen die zuvor bei Foo-Testaten gestellt wurden, weil die benötigte Zeit nach oben sehr groß ist. 10 Minuten für eine Aufgabe sind einfach zu viel, wenn man ein schlechtes Beispiel erwischt. Zum Vergleich Algos, die ich bekommen habe:
Einfaches Bsp: 6 Zahlen einfügen, 2 Kollisionen
Schweres Bsp: 14 Zahlen einfügen, 10 Kollisionen

Man kann sich vorstellen, dass sich die Zahlen dann auch nicht mehr im "Ein mal Eins" befinden, wenn es bei dem Einfügen einer Zahl 5 Kollisionen gibt. (10+5*56)mod18 ist schon eine Schwierigkeit für sich ohne Tachenrechner zu berechnen. Zumal das dann nur eine von 24 (14 Zahlen + 10 Kollisionen) Rechnungen dieser Art sind (obwohl natürlich nicht alle so schwer sind). Sodass ich diesen als den bisher schwierigsten Aufgabentyp empfinde.
Wenn ich mir dann noch bedenke, dass B-Tree noch schwerer sein soll, Hut ab...

Mfg,
Nullmann

PS: Ich habe das erste Foo-Testat nicht bestanden. Man kann dieses zwar später auch irgendwann nachholen, aber trotzdem lastet deswegen ein gewisser Druck auf mir ;)

Edit: Nach 3 Stunden Üben, 5 mit Rechnungen voll geschriebenen Seiten, 9 von 15 letzten Richigen (60 Prozent) und durchschnittlich 5 Minuten pro Aufgabe bin ich immer noch der Meinung, dass das viel zu viel pures, stupides Rechnen ist. Bei anderen Algos habe ich mir danach meistens gedacht "ach, da habe ich einen Denkfehler gemacht" oder "darauf muss ich das nächste Mal besser aufpassen". Wenn ich allerdings hier etwas falsch habe, ist es fast immer nur ein Rechenfehler.
Und ich hab das Gefühl, mein Kopf platzt. Wurden Rechner (und Algorithmen) nicht eigentlich dafür entworfen? Dass man eben nicht so viel per Hand ausrechnen muss?

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von luedecke »

Nullmann hat geschrieben:Hallo zusammen, ich nochmal. Mittlerweile habe ich den Algo zwar verstanden, aber empfinde diese Aufgabe immer noch als sehr schwierig, da sehr rechenintensiv. Dies wirkt sich zum einen sehr stark auf die Zeit und auf die Fehleranfälligkeit aus. Zudem sind hier die Unterschiede in den Schwierigkeitsgraden noch extremer als bei den Algorithmen die zuvor bei Foo-Testaten gestellt wurden, weil die benötigte Zeit nach oben sehr groß ist. 10 Minuten für eine Aufgabe sind einfach zu viel, wenn man ein schlechtes Beispiel erwischt. Zum Vergleich Algos, die ich bekommen habe:
Einfaches Bsp: 6 Zahlen einfügen, 2 Kollisionen
Schweres Bsp: 14 Zahlen einfügen, 10 Kollisionen
Die Aufgaben aus dem Übungsmodus werden nicht immer 1 zu 1 in den Testatmodus übernommen ;)
Nullmann hat geschrieben: (10+5*56)mod18 ist schon eine Schwierigkeit für sich
Mathe 1 Script @ 2.1.1. Modulare Arithmetik (Anhang), aber auf auf Wikipedia nachlesbar, insofern Mathe 1 für Infs nicht belegt wurde. Sollte man vllt. ins Algowiki aufnehmen.

\((10+5\cdot56)\ mod\ 18\ \equiv\ (10\ mod\ 18\ +\ 5\cdot56\ mod\ 18)\ mod\ 18 \equiv\)
\((10\ mod\ 18\ +\ ((5\ mod\ 18) \cdot (56\ mod\ 18)\ mod\ 18)\ mod\ 18 =\)
\((10+ 5\ \cdot 2)\ mod\ 18\ =\ 2\)
In Kurz: Jede Addition und jede Multiplikation lassen sich sauber durchMod'den. Da das Schema gleich bleibt, kann man diese zwei Regeln stets anwenden. Die Einzige Schwierigkeit besteht dann eigentlich nur noch beim \(56\ mod\ 18\)
Geht mit Übung alles im Kopf :) Mit mehr Sicherheit dann auf dem Papier!
Nullmann hat geschrieben:Wurden Rechner (und Algorithmen) nicht eigentlich dafür entworfen? Dass man eben nicht so viel per Hand ausrechnen muss?
Dennoch benötigen diese ein Programm von einem Menschen, welches der Mensch vorher an geschickten Testwerten mehrmals (auch per Hand) getestet haben sollte. :idea:

Das durch foo gezeigte Beispiel, stellt ein Problem von Hashtables dar, das sowohl du, als auch die Rechner haben. Somit auch den Nutzen und die Problematik dieser Datenstruktur, die man durch einfaches Pro und Contra bezüglich der Zugriffszeit und Datenmenge abzuwägen sind. Deshalb gibt es auch drei Variationen dieser Aufgabe.

Demnach glaube ich, dass der didaktische Wert dieser Aufgabe gewährleistet ist. Wenn nicht, wie sollte man es besser machen?
Dateianhänge
Mathe 1 Script 2.1.1. Modulare Arithmetik
Mathe 1 Script 2.1.1. Modulare Arithmetik
mod.PNG (36.71 KiB) 788 mal betrachtet

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von Nullmann »

luedecke hat geschrieben: \((10+5\cdot56)\ mod\ 18\ \equiv\ (10\ mod\ 18\ +\ 5\cdot56\ mod\ 18)\ mod\ 18 \equiv\)
\((10\ mod\ 18\ +\ ((5\ mod\ 18) \cdot (56\ mod\ 18)\ mod\ 18)\ mod\ 18 =\)
\((10+ 5\ \cdot 2)\ mod\ 18\ =\ 2\)
Vielen Dank für das Beispiel, dadurch konnte ich zumindest meine durchschnittliche zeit von 5 auf 3 Minuten verkürzen. Muss dann vor dem Testat viel üben und mich währenddessen ziemlich konzentrieren, um keine kleinen Rechenfehler zu machen.
luedecke hat geschrieben:Die Aufgaben aus dem Übungsmodus werden nicht immer 1 zu 1 in den Testatmodus übernommen ;)
*hust* hab ich beim ersten Testat bemerkt *hust*
(Soll jetzt keine Anschuldigung sein, nur eine nebensächliche Bemerkung)

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von sqrt(2) »

Hallo,
wenn ich es richtig verstanden habe dürfen wir keinen Taschenrechner benutzen?

Danke im Voraus.
Gruß

hololol2
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 27. Apr 2015 14:13

Re: Double Hashing Verständnis + Taschenrechner + Schwierigk

Beitrag von hololol2 »

Nein, keine Hilfsmittel.

Antworten

Zurück zu „Archiv“