Foo Aufgaben für die Klausur

robtothein
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 1. Aug 2014 13:33

Re: Foo Aufgaben für die Klausur

Beitrag von robtothein »

NonStop hat geschrieben:
Prof. Karsten Weihe hat geschrieben:Hallo allerseits,

Methode decrease key von Heap sollte keine falschen Lösungen mehr liefern, der Off-by-One-Error ist korrigiert.

KW
Hallo,
ich habe noch eine Frage bezüglich der Iterationenzahl.
- 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)

Ist das auch ein Fehler in der Implementierung eines der beiden Algorithmen auf foo-Plattform oder soll es so sein?
Bei mir beginnen beide ab der 1. Iteration. Wurde glaube eben geupdatet.
VG,
robtothein

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

Re: Foo Aufgaben für die Klausur

Beitrag von Prof. Karsten Weihe »

NonStop hat geschrieben: Ist das auch ein Fehler in der Implementierung eines der beiden Algorithmen auf foo-Plattform oder soll es so sein?
Das müssen wir uns nach der Klausur überlegen, bis dahin wird es keine Änderungen an den Aufgaben mehr geben, die die Logik modifizieren.

KW

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Foo Aufgaben für die Klausur

Beitrag von NonStop »

robtothein hat geschrieben: Bei mir beginnen beide ab der 1. Iteration. Wurde glaube eben geupdatet.

Habe gerade beide Aufgaben noch mal getestet, es ist immer noch so. Hier ist Iteration 1 von Insert:
Bild
Das neue Heap-Element wird nur eingefügt. Vertauscht wird es erst ab der 2. Iteration.

Hier ist Iteration 1 von decrease key:
Bild
Der Schlüsselwert wird verringert und direkt mit dem Vorgänger vertauscht, falls nötig.

Das ist das Komische :)

Crystal
Erstie
Erstie
Beiträge: 13
Registriert: 10. Sep 2015 16:46

Re: Foo Aufgaben für die Klausur

Beitrag von Crystal »

Ich fürchte B-Tree: Insert funktioniert noch nicht so ganz einwandfrei.

https://foo.algo.informatik.tu-darmstad ... 4255f24524

In dem Schritt 4 wird die Invariante eiskalt ignoriert.

Antworten

Zurück zu „Archiv“