---

Geschrieben von Annamaria am 01.12.2012 um 13:34:

  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?
_________________

---

Geschrieben von Karlito am 01.12.2012 um 16:57:

  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. .

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

---

Geschrieben von Annamaria am 01.12.2012 um 20:15:

  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.

---

Geschrieben von Karlito am 01.12.2012 um 21:48:

 

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