Blatt 15 Aufgabe 2

Korrigiert mich wenn ich Unsinn rede, aber für b = 0 wird der Wert der Ungleichung für die inneren Knoten negativ, damit kann die Ungleichung nicht gelten, also kann der zu zeigende Satz so gar nicht stimmen. Sollte auf der Angabe nicht stehen b > 1, oder wenigstens b > 0?

Nennt mich einen Korinthenkacker, aber ich finde der TI-Vorlesung bzw. den Übungsblättern mangelt es manchmal an formalen Vorgaben.
Wenn ich formale Beweise führen soll verstehe ich darunter, dass ich formale Aussagen (möglichst nicht deutsche Sätze) mit formal definierten Umformungsregeln irgendwie in die zu zeigende Aussage umforme.
Oft schreibe ich für Beweise eine Seite formale Definitionen, weil ich sie nicht finde oder sie mir nicht klar genug erscheinen - die Definitionen werden länger als der eigentliche Beweis. Oft weiß ich nicht welche offensichtlichen Eigenschaften oder Regeln ich in meinem Beweis einfach benutzen darf, und welche ich erst formal hinschreiben muss.

lg
Julian

Hallo Julian,

nun gut, ich gebe zu dass eine Unterscheidung zwischen positiven ganzen Zahlen und nicht-negativen ganzen Zahlen nicht immer einheitlich war. Aber meistens ist es doch so, dass N die positiven ganzen Zahlen bezeichnet. Weiterhin kann man darauf kommen, dass es hier keinen großen Sinn macht Knoten mit Ausgangsgrad 0 zu betrachten.

Grüße
Christian

Ich verstehs nicht, was ist ein Baum t(x,s) ?
Oder auf welcher Folie soll das stehen
auf Folie 9.2 steht ein Out-Baum aber der ist anderst...
da sagt mir das x und das s nichts oder ich weiss halt nicht was die größen sollen

Mfg
Jan

In der Aufgabenstellung heißt es man soll zeigen, dass ein Baum T(x,s) existiert. D.h. eigentlich soll man zeigen: es gibt einen Baum T, der die dann folgenden Eigenschaften hat. Diese wären u.a.:

"T(x, s) hat x Blätter." (ahhh... x ist also die Anzahl der Blätter...)

"Alle Pfade von der Wurzel zu einem Blatt in T(x, s) haben Länge s." (s ist also die Länge der Pfade).

Ums nochmal zusammenzufassen:
man soll zeigen, dass ein Baum existiert, der x Blätter hat (wobei x = {1,...,b^s} mit Ausgangsgrad des Baumes <= b und s = Länge aller Pfade - sieht Aufgabenstellung) und bei dem alle Pfade von Wurzel bis zum Blatt Länge s hat (also insbesondere sind alle Pfade gleich lang). Zusätzlich soll er halt noch eine weitere Bedinung für die inneren Knoten erfüllen. Diesen Baum NENNEN wir dann T(x,s). Und wie schon gesagt: dessen Existenz soll jetzt erst noch bewiesen werden.
In dem Hinweis steht, man solle über s induzieren. Man kann den Beweis also auch so formulieren: für ein beliebiges, aber festes s soll es einen Baum geben, bei dem alle Pfade s lang sind, der x Blätter hat und bei dem diese Eigenschaft für die inneren Knoten gilt (alles gleichzeitig). Und das für alle s aus N.

Jetzt klarer?

achso so weit hab ich nicht gelesen, ich hab erstmal versucht zu verstehen, was das überhaupt für ein baum ist, bevor ich mich an die drei Punkte mache....
ich habe auserordentliches talent

Hallo.Ich habe eine Frage bei Aufgabe 2. Konnte man annehmen ,dass x = b^s ist?

Hallo,

es ist ja gerade Sinn und Zweck dieser Aufgabe zu beweisen, dass es für ein _beliebiges_ x aus {1...b^s} einen solchen Baum T(x,s) gibt. Also kann man nicht generell annehmen, dass x=b^s ist. Oder habe ich deine Frage missverstanden?

Grüße
Christian