• Zum darstellen der Heaps habe ich ein Packet benutzt (qtree.sty), das leider nicht richtig als pdf-Datei darstellbar ist (es fehlen die Linien, sonst ist alles ok). Wer selbst LaTeX zur verfuegung hat, sollte eher den Quelltext benutzen um .dvi oder .ps Dateien zu erstellen.


    Diverse Tipp- und Rechenfehler wurden ausgebessert.
    Der Sourcecode fuer Aufgabe 8 wurde korrigiert.
    Der Beweis fuer Aufgabe 4 (siehe unten) wurde hinzugefuegt.


    seit 23.04.02, 0:15 ist die Version 1.0 online unter uebung.html


    /edit 20.04.02:
    Beim Repetitorium wurde anscheinend ein anderer Algorithmus zum erstellen des Heaps gezeigt (siehe den naechsten post). Ich kenne nur den aus der Vorlesung und dem Skriptum und habe mich an diesen gehalten. ich denke der sollte eigentlich auch durchgehen :-).


    /edit 22.04.02:
    Ich war heute in der Uebung und bei Aufgabe Vier habe ich nicht ganz gemacht, was eigentlich gemeint war. Laut Kraml, der heute bei uns in der Uebung war, sollte man eigentlich zeigen, dass bei einem Heap der 2^(n) - 1 Elemente hat, das n die Anzahl der Ebenen angibt und das in der letzten Ebene 2^(n - 1) Elemente sind. Das waere durch Induktion zu zeigen. Ich habe den Beweis bereits hinzugefuegt.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • hab eine frage zu bsp 2. beim erstellen des heaps schreibst du zuerst die ganze folge als "heap" an, was ja noch keiner ist, und beginnst dann mit den versickerungen. so kommt zwar ein richtiger heap heraus, aber der georg kraml hat am dienstag im repetitorium so ein beispiel vorgerechnet und ausdrücklich gesagt, dass die elemente nacheinander einzufügen sind, und nach jedem element der heap richtigzustellen ist. hoffe du weißt wie ich das meine. also man schreibt zuerst nur 28, dann kommt 58 dazu, das wird dann aber gleich richtiggestellt, und dann das nächste element usw... Laut Repetitorium is es anders ausdrücklich falsch. Oder irre ich mich da jetzt?


    Bernie

  • Bernie :
    stimmt, der kraml hat im reprtitorium einen anderen algorithmus zum erstellen des heaps benutzt (der mir persönlich auch besser gefällt). Ich würde aber die variante, die wir in der vo gemacht haben und die auch im skriptm steht, verwenden, weil sich die anderen beispiele auf dem übungsblatt auch ausdrücklich auf die vo beziehen...

    hi, i'm a signature virus. copy me into your signature to help me spread.

  • erstma ein großes danke :)


    was mir bis jetz aufgefallen ist


    bei aufgabe 1 ist dir bei der vierten zahlenfolge ein kleiner abschreibefehler passiert (letzte zeile)

    bsp 6 es heißt doch Partition(A,l,r,x) <- also immer das rechte element von der der eingeklammerten folge
    bsp8 => selection sort ;)

  • bsp 5


    Ich komm auf 2^(n+1)-5 Vergleiche, du hast ja 2^n-1 Elemente beim letzten wird Versickere garnicht mehr aufgerufen -> 2 Vergleiche weniger, das Vorletzte hat kein rechtes Kind -> 1 Vergleich weniger


    macht (2^n-1)*2-3=2^(n+1)-5


    bsp 4


    kleiner Umformungsfehler ganz am End
    (2^(n-1)-1)*2=2^n-2

  • Danke fuer alle Hinweise auf Fehler, ich bin dabei das auszubessern.


    qmp (bsp 5):
    Bei deiner Argumentations geht mir irgendwie das dritte Element ab. In den ersten zwei Ebenen sind drei Elemente. Wenn das hinterste an die Spitze getauscht wird, hat die Spitze wie du sagst, kein rechtes Kind mehr -> 1 Vgl. weniger. Wenn wieder das naechste getauscht wird, hat die Spitze ueberhaupt keine Kinder mehr -> 2 Vgl. weniger. Jetzt ist noch immer ein Element da! das steht allerdings schon an der Spitze darum wird es nicht getauscht und es hat auch keine Kinder mehr, also -> 2 Vgl. weniger => (2^(n) - 1) * 2 - 5 = 2^(n) - 7. Erst jetzt haben wir alle 2^(n) - 1 Elemente betrachtet.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • stimmt, war ein off by one Denkfehler


    die letzen Aufrufe sind ja
    Versickere(A, 1, 2)
    Versickere(A, 1, 1)
    und für das letzte Element entfällt der Aufruf


    danke für die Aufklärung

  • Frage zu Bsp. 2 zum Erstellen des Heap.
    In deiner Lösung : Bei Versickere 12:
    Die Zahlenreihenfolge vor Versickere (A,4,16) sieht so aus:
    28, 58, 6, 12, 67, 21, 43, 55,58, 38, ....
    Nun habe ich eben i = 4 .. j = 8 ... was 43 wäre ... A(j+1) = 55 .. also ist j = 9 ... aber ... j(9) < j(10) ... also müsste doch eigentlich A(4) mit A(10) vertauscht werden .. ist aber bei dir nicht der Fall ...
    Ist bei Dir der Fehler oder bei mir????

  • Gehört in der falls-Schleife nicht (r-l+1) <= k ? Denn wenn ich Teilfolgen z.B. der Länge 4 mit Selection-Sort sortieren will, und ich hab die Indexgrenzen l=1 und r=5 -> wären 5 Elemente, würde aber akzeptiert.

  • im beispiel 8 sollte es nicht "falls (r-l) <= k heißen, sondern (r-l+1)<=k ...


    hat heut bei den übungen unser tutor gesagt.. ist an sich auch logsch ;)


    mfg, Chris


    /edit: hoppla, da war einer schneller beim schreiben ;)

    hi, i'm a signature virus. copy me into your signature to help me spread.

  • Zitat

    Original geschrieben von ghost dog
    frage zu bsp. 6 (quicksort):
    zu partitionsaufruf. müsste nicht der r- zeiger immer um einen index kleiner als das pivot element sein?


    Nein! beim Aufruf wird sicher der Index des Pivoteelement übergeben.
    - wenn du dir den Allgorithmus im Skriptum anschaust wird nach dem Aufruf in der Methode Partition r auf j geschrieben und der erste Vergleich findet dann eh mit j-1 statt

  • Iris :
    A[10] ist ein Kind von A[5]! Du wuerdest ein Kind vom Knoten A[4] mit einem Kind des Knotens A[5] vertauschen. Man kann einen Knoten an der Position i nur mit den Elementen an den Positionen 2i und 2i + 1 vertauschen (nur das sind seine Kinder).


    Chris & skytale:
    Stimmt, es muss (r - l + 1) <= k ... heiszen.


    Ich war heute in der Uebung und bei Aufgabe Vier habe ich nicht ganz gemacht, was eigentlich gemeint war. Laut Kraml, der heute bei uns in der Uebung war, sollte man eigentlich zeigen, dass bei einem Heap der 2^(n) - 1 Elemente hat, das n die Anzahl der Ebenen angibt und das in der letzten Ebene 2^(n - 1) Elemente sind. Das waere durch Induktion zu zeigen. Ich bin gerade dabei, das umzuschreiben.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • Zitat

    Original geschrieben von yrucrem

    Ich war heute in der Uebung und bei Aufgabe Vier habe ich nicht ganz gemacht, was eigentlich gemeint war. Laut Kraml, der heute bei uns in der Uebung war, sollte man eigentlich zeigen, dass bei einem Heap der 2^(n) - 1 Elemente hat, das n die Anzahl der Ebenen angibt und das in der letzten Ebene 2^(n - 1) Elemente sind. Das waere durch Induktion zu zeigen. Ich bin gerade dabei, das umzuschreiben.


    huh? laut skriptum:


    2^n -1 elemente = vollständiger heap
    ein heap mit n schlüsseln genau aufrund(log(n+1)) Stufen


    log2 (2^n) = n


    auf stufe k sind höchstens 2^(k-1) schlüssel


    steht eh alles da was ma braucht ;)

  • eXe :
    Stimmt, und wenn man wirklich fest ueberzeugt sagen kann, dass das unmittelbar einsichtig ist, bzw. einen Induktiven Ansatz sagen kann, warum das alles so ist (in der ersten Ebene sind 2^0 El., ..., in der letzten sind 2^(n - 1) El.), glaubt er einem auch, dass man es verstanden hat.


    Ich denke, dass man einfach nachweisen koennen sollte, warum diese Sachen gelten (koennte mir gut die Zwischen frage vom Tutor denken: "und warum sind in der letzten Ebene 2^(n - 1) Elemente?"). Und Induktion bietet sich sehr schoen an.


    Ich finde die Fragestellung auch etwas seltsam, weil es sich ja so anhoert, als ob man die Sachen aus dem Skriptum einfach vorraussetzen kann.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • @yucrem Nun ja .. wenn Du den Algorithmus durchrechnest, dann ist es aber sehr wohl so, dass j immer weiter wandert, bis das Element gefunden wird, das größer ist als j ...
    Ich habe es nach dem Algorithmus durchgerechnet und da stimmt es dann nicht ...