Erwartete Laufzeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:31 Mi 28.05.2008 | | Autor: | LL0rd |
| Aufgabe | | Geben Sie die erwartete Laufzeit Ihres Algorithmus an. |
Hallo,
ich habe gerade ein kleines Problem, die Laufzeit eines Algorithmus zu bestimmen. Da ich weiß, dass hier auch andere Studenten meiner Hochschule mitlesen und ich eh nicht möchte, dass andere für mich meine Hausaufgaben machen, gebe ich hier absichtlich einen ähnlichen aber nicht den richtigen Algorithmus an.
while(zahl1!=5)
zahl1= neueZufallszahl();
Das ist auch schon alles. Aber wie errechne ich die erwartete Laufzeit? Ich weiß ja nicht genau, wann ein zufälliges Ereignis eintritt.
Im Best Case habe ich die 5 schon in dem ersten Schleifendurchlauf. Dann hätte ich eine Best Case Laufzeit von O(1), im Worst Case habe ich jedoch nie eine 5 und eine Laufzeit von [mm] O(\infty). [/mm] Deshalb verstehe ich nicht, wie man auf die Lösung kommt. Bitte deshalb um einen Tipp. Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:22 Mi 28.05.2008 | | Autor: | Gilga |
Mir scheint die Aufgabe etwas seltsam. Hast du villeicht zu viel verändert?
Das entscheidende ist welche Art von werten neueZufallszahl() mit welcher verteilung zurückgibt.
z.B. Integer mit n Bits gleichverteilt.
Wird nur 5 oder eine beliebige aber feste Zahl zurückgegeben gilt: 1/2 * 1 + 1/4*2 + 1/8*3 .....
5 x5 xx5 ....
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:44 Mi 28.05.2008 | | Autor: | LL0rd |
Naja, zu viel habe ich nicht wirklich verändert. Wenn du die ganze Aufgabe sehen möchtest, unter diesem Link habe ich die im Internet wiedergefunden.
http://www.informatikforum.de/showthread.php?p=98300#post98300
Es geht da um die Aufgabe 1. Aus diesem Grund möchte ich meinen Lösungsansatz hier auch nicht wirklich veröffentlichen, da ich den Poster auch in diesem Board einige Male gesehen habe.
Aber nun mal zurück zum ursprünglichen Problem meines ersten Postings. Denn am eigentlichen Problem - Laufzeit berechnen mit einer While Schleife und einer Zufallszahl - wird sich nicht wirklich was ändern.
In meinem Beispiel habe ich statt einem Münzwurf eine Zahl genommen. Trivialerweise sind es Integer Zahlen, die generiert werden. Aber der Zufallsgenerator ist nicht "fair". Deshalb auch mein Problem.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:39 Do 29.05.2008 | | Autor: | Gilga |
Meinst du diese Aufgabe? Wenn ja dann ist da schon ein unterschied!
Laufzeit hängt ja von der gewünschten Genauigkeit ab.
Mit der einfachen while Schleife kommst du auch nicht weiter.
Wirf n unfaire Münzen => p schätzen => faire Münze simulieren
Habe einige Augaben gekriegt, weiß nicht wie ich es lösen soll...
1. Angenommen Sie sind im Besitz einer Munze, die mit einer bestimmten, Ihnen unbe-kannten, Wahrscheinlichkeit p auf Kopf landet.
a) Geben Sie einen Algorithmus in Pseudocode an, der mit Hilfe der (unter Umstanden) unfairen Munze eine faire Munze1 simuliert. (5T)
b) Geben Sie die erwartete Laufzeit Ihres Algorithmus an. (3T)
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 18:52 Fr 30.05.2008 | | Autor: | LL0rd |
Diese Lösung habe ich auch von vielen aus der Uni gehört. Ich halte sie jedoch für nicht ganz richtig. Da das Blatt bis heute 13 Uhr hätte abgegeben werden müssen, kann ich hier meinen Ansatz verraten. Ich habe es eher nach der Mathematischen Methode gemacht und nicht nach der Brute Force. Wir können gerne darüber diskutieren.
Meine Annahmen sind folgende:
Kopf tritt mit einer Wahrscheinlichkeit von p auf, q mit der Gegenwahrscheinlichkeit 1-p. Alle Würfe sind voneinander unabhängig. Um zu entscheiden, ob es nun Kopf oder Zahl ist, brauche ich zwei Ereignisse, die mit der gleichen Wahrscheinlichkeit auftreten.
Da ich p nicht kenne, kann ich es auch nicht ausrechnen. Und p zu messen ist etwas umständlich. Deshalb mein Ansatz: Ich würfle zwei Mal. Dabei können sich folgende Kombinationen mit Wahrscheinlichkeiten ergeben:
KK = p*p
ZZ = q*q
KZ = p*q
ZK = q*p
jetzt sieht man, dass ZK und KZ mit der gleichen Wahrscheinlichkeit auftreten. Um aus der unfairen Münze nun eine Faire zu machen, muss man einfach nur zwei Mal werfen. Ist der erste Wurf != dem zweiten, so hat man ein gültiges Ergebnis.
Und genau das habe ich in einer While Schleife auch gemacht.
while(w1=w2)
w1=neuerWurf();
w2=neuerWurf();
endwhile
Doch nun ist die Frage, wie man auf die Laufzeit des ganzen kommt. Mein Ansatz, mit dem ich die Aufgaben auch abgegeben habe, war folgender. Ich errechne mir die erwartete Laufzeit. Denn wenn p!=0 und p!=1 ist, wird der Algorithmus irgendwann terminieren. Die Wahrscheinlichkeit fürs Terminieren eines des Ereignisses P(KZ) = p*q = p * (1-p) = [mm] p-p^2
[/mm]
Für beide Ereignisse habe ich dann P(KZ [mm] \cup [/mm] ZK) = [mm] 2(p-p^2). [/mm] Da ich nun erwarte, dass das Ereignis eintritt, muss ich die Anzahl der Durchläufe n ausrechnen, damit ich die Wahrscheinlichkeit 1 rausbekomme.
[mm] \Rightarrow [/mm] 1 = [mm] 2n(p-p^2)
[/mm]
[mm] \gdw [/mm] n = 1 / [mm] 2p-2p^2
[/mm]
Die Laufzeit ist deshalb linear von der Wahrscheinlichkeit p abhängig und damit O(n)
Das ist so meine Lösung, wie ich diese nun auch abgegeben habe. Seht ihr das genauso? Oder habe ich irgendwo an einer Stelle falsch gedacht?
|
|
|
| |
|
Hallo,
der Ansatz mit den zwei unterschiedlichen unfairen Würfen, die in einen fairen umgewandelt werden, ist mir auch in den Sinn gekommen, als ich deinen Post las. Er hat allerdings einige Macken:
Da du immer die Wechsel KZ und ZK betrachtest, ist die Reihenfolge der daraus gewonnenen fairen Würfe bereits festgelegt, denn auf einen KZ-Wechsel folgt nie ein zweiter KZ-Wechsel, analog für ZK. Also würde dein fairer Würfel immer (Z)KZKZKZKZKZKZKZK... ergeben. Für Simulationen wäre das aber ziemlich unbrauchbar.
Was den Algorithmus angeht: Er muss auf jeden Fall nach endlich vielen Schritten terminieren. Da wir es aber mit Wahrscheinlichkeiten [mm] $\neq [/mm] 0$ und [mm] $\neq [/mm] 1$ zu tun haben, kommen wir NIE auf einen bestimmten sicheren Wurf. Das ist so, als würdest du bei sechs Würfen mit einem Spielwürfel immer eine Sechs dabeihaben. Also passt etwas an deiner mathematischen Betrachtung nicht.
Die Wahrscheinlichkeit, dass ich mit zwei Würfen ein KZ oder ein ZK werfe, ist $P(2) = pq + qp = 2pq$.
Die Wahrscheinlichkeit, dass ich mit spätestens beim dritten Wurf eine solche Kombination werfe, ist $P(3) = (pq + ppq) + (qp + qqp) = 4pq$.
Mit vier Würfen: $P(4) = (pq + ppq + pppq) + (qp + qqp + qqqp) $.
Und mt $n$ Würfen: $P(n) = [mm] q\sum_{i=1}^{n-1}p^i [/mm] + [mm] p\sum_{i=1}^{n-1}q^i$.
[/mm]
Mit $q=1-p$ und einigen Umformungen, kommst du über deine "sichere" Bedingung $1 = [mm] \dots$ [/mm] auf: [mm] $p^n [/mm] = [mm] -\left(1-p\right)^n$. [/mm] Und hier geht es nicht weiter...
Ich kann mir keinen Algorithmus vorstellen, der genau ist (sonst s. Gilgas Antwort) und terminiert (sonst ist es auch kein Algorithmus). Man kann höchstens heuristisch sagen, dass dieses Verfahren mit der-und-der Wahrscheinlichkeit ein Ergebnis liefert. Daher fällt mir auch nix Besseres ein...
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:12 Sa 31.05.2008 | | Autor: | Gilga |
Ich finde deine Idee mit ZK und KZ sehr gut!
Sei i das Ergeignis dass erstmals beim i-ten Würfeln ZK oder KZ kommt
Die erwartete Laufzeit ist
1*P(1)+2*p(2)+3*P(3)+......
mit P(i) = (1-2pq)^(i-1)*2pq
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Sa 07.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
