| Autor |
Beitrag |
    
anke
| | Veröffentlicht am Montag, den 07. Januar, 2002 - 12:00: | 
|
Aloah an Alle.
Ich verzweifle.
Sei X die Laufzeit eines randomisierten Algorithmus, der mit Wahrscheinlichkeit p nach k1 Schritten und mit Wahrscheinlichkeit 1-p nach k2 Schritten terminiert (k1 < k2). Ein Anwender überlegt sich, den Algorithmus bei nicht erfolgter Ausgabe nach jeweils k1 Schritten unabhängig neu zu starten. Unter welchen Umständen ist dieses Verfahren das bessere? (Verwenden Sie als Maß für die Güte eines randomisierten Algorithmus seine erwartete Laufzeit.)
Danke.
Anke |
Dr. Geiger
| | Veröffentlicht am Dienstag, den 08. Januar, 2002 - 21:06: |
|
Das hat jemand schon am 28.12. gefragt. Scheint unlösbar zu sein ;) |
Grasmo (Grasmo)
| | Veröffentlicht am Mittwoch, den 09. Januar, 2002 - 01:49: |
|
na mal sehen, ob jemanden die Loesung noch hilft....
da ich schon muede bin, ist hier die knappe Loesung:
Es macht Sinn, wenn (1/p)*k1 < k2!!!
als Hinweis duerfte der Erwartungswert einer geometrischen Reihe reichen
jetzt mal noch eine Frage:
wer sind denn die ganzen weibl. Personen, in der Vorlesung sind irgendwie nicht mehr so viele.... |
|
