| Die letzten 9 Beiträge |
| Ic3Cub3 |
Alles klar! Vielen Dank! :) |
| as_string |
Hallo!
Nein, das ist schon richtig.
Die Idee ist, dass man im Induktionsschritt beweist: falls (angenommen) für h die Hypothese schon erfüllt wäre, beweise, dass sie für h+1 auch noch stimmt. Das allerdings allgemein für alle h ab dem Induktionsanfang. Damit hast Du ja viel mehr gezeigt, als nur den Schritt von h=0 auf h=1.
Umgekehrt ausgedrückt: mit dem Induktionsschritt hast Du auch das schon bewiesen, wie Du vom Induktionsanfang eins erhöhst. Du kannst ja einfach für h eine 0 einsetzen. Dann wäre b(0) laut Hypothese gerade 1 und ich zeige, wenn das tatsächlich der Fall ist, dann ist b(0+1) = 2.
Dass das für b(0) der Fall ist, zeige ich separat mit dem Induktionsanfang.
Jetzt kann ich meinen Induktionsschritt aber nochmal verwenden, ich hab ja b(1) = 2 schon bewiesen. Daraus kann ich dann auch b(2) = 4 zeigen und so weiter für jedes h. Hätte ich für meinen Induktionsschritt nur h = 0 verwendet, würde ich ja immer nur auf h = 1 kommen und nicht weiter bewiesen haben. Ich hab im Induktionsschritt bewiesen, dass für alle Schritt von h auf h +1 die Kette noch stimmt, Du hättest viel weniger bewiesen, nämlich nur für den ersten Schritt.
Gruß
Marco |
| Ic3Cub3 |
Hallo nochmal,
ich habe da noch eine Frage. Sollte sich der Induktionsschritt nicht auf den Induktionsanfang beziehen, da falls man sich auf die Induktionshypothese bezieht und diese falsch ist man sozusagen in eine Schleife mit Fehlern gerät?
LG Ic3Cub3 |
| Ic3Cub3 |
Hallo Marco,
vielen Dank für deine Antwort. Ist anschaulich und verständlich! Danke.
LG Ic3Cub3 |
| as_string |
Hallo!
Also ich würde schreiben:
Induktionshypothese:
Sei h die Höhe eines vollständigen Binärbaums T und b die Anzahl seiner Blätter. Dann gilt
![[latex]b(h) = 2^h[/latex]](http://www.matheboard.de/latex2png/latex2png.php?b(h) = 2^h)
Induktionsanfang:
Ein Baum mit Höhe 0 hat nur einen einzigen Wurzelknoten, der auch gleichzeitig das einzige Blatt ist.
Der Induktionsanfang
![[latex]b(0) = 1 = 2^0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?b(0) = 1 = 2^0)
ist also erfüllt.
Induktionsschritt:
Wenn man bei einem vollständigen Binärbaum seine Höhe h um eins erhöht, bekommt jedes bisherige Blatt zwei neue Kinder, die jeweils zu neuen Blättern werden. Die Anzahl der Blätter verdoppelt sich also.
![[latex]b(h+1) = 2\cdot b(h) = 2\cdot 2^h = 2^{h+1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?b(h+1) = 2\cdot b(h) = 2\cdot 2^h = 2^{h+1})
Beim zweiten Gleichheitszeichen hab ich die Induktionshypothese verwendet, indem ich b(h) durch 2^h ersetzt habe.
Gruß
Marco |
| Ic3Cub3 |
Hallo Marco,
Vielen Dank für deine Antwort!
| Zitat: |
Auch das würde ich anders machen. Du gehst ja quasi von einem größeren Baum aus und halbierst den dann. Das mag zwar letztlich auch funktionieren indem Du das Ergebnis dann quasi rumdrehst, aber da bin ich mir nicht ganz sicher.
Eigentlich musst Du ja von einem Baum mit Tiefe h (zuerst mit einem Knoten, also h=1, dann aber für alle folgenden) auf einen Baum mit Tiefe h+1 kommen.
Da an jedes Blatt des Baumes mit Tiefe h jeweils zwei neue Knoten angehängt werden, die dann zu den neuen Blättern werden, ist es klar, dass sich bei h -> h+1 auch die Blattzahl verdoppeln muss, also b -> 2*b.
Hier siehst Du vielleicht dann auch nochmal meine Bauchschmerzen mit Deinem Induktionsanfang: Wenn ich mit 0 Knoten anfange, dann kann ich an kein Blatt zwei weitere Blätter anhängen. Ich komme so nie mit meinem Induktionsschritt vom Induktionsanfang auf die nächste Baumtiefe. |
bei h=0 hat der Baum genau h^0=1 Knoten, was ich im IA gezeigt habe.
Ich beziehe mich auf deine Idee und gehe eine Ebene tiefer auf h+1.
Die Knoten verdoppeln sich, also habe ich 2*1=2 Blätter.
h+2<=>h=2: 2*2*1=2^2 Blätter
h+3<=>h=3: 2*2*2*1=2^3 Blätter
.
.
.
h: 2^h Blätter
--> ein vollständiger binärer Baum hat 2^h Blätter
Ist das was du meinst? Und könntest du mir bei der Formailtät helfen? :)
Vielen Dank im Voraus!
LG Ic3Cub3 |
| as_string |
Hallo nochmal!
Ich glaube, ich habe einen Fehler gemacht: Dein Baum der Höhe 0 hat ja schon einen Knoten. Das entspricht ja gerade dann dem, was ich eigentlich machen wollte, nur dass ich anders zu Zählen angefangen habe.
Dann ist Dein Induktionsanfang doch richtig! Tut mir Leid wegen der Verwirrung!
Gruß
Marco |
| as_string |
RE: Beweis Anzahl Blätter vollständiger Binärer Baum
| Zitat: |
Original von Ic3Cub3
da ich neu in diesem Forum bin, bitte ich um Nachsicht, falls ich Fehler machen sollte 
|
Willkommen im Informaitkerboard! 
| Zitat: |
Original von Ic3Cub3
Induktionsanfang:
für h=0 --> 2^0=1 Blatt
stimmt. |
Ich würde nicht gerade mit der 0 anfangen, ich glaube sogar, dass dann der Beweis falsch wird:
Die Grundidee ist ja bei der vollständigen Induktion: Nimm einen konkreten Anfang, für den es i. A. ja einfach ist zu zeigen, dass die Bedingung erfüllt ist. Beweise dann mithilfe des Induktionsschritts, dass es für das darauf folgende und das dann darauf folgende und so weiter auch erfüllt ist.
Das bedeutet: Insbesondere musst Du natürlich mit dem Induktionsschritt vom Induktionsanfang auf das nächste zuerst einmal kommen können. Ein Baum mit 0 Knoten kann ich aber nicht so erweitern, dass ich danach dann doppelt so viele Blätter hätte.
So klar ist es ja auch erstmal nicht, dass irgendeine Zahl hoch 0 immer eine 1 ergibt. Wenn man mal von der Regel ausgeht, dass z. B. 2^n das Produkt aus n Zweien ist, dann kann man 2^0 so ja noch nicht ohne weiteres bestimmen. Letztlich ist es bei einer solchen Definition noch zwingend, dass der Exponent eine natürliche Zahl (ohne 0) ist. Erst wenn man das noch erweitert, kann man für den Exponenten reelle Zahlen verwenden.
| Zitat: |
Original von Ic3Cub3
Induktionsschritt:
T ist ein Baum der Höhe h
die Wurzel von T hat zwei Teilbäume als Söhne, die jeweils die Höhe h-1 haben
Diese Teilbäume haben eine Blätteranzahl von 2^(h-1)
Somit hat T 2*2^(h-1)=2^(h) Blätter. |
Auch das würde ich anders machen. Du gehst ja quasi von einem größeren Baum aus und halbierst den dann. Das mag zwar letztlich auch funktionieren indem Du das Ergebnis dann quasi rumdrehst, aber da bin ich mir nicht ganz sicher.
Eigentlich musst Du ja von einem Baum mit Tiefe h (zuerst mit einem Knoten, also h=1, dann aber für alle folgenden) auf einen Baum mit Tiefe h+1 kommen.
Da an jedes Blatt des Baumes mit Tiefe h jeweils zwei neue Knoten angehängt werden, die dann zu den neuen Blättern werden, ist es klar, dass sich bei h -> h+1 auch die Blattzahl verdoppeln muss, also b -> 2*b.
Hier siehst Du vielleicht dann auch nochmal meine Bauchschmerzen mit Deinem Induktionsanfang: Wenn ich mit 0 Knoten anfange, dann kann ich an kein Blatt zwei weitere Blätter anhängen. Ich komme so nie mit meinem Induktionsschritt vom Induktionsanfang auf die nächste Baumtiefe.
| Zitat: |
Original von Ic3Cub3
Außerdem bin ich mir auch nicht sicher wie ich den Beweis formal korrekt aufschreiben soll...
|
Mit dem Formalen hatte ich auch immer meine Probleme... Vielleicht versuchen wir das gleich mal gemeinsam.
Gruß
Marco |
| Ic3Cub3 |
Beweis Anzahl Blätter vollständiger Binärer Baum
Meine Frage:
Hallo,
da ich neu in diesem Forum bin, bitte ich um Nachsicht, falls ich Fehler machen sollte
Aufgabe: Wie viele Blätter hat ein vollständiger binärer Baum der Höhe h? Beweis per vollständiger Induktion.
Meine Ideen:
Behauptung:
Baum der Höhe h hat 2^h Blätter
Induktionsanfang:
für h=0 --> 2^0=1 Blatt
stimmt.
Induktionsschritt:
T ist ein Baum der Höhe h
die Wurzel von T hat zwei Teilbäume als Söhne, die jeweils die Höhe h-1 haben
Diese Teilbäume haben eine Blätteranzahl von 2^(h-1)
Somit hat T 2*2^(h-1)=2^(h) Blätter.
Ich denke, dass die Grundidee hierbei richtig ist.
Allerdings glaube ich, dass dieser Beweis nicht vollständig ist. Z.B. weiß ich nicht, wie ich beweisen soll, dass die Teilbäume eine Blätternanzahl von 2^(h-1) haben.
Außerdem bin ich mir auch nicht sicher wie ich den Beweis formal korrekt aufschreiben soll...
Ich wäre sehr dankbar für eure Hilfe!
LG Ic3Cub3 |
|
|
