Autor |
Beitrag |
Grasmo (Grasmo)
| Veröffentlicht am Freitag, den 28. Dezember, 2001 - 13:55: |
|
Grueße! Ich habe hier mit folgender Aufgabe zu kaempfen und waere schon ueber grundlegende Tips dankbar (habe leider keine bekommen): Sei X die Laufzeit eines randomisierten Algorithmus, der mit W'keit p nach k1 Schritten und mit der W'keit q = (1 - p) nach k2 Schritten terminiert (k1 < k2). Ein Anwender ueberlegft sich, den Algorithmus bei nicht erfolgter Ausgabe nach jeweils k1 Schritten unabhaengig neu zu starten. Unter welchen Umstaenden ist dieses Verfahren das bessere? (Verwenden Sie als Maß fuer die Guete eines randomisierten Algorithmus seine Laufzeit). |
|