Übungsaufgabe Wahrscheinlichkeit

[Klaus S. (klaus888)]

8. Klasse Denkaufgabe am Abend

Bei der Suche nach der Bestätigungszahl für einen Bitcoin-Block müssen 
Hashwerte berech-net werden, die eine bestimmte Anzahlnan Nullbits am 
Anfang des Hashwerts aufweisen.Die Hashwerte selbst sind 160 Bit lang.
a) Wie groß ist die Wahrscheinlichkeit, dass der Hashwert für die erste 
BestätigungszahlbereitsnNullbits am Anfang aufweist?

Ich sage, es müssen 2^(n+1) Möglichkeiten betrachtet werden, da ja das 
n+1 Bit eins sein muss. Also wäre die Wahrscheinlichkeit 1/2^(n+1)

[Klaus S. (klaus888)]

b) Wie viele Bestätigungszahlen muss man ausprobieren, damit ein 
Hash-Wert mit n=32Nullbits am Anfang mit einer Wahrscheinlichkeit von 
50% gefunden ist? Wieviele Versuche braucht man für n=33?

Meine Antwort: Gleichung nach x Auflösen 0.5= x * 1/2^(32+1)
Lösung lässt sich sofort ablesen: 2^32

Anzahl der Versuche: 0.5= x * 1/2^(33+1) <=> x = 2^33

[Klaus S. (klaus888)]

c) Wie groß ist der Rechenaufwand (in der O-Notation), um einen 
Hash-Wert mit n Nullbits am Anfang zu finden?

[A. S. (rava)]

a)
Ja, wenn du die Frage richtig verstanden hast. Das nennen wir p(n).


b)
Wahrscheinlichkeit eines Fehlversuches: 1-p(n)
Wahrscheinlich von N Fehlversuchen (1-p(n))^N. Das soll kleiner 50% 
sein. Dann nach N auflösen


c)
Rechenaufwand ~ N
das Ganze als Funktion von n aufschreiben und in O(n)-Notation 
überführen



8. Klasse halte ich für ein Gerücht. Bei mir war das damals 11.

[Max M. (jens2001)]

Edit:
Selbst gemerkt. War Quatsch

[Klaus S. (klaus888)]

A. S. schrieb:
> Wahrscheinlichkeit eines Fehlversuches: 1-p(n)
> Wahrscheinlich von N Fehlversuchen (1-p(n))^N. Das soll kleiner 50%
> sein. Dann nach N auflösen

du meinst also: N = log 1-1/2^33 (0,5) = 5954105403?

A. S. schrieb:
> c)
> Rechenaufwand ~ N
> das Ganze als Funktion von n aufschreiben und in O(n)-Notation
> überführen

wie sähe das aus?

[Klaus S. (klaus888)]

Warum sollte man über die Fehlversuche gehen? Warum kommt bei meinem 
Ansatz eine andere Zahl heruas?

[A. S. (Gast)]

Klaus S. schrieb:
> Ich sage, es müssen 2^(n+1) Möglichkeiten betrachtet werden, da ja das
> n+1 Bit eins sein muss.

Deine Formulierung suggeriert was anderes. Das kann man aber nicht durch 
diskutieren klären.

[A. S. (rava)]

Klaus S. schrieb:
> Warum sollte man über die Fehlversuche gehen? Warum kommt bei meinem
> Ansatz eine andere Zahl heruas?

du willst in der Regel nicht wissen, ob du in N Versuchen genau 1 Hash 
findest, 2 Hashs wären auch okay, oder drei, oder vier, oder?

Klaus S. schrieb:
> wie sähe das aus?


keine Ahnung, definitiv keine Achtklässlermathematik.
Am Ende wird aber wohl rauskommen, dass das exponentielle Komplexität 
hat.