Rekursionsgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo, wir schreiben am Dienstag eine Klausur.
Zur Vorbereitung darauf, will mir eine Aufgabe einfach nicht gelingen.
Finden Sie eine geschlossene Form für die Funktion T(n), die folgendermaßen definiert ist:
T(n) = 2T(n/2) + [mm] nlog_{2}n [/mm] für n > 1
und T(1) = 0.
Es genügt, nur Argumente der Form n = [mm] 2^{k} [/mm] für k [mm] \in \IN [/mm] zu betrachten.
Beweisen Sie die Korrektheit ihrer Lösung mittels vollständiger Induktion.
Folgende Beweisart sollte man dafür benutzen.
2-maliges iteratives Einfügen + Induktionsbeweis.
Was genau habe ich hier unter 2-malig iterativem Einfügen zu verstehen ?
Ich würde mich freuen, wenn mir jemand ein wenig helfen könnte.
Danke
Gruß Chiro
P.S. Ich habe diese Frage auf keiner anderen Internetseite gestellt.
|
|
| |
|
Hallo Chiro,
> Finden Sie eine geschlossene Form für die Funktion T(n),
> die folgendermaßen definiert ist:
>
> T(n) = 2T(n/2) + [mm]nlog_{2}n[/mm] für n > 1
>
> und T(1) = 0.
>
> Es genügt, nur Argumente der Form n = [mm]2^{k}[/mm] für k [mm]\in \IN[/mm]
> zu betrachten.
> Beweisen Sie die Korrektheit ihrer Lösung mittels
> vollständiger Induktion.
>
> Folgende Beweisart sollte man dafür benutzen.
> 2-maliges iteratives Einfügen + Induktionsbeweis.
>
> Was genau habe ich hier unter 2-malig iterativem Einfügen
> zu verstehen ?
Für den Induktionsbeweis habe ich jetzt leider keine Zeit, was aber das Einsetzen angeht, so mußt Du [mm] $T\left(2^k\right)$ [/mm] berechnen (denke ich).
Ich hab's jedenfalls gemacht und es hat auch funktioniert. Vermutlich mußt Du dann die entgültige Formel noch mit Induktion beweisen.
Ich würde dir raten zuerst einige konkrete Zahlenbeispiele (z.B. 2, 4, 8) in T einzusetzen, um ein Gefühl für die Rekursionsgleichung zu bekommen. Danach wagst Du dich an das Obige [mm] $T\left(2^k\right) [/mm] = ?$.
Bei dieser Art von Rekursionen geht es darum Muster in den entstehenden Termen zu entdecken. Dazu darfst Du hier die Terme auf keinen Fall "kompakt" zusammenfassen, weil Du dadurch das Bildungsmuster verstecken würdest. Laß also die entstehenden Terme erstmal so stehen und multipliziere die Klammerblöcke aus (Laß aber die 2er-Potenzen, die dabei entstehen in Ruhe  , sondern erhöhe einfach den Exponenten wo es dir nötig erscheint. Also z.B. nicht [mm] $2*2^2 [/mm] = 8$ rechnen, sondern [mm] $2*2^2 [/mm] = [mm] 2^3$). [/mm] Versuche das und melde dich, wenn Du nicht weiterkommst.
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
Hallo Karl,
danke für deine Hilfe.
Ich bin das jetzt mal durch gegangen und bin dann auf sowas von der Art
[mm] \bruch{k(k+1)}{2} [/mm] * [mm] 2^{k} [/mm] gestoßen.
Falls das jetzt stimmen sollte, wie genau soll ich die Induktion dann ansetzen ?
Gruß Chiro
|
|
|
| |
|
Hallo Chiro,
> Ich bin das jetzt mal durch gegangen und bin dann auf sowas
> von der Art
>
> [mm]\bruch{k(k+1)}{2}[/mm] * [mm]2^{k}[/mm] gestoßen.
Genau das hatte ich auch raus und ich bin mir auch sehr sicher, daß es stimmt. ![[ok]](/images/smileys/ok.gif "[ok]")
> wie genau soll ich die
> Induktion dann ansetzen ?
[mm] $''T\left(1\right) [/mm] = 0''$ ist ja der Spezialfall der Rekursion. Ich denke, daß hier auch die Induktion beginnen sollte, wobei wir [mm] $T\left(2^k\right) [/mm] = [mm] 2^k\bruch{k\left(k+1\right)}{2}$ [/mm] beweisen wollen.
Wegen dem Spezialfall wäre es sinnvoll bei k = 0 anzufangen. Allerdings weiß ich nicht, wie ihr [mm] $\IN$ [/mm] definiert habt. Deshalb definiere ich jetzt einfach  : [mm] $\IN [/mm] := [mm] \left\{0,1,2,\ldots\right\}$.
[/mm]
Induktionsanfang (k = 0):
[m]T\left( {2^0 } \right) = T\left( 1 \right) = 0 = 2^0 \frac{{0\left( {0 + 1} \right)}}{2}[/m]
Wir nehmen also an, die Aussage stimme und machen den ...
Induktionsschritt (k --> k+1):
[m]T\left( {2^{k + 1} } \right) = 2\green{T\left( {2^k } \right)} + 2^{k + 1} \log _2 2^{k + 1} \mathop = \limits^{{\text{Induktionsannahme}}} \cdots[/m]
So das war's. Der Rest ist eigentlich nur Rechnerei (Das Erfolgserlebnis möchte ich dir deshalb nicht nehmen. )
Nach der Induktionsannahme mußt Du den entstandenen Term so umformen, daß er exakt folgende Form annimmt:
[m]2^{k + 1} \frac{{\left( {k + 1} \right)\left( {\left( {k + 1} \right) + 1} \right)}}{2}[/m]
Dann hast Du genau [mm] $A\left(n\right) \Rightarrow A\left(n+1\right)$ [/mm] gezeigt, und die Aussage bewiesen.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:11 So 17.07.2005 | | Autor: | Chironimus |
Hi Karl.
Vielen Dank.
Hat geklappt
Gruß Chiro
|
|
|
| |
|
> Ich bin das jetzt mal durch gegangen und bin dann auf sowas
> von der Art
>
> [mm]\bruch{k(k+1)}{2}[/mm] * [mm]2^{k}[/mm] gestoßen.
>
>
> Gruß Chiro
Wie kommt man darauf? Habe es jetzt mehrmals probiert nachzurechnen, komme aber nicht auf diesen Term.
MfG Andi
PS: Bin auf der gleichen Uni wie Chironimus *gg*.
|
|
|
| |
|
Hallo DerMathematiker,
> Wie kommt man darauf? Habe es jetzt mehrmals probiert
> nachzurechnen, komme aber nicht auf diesen Term.
Du mußt die Rekursionsgleichung mehrmals in sich selbst einsetzen, um das Bildungsmuster zu sehen:
[m]\begin{gathered}
T\left( n \right) = 2T\left( {\frac{n}
{2}} \right) + n\log _2 n = 2\left( {2T\left( {\frac{n}
{{2^2 }}} \right) + \frac{n}
{2}\log _2 \frac{n}
{2}} \right) + n\log _2 n \hfill \\
= 2^2 T\left( {\frac{n}
{{2^2 }}} \right) + n\left( {\log _2 n - 1} \right) + n\log _2 n = 2^2 T\left( {\frac{n}
{{2^2 }}} \right) + 2n\log _2 n - n \hfill \\
= 2^2 \left( {2T\left( {\frac{n}
{{2^3 }}} \right) + \frac{n}
{{2^2 }}\log _2 \left( {\frac{n}
{{2^2 }}} \right)} \right) + 2n\log _2 n - n \hfill \\
= 2^3 T\left( {\frac{n}
{{2^3 }}} \right) + n\left( {\log _2 n - 2} \right) + 2n\log _2 n - n = 2^3 T\left( {\frac{n}
{{2^3 }}} \right) + 3n\log _2 n - 3n \hfill \\
= 2^3 \left( {2T\left( {\frac{n}
{{2^4 }}} \right) + \frac{n}
{{2^3 }}\log _2 \left( {\frac{n}
{{2^3 }}} \right)} \right) + 3n\log _2 n - 3n \hfill \\
= 2^4 T\left( {\frac{n}
{{2^4 }}} \right) + n\log _2 n - 3n + 3n\log _2 n - 3n = 2^4 T\left( {\frac{n}
{{2^4 }}} \right) + 4n\log _2 n - 6n \hfill \\
= 2^5 T\left( {\frac{n}
{{2^5 }}} \right) + 5n\log _2 n - 10n \hfill \\
\end{gathered}[/m]
Jetzt setzen wir einige unserer Zwischenergebnise nebeneinander, und lassen sie auf uns wirken .
[m]\begin{gathered}
2^1 T\left( {\frac{n}
{{2^1 }}} \right) + 1*n\log _2 n - 0*n \hfill \\
2^2 T\left( {\frac{n}
{{2^2 }}} \right) + 2*n\log _2 n - \left( {0 + 1} \right)*n \hfill \\
2^3 T\left( {\frac{n}
{{2^3 }}} \right) + 3*n\log _2 n - \left( {0 + 1 + 2} \right)*n \hfill \\
2^4 T\left( {\frac{n}
{{2^4 }}} \right) + 4*n\log _2 n - \left( {0 + 1 + 2 + 3} \right)*n \hfill \\
2^5 T\left( {\frac{n}
{{2^5 }}} \right) + 5*n\log _2 n - \left( {0 + 1 + 2 + 3 + 4} \right)*n \hfill \\
\vdots \hfill \\
2^i T\left( {\frac{n}
{{2^i }}} \right) + i*n\log _2 n - \left( {0 + 1 + \cdots + i - 1} \right)*n \hfill \\
\end{gathered}[/m]
Jetzt haben wir zwar das Bildungsmuster rausgekriegt, [mm] $T(\cdot{})$ [/mm] jedoch nicht entfernen können. Es gilt aber nach Definition $T(1) = [mm] 0\!$. [/mm] Wann wird also [mm] $\tfrac{n}{2^i} [/mm] = 1$? Eine Nebenrechnung schafft Klarheit:
[mm] $\frac{n}{2^i} [/mm] = [mm] 1\Leftrightarrow [/mm] n = [mm] 2^i\Leftrightarrow\log_2 [/mm] n = i$
Bevor wir das für das [mm] $i\!$ [/mm] einsetzen, machen wir noch eine letzte Umformung, damit der Term übersichtlich bleibt:
[m]\begin{gathered}
2^i T\left( {\frac{n}
{{2^i }}} \right) + i*n\log _2 n - \left( {0 + 1 + \cdots + i - 1} \right)*n \hfill \\
= 2^i T\left( {\frac{n}
{{2^i }}} \right) + i*n\log _2 n - \frac{{i\left( {i - 1} \right)}}
{2}*n \hfill \\
\end{gathered}[/m]
Einsetzen liefert: [m]n*0 + \log _2 n*n\log _2 n - \tfrac{{\log _2 n\left( {\log _2 n - 1} \right)}}{2}*n[/m]. Damit kann man den Term vereinfachen:
[m]\begin{gathered}
n\left( {\log _2 n} \right)^2 - \frac{{\left( {\log _2 n - 1} \right)\log _2 n}}
{2}*n = \hfill \\
n\left( {\log _2 n} \right)^2 - \frac{{\left( {\log _2 n} \right)^2 - \log _2 n}}
{2}*n = \hfill \\
n\left( {\log _2 n} \right)^2 - \frac{n}
{2}\left( {\log _2 n} \right)^2 + \frac{n}
{2}\log _2 n = \hfill \\
\frac{n}
{2}\left( {\log _2 n} \right)^2 + \frac{n}
{2}\log _2 n = \frac{n}
{2}\log _2 \left( n \right)\log _2 \left( {2n} \right) \hfill \\
\end{gathered}[/m]
Wenn Du nun für das [mm] $n\!$ [/mm] den Term [mm] $2^k$ [/mm] einsetzt, kommst Du auf die Form, die Chiro und ich raushatten.
Viele Grüße
Karl
|
|
|
| |
|
Hi,
danke für deine Antwort. Jetzt hab ich's geschnallt. Kennst du zufälligerweise Seiten, auf denen es weitere solcher Aufgaben gibt incl. Lösungen? Würde das gerne noch ein wenig üben.
MfG Andi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:52 Sa 27.08.2005 | | Autor: | Karl_Pech |
Hallo Andi,
> danke für deine Antwort. Jetzt hab ich's geschnallt. Kennst
> du zufälligerweise Seiten, auf denen es weitere solcher
> Aufgaben gibt incl. Lösungen?
Im Moment nicht, aber es sollte einfach sein solche Übungsaufgaben über Google zu finden.
Viele Grüße
Karl
|
|
|
|
