Das Problem
Zur Orientierung
Algorithmen werden entwickelt, um Probleme automatisiert zu lösen. Dabei spielt der Aufwand zum Lösen des Problems eine wichtige Rolle. Bevorzugt werden Algorithmen, die schnell (d.h. mit wenig Aufwand) zur Lösung gelangen. Wenn mehrere Algorithmen zum Lösen eines Problems zur Wahl stehen, dann führt man Wachstumsvergleiche mit den zugehörigen Aufwandsfunktionen durch. Wachstumsvergleiche sind also ein gängiges Verfahren bei der Entwicklung von Algorithmen. In diesem Abschnitt verdeutlichen wir die Vewendung von Wachstumsvergleichen anhand einer einfachen Problemstellung.
Das Problem Zahlenraten
Vorab wird vereinbart, wie viele Stellen ein zu ratende Zahl haben darf. Du denkst dir eine Zahl (mit der vorgegebenen Stellenanzahl) aus und notierst sie auf einen Zettel. Aufgabe des Algorithmus ist es, diese Zahl herauszufinden. Der Algorithmus darf dabei Ja-Nein-Fragen stellen, die du natürlich wahrheitsgemäß beantwortest.
Aufgabe 1
Probiere das Zahlenraten zunächst selbst aus. Eine Person denkt sich eine Zahl mit $2$ Stellen (z.B. die Zahl 13) aus. Die andere Person versucht, diese Zahl mit Ja-Nein-Fragen herauszufinden.
Aufgabe 2
Eine Person denkt sich eine Zahl mit $10$ Stellen (z.B. die Zahl 6421683224) aus. Schätze, mit wie vielen Ja-Nein-Fragen ein guter Algorithmus die Zahl herausfinden kann.
