Seite 1 von 2

Heap: decrease key: Seltsame Lösung

Verfasst: 31. Aug 2015 17:55
von james0707007
Ich habe eben eine Aufgabe zu "decrease key" gemacht, die Aufgabenstellung lautete: "Reduzieren Sie den Schlüssel mit ID = 7 auf den Wert Key = 0. Geben Sie den Heap und das Array Positions nach der Iteration i := 3 an." In der Lösung wurde allerdings der Schlüssel mit ID 8 auf 0 reduziert.
Hier der Seed: 96a132b46aabf19e7f5b56508bcf15ff

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 3. Sep 2015 14:23
von js70
Die gleiche Art Fehler tritt bei den folgenden seeds auf:
d63e5b61951f9fed66fd2ba5f93fa7c5
328d19604c21b15da1076b2e5aa63603

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 3. Sep 2015 16:29
von cr4ckl1n
Moin,
die Seeds sind auch fehlerhaft:
34c8a0ce6ada8e12894a38afaa6f75c4
d42420121b82d9006ec104e568553e84

Liegt das vielleicht einfach am decrease key ?

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 3. Sep 2015 20:33
von KevinK
Hi :)
Bei mir das selbe.
57c5a2e28835b7939b7e944622cb8dbd
Man muss wohl immer bis das "Problem" behoben ist den ID+1 Key wechseln.

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 6. Sep 2015 13:47
von KevinK
Dazu hatte ich gerade das Problem, dass gefragt wurde, wie Heap und Array nach der 3 Iteration aussehen, es aber nur 2 Iterationen gab, bis alles an richtiger Stelle war.
015bca677a98aab6fb9e41de757a5369

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 7. Sep 2015 02:35
von headhumper
Reduzieren Sie den Schlüssel mit ID = 10 auf den Wert Key = 18. Geben Sie den Heap und das Array Positions nach der Iteration i := 2 an.

Angefasst wurden in der Lösung die Elemente mit ID 5 und 11 :?:

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 7. Sep 2015 12:11
von KevinK
Ja wie schon ein paar Posts davor geschrieben das ist glaube ich ein kleiner Fehler. Probier einfach solange dieser nicht behoben ist, das ID+1 Element einen neuen Key zuzuweisen also nicht ID10 sondern ID11 das hat bei mir bis jetzt immer geklappt :)

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 9. Sep 2015 23:50
von aloha
Hallo,
mich stört bei den Heap-Aufgaben abgesehen von dem Problem mit der ID noch zusätzlich, dass es Differenzen beim Iterationsschema zwischen heap: decrease key und heap: insert gibt.
- Heap: decrease key beginnt ab der 0. Iteration und es wird schon in der 0. Iteration nach dem Verringern des Keys mit dem Vorgänger getauscht.
- Heap: insert beginnt ab der 1. Iteration und es wird nach dem Erstellen eines neuen Keys noch nicht mit dem Vorgängerkey getauscht (das beginnt erst ab der 2. Iteration)
Somit würde ich z.B. bei der Aufgabenstellung "Geben Sie den Heap nach der Iteration i := 1 an." im ersten Fall bis zu zwei mal mit dem Vorgänger tauschen und im zweiten Fall kein einziges Mal.
Steckt da irgendwie ein Sinn dahinter oder ist das ein Fehler?

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 10. Sep 2015 09:50
von headhumper
Auch dazu gibt es schon ein Issue bei Github. Die Entwickler scheinen da aber zur Zeit nicht reinzuschauen.

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 10. Sep 2015 12:52
von bekir
aloha hat geschrieben:Hallo,
mich stört bei den Heap-Aufgaben abgesehen von dem Problem mit der ID noch zusätzlich, dass es Differenzen beim Iterationsschema zwischen heap: decrease key und heap: insert gibt.
- Heap: decrease key beginnt ab der 0. Iteration und es wird schon in der 0. Iteration nach dem Verringern des Keys mit dem Vorgänger getauscht.
- Heap: insert beginnt ab der 1. Iteration und es wird nach dem Erstellen eines neuen Keys noch nicht mit dem Vorgängerkey getauscht (das beginnt erst ab der 2. Iteration)
Somit würde ich z.B. bei der Aufgabenstellung "Geben Sie den Heap nach der Iteration i := 1 an." im ersten Fall bis zu zwei mal mit dem Vorgänger tauschen und im zweiten Fall kein einziges Mal.
Steckt da irgendwie ein Sinn dahinter oder ist das ein Fehler?
Ganz allgemein finde ich es verwirrend, dass bei manchen Algos ab 0, und bei anderen ab 1 gezählt wird. Ich komme da immer ganz durcheinander. Etwas mehr Einheitlichkeit wäre wünschenswert.

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 11. Sep 2015 18:12
von NonStop
Der Thread wurde am 31. Aug 2015 erstellt, bis heute ist der Fehler nicht behoben. Kann wenigstens einer sagen, ob es mit der Iterationszahl und ID's auch in der Klausur so sein wird? Es wäre schade, wenn man sich daran gewöhnt, Heap-Aufgaben zu lösen, wie es auf foo-Plattform erwartet wird und in der Klausur plötzlich mit ID=n tatsächlich ID=n und nicht ID=n+1 gemeint wird.

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 11. Sep 2015 22:09
von Darmstadt
Guden,
echt komisch teilweise. Die Lösung ist Laut Korrekturausgabe richtig, jedoch nach den Iterationssteps falsch.
solution/10/ae95d21b1909bda86b6270d804f47f8c.

Ich denke die Entwickler werden den Fehler (sofern es einer ist) schon noch fixen, bedenkt es sind an der TU Darmstadt "Semesterferien". :lol:

Mich würde jedoch mal interessieren, inwieweit diese ID+1 Annahme korrekt ist.
Leider habe ich den bereitgestellten Vorlesungsmaterialien noch im Algo-Wiki keine Hinweise darauf gefunden, ev. jemand anders?

PS: Bitte keinen Lünchmob oder Shitstorm hier jetzt eröffnen, mir scheint hier wäre ein Potenzial vorhanden.

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 14. Sep 2015 21:18
von Nullmann
Gleiches bei mir. Ich soll den Key mit der ID 6 auf 5 reduzieren - die Lösung reduziert allerdings den Key mit der ID 7.

Seed: f12613bbc3192e2f471d7c39c178f30d

Edit: So dumm es auch ist, es ist einfach nur ein Anzeigefehler. Bei allen Versuchen, die ich bisher gestartet habe, wird die ID+1 verringert! (Wurde aber auch oben schon beschrieben, ups)

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 15. Sep 2015 13:11
von cvoelcker
Trotzdem würde ich mir eine Aussage vom Veranstalter dazu wünschen, da die Aufgabe ja immerhin Klausurrelevant ist und ich es eigentlich nicht als Klausurleistung sehe, mir Foo-Bugs zu merken und diese dann in der Klausur zu rechnen. Je nachdem ob die Lösungen mit Foo geprüft werden, kann das ganz schön in die Hose gehen.

Re: Heap: decrease key: Seltsame Lösung

Verfasst: 17. Sep 2015 20:35
von Nullmann
Weiß nicht seit wann, allerdings scheint bei mir die Aufgabe nun korrekt zu sein. Die angegebene ID wird reduziert.