Induktion k-närer Bäume < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:09 Mo 22.09.2008 | | Autor: | Dextro |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Beweisen Sie durch Induktion über die Höhe h:
Jeder binäre Baum der Höhe h hat höchstens [mm] 2^{h+1}-1 [/mm] viele Knoten |
Es handelt sich hier um Algorithmen ( k-näre Bäume ), die Formel ist zwar korrekt, aber ich weiss nicht, ob ich die Aufgabe richtig gelöst habe.
Ich habe wie folgt angefangen:
A(h)= [mm] 2^{h+1} [/mm] -1
Induktionsanfang:
[mm] A(1)=2^{1+1}-1 [/mm] = 4-1 = 3, korrekt
Induktionsbehauptung:
[mm] A(h+1)=2^{(h+1)+1}-1
[/mm]
Induktionsvorraussetzung:
A(h)= [mm] 2^{h+1} [/mm] -1
Induktionsschritt:
[mm] A(h+1)=2^{(h+1)+1}-1
[/mm]
[mm] A(1+1)=2^{(1+1)+1}-1
[/mm]
[mm] A(2)=2^{(2)+1}-1
[/mm]
[mm] A(2)=2^{3}-1
[/mm]
A(2)=7
Ist das so richtig von der Schreibweise oder überhaupt so korrekt ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:22 Mo 22.09.2008 | | Autor: | leduart |
Hallo
Nein, du hast gar nichts bewiesen,
a) ist der Schluss von 1 nach 2 keine Induktion,
b) woher weisst du, dass 7 fuer 2 die richtige Zahl ist?
du hast ueberhaupt nicht benutzt, dass das die maximalzahl der Knoten ist.
Du musst aus maximal [mm] 2^{h+1}-1 [/mm] Knoten fuer einen binaeren Baum der Hoehe h, auf die Maximalzahl der knoten fuer h+1 schleissen. ohne die eigenschaft des bin. B. zu benutzen kannst du das nicht!
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:28 Mi 24.09.2008 | | Autor: | Dextro |
| Aufgabe | Beweisen Sie durch Induktion über die Höhe h:
Jeder binäre Baum der Höhe h hat höchstens [mm] 2^{h+1}-1 [/mm] viele Knoten |
Das heisst also, Lösung z.B. so:
Ind.anfang:
h=0
-> ein bin. Baum der Höhe 0 besteht nur aus der Wurzel. d.h. er hat genau 1 Knoten.
[mm] ->2^{h+1}-1 [/mm] = (über dem = kommt h=0 (symbol nicht gefunden) [mm] 2^1-1=2-1=1
[/mm]
Ind.schluß:
h~>h+1
Ind.voraussetzung:
Jeder bin. Baum der Höhe hat <= [mm] 2^{h+1}-1 [/mm] Knoten
Ind.behauptung:
Jeder bin. Baum der Höhe (h+1) hat <= [mm] 2^{(h+1)+1}-1 [/mm] Knoten
Ind.beweis:
Jeder knoten in einem bin. Baum hat <= 2 Kinder
Jedes Kind ist Wurzel eines Baumes dessen Höhe um mindestens eins kleiner ist als die Höhe des Gesamtbaumes
[mm] \Rightarrow [/mm] Knotenzahl/Gesamtbaum
=Knotenzahl/linker Unterbaum
+Knotenzahl/rechter Unterbaum
+1
<=(hier drüber ein N) [mm] (2^{h+1}-1) [/mm] + [mm] (2^{h+1}-1) [/mm] + 1
[mm] =2*2^{h+1}-1
[/mm]
[mm] =2^{(h+1)+1}-1
[/mm]
ist das nun so korrekt ?
|
|
|
| |
|
> Beweisen Sie durch Induktion über die Höhe h:
> Jeder binäre Baum der Höhe h hat höchstens [mm]2^{h+1}-1[/mm]
> viele Knoten
> Das heisst also, Lösung z.B. so:
> Ind.anfang:
> h=0
> -> ein bin. Baum der Höhe 0 besteht nur aus der Wurzel.
> d.h. er hat genau 1 Knoten.
> [mm]->2^{h+1}-1[/mm] = (über dem = kommt h=0 (symbol nicht
> gefunden) [mm]2^1-1=2-1=1[/mm]
> Ind.schluß:
> h~>h+1
> Ind.voraussetzung:
> Jeder bin. Baum der Höhe hat <= [mm]2^{h+1}-1[/mm] Knoten
> Ind.behauptung:
> Jeder bin. Baum der Höhe (h+1) hat <= [mm]2^{(h+1)+1}-1[/mm]
> Knoten
> Ind.beweis:
> Jeder knoten in einem bin. Baum hat <= 2 Kinder
> Jedes Kind ist Wurzel eines Baumes dessen Höhe um
> mindestens eins kleiner ist als die Höhe des Gesamtbaumes
>
> [mm]\Rightarrow[/mm] Knotenzahl/Gesamtbaum
> =Knotenzahl/linker Unterbaum
> +Knotenzahl/rechter Unterbaum
> +1
>
> <=(hier drüber ein N) [mm](2^{h+1}-1)[/mm] + [mm](2^{h+1}-1)[/mm] + 1
> [mm]=2*2^{h+1}-1[/mm]
> [mm]=2^{(h+1)+1}-1[/mm]
>
> ist das nun so korrekt ?
Hallo!
Das klingt schon viel besser. Beim Induktionsbeweis hast du den (richtigen) Ansatz aber etwas umständlich formuliert. Es reicht:
Bei einem Binärbaum der Höhe h+1 hat die Wurzel höchstens 2 (IV) Kindbäume, welche dann höchstens die Höhe h besitzen. Nach IV ist die Anzahl der Knoten eines jeden dieser beiden Teilbäume [mm] \le 2^{h+1} [/mm] + 1.
Der Gesamtbaum kann also höchstens so viele Knoten haben wie die Summe aus der Höchstanzahl der Knoten der beiden Teilbäume und der Zahl 1 (Wurzel des Gesamtbaums). D.h. es gilt....
Naja - meinte eben nur, dass das bei deinem Beweis alles etwas losgelöst dastand. Sicher wäre es für den Beweis auch sinnvoll (du sparst dir jede Menge Schreibaufwand und es ist mathematisch gesehen eleganter), wenn du Die Anzahl der Knoten mit A oder so bezeichnest.
Stefan.
|
|
|
|
