Analyse der Algorithmen

Den Aufwand des Algorithmus Zahlenraten – Version 1 beschreiben

Hier noch einmal das Applet zum Algorithmus Zahlenraten – Version 1:

Zum Herunterladen: zahlenraten_linear.ggb

Der Algorithmus Zahlenraten – Version 1 geht der Reihe nach alle Zahlen durch, bis die Zahl gefunden ist.

Aufgabe 1

(a) Vorgegeben ist die Stellenanzahl $n = 2$. Welche Ratezahl sollte man wählen, damit der Algorithmus möglichst viele Ja-Nein-Fragen stellen muss? Das ist dann der sogenannte worst case für den Algorithmus. Wie viele Ja-Nein-Fragen sind im worst case erforderlich?

(b) Die Anzahl der Ja-Nein-Fragen im worst case wird mit einer Funktion $f_1$ erfasst. Die Funktion $f_1$ ordnet dabei der Stellenzahl $n$ die Anzahl der Ja-Nein-Fragen im worst case beim Algorithmus Zahlenraten – Version 1 zu. Ergänze die Funktionsgleichung der Funktion $f_1$.

$f_1(n) = \dots$

Zur Kontrolle

$f_1(n) = 10^n$.

Den Aufwand des Algorithmus Zahlenraten – Version 2 beschreiben

Hier noch einmal das Applet zum Algorithmus Zahlenraten – Version 2:

Zum Herunterladen: zahlenraten_binaer.ggb

Die Anzahl der Ja-Nein-Fragen im worst case wird mit einer Funktion $f_2$ erfasst. Die Funktion $f_2$ ordnet dabei der Stellenzahl $n$ die Anzahl der Ja-Nein-Fragen im worst case beim Algorithmus Zahlenraten – Version 2 zu. Um Aussagen über die Funktionsgleichung der Funktion $f_2$ zu gewinnen, muss man erst einmal eine Reihe von Vorüberlegungen anstellen.

Der Algorithmus Zahlenraten – Version 2 halbiert (in etwa) mit jeder Ja-Nein-Frage den Bereich, in dem die Ratezahl liegt. Wenn man die Ratezahl $z = 43$ zur Stellenzahl $n = 2$ gewählt hat, dann geht der Algorithmus so vor:

Liegt die Zahl zwischen 0 und 49?
[Ja] Jetzt weiß man, dass z im Bereich 0..49 liegt.
Liegt die Zahl zwischen 0 und 24?
[Nein] Jetzt weiß man, dass z im Bereich 25..49 liegt.
Liegt die Zahl zwischen 25 und 37?
[Nein] Jetzt weiß man, dass z im Bereich 38..49 liegt.
Liegt die Zahl zwischen 38 und 43?
[Ja] Jetzt weiß man, dass z im Bereich 38..43 liegt.
Liegt die Zahl zwischen 38 und 40?
[Ja] Jetzt weiß man, dass z im Bereich 38..40 liegt.
Liegt die Zahl zwischen 38 und 39?
[Ja] Jetzt weiß man, dass z im Bereich 38..39 liegt.
Liegt die Zahl zwischen 38 und 38?
[Ja] Jetzt weiß man, dass z im Bereich 38..38 liegt.

Der vorgegebene Zahlenbereich umfasst zunächst die $100$ Zahlen $0..99$. Wenn man diesen Zahlenbereich wiederholt (in etwa) halbiert, ergibt sich diese Folge von Längen der ereichten Zahlenbereiche.

100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1

Jeder Pfeil entspricht dabei einer Ja-Nein-Frage. Man benötigt also maximal $f_2(2) = 7$ Ja-Nein-Fragen, um zu einem Zahlenbereich mit nur einer Zahl zu gelangen.

Beachte: Wenn man einen Bereich der Länge $25$ halbiert, entsteht ein Bereich der Länge $13$ und ein Bereich der Länge $12$. In der oben gezeigten Halbierungskette ist immer der längere Bereich als worst case angegeben.

Aufgabe 2

(a) Zeige, dass man bei für die Stellenzahl $n = 3$ mit maximal $f_2(3) = 10$ Halbierungen zur Bereichslänge $1$ gelangt.

1000 -> 500 ->

(b) Die maximale Anzahl der Halbierungen bei einer vorgegebenen Bereichslänge $10^2 = 100$ lässt sich mit folgender Gleichung bestimmen:

$10^2 = 2^x$ bzw. $e^{\ln(10) \cdot 2} = e^{\ln(2) \cdot x}$

Zeige, dass $x = \frac{\ln(10)}{\ln(2)} \cdot 2 \approx 3.32 \cdot 2 = 6.64$ diese Gleichung löst.

Die maximale Anzahl der Halbierungen bei einer Bereichslänge $10^2$ erhält man dann, wenn man $x = \frac{\ln(10)}{\ln(2)} \cdot 2$ aufrundet. Man erhält so folgende Abschätzung: $f_2(2) \approx \frac{\ln(10)}{\ln(2)} \cdot 2 \approx 3.32 \cdot 2$.

(c) Bestimme die maximale Anzahl der Halbierungen bei einer vorgegebenen Bereichslänge $10^3 = 1000$. Gehe analog zum Aufgabenteil (b) vor. Zeige, dass man für $n = 3$ so folgende Abschätzung erhält: $f_2(3) \approx 3.32 \cdot 3$.

(d) Erkläre, wie man durch eine Verallgemeinere der Ergebnisse aus (b) und (c) zu der folgenden groben Abschätzung kommt:

$f_2(n) \approx 3.32 \cdot n$

Einen Aufwansvergleich durchführen

Der Worst-Case-Aufwand der beiden Algorithmen zum Zahlenraten lässt sich mit folgenden Aufwandsfunktionen abschätzen:

• Algorithmus Zahlenraten – Version 1: $f_1(n) = 10^n$
• Algorithmus Zahlenraten – Version 2: $f_2(n) \approx 3.32 \cdot n$

Aufgabe 3

(a) Welche Aufwandsfunktion gewinnt (langfristig) das Wachstumswettrennen? Welche Relevanz hat das für die Verwendung der beiden Algorithmen?

(b) Du hast dir eine PIN mit 10 Stellen ausgedacht. Die beiden Algorithmen zum Zahlenraten wollen diese PIN mit Ja-Nein-Fragen herausfinden. Die Beantwortung einer Frage dauert in etwa $1$ Sekunde. Schätze ab, wie lang es im worst case dauert, bis der benutzte Algorithmus die PIN gefunden hat.

Zur Kontrolle

Es gilt $f_1(10) = 10^{10} = 10000000000$. Der Algorithmus benötigt also $10000000000$ Sekunden. Das sind etwa $317$ Jahre.

Es gilt $f_2(10) \approx 3.32 \cdot 10 = 33.2$. Der Algorithmus benötigt etwas mehr als eine halbe Minute.