log(n) Knoten um n Pfade zu unterscheiden?

27/05/2016 - 10:42 von WM | Report spam
Jürgen Rennenkampff behauptet: Um n Pfade zu unterscheiden, brauchen wir nur etwa log(n) Knoten, d. h. aleph_0 Knoten ergeben 2^aleph_0 Pfade.

Was ist dazu zu sagen?

Der Binàre Baum enthàlt 2^n Knoten auf der Ebene n. Damit lassen sich N = 2^n Pfade unterscheiden. Hier das Beispiel für Ebene 1:

0,
/ \
0 1

Es sind demnach zur Unterscheidung von n Pfaden, falls ein Pfad gegeben ist, noch n-1 Knoten erforderlich.

Der Fehler des Herrn Rennenkampff besteht also darin, dass er die Pfadlànge log(N) mit der Anzahl unterscheidbarer Pfade N und den dafür erforderlichen Knoten verwechselt.

(Auf der Ebene aleph_0, die der Binàre Baum indessen nicht enthàlt, ließen sich durch 2^aleph_0 Knoten ebensoviele Pfade unterscheiden.)

Gruß, WM
 

Lesen sie die antworten

#1 Me
27/05/2016 - 11:42 | Warnen spam
On Friday, May 27, 2016 at 10:42:35 AM UTC+2, WM wrote:

Jürgen Rennenkampff behauptet: Um n Pfade [unterscheiden zu können],
brauchen wir nur etwa log(n) Knoten



Vermutlich meinte er die "Pfadlànge" (oder hat sich einen kleinen Thinko geleistet, nichts Dramatisches).

Was ist dazu zu sagen?



Siehe oben.

Der Binàre Baum enthàlt 2^n Knoten auf der Ebene n. Damit lassen sich
N = 2^n Pfade unterscheiden.



Ihre durch und durch "psychologistische" Ausdrucksweise im Zusammenhang mit /mathematischen Sachverhalten/ ist wirklich gruselig, Mückenheim. "lassen sich unterscheiden" huh?!

Ein Mathematiker würde sagen, dass es in so einem Baum 2^n Pfade GIBT.

(Niemand interessiert sich dafür, ob Sie oder ich oder wer auch immer diese unterscheiden kann oder auch nicht.)

Kleiner Tipp: Es gibt eine Bijektion zwischen der Menge der Endknoten des _endlichen Baumes_ und der Menge der Pfade vom Wurzelknoten bis zu den Endknoten. (Man braucht bloß jeden Endknoten dem Pfad zuzuordnen, der ihn enthàlt.)

Hier das Beispiel für Ebene 1:

0,
/ \
0 1 <<<<< Ebene 1


Der Fehler des Herrn Rennenkampff besteht also darin, dass er die
Pfadlànge log(N) mit der Anzahl unterscheidbarer Pfade N und den
dafür erforderlichen Knoten verwechselt.



Siehe oben.

So schön diese Überlegungen auch sind, für _unendliche Bàume_ sind sie nicht mehr von Belang aus dem einfachen Grund, weil es in einem unendlichen Baum keine "Endknoten" gibt. (Sie lernen es wirklich nicht mehr, Mückenheim.)

Ähnliche fragen