Die letzten 4 Beiträge |
Karlito |
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 |
Annamaria |
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. |
Karlito |
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 |
Annamaria |
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?
_________________ |
|
|