Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Probeklausur: Aufgabe 1 - Rekurrenz
Hallo zusammen,
ich sitze momentan an der genannten Aufgabe der Probeklausur und habe dort gerade einen Haenger. Wir sollen ja fuer den Fall n = 2^k eine rekurrenzfreie exakte Loesung finden. Durch Auffaechern findet man auch problemlos einen entsprechenden Summenausdruck:
T(2^k) \leq C \sqrt{2^k} + T(2^{k-1}) = … = a + C\sqrt{2^k} \sum^{k-1}{i=0} \sqrt{2^{-i}}
Offensichtlich handelt es sich dabei ja nicht um die Partialsumme einer geometrischen Reihe und mir ist auch sonst nicht eingefallen wie ich das in eine summenzeichenfreie Formel umformen koennte, also hab ich Wolfram Apha gefragt, welches mir folgende Loesung ausgespuckt hat:
\sum^{k-1}{i=0} \sqrt{2^{-i}} = \frac{2(\sqrt{2^{-k}}-1)}{\sqrt{2}-2}
Dass das korrekt ist, habe ich per Induktion auch schon nachgeprueft, aber wie man darauf kommt ohne Wolfram Alpha zu fragen, ist mir vollkommen unklar (zugegeben im Bronstein hab ich nicht nachgesehen, den hab ich grad nicht zur Hand). Vielleicht hat ja jemand eine plausible Erklaerung. Ich habe die Herleitungsschritte mal als pdf beigefuegt (die Induktion fehlt allerdings, die jetzt auch noch zu texen war ich grade zu faul, ist aber nicht weiter schwer), weil tex-Sourcecode lesen relativ eklig ist.
Attachment:
main.pdf: https://fsi.cs.fau.de/unb-attachments/post_124160/main.pdf
Nunja das ist eigentlich ganz einfach: du musst nur diese formel anwenden für die endliche geometrische Reihe anwenden. http://de.wikipedia.org/wiki/Geometrische_Reihe hier ist die Formel erklärt. Für den endlichen Fall gilt die Formel auch, wenn der Summand nicht betragsmäßig kleiner als 1 ist.
Ich hoffe das hilft dir weiter, ansonsten melde dich!
Ah, jetzt seh ichs auch, danke! War aus irgendeinem Grund auf dem Auge vollkommen blind und hab deshalb uebersehen dass:
\sqrt{2^{-i}} = (2^{-1/2})^i
Was habt ihr denn so für T(n) für eine Abschätzung raus?
Ich komme auf T(n)<=a+c*((sqrt(2)*(1-sqrt(n)))/(1-sqrt(2)))
Ich glaub wie weit man das abschaetzt ist relativ willkuerlich. Alles abgesehen von n <= 2^{\lceil log n \rceil} <= 2n ist eh nur noch rein kosmetisch. Letztlich gilt jedenfalls T(n) \in O(\sqrt(n))
1 „Gefällt mir“
Seid ihr sicher, dass das stimmt? Wolframalpha interpretiert i als imaginäre Zahl.
Hab ich auch raus.
Nur wenn mans falsch bedient.
-chris
1 „Gefällt mir“
Gut, bekomme ich auch raus.
Wie schreibt man denn den Abschätzungsschritt (<=) formal richtig hin?
2 „Gefällt mir“
Irgendwie bekomm ich wiedermal was anderes raus als ihr… Könnt ihr mir sagen wo mein Fehler liegen könnte?
Induktions Annahme: T(2^k) = a + c * { [sqrt(2) * sqrt( 2^k ) - 1] / [ sqrt(2) - 1] - 1}
Das ganze ist die endliche geometrische Reihe mit a = sqrt(2) und k. Zusätzlich hat man das - 1 ganz am Ende für den Fall sqrt(2)^0 der ja bereits mit a abgearbeitet ist.
Aus der Übung habe ich n <= 2^(ld2+1) = 2*n
Wenn man das einsetzt erhält man:
T(n) = a + c * { [sqrt(2) * sqrt( 2*n ) - 1] / [ sqrt(2) - 1] - 1} = a + c * { [2 * sqrt(n) -1] / [ sqrt(2) - 1] - 1}
Ich hoffe man kann des lesen.
Was ist deine T(2^k) bevor du die Summe aufgelöst hast? Die gleiche wie oben oder hast du eventuell von unten nach oben (0 bis k-1) aufsummiert, was ja auch gehen müsste?
Warum genau setzt du a=sqrt(2)? Wenn man die Wikipedia Seite als Referenz nimmt, müsste a = 1 und q = sqrt(2) sein.
Und hier ist auch der Wurm drin:
Im zweiten Teil verschwindet n ja komplett 0_o
Also fangen wir mal an:
-
Meine Summe T(2^k) = a + c * \sum^{k}_{i=1} \sqrt[2^(i)]
-
Mit a = sqrt(2) hab ich dei Formel aus der Formelsammlung gemeint für die geometrische Reihe a^k heißt es da.
-
Wo ist der Fehler denn dann bei n <= 2*n und wie würde des richtig lauten?
-
Und n müsste doch immer dabei sein???
T(n) = a + c * { [sqrt(2) * sqrt( 2*n ) - 1] / [ sqrt(2) - 1] - 1} = a + c * { [2 * sqrt(n) -1] / [ sqrt(2) - 1] - 1}
-
Stimmt, die Summe muss natürlich von 1 bis k gehen. Allerdings kann man dann die geometrische Summenformel noch nicht anwenden woher deine -1 kommt. Wenn du dann die 1 mit sqrt(2)-1 erweiterst, das zu einem Bruch zusammenfasst und 2 ausklammerst, hast du das gleiche wie oben.
-
Ok, ich war verwirrt weil du sqrt(2)*sqrt(2^k) geschrieben hast, und ich das dann für den Vorfaktor aus der Wikipedia gehalten habe.
-
Der Fehler war bei n <= 2^(ld2+1) =2*n Das fette enthält ja gar kein n mehr, weshalb ich deiner Übungsmitschrift hier nicht so ganz traue.
Relevanter ist eigentlich, dass n <= n^(ceil(ldn)) ist, wenn man dan k = ceil(ldn) setzt, kann man die Funktion wieder auf n umbauen.
- siehe 3.
1 und 2 wären dann damit erledigt.
-
Ist einfach nur n blöder Tippfehler den ich einfach überlesen hab…
-
Also für die Abschätzung der Allgemeinen Form:
n <= 2^(ceil(ldn)) <= 2^(ldn +1) = 2 * 2^(ldn) = 2*n
T(n) <= T(2^(ceil(ldn)) = a+ c * [sqrt(2) - 2 * sqrt(n)] / [1 - sqrt(2)]
Und bei euch in der Lösung ist die 2 ein sqrt(2). Und ich komm einfach ned drauf wieso.
Meine 2 kommt zustande weil ich sqrt(2) aus der Summen-Formel habe und des * sqrt(2) wegen 2*n unter der Wurzel.
Ok, ich glaube der Unterschied ist dass die anderen sqrt(2^(k+1)) durch sqrt(2n) ersetzt haben, wärendu du sqrt(2^k) ersetzt hast, wodurch dann ein sqrt(2) mehr übrig bleibt. Ich weiss allerdings nicht was richtig ist und ob das überhaupt wichtig ist.
Ah okay danke für deine Hilfe. Sollte jemand ne sichere Antwort finden, was jetzt stimmt wärs toll wenn er sie mal postet. Also ob man die +1 jetzt untern Tisch fallen lässt oder ned.
Also ich glaub wir sind uns einig, dass wir für den Fall n = 2^k folgende Abschätzung haben:
T(n) <= 2C( (\sqrt{n}-1) / (2-\sqrt(2) )
Für den allgemeinen Fall können wir das wie folgt abschätzen:
n <= 2^{\lceil ld n \rceil}
T(n) <= T(2^{\lceil ldn \rceil}) <= 2C( (\sqrt{2^{\lceil ld n \rceil}}-1) / (2-\sqrt(2) )
Will man jetzt noch den Logarithmus loswerden, bleibt einem denke ich nur noch 2^{\lceil ldn \rceil} durch 2n weiter nach oben abzuschätzen:
T(n) <= T(2^{\lceil ld n \rceil}) <= 2C( (\sqrt{2n}-1) / (2-\sqrt(2) ) = C( (2 \sqrt{n} - \sqrt{2}) / (\sqrt{2} - 1)
Nichts für ungut, aber bitte verwendet sowas wie http://www.codecogs.com/latex/eqneditor.php, längere Formeln werden nämlich sonst wirklich schwer zu lesen. ^-^ Einfach tex-Code eingeben, dann Rechtsklick aufs Bild → Bild-URL kopieren → hier im Forum dann beim Beitrag posten oben auf “Bild” klicken und dann die Bild-URL einfach einfügen.
1 „Gefällt mir“
In diesem Sinne:
3 „Gefällt mir“