FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

Fragen zu AD

Fragen zu AD 2010-01-30 19:42
Baum
Hey. Da ich alle AD Aufgabenblätter durcharbeite und mit sicherheit öfter mal Fragen haben werde, mache ich hier mal einen allgemeinen Thread auf und lade meine Kommilitionen natürlich herzlich ein, ihn ebenfalls für die Klausurvorbereitung zu nutzen. Finde solche Sammelthreads immer sehr nützlich, da manche Fragen auch für andere Interessant sind.

Meine erste Frage bezieht sich auf die Heaps. Genauer geht es um das, was Herr Jantzen in seinen Folien den DownHeap nennt. (Also Aufgabenblatt 3 die 3. Aufgabe)

Ich habe den DownHeap so verstanden, dass ich beim "Absickern" eigentlich den Array von links nach rechts durchlaufe und beim ersten größeren Kindsknoten (MaxHeap) Vater mit Kind vertausche. Ist also das linke Kind größer, wird es auch zuerst vertauscht.

So ist das mMn auch in der Lösung zu 3.3.2 gemacht worden. Bei 3.3.3 wird aber plötzlich beim Absickern(also nicht beim Durchsuchen auf HeapVerletzungen, da geht man von rechts nach links) nicht mehr das linke größere Kind "bevorzugt", sondern es wird einfach das rechte genommen.  

Als Mensch sehe ich natürlich, dass das zu weniger Vertauschungen führt, aber wie funktioniert denn der Algorithmus? Der wird doch nicht prüfen, wieviele Schritte eine bestimmte Operation nach sich zieht und beim Suchen des kleineren Kindes ist es unlogisch einen Knoten zu überspringen um den rechten zu prüfen und ggbfalls zu nehmen.

Ist die Lösung also falsch oder bin ich mit meinen Gedanken in die falsche Richtung gefahren?

RE: Fragen zu AD 2010-01-30 21:10
Anonymer User
Für mich sieht die Musterlösung richtig aus. Wo wird den deiner Meinung
nach falsch getauscht? (Hast du vielleicht übersehen/lesen, dass da anders
als bei 3.3.2 der Baum immer nur nach einer vollständigen Down-Heap-
Operation abgebildet wird?)

Zunächst wird da 6 mit 14 getauscht (14 > 12, also macht das Sinn), dann
6 mit 13.

Dann wird die Down-Heap-Operation auf den Knoten mit der 4 angewandt
und die mit der 10 getauscht (macht auch Sinn wegen 10 > 8). Die 4 wandert
dann noch weiter nach unten und tauscht mit der 7 (macht auch Sinn wegen
7 > 5).

Und die Down-Heap-Operation auf die 2 sieht für mich auch korrekt aus
(14 > 10, also rechter Zweig, dann 13 > 12 also wieder rechter Zweig, zu-
letzt mit der 6, weil auch die noch grösser als die 2 ist).

Frank :)

RE: Fragen zu AD 2010-01-30 21:15
Anonymer User
Gnarf! Jetzt sehe ich erst, was du falsch verstanden hast. Du schreibst:

Ich habe den DownHeap so verstanden, dass ich beim "Absickern" eigentlich den Array von links
nach rechts durchlaufe und beim ersten größeren Kindsknoten (MaxHeap) Vater mit Kind vertausche.

Das ist *falsch*. Du wanderst im Array nicht von links nach rechts, sondern vergleichst den
aktuellen Knoten k mit seinem linken *und* seinem rechten Kind. Ist eines davon grösser als
k, so tauscht du k mit dem *grösseren* der beiden!

Ist i der Index (im Array) des gerade betrachteten Knotens, so kommst du bei einem Heap
sehr leicht an das linke und rechte Kind. Dies liegt nämlich im Array bei i*2 bzw. bei i*2 + 1.
(Array startet dafür mit Index 1 nicht mit 0!)

Alles klar?

Frank :)

PS Das Kapitel über Heaps im Cormen ist sehr gut!

RE: Fragen zu AD 2010-01-30 21:17
Anonymer User
Noch eine Kleinigkeit: Das steht nicht im Widerspruch zur Lösung
von 3.3.2. Dort ist nämlich zufällig der linke Kindsknoten jedes Mal
der grössere der beiden Kindsknoten (und grösser als der gerade
betrachtete Knoten, daher kommt es zur Vertauschung).

So, genug, und ich such mal wieder meinen Account raus, dann
kann ich meine Einträge auch endlich mal wieder editieren ;-)

Frank :)

RE: Fragen zu AD 2010-01-30 21:30
Baum
so tauscht du k mit dem *grösseren* der beiden!

Ach so ist das. War also Zufall, dass es mal immer der linke Kindsknoten und dann immer der rechte war. So macht das schon Sinn, ich danke dir!

RE: Fragen zu AD 2010-01-30 23:11
Anonymer User
Wer es noch nicht kennen sollte:
Wenn ihr euch die RB und AVL Bäume verdeutlichen wollt, ist das hier eine große Hilfe
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

RE: Fragen zu AD 2010-02-10 18:02
Anonymer User
Laufzeitanalyse 2 (PDF "2auf1" Seite 47)

[img]http://img706.imageshack.us/img706/2822/wiedenn.png[/img]


Frage dazu: Bei Tlog(a,k) steht dort in der ersten Zeile plötzlich zwei mal log(a^k). Wegen p*q<= a^k verstehe ich das eine log(a^k), aber wie wird aus 2*log(a) denn plötzlich auch 2*log(a^k) ? Ergibt für mich absolut keinen Sinn.

Meine Laufzeitabschätzung für diesen Algorithmus lautet
O(log(k+1) * k * log(a))

Bekomme ich heraus, wenn ich alles ausmultipliziere und dann den größten Teilausdruck für die obere Schrankeverwende (wie bei O Notation üblich).

Kann mir einer helfen?

RE: Fragen zu AD 2010-02-10 21:37
tein
Bei Tlog(a,k) steht dort in der ersten Zeile plötzlich zwei mal log(a^k). Wegen p*q<= a^k verstehe ich das eine log(a^k), aber wie wird aus 2*log(a) denn plötzlich auch 2*log(a^k) ? Ergibt für mich absolut keinen Sinn.
Wenn p*q <= a^k, dann muss doch auch q <= a^k gelten.

RE: Fragen zu AD 2010-02-11 17:24
Anonymer User
Mist, irgenwie scheinen mir kurz vor der Klausur die Sicherungen durchzubrennen.

Kann mir vielleicht einer erklären, worin genau der Unterschied zwischen Bellman Ford und Dijkstra Algorithmus liegt? Klar, Bellman verarbeitet auch Graphen mit negativen Kanten, aber ich sehe bei der Arbeitsweise keinerlei Unterschiede? Bis vor kurzem war ich der Meinung, dass mir der Unterschied völlig klar ist. Jetzt habe ich mich aber noch mal durch Wikipedia gelesen und blicke wohl nicht mehr durch.

Bellman macht das ja in etwa so:
Initialiseire startknoten mit 0, übrigen mit oo (unendlich)
Schau dir die vom kleinsten Knoten erreichbaren Knoten an, in diesen Knoten wird die vorher durchlaufene Distanz (im ersten Schritt die 0) + das Kantengewicht geschrieben und der kleinere wird zum Pfad hinzugefügt.

Was macht Dijkstra nun anders? So wie ich das sehe gibt es da nur noch die zusätzliche Information für den Vorgänger.

Wäre sehr dankbar, wenn das jemand prägnant "für dumme" erklären könnte.

RE: Fragen zu AD 2010-02-11 19:32
Anonymer User
Dijkstra relaxt vom Knoten mit der geringsten Distanz aus weiter. Außerdem markiert Dijkstra auch bereits besuchte Knoten. Bellmann geht |V|-1 mal alle Kanten durch und relaxt dort.

Mach die beiden Algorithmen einfach mal auf einen Blatt Papier an einem einfachen Graphen, dann siehst du recht schnell die Unterschiede.