Wahrscheinlichkeit Termination nach k Schritten Algorithmus x beliebige Zahl aus 2^n -1

Neue Frage »

Krähe Auf diesen Beitrag antworten »
Wahrscheinlichkeit Termination nach k Schritten Algorithmus x beliebige Zahl aus 2^n -1
Meine Frage:
Guten Abend,

ich habe hier eine Aufgabe, zu der ich im Moment keinen Ansatzpunkt finde:

Im Speicher eines Computers sind verschiedene Zahlen a1, ...,
in aufsteigender Reihenfolge gespeichert. Für eine Zahl x soll überprüft werden, ob x Element A := {a_1, ..., } gilt. Dazu wird x zuerst mit der in der Mitte liegenden Zahl verglichen. Hierbei können die folgenden Fälle eintreten:
a) . In diesem Fall wird eine positive Antwort gegeben.
b) x ungleich ) und n = 1. In diesem Fall wird eine negative Antwort gegeben.
c) x < und n ungleich 1. In diesem Fall wird die Suchprozedur auf die Menge
{a1, ..., )} angewandt.
d) x > und n ungleich 1. In diesem Fall wird die Suchprozedur auf die Menge
{ ), ..., } angewandt.
Der Algorithmus terminiert nach maximal n Schritten.
Nun werde f¨ur x ein zuf¨allig ausgew¨ahltes Element aus A genommen (wobei eine
Gleichverteilung auf A vorausgesetzt wird). Bestimmen Sie die Wahrscheinlichkeit,
dass der Algorithmus nach genau k Schritten terminiert.

Meine Ideen:
Ich habe schon in die VL geschaut und gegoogelt, aber mir fehlt eine grobe Einordnung oder ein Begriff wie z.b. deterministisch um mir das Thema nochmal durchzulesen, sonst weiss ich nicht, wo ich anfangen soll.

schon mal vielen Dank für die Hilfen
HAL 9000 Auf diesen Beitrag antworten »

Wenn ich mir deine Beschreibung des Algorithmus so anschaue, erkenne ich eine Menge Unsauberkeiten und z.T. falsche Indizes. Ich korrigiere mal:

Zitat:
a) . In diesem Fall wird eine positive Antwort gegeben.

b) und . In diesem Fall wird eine negative Antwort gegeben.

c) und . In diesem Fall wird die Suchprozedur auf die Menge angewandt.

d) und . In diesem Fall wird die Suchprozedur auf die Menge angewandt.

Der Algorithmus terminiert nach genau Schritten, wenn der zu gehörende Index genau -mal den Primfaktor 2 enthält. Unter den Indizes trifft das auf genau Zahlen zu, die Wahrscheinlichkeit ist gemäß der ja gleichverteilt angenommenen Zufallsauswahl von aus dann demnach für .


Ich mach das mal am Beispiel mit deutlich, was je nach Zufallswahl von passiert:

wird im ersten Schritt gefunden,

werden im zweiten Schritt gefunden,

werden im dritten Schritt gefunden,

werden im vierten Schritt gefunden und

werden im fünften und letzten Schritt gefunden.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »