Frage zu optimalen Suchbäumen |
| 01.12.2012, 13:34 | Auf diesen Beitrag antworten » | ||||||
| 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? _________________ |
||||||
|
|
|||||||
| 01.12.2012, 16:57 | Auf diesen Beitrag antworten » | ||||||
| Karlito | RE: Frage zu optimalen Suchbäumen
Ich denke das passt.
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 |
||||||
| 01.12.2012, 20:15 | Auf diesen Beitrag antworten » | ||||||
| Annamaria | RE: Frage zu optimalen Suchbäumen
Es ist aber nicht möglich 5 Suchbäume aus 3 Elementen zu bauen. Also ich kann nur drei bauen. |
||||||
| 01.12.2012, 21:48 | Auf diesen Beitrag antworten » | ||||||
| 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 |
||||||
| Anzeige | |||||||
|
|
|||||||
|
|