Rekursionsgleichung lösen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:28 Mo 10.05.2010 | | Autor: | DerGraf |
Hallo,
mir ist folgende Rekursionsgleichung gegeben,die ich lösen soll:
[mm] T\left(n\right)=n*T\left(\bruch{n}{2}\right)+n
[/mm]
Da vor dem [mm] T\left(\bruch{n}{2}\right) [/mm] der Faktor "n" steht (,also kein konstanter Wert), kann ich das Mastertheorem nicht anwenden. eine geeignete Substitution habe ich leider auch noch nicht gefunden. T(n) muss größer sein als [mm] n^k [/mm] mit k beliebig groß, aber kleiner als [mm] 2^n.
[/mm]
Hat vielleicht jemand von euch eine Idee für mich?
Ich bin für jede Hilfe dankbar.
Gruß
DerGraf
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:47 Mo 10.05.2010 | | Autor: | iMod109 |
Hast du es schonmal mit auffalten versucht?
Du kannst die Formel ja immer weiter aufdröseln:
[mm] T(n)=n*T(\bruch{n}{2})+n [/mm] = [mm] n*(\bruch{n}{2}*T(\bruch{n}{4})+\bruch{n}{2})+n [/mm] = usw...
Vielleicht hilft dir das weiter
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:36 Mo 10.05.2010 | | Autor: | DerGraf |
Hallo iMod109,
mit Hilfe deiner Idee bin ich zu folgendem Ergebnis gelangt:
$ [mm] T(n)=n\cdot{}T(\bruch{n}{2})+n [/mm] $ = $ [mm] n\cdot{}(\bruch{n}{2}\cdot{}T(\bruch{n}{4})+\bruch{n}{2})+n [/mm] $
Setze nun [mm] S(n)=\bruch{1}{n}*T(n), [/mm] dann sollte doch gelten:
[mm] S(n)=\bruch{1}{n}*T(n)=\bruch{1}{n}\left( n\cdot{}\left(\bruch{n}{2}\cdot{}T\left(\bruch{n}{4}\right)+\bruch{n}{2}\right)+n\right)=\bruch{n}{2}*T\left(\bruch{n}{4}\right)+\bruch{n}{2}+1=2*S\left(\bruch{n}{4}\right)+\bruch{n}{2}+1
[/mm]
Auf S(n) wende ich nun das Mastertheorem an und erhalte eine Lösung für S(n) und somit letztendlich auch für T(n).
Ist das so richtig?
Gruß
DerGraf
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:21 Di 11.05.2010 | | Autor: | DerGraf |
Mist,ich habe mich leider verrechnet. So einfach gehts dann wohl doch nicht :(
|
|
|
| |
|
Hallo DerGraf,
Wie dir schon iMod109 geraten hat, kannst du die rekursive Beziehung hier mehrmals in sich einsetzen und schauen, welche Terme dabei entstehen. Um den Vorgang teilweise zu automatisieren, habe ich folgendes kleines Programm in ![[]](/images/popup.gif) Python unter Benutzung von sympy geschrieben:
| 1: | from sympy import symbols, latex
| | 2: |
| | 3: | n = symbols('n')
| | 4: |
| | 5: | def T0(a,m,k):
| | 6: | if k < m:
| | 7: | return a*T0(a/2,m,k+1)+a
| | 8: | else:
| | 9: | return symbols('x')
| | 10: |
| | 11: | def T1(a,m,k):
| | 12: | if k < m:
| | 13: | return T1(a/2,m,k+1)
| | 14: | else:
| | 15: | return a
| | 16: |
| | 17: | for m in range(10):
| | 18: | r = str(latex(T0(n,m,0).expand())), str(latex(T1(n,m,0).expand()))
| | 19: | print 'm = %d : %s'%(m, r[0].replace('x','T(%s)'%r[1]))
|
Zur Ausführung des Programms wird Python 2.6.x benötigt. Das Programm "entfaltet" den Ausdruck, der von T() (hier als T0() und T1()) generiert wird rekursiv bis zu einer vorgegebenen Rekursionstiefe m. Startet man das Programm und bearbeitet das Ergebnis teilweise von Hand nach, erhält man:
[mm]m = 0:\quad T\left(\frac{n}{2^0}\right)[/mm]
[mm]m = 1:\quad\frac{n^1}{2^0} + \frac{n^1}{2^0}\cdot{}T\left(\frac{n}{2^1}\right)[/mm]
[mm]m = 2:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^2}{2^1}\cdot{}T\left(\frac{n}{2^2}\right)[/mm]
[mm]m = 3:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^3}{2^3}\cdot{}T\left(\frac{n}{2^3}\right)[/mm]
[mm]m = 4:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^4}{2^6} + \frac{n^4}{2^6}\cdot{}T\left(\frac{n}{2^4}\right)[/mm]
[mm]m = 5:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^4}{2^6} + \frac{n^5}{2^{10}} + \frac{n^5}{2^{10}}\cdot{}T\left(\frac{n}{2^5}\right)[/mm]
[mm]m = 6:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^4}{2^6} + \frac{n^5}{2^{10}} + \frac{n^6}{2^{15}} + \frac{n^6}{2^{15}}\cdot{}T\left(\frac{n}{2^6}\right)[/mm]
[mm]m = 7:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^4}{2^6} + \frac{n^5}{2^{10}} + \frac{n^6}{2^{15}} + \frac{n^7}{2^{21}} + \frac{n^7}{2^{21}}\cdot{}T\left(\frac{n}{2^7}\right)[/mm]
[mm]m = 8:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^4}{2^6} + \frac{n^5}{2^{10}} + \frac{n^6}{2^{15}} + \frac{n^7}{2^{21}} + \frac{n^8}{2^{28}} + \frac{n^8}{2^{28}}\cdot{}T\left(\frac{n}{2^8}\right)[/mm]
[mm]m = 9:\quad\frac{n^1}{2^0} + \frac{n^2}{2^1} + \frac{n^3}{2^3} + \frac{n^4}{2^6} + \frac{n^5}{2^{10}} + \frac{n^6}{2^{15}} + \frac{n^7}{2^{21}} + \frac{n^8}{2^{28}} + \frac{n^9}{2^{36}} + \frac{n^9}{2^{36}}\cdot{}T\left(\frac{n}{2^9}\right)[/mm]
Jetzt gilt es das Prinzip zu verstehen, dem die Exponentenfolge der 2er-Potenzen folgt. Es gilt z.B. 0+1+2+3 = 6 und 0+1+2+3+4 = 10. Für ein vorgegebenes m, scheint T() also folgenden Term zu bilden:
[mm]\frac{n^m}{2^{m(m-1)/2}}\cdot{}T\left(\frac{n}{2^m}\right)+\sum_{k=0}^{m-1}{\frac{n^{k+1}}{2^{k(k+1)/2}}}[/mm]
Jetzt müßtest du uns nur noch verraten, welchen Anfangsbedingungen T() genügt. War in der Aufgabenstellung z.B. von T(1) = ... die Rede? Sonst ist die Aufgabe unlösbar. Ansonsten kannst du das m so wählen, daß T() die Anfangsbedingung erreicht und somit aus dem Termausdruck "verschwindet". Danach mußt du diese Darstellung für T() als Summe mit vollständiger Induktion über n beweisen, um sicherzugehen, daß die Darstellung auch stimmt. Danach kannst du schauen, ob du die Summe in einem geschlossenen Ausdruck darstellen kannst. Die Summe sieht ziemlich kompliziert aus. Eine geometrische Reihe scheint das wegen dem komplizierten Exponenten im Nenner nicht zu sein.
Viele Grüße
Karl
|
|
|
|
