Loesungen
Results 1 to 18 of 18

Thread: Loesungen

  1. #1

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts

    Post SS 02 Loesungen

    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.
    Last edited by yrucrem; 13-10-2002 at 03:07.
    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  2. #2

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien & Burgenland
    Posts
    40
    Thanks
    0
    Thanked 0 Times in 0 Posts

    frage zu beispiel 2

    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

  3. #3

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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.

  4. #4
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by eXe; 20-04-2002 at 16:10.

  5. #5

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  6. #6

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    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!

  7. #7

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  8. #8

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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????

  9. #9
    Calida's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Posts
    128
    Thanks
    6
    Thanked 0 Times in 0 Posts
    warum kann ich meinen eigenen beitrag nicht löschen?
    Last edited by Calida; 22-04-2002 at 14:03.
    Ich gehe jetzt ein Byte trinken. Das sind acht Bit.

  10. #10

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Bsp 8

    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.

  11. #11

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts

    kleiner fehler im beispiel 8

    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.

  12. #12

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts
    thx für die bestätigung!

  13. #13
    ghost dog's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Location
    Posts
    498
    Thanks
    0
    Thanked 1 Time in 1 Post
    frage zu bsp. 6 (quicksort):
    zu partitionsaufruf. müsste nicht der r- zeiger immer um einen index kleiner als das pivot element sein?
    bsp: statt partition(feld, 1, 16, 65) sollte stehen partition(feld,1,15,65) ??

  14. #14
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  15. #15

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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!

  16. #16
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  17. #17

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @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!

  18. #18

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Beispiel 2

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

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •