Forums Neueste Beiträge
 

Die reellen Zahlen sind nicht überabzählbar.

05/06/2016 - 12:41 von WM | Report spam
Der Binàre Baum

0,
/ \
0 1
/ \ / \
0 1 0 1
...

enthàlt alle reellen Zahlen aus dem Einheitsintervall als unendliche Binàrfolgen, sogenannte Pfade. Die Bits mit Wert 0 oder 1 nennt man auch Knoten. Wenn Abzàhlbarkeit eine widerspruchsfreie Eigenschaft von Mengen ist, so ist die Knotenmenge abzàhlbar.

0
1 2
3 4 5 6
...

Um den Beweis ganz allgemein zu halten, nummerieren wir die Pfade folgendermaßen in einer beliebigen Reihenfolge: Ein beliebig wàhlbarer Pfad erhàlt die Nummer 1. Alle sein Knoten werden entfernt. Ein beliebiger anderer Pfad erhàlt die Nummer 2. Alle seine noch vorhandenen Knoten, werden entfernt. Ein weiterer beliebiger Pfad erhàlt die Nummer 3. Alle seine noch vorhandenen Knoten, werden entfernt. Und so weiter. Nach abzàhlbar vielen Schritten sind alle Knoten entfernt. Damit sind alle Pfade entfernt, die als unendliche Binàrfolgen von Knoten existieren.

Eine Diagonalisierung ist nicht möglich, da der Binàre Baum nach Konstruktion alle Binàrfolgen enthàlt.

Gruß, WM
 

Lesen sie die antworten

#1 Jens Kallup
05/06/2016 - 17:03 | Warnen spam
Am 05.06.2016 um 12:41 schrieb WM:

Der Binàre Baum

0,
/ \
0 1
/ \ / \
0 1 0 1


enthàlt alle reellen Zahlen aus dem Einheitsintervall als unendliche Binàrfolgen, sogenannte Pfade.



Falsch!
Reelle Zahlen setzen sich aus rationalen und irrationalen Zahlen zusammen.
Eine rationale Zahl wird durch einen Bruch dargestellt;
in der Form:
1

2

oder 1/2 - 1 als Zàhler als ganze Zahl und der Nenner 2 als natürliche Zahl.
Rationale Zahlen kann man als Bruch darstellen, irrationale Zahlen
jedoch nicht! Da sie zu ungenau sind.

Und ein Intervall ist die Summe eines Start- und Endwertes und wird
bei natürlichen Zahlen wie folgt dargestellt:

{ 3,4,5,6,7 }

als Schlußfolgerung:
3 < 5 < 6 < 7

und bei reellen Zahlen:
[0, 1] = { 0 < r < 1 ] (die Menge aller Zahlen zwischen 0 und 1)

als Schlußfolgerung:
0 < 0.2 < 0.4 < 1

Da verwechselt WM wohl was mit Brüchen und die Darstellung von
Informationen auf/in einen Computer?
Ein Bit ist in der Infortmatik die kleinste Einheit, die mit heutiger
Technik dargestellt werden kann.
Dabei steht 0 für "strom aus" und 1 "strom an".

Nehmen wir als Intervall: { 3,4,5 }, dann ergibt sich eine
Informationsmenge von (bitte jetzt nicht Lachen!) 6 Bytes, mit der
Menge von 3 Bits:

Bitfolge Wert
000 = 0
001 = 1
010 = 2
011 = 3 < Das zu untersuchende
100 = 4 <
101 = 5 < Intervall

Und wie MM schreibt, ist das immer noch kein Binàrbaum, sondern ein
Array aus 3 Folgen:

[0][1][1] <-- 3
[1][0][0] <-- 4
[1][0][1] <-- 5

Ein Binàrbaum besteht aus eine Wurzel und einer "endlichen" Anzahl von
Knoten.
Jeder Knoten eines Binàrbaumes kann (muss nicht zwingend) weiter Konten
besitzen, die als Kinderknoten bezeichnet werden ( A und B).
Wenn das Kindknoten B kleiner als A ist, wird es "links" angeordnet an
den Ursprungsknoten (Wurzel) angekettet und A wird dann "rechts" angekettet.
Alle Bn Knoten, die kleiner B1 sind werden ebenso links angeordnet,
ansonsten rechts.
Jeder Knoten (außer der Wurzel) hat genau "einen" Vater.

Das abarbeiten der Bitfolge ist eine List, also damit ein
"degeneriter Baum"
WM's Beschreibung würde also keinen "vollstàndig ausgeglichenen Baum"
bedeuten.

Zur Verdeutlichung:
W = Wurzel
L = Linkes Kind
R = Rechtes Kind

L1 = 0.1 LL2 = 0.05
R1 = 1 LR2 = 1

W
/ \
L1 R1
/ \
LL2 LR2


LL2 hat als Vater Knoten L1 und L1 als Vater W
LR3 ...

R1 -> W

Daraus ergibt sich:
LL2 = 2 Knoten zur Wurzel
+ L1 = 1 Knoten ...

= 3 - 1 = 2
=
R1 = 1 Knoten zur Wurzel - 1, da keine Weiteren Knoten vorhanden.

Daraus folgt 4 Elemente, aber nur 3 Knoten

Es gibt 3 Möglichkeiten "Ordnungen", die sich aus der Struktur des
Baumes ergeben, Bàume zu durchlaufen:

- Preorder/Prefix-Notation "Wurzel-Links-Rechts"
Es wird immer von der Wurzel, dann der linke, danach der rechte Teilbaum
angearbeitet.

- Inorder "Links-Wurzel-Rechts"
Bei dieser Reihenfolge wird erst der linke Teilbaum bis zum Ende, danach
wird der direkte Vorgànger (Wurzel) abgearbeitet.
Und dann der rechte Teilbaum...

- Postorder "Links-Rechts-Wurzel"
Es wird immer der erst der linke, dann der rechte Baum und am Ende
die Wurzel durchlaufen.


Die Bits mit Wert 0 oder 1 nennt man auch Knoten. Wenn Abzàhlbarkeit eine widerspruchsfreie Eigenschaft von Mengen ist, so ist die Knotenmenge abzàhlbar.



Zu dem Thema Knoten -> siehe oben.
Abzàhlbarkeit wurde gegenüber gestellt und ist kein Widerspruch,
da man mit 3 Bit's 7 Zustànde belegen kann.
Erst dann, wenn man Operationen durchführen möchte, gibt es einen
kleinen Widerspruch:
a) der geneigte Betrachter fàngt mit der Zàhlung von vorne an,
berücksichtigt aber Vorher gemachte Zàhlungen (Beweis: Ich habe mit
Daumen 10 Finger; mit diesen "Grundmitteln" kann man weit über
20 Zàhlen...)
b) bei nichtsdenkende Maschienen wird ein Überlauf generiert und eine
Ausnahme (Interrupt) generiert.


0
1 2
3 4 5 6


Um den Beweis ganz allgemein zu halten, nummerieren wir die Pfade folgendermaßen in einer
beliebigen Reihenfolge: Ein beliebig wàhlbarer Pfad erhàlt die Nummer 1.
Alle sein Knoten werden entfernt.
Ein beliebiger anderer Pfad erhàlt die Nummer 2.
Alle seine noch vorhandenen Knoten, werden entfernt.
Ein weiterer beliebiger Pfad erhàlt die Nummer 3. Alle seine noch vorhandenen Knoten, werden entfernt.
Und so weiter.
Nach abzàhlbar vielen Schritten sind alle Knoten entfernt.
Damit sind alle Pfade entfernt, die als unendliche Binàrfolgen von
Knoten existieren.



Was will uns WM damit sagen?
Ich dachte es ging um die Bitfolge 0 und 1 und nicht um Byte Informationen?
*kratz am Kopf :-)

Wenn alle "Pfade" entfernt werden, dann besteht kein Baum mehr!
Eher ein Wirrwar an angeordneter (Bits) ?
Die Blàtter liegen dann auf dem Boden und werden zu Kompost.
Allgemein gesagt ist mir der Sinn hier nicht klar...
Will WM die Blàtter eines Baumes zàhlen?


Eine Diagonalisierung ist nicht möglich, da der Binàre Baum nach Konstruktion alle Binàrfolgenenthàlt.



Man kann auch Binàrfolgen erstellen, die nicht mit herkömlichen
Computern gelesen werden können.
Aber was nütz das?
Will WM ein Cryptoprogramm schreiben, das nur er vermag zu entschlüsseln ?


Gruß, WM




Jens

Ähnliche fragen