Erwartungswerte < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:12 Fr 27.11.2009 | | Autor: | virgo |
| Aufgabe 1 | a) Bestimmen Sie das Minimum und das Maximum der möglichen Erwartungswerte der Suchzeit X der Binären Suche in einer Liste von sieben Elementen w1<w2<w3<w4<w5<w6<w7, wobei nur Elemente aus der Liste angefordert werden und Sie wissen, dass in der Liste 2 Elemente mit Wahrscheinlichkeiten 0.05, 2 mit 0.1 und 2 mit 0.15 angefordert werden, aber nicht wissen, welche dies sind.
|
| Aufgabe 2 |
b) Lösen Sie das analoge Problem für die lineare Suche in sieben Elemente und vergleichen Sie die beiden Ergebnisse. |
Wie kann ich das lösen? Welche Werte soll X annehmen?? die Anzahl der Vergleiche, die bei der Suche entstehen??? Was wir mit Minimum und Maximum gemeint???
Keine Ahnung wie ich anfangen kann. Kann mir jemand bitte helfen???
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
da ich zur binären Suche nichts weiter sagen kann, beschränke ich mich auf die lineare Suche.
Die Werte stehen nacheinander in so einer Liste. Nun ist das so gemeint, dass einige dieser Werte sehr selten angefragt werden, andere dagegen häufiger. Sucht man linear, dann fängt man vorn in der Liste an und schaut, ob man den richtigen Wert schon gefunden hat. Steht ein Wert, den man sehr häufig sucht, weit vorn in der Liste, sind auch nicht so viele Suchanfragen nötig. Wären also in deiner Aufgabe die Werte nach ihrer Häufigkeit der Suchanfrage sortiert mit dem häufigsten zuerst, dann erhältst du den minimalen Erwartungswert. In deinem Fall kommt minimal
0.4*1+0.15*2+0.15*3+0.1*4+0.1*5+0.05*6+0.05*7=2.7
heraus. Das Maximum berechnest du analog, nur dass die Liste andersherum sortiert ist.
Jetzt ist halt noch die Frage, wie das binäre Suchen funktioniert und was dort der schlechteste Fall und was der beste Fall ist. (Also wie müssen die Werte in der Liste liegen, damit entweder der beste Fall oder der schlechteste Fall vorliegt.)
Viel Erfolg,
Roland.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:13 So 29.11.2009 | | Autor: | virgo |
Hallo Roland,
vielen Dank für Deine Antwort.
Bei der binäre Suche wird zuerst das mittlere element überprüft [(links+rechts)/2=mitte] hier wäre dann w4, ist dieses element aber nicht das gesuchte und ist das gesuchte kleiner als dieses Element, überprüft man die linke Hälfte der Liste (links, mitte-1) dann wäre hier w2. Ist das gesucht aber größer dann überprüft man die rechte Hälfte der Liste (mitte+1, rechts), und man geht so vor bis das gesuchte gefunden wird.
Wie müssen die Werte in der Liste liegen, damit entweder der beste Fall (minimum) oder der schlechteste (maximum) Fall vorliegt?
Meine Antwort:
0,05| 0,15 | 0,1 | 0,4 | 0,05 | 0,15| 0,1 (für beste Fall)
E(x)min= 0,05*1 + 0,15*2 + 0,1*3 + 0,4*4 + 0,05*5 + 0,15*6 + 0,1*7
0,15| 0,05 | 0,1 | 0,05 | 0,15 | 0,1 | 0,4 (für schlechteste Fall)
E(X)maxi= 0,15*1 + 0,05*2 + 0,1*3 + 0,05*4 + 0,15*5 + 0,1*6 + 0,4*7
Würdest du das auch so lösen????
|
|
|
| |
|
Hallo,
deine Listen für den günstigsten und ungünstigsten Fall sind schon mal richtig, bzw. würde ich auch so lösen. Doch bei den Erwartungswerten nimmt man nicht die Position in der Liste, sondern die Anzahl der Suchanfragen. Bei der binären Suche hat man in deinem Fall somit maximal 3 (in Worten: drei!) Suchanfragen. Der Erwartungswert wird also auf jeden Fall kleiner sein, als bei der linearen Suche.
Um es nochmal deutlich zu machen: Gezählt wird hier die Anzahl der Zugriffe auf deine Liste.
Beim schlechtesten Fall der binären Suche hast du nun das Problem (was du sicher selbst lösen kannst!), dass beispielsweise für die Suchanzahl 2 zwei verschiedene Wahrscheinlichkeiten angegeben sind. Überlege mal, was das bedeutet und wie man dann rechnen muss.
Ein Ergebnis kann ich dir schon mal vornweg geben: [mm] E_{min}=0.4*1+0.15*2+0.1*3+0.05*4=1.2
[/mm]
Im Vergleich zur 2.7 bei der linearen Suche ist das schon wesentlich besser - "teile und herrsche" - war schon immer gut! 
Viel Erfolg noch,
Roland.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:59 Di 01.12.2009 | | Autor: | virgo |
Vielen Dank Roland!!! Deine Hilfe hat mir viel geholfen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:30 Mi 02.12.2009 | | Autor: | PeterH |
> Ein Ergebnis kann ich dir schon mal vornweg geben:
> [mm]E_{min}=0.4*1+0.15*2+0.1*3+0.05*4=1.2[/mm]
Da es bei de Binärsuche mit 7 Elementen maximal 3 Suchvorgänge gibt, sollten beim Erwartungswert doch nur 3 Werte stehen und nicht wie bei dir 4 oder?
|
|
|
| |
|
Hallo,
danke für die Korrektur. Es sind tatsächlich nur 3 Feldabfragen.
Der Erwartungswert ist also noch niedriger.
[mm] E_{min}=0.4*1+0.15*2+0.15*3=1.15
[/mm]
Mit freundlichem Gruß,
Roland.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:01 Do 03.12.2009 | | Autor: | Mephis |
Hallo,
darf ich fragen warum $ [mm] 0.15\cdot{}3 [/mm] $?
Bis $ [mm] 0.4\cdot{}1+0.15\cdot{}2 [/mm] $ ist klar.
Danke im Vorraus
Mephisto
|
|
|
| |
|
Hallo,
gefragt werden darf immer...
Wenn Elemente der Liste gesucht werden, die zu 5% gesucht werden, dann braucht man 3 Suchschritte, bzw. drei Listenzugriffe. Für die die mit 10%iger Wahrscheinlichkeit einen Zugriff haben, sind es auch 3 Zugriffe.
Man könnte den Erwartungswert also auch ausführlich schreiben:
E=0.4*1+0.15*2+0.1*3+0.05*3
Klammert man die 3 aus, so kommt man auf 0.1+0.05=0.15.
Netten Abend noch,
Roland.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:28 Do 03.12.2009 | | Autor: | Mephis |
Ahh, klar.
Danke und ebenso einen schönen Abend
|
|
|
|
