Heap: decrease key: Seltsame Lösung

[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

[js70]

Die gleiche Art Fehler tritt bei den folgenden seeds auf:
d63e5b61951f9fed66fd2ba5f93fa7c5
328d19604c21b15da1076b2e5aa63603

[cr4ckl1n]

Moin,
die Seeds sind auch fehlerhaft:
34c8a0ce6ada8e12894a38afaa6f75c4
d42420121b82d9006ec104e568553e84

Liegt das vielleicht einfach am decrease key ?

[KevinK]

Hi
Bei mir das selbe.
57c5a2e28835b7939b7e944622cb8dbd
Man muss wohl immer bis das "Problem" behoben ist den ID+1 Key wechseln.

[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

[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

[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

[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?

[headhumper]

Auch dazu gibt es schon ein Issue bei Github. Die Entwickler scheinen da aber zur Zeit nicht reinzuschauen.

[bekir]

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.

[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.

[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".

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.

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

[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.

[Nullmann]

Weiß nicht seit wann, allerdings scheint bei mir die Aufgabe nun korrekt zu sein. Die angegebene ID wird reduziert.