Blatt2 - Loesungen
Results 1 to 36 of 36

Thread: Blatt2 - 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

    Waere toll, wenn sich ein paar Korrekturleser finden.

    Ein Rechenfehler bei Aufgabe 8 wurde ausgebessert.
    Die Aufgabe 9 wurde hinzugefuegt :-)
    Ein Tippfehler in Aufgabe 2 wurde korrigiert (da stand ein
    i statt einem j)
    Bei den Aufgaben 7 und 8 hatte sich ein Denkfehler eingeschlichen
    Engueltiges Errata fuer Quicksort.

    Seit 12.04.02, 11:57 ist die Version 1.0 online unter uebung.html
    Last edited by yrucrem; 13-10-2002 at 03:06.
    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 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi!

    das meiste scheint zu passen.

    nur bei Beispiel 8 hab ich was Anderes.

    die Summe von (n - i+1) ist bei mir (n² + n - 2)/2, die Summe von (n-i) ist n*(n-1)/2.

    Was an sich an Theta (n²) nix ändert.

    lg, Geli

  3. #3

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

    Uups

    @Geli:
    Stimmt. Bruchrechnen sollte man koennen *ganzschrecklichrotwerd*.

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

  4. #4
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question ad Bsp 5 ...

    also ich glaube, dass die behauptung 3^5^(n+1) = @(3^5^n)von Aufgabe 5 richtig ist.

    denn 3^5^(n+1) ist dasselbe wie 3^5^n * 3^5

    dh.
    c1*3^5^n < 3^5^n * 3^5 < c2 * 3^5^n ...... // durch 3^5^n dividieren
    c1 < 3^5 < c2

    ... und das ist immer wahr

    mfg,
    -z0nk-

  5. #5
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    hm... also ich würde 3^5^(n+1) ansehen als 3^(5^n*5), während ich 3^5^n*3^5 zu 3^(5^n+5) umformen würde. Wäre also nicht gleich. Kann auch kompletter Blödsinn sein... aber ich glaub halt es ist so.
    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  6. #6
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    @yucrem: nur weils mir grad auffallt:
    hat deine Signatur eher ästhetischen oder sinnhaften Charakter?
    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  7. #7

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also für mich klingt die lösung von yucrem ziemlich einleuchtend.
    mathematica ist bei dem problem auch keine große hilfe (oder ich bin einfach nur zu müde/blöd es zu bedienen)

    @yucrem: deine sig ist brainf*ck-code, oder?
    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  8. #8
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    Original geschrieben von -z0nk-
    [B]also ich glaube, dass die behauptung 3^5^(n+1) = @(3^5^n)von Aufgabe 5 richtig ist.

    denn 3^5^(n+1) ist dasselbe wie 3^5^n * 3^5
    Eigentlich nicht weil:
    3<SUP>5<SUP>n+1</sup></sup>=
    3<SUP>5*5<SUP>n</sup></sup>=
    während
    3<sup>5<sup>n</sup></sup>*3<sup>5</sup>=
    3<sup>5<sup>n</sup>+5</sup>

    Danke für das pdf, as you would say:

    >+++++>+>++++++++++++++>+++++++++>+++++[++++++++++++++++++++++++++++++++.<]
    Last edited by shabby; 27-03-2002 at 13:58.

  9. #9

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @-z0nk-:
    Ich denke auch, dass 3^5*3^(5^n) = 3^(5 + 5^n) ist.

    @ded & jeuneS2:
    Stimmt ist Brainf*ck. Ich kann zwar nicht wirklich viel damit machen, aber immerhin meinen namen schreiben ;-).
    Last edited by yrucrem; 27-03-2002 at 12:16.
    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  10. #10
    dj_m.o.h.t.'s Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    428
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @yrucrem: wo ist denn eigentlich die aufgabe 9? sie geht mir irgendwie bei deinen lösungen ab.

  11. #11

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    bsp5: 3^5^n+1 wächst schneller als 3^5^n => kann nicht durch eine konstante gehalten werden.

    bsp9 ich glaub der alg is stabil, unstabil wäre er imho wenn statt "<" "<=" verwendet werden würde.

    laborg

  12. #12
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts

    nochmal ad bsp 5

    angenommen man setzt n = 1 in die beiden funktionen ein, dann n=2 und n=3 usw. und vergleicht die ergebnisse.

    für n=2 kommt bei der funktion 3^5^n klarerweise derselbe wert raus, wie für n=1 bei der funktion 3^5^n+1.
    für n=3 bei 3^5^n dasselbe wie für n=2 bei 3^5^n+1
    usw. bis ins unendliche

    dh die eine funktion hinkt der anderen immer nur um 1 nach, aber wächst doch gleich schnell, oder ?

    naja, vielleicht ist da irgendwo ein denkfehler ... krankes beispiel

    mfg,
    -z0nk-

  13. #13

    Title
    Veteran
    Join Date
    Mar 2002
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Korrektur zur Bsp. 1 Lösung

    das zweite programm im ersten beispiel hat natürlich auch eine laufzeit von T=k - k ist halt nur ein anderer bezeichner als n.

    gruss peter

  14. #14

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Korrektur zur Bsp. 1 Lösung

    @ sPecTRon

    Die Frage is aber nach der Laufzeit in Abhängigkeit von n. k hängt aber nicht von n ab, also is es für die Laufzeit komplett gleich, wie groß n ist.

    lg, Geli

  15. #15

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: nochmal ad bsp 5

    @ z0nk

    um mal deine Beispiel zu verwenden:
    bei n=2 kommt 3^125 bzw. 3^25 raus,
    bei n=3 kommt 3^625 bzw. 3^125 raus, usw.

    Das heißt der Exponent ist immer 5 mal so groß. Offensichtlich wird dadurch der Abstand immer größer zwischen den zwei Funktionen.
    Das siehst auch, wennst zwei gleiche Exponentialfunktionen um eine Einheit zueinander verschoben aufzeichnest. Der senkrechte Abstand zwischen den Kurven wird immer größer.

    Deshalb kannst du nie eine Konstante finden, die groß genug ist, das c*3^(5^n) eine obere Schranke bildet.

    lg, Geli

  16. #16
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    jo da hast recht ... der senkrechte abstand wird immer größer und deshalb findet man keine konstante.

    was mich verwirrt ist halt nur, dass die kurven paralell sind, dh sie wachsen gleich schnell.

    die formel stimmt jedenfalls net.

  17. #17

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    Original geschrieben von -z0nk-
    was mich verwirrt ist halt nur, dass die kurven paralell sind, dh sie wachsen gleich schnell.[/B]
    kurven parrallel? aehm welche kurven meinst du?

  18. #18

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    zu Beispiel 1 Programm 2

    [edit: bin auf das n=2^k reingefallen]
    Last edited by qmp; 06-04-2002 at 02:27.

  19. #19
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    ad bsp 6:


    ich nehme an es wurde nicht berücksichtigt, dass es O(n) benötigt, um festzustellen ob eine Zahl eine Primzahl ist, und für sehr große n es sogar noch länger dauern kann ? (das ist dann sogar architekturabhängig, da man für kleinere zahlen weniger speicher braucht um den modulo von der hälfte aller kleineren ganzzahlen von n gegen 0 zu checken ...)


    hier stellt sich auch in der angabe die frage: ist dieses wissen ob eine zahl primzahl ist vorausgesetzt, oder dient der algorithmus der f=n^2 bzw f=n^3 benötigt zur feststellung dieses wissens (dann wäre er sehr ineffizient)


    im ersten fall (wissen vorausgesetzt) stimmt:
    (1) ist falsch
    (2) ist wahr
    (3) ist falsch
    (4) ist falsch

    im zweiten fall (O(n) muss noch zu n^2 und n^3 dazumultipliziert werden) behaupte ich:
    (1) ist falsch ( es ist immer mindestens O(n^3) )
    (2) ist falsch ( es kommt auch O(n^4) vor )
    (3) ist falsch ( es kommen immer noch Primzahlen ... Begründung wie im ersten Fall )
    (4) ist wahr ( es ist immer mindestens O(n^3) )

    peter

  20. #20

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ yrucrem

    aufgabe 2: zeile 5 des algorithmus lautet bis A[i].key>x und
    nicht bis A[i].key>=x

    somit stimmt die veranschaulichung nicht mehr ganz, weil auch elemente mehrfach vorkommen und so unnötig getauscht wird

    --------------------------------------------------------------------------------

    habe mittlerweile eingesehen daß in zeile 5 doch ein >= kommt auch wenn es nicht steht, aber bei der erklärung im buch kann man darauf schließen:

    erste schleife: klar durch wahl des pivotelements "ganz rechts".

    allerdings stellt sich jetzt noch die frage ob man jetzt nicht auch noch in der zeile 8 ein <= setzten soll, meiner meinung nach schon denn:

    Stoppelement A[0].key=kleine Zahl<= min (i=1 bis n) A[i].key

    weil sonst müsste hier nur < stehen glaube ich
    Last edited by andy; 07-04-2002 at 17:25.

  21. #21

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Was passiert jetzt aber in dem Fall wenn es kein i gibt dass größer ist als x oder auch wenn es kein j gibt, dass kleiner ist ... wohin zeigt dann i???
    Vielleicht stehe ich auch nur auf der leitung ...

  22. #22

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @Iris:
    Das i muss kein Element finden das _groeszer_ ist, sondern eines, das _groeszer oder gleich_ ist als das Pivotelement. Und spaetestens, wenn es beim P-Element selbst ankommt hat es so ein Element gefunden. Dann wird eben das P-Element auf sich selbst verschoben.

    Das j bleibt spaetestens ganz am anfang des Feldes stehen wo ja ein Stop-Element plaziert wurde, dass kleiner ist als alle anderen Elemente im Feld.
    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  23. #23

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    jetzt müßte in zeile 8 auch noch <= stehen, denn laut buch:

    stoppelement A[0].key=kleine Zahl<= min (i=1 bis n) A[i].key

    wenn das stoppelement gleich ist mit dem minimum (pivotelement): endlosschleife

  24. #24

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ok jetzt sollte das problem gelöst sein

    ich habs anhand folgendem beispiel probiert:
    2 2 4 2 2

    in zeile 8 kommt auch <=, denn sonst funktionierts nicht

    endgültig:
    - zeile 5 >=
    - zeile 8 <=
    - zeile 9 <
    - zeile 12 >
    Last edited by andy; 07-04-2002 at 20:40.

  25. #25

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts

    beispiel 1

    korrigiert mich, falls ich mich irre, aber gehört beim 2. Teil nicht

    c1+(k+1)c2+k*c3="theta"(k )?

  26. #26

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts

    beispiel 7,8

    meiner meinung nach müsste die Laufzeit von zeile 4
    von bubblesort

    SUMME (i=1 bis (n^2-n)/2) von ti, ti element aus {0,1}

    so wie es im file steht mit SUMME (i=1 bis n-1), wäre ja nach
    einem durchlauf die folge schon sortiert.

    oder hab ich da einen denkfehler?
    lg, tocvolxa

  27. #27

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    @andy:
    Stimmt, wenn man das Stop-Element kleiner oder gleich waehlt, dann braucht man ein <=. Wenn man eins nimmt, das kleiner ist reicht ein <. Aber ich denke, dass es vor allem wichtig ist, dass man verstanden hat, _warum_ eine dieser Aenderungen noetig ist (und das man die Aenderungen so vornimmt, dass der Tutor am moeglichst verwirrt ist :-)).

    @josi:
    Dieser Einwand wurde schon gebracht. Es wird aber ausdruecklich nach der Laufzeit in abhaengigkeit von _n_ gefragt! Die hoechste Potenz von n in c1+(k+1)c2+k*c3 ist n^0 = 1 --> \Theta(1)

    @tocvolxa:
    Stimmt! Grober Denkfehler von mir. Ich bin gerade dabei das zu korigieren.

    /edit:
    Hab's ausgebessert. Mein Denkfehler war folgender: es kann maximal (summe von i = 1 bis n - 1)(i)-mal sein, dass Vertauscht werden muss (das sind (n^2 - n)/2) und ich habe aus dem i einfach gleich das ti gemacht.

    Danke fuer den Hinweis!
    Last edited by yrucrem; 07-04-2002 at 23:05.
    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  28. #28

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    aufgabe 7) + 8):

    also ich glaube daß dort die Summe von ti*c4 von 1 bis n-1 läuft,
    denn wenn sie von 1 bis (n^2-n)/2 laufen würde, würde schlimmstenfalls eine ordnung von theta(n^4) herauskommen und das stimmt sicherlich nicht

  29. #29

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @andy:
    nein, denn im gegensatz zu den anderen summen summierst du hier ja nich die laufvariable selbst auf, sonder immmer nur 1 oder 0
    schlimmstenfalls ist es also (n^2-2)/2*c4 (-> also ti=1 für alle i)
    also ordnung n^2

  30. #30

    Title
    Principal
    Join Date
    Jan 2002
    Posts
    46
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ok danke habs jetzt verstanden

  31. #31

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    27
    Thanks
    0
    Thanked 0 Times in 0 Posts
    kann mir das bitte nocheinmal jemand erklären, warum jetzt summe i=1 bis (n²-n)/2 gehört!?

    ich war vorhin so glücklich dass i ch es kapiert habe, und jetzt...

    danke

  32. #32

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts
    In der Zeile 4 gibt es n²-n/2 mal die Möglichkeit,dass ein Element wirklich verschoben wirst. Wenn du dir dir den Code der nächsten optimierten Aufgabe ansiehst, siehst du, dass die Zeile 3 und deshalb auch die Zeile 4 max. n²-n/2 mal ausgeführt werden kann. Daher musst du bis dorthin summieren.

  33. #33
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von laborg


    kurven parrallel? aehm welche kurven meinst du?
    naja, 3^5^n und 3^5^n+1 mit n gegen unendlich

    mfg, -z0nk-

  34. #34
    steve's Avatar
    Title
    Super Moderator
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts

    Bsp. 1 Teil 2...

    Ich will ja keinem die Freude verderben, aber:

    das Ganze sieht auf den ersten Blick aus wie Theta(1), weil die Wiederholung der Schleife ja von k abhängt und nicht von n.

    Aber ... wovon hängt denn nun n ab?
    Damit n größer werden kann, muss zuerst k gestiegen sein (Zeile 1). Somit hängt n also doch mit k zusammen, oder?

    Meiner Meinung nach ist
    k= ln(n) / ln(2)
    (was dem ld=logarithmus dualis entspricht, oder?).
    Somit bedeutet das, dass das Programm
    Theta( ln(n) ) als Laufzeit hat, oder? Verkalkulier ich mich da irgendwo? Ich bin für Anregungen offen...

    soweit, sogut,
    steve
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  35. #35

    Title
    Principal
    Join Date
    Nov 2001
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Bsp. 1 Teil 2...

    Original geschrieben von steve
    Ich will ja keinem die Freude verderben, aber:

    das Ganze sieht auf den ersten Blick aus wie Theta(1), weil die Wiederholung der Schleife ja von k abhängt und nicht von n.

    Aber ... wovon hängt denn nun n ab?
    Damit n größer werden kann, muss zuerst k gestiegen sein (Zeile 1). Somit hängt n also doch mit k zusammen, oder?

    Meiner Meinung nach ist
    k= ln(n) / ln(2)
    (was dem ld=logarithmus dualis entspricht, oder?).
    Somit bedeutet das, dass das Programm
    Theta( ln(n) ) als Laufzeit hat, oder? Verkalkulier ich mich da irgendwo? Ich bin für Anregungen offen...

    soweit, sogut,
    steve

    also ich hatte heute ue und unser tutor/gruppenleiter/whatever hat nix gegen theta(1) gesagt ! .... immerhin ist ja die laufzeitnotation von n gefragt und nicht von k ...und da die schleife von 1 bis k läuft und nicht bis n, ist es nun mal theta(1)

  36. #36
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    Beim Bsp. 1 / 2. Teil kann man Zeile 3 ja auch schreiben als "sum = sum + 2^k + 2^k;". Dann gibts kein n mehr folglich isses wurscht. == Theta(1)
    Why bother spending time reading up on things? Everybody's an authority, in a free land.

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
  •