Rekursionsgleichung lösen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) reagiert/warte auf Reaktion | Datum: | 18:55 Di 17.10.2017 | Autor: | pc_doctor |
Aufgabe | Lösen Sie die folgenden Rekursionsgleichungen. Beweisen Sie jeweils die Richtigkeit ihrer Lösung (z.B. durch vollstände Induktion)
a)
T(1) = 0
T(n) = [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n für n > 1
Sie dürfen annehmen, dass n eine Zweierpotenz ist. |
Hallo,
ich habe Probleme bei dieser Aufgabe.
Also normale Rekursionsgleichungen mittels charak. Polynom ist eigentlich kein Problem, aber die Gaußklammern stören mich etwas.
Ich habe mal testweise Werte eingesetzt, um ein System zu erkennn, doch vergebens:
T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2
T(3) = 5
T(4) = 8
T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24
T(9) = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59
Ich erkenne, dass für n = 2,3 und 4 die Differenz immer 3 beträgt
von n = 5 bis 8 ist die Differenz 4
und ab n = 8 bis ?? ist die Differenz 5
Ich werde aber daraus nicht schlau. Oder gibt es einen anderen Ansatz?
Ich würde mich über einen Tipp freuen.
Vielen Dank im Voraus.
|
|
|
|
Du solltest den Zahlenwert von [mm] \lfloor log_2(n)\rfloor [/mm] betrachten.
Damit kannst du einerseits die sich ändernden Stufenabstande in den Griff bekommen und andererseits eine Korrektur zu den richtigen Werten finden (dazu brauchst du dann aber [mm] 2^{\lfloor log_2(n)\rfloor}).
[/mm]
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 20:58 Di 17.10.2017 | Autor: | pc_doctor |
Danke für den Tipp, mit dem komme ich weiter!
|
|
|
|
|
Hallo,
ich habe mal bisschen anders gerechnet, um die Rekursionsgleichung zu lösen. Ich komme auf log(n), allerdings fehlt da etwas, aber ich weiß nicht was.
Also wir hatten:
T(1) = 0 , das ist der Anker
T(n) = $ [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] $ + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n für n > 1
Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also so aussieht n = [mm] 2^{a} [/mm] , a [mm] \in \IN
[/mm]
Damit ändert sich T(n) zu:
T(n) = [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{2} [/mm] + n , für n > 1, n Zweierpotenz.
So, dann versuche ich die Rekursionsgleichung aufzulösen, indem ich immer rekursiv einsetze. Ich setze jetzt also [mm] \bruch{n}{2} [/mm] ein für den Anfang.
[mm] T(\bruch{n}{2}) [/mm] = [mm] T(\bruch{n}{4}) [/mm] + [mm] T(\bruch{n}{4}) [/mm] + n + [mm] \bruch{n}{2}
[/mm]
Jetzt setzen wir [mm] \bruch{n}{4} [/mm] ein
[mm] T(\bruch{n}{4}) [/mm] = [mm] T(\bruch{n}{8}) [/mm] + [mm] T(\bruch{n}{8}) [/mm] + n + [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{4} [/mm]
=
..
= [mm] T(\bruch{n}{2^k}) [/mm] + [mm] T(\bruch{n}{2^k}) [/mm] + [mm] \summe_{i=0}^{k} \bruch{n}{2^k}
[/mm]
So, so sieht wohl die Rekursion für k Schritte aus.
Wir setzen [mm] \bruch{n}{2^k} [/mm] = 1
Formen nach k um:
k = [mm] log_2(n) [/mm] mit k [mm] \le log_2(n)
[/mm]
Naja, daraus folgt:
[mm] T(\bruch{n}{2^k}) [/mm] = T(1) = 0
Jetzt müssen wir ja k in die Summe einsetzen, k ist ja k = [mm] log_2(n)
[/mm]
Aus der Summe wird nun also [mm] \summe_{i=0}^{log_2(n)} \bruch{n}{2^{log_2(n)}} [/mm] und das ist gleich
[mm] \summe_{i=0}^{log_2(n)} [/mm] 1 = [mm] log_2(n) [/mm] + 1 ( laut Wolframalpha ? )
Also erhalten wir
T(n) = T(1)+ T(1) + [mm] log_2(n) [/mm] +1
T(n) = 0+0+ [mm] log_2(n) [/mm] +1 = [mm] log_2(n) [/mm] +1
Das funktioniert aber irgednwie nicht, wenn ich Testeinsetzungen mache. Wo ist mein Fehler ?
|
|
|
|
|
> Hallo,
>
> ich habe mal bisschen anders gerechnet, um die
> Rekursionsgleichung zu lösen. Ich komme auf log(n),
> allerdings fehlt da etwas, aber ich weiß nicht was.
>
> Also wir hatten:
>
> T(1) = 0 , das ist der Anker
>
>
> T(n) = [mm]T(\lfloor\bruch{n}{2}\rfloor)[/mm] +
> [mm]T(\lceil\bruch{n}{2}\rceil)[/mm] +n für n > 1
>
> Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also
> so aussieht n = [mm]2^{a}[/mm] , a [mm]\in \IN[/mm]
>
Sorry, aber ich hatte bei meinem Tipp vergessen, dich auf Folgendes aufmerksam zu machen:
n=Zweierpotenz ist völlig unsinnig, wenn n die natürlichen Zahlen durchlaufen soll.
Wenn T nur für Zweierpotenzen definiert werden soll, müsste es heißen:
T(1)=0
[mm] T(2^n)=[/mm] [mm]T(\lfloor\bruch{2^n}{2}\rfloor)[/mm] + [mm]T(\lceil\bruch{2^n}{2}\rceil)[/mm] [mm] +2^n [/mm]
= [mm]T(2^{n-1})[/mm] + [mm]T(2^{n-1})[/mm] [mm] +2^n [/mm] = [mm]2*T(2^{n-1})[/mm] [mm] +2^n.
[/mm]
Man würde also immer nur 2-er-Potenzen addieren.
T(3), T(5),... wären gar nicht definiert, und das Ergebnis wäre auch trivial. Es wäre [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung damit sinnlos.
Nehmen wir an, es wäre doch so gemeint, wie es sich anhört. Wenn n eine Zweierpotenz wäre, wäre [mm] \bruch{n}{2} [/mm] ganzzahlig und damit [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung gäbe, wie in meinem obigen Gesagten, wieder keinen Sinn.
Was müsste man nun für n=7 rechnen? [mm]\lfloor\bruch{n}{2}\rfloor[/mm]=3, [mm]\lceil\bruch{n}{2}\rceil[/mm]=4, und dann 7 addieren? 7 ist aber keine 2-er-Potenz, n sollte aber eine sein!
Man merkt, dass die Bemerkung so unsinnig ist. Sie hätte heißen müssen:
Hinweis: Betrachten sie die 2-er-Potenzen, zwischen denen n liegt.
Dann wäre man auch sehr schnell auf die Funktion [mm] log_2 [/mm] gestoßen...
|
|
|
|
|
Danke für die Antwort.
Sofern ich weiß, soll davon ausgegangen werden, dass n eine Zweierpotenz ist. Nehmen wir an, als geschlossene Formel kommt [mm] log_2(n) [/mm] raus, dann wäre dieser Logarithmus für nicht-Zweierpotenzen nicht definiert, habe ich das richtig verstanden?
|
|
|
|
|
Natürlich ist [mm] log_2(n) [/mm] für alle n definiert.
Ich schreibe mal auf, was ich für die von dir gebildete Reihe herausgefunden habe.
T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2
T(3) = 5
T(4) = 8
T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24
T(9) = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59
T(16) = 64
T(17) = 70
Die einzelnen Abschnitte bilden jeweils für sich eine arithmetische Folge und sind damit beschreibbar durch jeweils eine lineare Funktion der Form y=a*x+b, wobei a und b jeweils angepasst werden müssen. An den Nahtstellen kommt es zu überlappungen, die 8 kann man auch schon zur nächsten Reihe zählen, ebenso 24 und 64.
Man erhält so die Funktionen
y = 2x - 2 für x = 1 bis 2 mit [mm]\lfloor log_2(x) \rfloor[/mm]= 0
y = 3x - 4 für x von 2 bis 4 3 mit [mm]\lfloor log_2(x) \rfloor[/mm]= 1
y = 4x - 8 für x von 4 bis 8 7 mit [mm]\lfloor log_2(x) \rfloor[/mm]= 2
y = 5x - 16 für x von 8 bis 16 15 mit [mm]\lfloor log_2(x) \rfloor[/mm]= 3
y = 6x - 32 für x von 16 bis 32 31 mit [mm]\lfloor log_2(x) \rfloor[/mm]= 4
usw.
Allgemein erkennt man: Der Faktor a ist [mm]\lfloor log_2(x) \rfloor[/mm] + 2, der Summand b ist [mm]-2^{\lfloor log_2(x) \rfloor+1}[/mm],
Somit [mm]T(n)=(\lfloor log_2(n) \rfloor \red{+} 2)*x - 2^{\lfloor log_2(x) \rfloor+1 [/mm]
Viel Spass beim Beweis durch vollständige Induktion ...
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 19:59 Mo 23.10.2017 | Autor: | pc_doctor |
Hallo nochmal,
vielen Dank für die Antwort.
Oh man, das kann ja mal was werden mit der Induktion. Ich versuche es :)
|
|
|
|
|
Sorry, habe noch einen Schreibfehler gehabt und ihn nun mit rot korrigiert.
|
|
|
|
|
Hallo,
darf ich fragen wie du auf $ [mm] \lfloor log_2(n)\rfloor [/mm] $ gekommen bist?
LG
|
|
|
|
|
Der Wechsel bei den Abständen der Folgeglieder geschieht immer an einer Zweierpotenz, also bei n = 2, 4, 8, 16,...
Somit brauche ich die Information, zu welchem Abschnitt z.B. die 10 gehört. [mm] 2^3\le 10<2^4. [/mm] somit muss mir die 10 irgendwie den Exponenten 3 liefern, und alle Zahlen zwischen 8 und 15 ebenfalls.
Der [mm] log_2(n) [/mm] fragt: [mm] 2^{wieviel}=n, [/mm] und so kommt für die Zahlen von 8 bis 15 der Wert 3,... heraus, den ich dann abrunde.
Den [mm] log_2 [/mm] von x bekommst du, indem du einen beliebigen log (z.B. ln oder lg=log_10) nimmst und den Wert durch log(2) dividierst, wobei log(2) mit dem selben log genommen werden muss. Also:
[mm] log_2(x)=\bruch{ln(x)}{ln(2)}=\bruch{lg(x)}{lg(2)}=\bruch{log_5(x)}{log_5(2)}=...
[/mm]
|
|
|
|