 Frage zu optimalen Suchbäumen |
Annamaria
unregistriert
 |
|
| Frage zu optimalen Suchbäumen |
     |
Meine Frage:
Hallo ,
ich habe gerade ein paar Verständnisschschwierigkeiten bei einer
Aufgabe:
a) Geben Sie eine Wahrscheinlichkeitsverteilung der Elemente {1,...n} an ,sodass der optimale Suchbaum eine lineare Kette ist.
b) Es gibt 5 verschiedene Suchbäume mit Knoten {1,2,3}. Geben Sie an , bei welchen Wahrscheinlichkeitsverteilungen mit welcher dieser Bäume als optimaler Suchbaum entsteht.
Mein Lösungansatz:
zu a)
Wenn die ich Elemente so anordne ,dass sie eine absteigende bzw. aufsteigende Reihenfolge bilden,dann entstehet eine lineare Kette.
Die Wahrscheinlichkeit sollte wohl so aufteilt sein ,dass bei aufsteingender Reihenfolge das kleinste Element die größte Wahrscheinlichkeit , das zweitkleinste die zweitgrößte Wahrscheinlichkeit hat usw.
oder liege ich falsch ?
zu b)
Ich soll einfach verschiede Wahrscheinlichkeitsverteilungen ausprobieren, aber welche?
Grundproblem: Was ist mit der Wahrscheinlichkeitsverteilung gemeint und wie wird sie berechnet?
_________________
Meine Ideen:
Mein Lösungansatz:
zu a)
Wenn die ich Elemente so anordne ,dass sie eine absteigende bzw. aufsteigende Reihenfolge bilden,dann entstehet eine lineare Kette.
Die Wahrscheinlichkeit sollte wohl so aufteilt sein ,dass bei aufsteingender Reihenfolge das kleinste Element die größte Wahrscheinlichkeit , das zweitkleinste die zweitgrößte Wahrscheinlichkeit hat usw.
oder liege ich falsch ?
zu b)
Ich soll einfach verschiede Wahrscheinlichkeitsverteilungen ausprobieren, aber welche?
Grundproblem: Was ist mit der Wahrscheinlichkeitsverteilung gemeint und wie wird sie berechnet?
_________________
|
|
01.12.2012 13:34 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| RE: Frage zu optimalen Suchbäumen |
|
| Zitat: |
Original von Annamaria
Mein Lösungansatz:
zu a)
Wenn die ich Elemente so anordne ,dass sie eine absteigende bzw. aufsteigende Reihenfolge bilden,dann entstehet eine lineare Kette.
Die Wahrscheinlichkeit sollte wohl so aufteilt sein ,dass bei aufsteingender Reihenfolge das kleinste Element die größte Wahrscheinlichkeit , das zweitkleinste die zweitgrößte Wahrscheinlichkeit hat usw.
oder liege ich falsch ?
|
Ich denke das passt.
| Zitat: |
Original von Annamaria
zu b)
Ich soll einfach verschiede Wahrscheinlichkeitsverteilungen ausprobieren, aber welche?
Grundproblem: Was ist mit der Wahrscheinlichkeitsverteilung gemeint und wie wird sie berechnet?
|
Mit Wahrscheinlichkeitsverteilung ist hier sicher gemeint, mit welchen Wahrscheinlichkeiten die Elemente im Suchbaum gesucht werden. Z.B. ![[latex]P(1) = 0,5, P(2) = 0,25, P(3) = 0,25[/latex]](http://www.matheboard.de/latex2png/latex2png.php?P(1) = 0,5, P(2) = 0,25, P(3) = 0,25) .
Meiner Meinung nach ist es sinnvoll sich erstmal die 5 Bäume aufzumalen und dann zu schauen, welche Wahrscheinlichkeitsverteilung hier günstig wäre.
VG,
Karlito
|
|
|
01.12.2012 16:57 |
|
|
Annamaria
unregistriert
|
|
| RE: Frage zu optimalen Suchbäumen |
|
| Zitat: |
Original von Karlito
| Zitat: |
Original von Annamaria
Mein Lösungansatz:
zu a)
Wenn die ich Elemente so anordne ,dass sie eine absteigende bzw. aufsteigende Reihenfolge bilden,dann entstehet eine lineare Kette.
Die Wahrscheinlichkeit sollte wohl so aufteilt sein ,dass bei aufsteingender Reihenfolge das kleinste Element die größte Wahrscheinlichkeit , das zweitkleinste die zweitgrößte Wahrscheinlichkeit hat usw.
oder liege ich falsch ?
|
Ich denke das passt.
| Zitat: |
Original von Annamaria
zu b)
Ich soll einfach verschiede Wahrscheinlichkeitsverteilungen ausprobieren, aber welche?
Grundproblem: Was ist mit der Wahrscheinlichkeitsverteilung gemeint und wie wird sie berechnet?
|
Mit Wahrscheinlichkeitsverteilung ist hier sicher gemeint, mit welchen Wahrscheinlichkeiten die Elemente im Suchbaum gesucht werden. Z.B. .
Meiner Meinung nach ist es sinnvoll sich erstmal die 5 Bäume aufzumalen und dann zu schauen, welche Wahrscheinlichkeitsverteilung hier günstig wäre.
VG,
Karlito |
Es ist aber nicht möglich 5 Suchbäume aus 3 Elementen zu bauen. Also ich kann nur drei bauen.
|
|
|
01.12.2012 20:15 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Ja, das mit den 5 hat mich auch irritiert, Dann mach es eben für die 3. Wenn ich noch drauf komme, wie 5 zustande kommen könnten, sag ich bescheid. Eine Idee ist: was ist mit Heaps?
VG,
Karlito
|
|
|
01.12.2012 21:48 |
|
|
|
