Blatt2 - Loesungen

[yrucrem]

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 (http://stud3.tuwien.ac.at/~e0125335/studium/algodat_1/uebung.html)

[Geli]

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

[yrucrem]

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

Hab's ausgebessert.

[-z0nk-]

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-

[jeuneS2]

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.

[jeuneS2]

@yucrem: nur weils mir grad auffallt:
hat deine Signatur eher ästhetischen oder sinnhaften Charakter?

[ded]

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?

[shabby]

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^5ⁿ*3⁵=
3^5ⁿ+5

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

>+++++>+>++++++++++++++>+++++++++>+++++[++++++++++++++++++++++++++++++++.<]

[yrucrem]

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

[dj_m.o.h.t.]

@yrucrem: wo ist denn eigentlich die aufgabe 9? sie geht mir irgendwie bei deinen lösungen ab.

[laborg]

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

[-z0nk-]

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-

[sPecTRon]

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

[Geli]

@ 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

[Geli]

@ 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

[-z0nk-]

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. :)

[laborg]

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?

[qmp]

zu Beispiel 1 Programm 2

[edit: bin auf das n=2^k reingefallen]

[LordOfTheBite]

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

[andy]

@ 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

[Iris]

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

[yrucrem]

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

[andy]

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

[andy]

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 >

[josi]

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

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

[tocvolxa]

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

[yrucrem]

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

[andy]

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

[tocvolxa]

@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

[andy]

ok danke habs jetzt verstanden

[meriadoc]

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

[skytale]

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.

[-z0nk-]

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-

[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

[SouljaRag]

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) :thumb:

[jeuneS2]

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)