Rekursion lösen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:12 Mo 10.11.2014 | | Autor: | evinda |
Hallo 
Ich will mit Induktion zeigen, dass [mm] S(m)=\Theta(m^2), [/mm]
[mm] S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2 [/mm]
Ich habe folgendes versucht:
Die Rekursion ist gut definiert, wenn [mm] \frac{m}{5}+3
Wir wollen zeigen, dass [mm] S(m)=\Theta(m^2).
[/mm]
Wir nehmen an, dass [mm] \exists c_1,c_2, n_0 \geq [/mm] 4, sodass [mm] \forall n_0 \leq [/mm] k<m:
[mm] c_1 k^2 \leq [/mm] S(k) [mm] \leq c_2 k^2
[/mm]
[mm] S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2 \leq 3c_2 \frac{m^2}{25}+2 \left(\frac{m}{5}+6 \right)^2+m^2=\frac{5c_2n^2}{25}+\frac{12c_2n}{5}+18c_2+n^2 \leq c_2 n^2
[/mm]
wenn [mm] c_2 n^2-\frac{5c_2n^2}{25}-\frac{12c_2n}{5}-18c_2+n^2 \geq [/mm] 0 [mm] \Rightarrow \frac{2c_2}{5}(2n^2-6n-45) \geq n^2 \Rightarrow \frac{2c_2}{5} \geq \frac{n^2}{2n^2-6n-45} \to \frac{1}{2} \Rightarrow 2c_2 \geq \frac{5}{2} \Rightarrow c_2 \geq \frac{5}{4}
[/mm]
Ähnlich zeigen wir, dass S(m) [mm] \geq c_1 m^2, [/mm] wenn [mm] c_1 \leq \frac{5}{4}.
[/mm]
Könntet ihr mir sagen ob es richtig ist?
|
|
| |
|
Hallo evinda,
da fehlt doch irgendetwas...
> Hallo
>
> Ich will mit Induktion zeigen, dass [mm]S(m)=\Theta(m^2),[/mm]
> [mm]S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2[/mm]
Schön. Damit wäre S(m) also rekursiv definiert.
Was ist [mm] \Theta(m^2) [/mm] ?
> Ich habe folgendes versucht:
>
> Die Rekursion ist gut definiert, wenn [mm]\frac{m}{5}+3
> m [mm]\geq[/mm] 4.
Hm. Was für eine Zahl ist denn m? Eine reelle? Eine reelle, positive?
> Wir wollen zeigen, dass [mm]S(m)=\Theta(m^2).[/mm]
Ab hier sehe ich den Zweck der Umformung nicht, weil ich nicht weiß, was [mm] \Theta [/mm] ist, was m ist, ob die Rekursion überhaupt konvergiert, etc.
Sag dazu doch erstmal etwas, dann sehen wir weiter.
Grüße
reverend
> Wir nehmen an, dass [mm]\exists c_1,c_2, n_0 \geq[/mm] 4, sodass
> [mm]\forall n_0 \leq[/mm] k<m:
>
> [mm]c_1 k^2 \leq[/mm] S(k) [mm]\leq c_2 k^2[/mm]
>
> [mm]S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2 \leq 3c_2 \frac{m^2}{25}+2 \left(\frac{m}{5}+6 \right)^2+m^2=\frac{5c_2n^2}{25}+\frac{12c_2n}{5}+18c_2+n^2 \leq c_2 n^2[/mm]
>
> wenn [mm]c_2 n^2-\frac{5c_2n^2}{25}-\frac{12c_2n}{5}-18c_2+n^2 \geq[/mm]
> 0 [mm]\Rightarrow \frac{2c_2}{5}(2n^2-6n-45) \geq n^2 \Rightarrow \frac{2c_2}{5} \geq \frac{n^2}{2n^2-6n-45} \to \frac{1}{2} \Rightarrow 2c_2 \geq \frac{5}{2} \Rightarrow c_2 \geq \frac{5}{4}[/mm]
>
> Ähnlich zeigen wir, dass S(m) [mm]\geq c_1 m^2,[/mm] wenn [mm]c_1 \leq \frac{5}{4}.[/mm]
>
> Könntet ihr mir sagen ob es richtig ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:44 Mo 10.11.2014 | | Autor: | DieAcht |
Hallo reverend,
> Was ist [mm]\Theta(m^2)[/mm] ?
![[]](/images/popup.gif) Landau-Symbole.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:39 Mo 10.11.2014 | | Autor: | DieAcht |
Hallo evinda,
> Ich will mit Induktion zeigen,
Wo benutzt du (unten) Induktion?
> dass [mm]S(m)=\Theta(m^2),[/mm]
> [mm]S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2[/mm]
> Die Rekursion ist gut definiert,
Diesen Begriff kenne ich nicht. Erläutere bitte!
> wenn [mm]\frac{m}{5}+3
Es ist
[mm] $\frac{m}{5}+3\frac{15}{4}$.
[/mm]
Mit meiner Annahme [mm] D_s:=\IN_0 [/mm] komme ich auch auf [mm] $m\ge [/mm] 4$.
> Wir wollen zeigen, dass [mm]S(m)=\Theta(m^2).[/mm]
>
> Wir nehmen an, dass [mm]\exists c_1,c_2, n_0 \geq[/mm] 4, sodass
> [mm]\forall n_0 \leq[/mm] k<m:
>
> [mm]c_1 k^2 \leq[/mm] S(k) [mm]\leq c_2 k^2[/mm]
Ich glaube, dass das falsch ist. Wir setzen
[mm] \tilde{S}(m):=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right),
[/mm]
so dass
[mm] S(m)=\tilde{S}(m)+m^2.
[/mm]
Zu zeigen: [mm] S(m)=\Theta(m^2). [/mm] Also ist zu zeigen:
Es existieren [mm] $c_1>0\$, $c_2>0\$ [/mm] und [mm] $n_0>0\$, [/mm] so dass
[mm] $\tilde{S}(m)+c_1*m^2\le S(m)\le\tilde{S}(m)+c_2*m^2$ [/mm] für alle [mm] $m>n_0\$.
[/mm]
(Dabei habe ich nicht beachtet, dass die Rekursion für [mm] $m\ge [/mm] 4$
gut definiert ist.)
Gruß
DieAcht
|
|
|
|
