\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

Erinnern Sie sich noch an das hier?

Ein Telefonbuch. Bildquelle: Wikimedia Commons

Vielleicht sind Sie ja dafür tatsächlich zu jung. Es ist ein Telefonbuch. Wenn man eine Telefonnummer herausfinden will, zum Beispiel vom Kfz-Mechaniker Windisch aus Freudenberg, dann schaut man im Telefonbuch unter "W" nach und blättert. Und heute? Da benutzt man immer noch ein Telefonbuch. Dies ist dann aber elektronisch, und das Blättern tun auch nicht Sie, sondern ein Rechner (oder viele). Sie können zum Beispiel Das Telefonbuch verwenden oder eine Suchmaschine Ihrer Wahl.

Und ob Sie eine Telefonnummer suchen oder etwas ganz Anderes, ein Großteil von dem, was Rechner erledigen müssen, beinhaltet, irgendwo Inhalte aus einer riesigen Datenmenge rauszufischen. Grund genug, diesem Thema ein paar Vorlesungsstunden zu widmen.

Um konkret zu werden: in der Datei englishVocabulary.txt finden Sie eine Liste von über 50.000 englischen Wörtern. Schauen Sie nach. Fällt Ihnen etwas auf? Die Wörter sind alphabetisch sortiert. Das sollte uns bei der Suche helfen. Spielen Sie das folgende Spiel, in dem Sie auf den Screenshot klicken:

Demo (binäre Suche)

Klicken Sie auf den Screenshot und spielen das Spiel.

Können Sie das gesuchte Wort mit höchstens sieben Klicks finden? Wahrscheinlich haben Sie rausgefunden, dass Sie als erstes irgendwo in der Mitte klicken sollten. Falls das dortige Wort "zu groß" ist, suchen Sie in der ersten Hälfte weiter; falls es zu klein ist, suchen Sie in der zweiten Hälfte weiter.

Average Case und Worst Case

Wie geht man optimal vor? Was ist eine optimale Strategie zum Suchen in Telefonbüchern oder, ganz allgemein, in sortierten Daten? In meinem obigen Spiel werden $n$ Wörter nach einem bestimmten System zufällig aus einer Datenbank von vielen englischen Wörtern ausgewählt. Wenn Sie wissen, nach welchem System, dann könnten Sie ihre Strategie daran anpassen. In diesem Kurs sind wir aber an Strategien interessiert, die immer gut funktionieren und nicht nur meistens. Also, als würden Sie nicht gegen eine zufällig ausgewählte Wortmenge spielen, sondern gegen eine gegnerisch gewählte. Wir stellen uns also vor, ein Gegner würde eine besonders boshaftige Menge von $n$ Wörtern wählen (aber immer noch sortiert). Wir stellen uns die Suche nach einer optimalen Strategie also vor als Spiel zwischen zwei Spielern: dem Sucher, der eine Suchstrategie ersinnt, und dem Gegner, der die Wörtermenge auswählt. Die Regeln sind so:

  1. Der Sucher legt eine Strategie fest (z.B. klicke auf $50$; falls dieses Wort zu weit hinten im Alphabet steht, klicke auf $25$ und so weiter).
  2. Der Gegner kennt nun die Strategie des Spielers und darf jetzt Menge von $n$ Wörtern wählen (inklusive Phantasiewörtern wie Ptyawedbasdfkjl) und diese auf $n$ Kärtchen schreiben. Dann verkündet er das gesuchte Wort. Es
  3. Jetzt beginnt das Spiel. Da beide Spieler ihre Strategie bereits festgelegt haben, steht das Ergebnis und somit auch die Anzahl der Klicks fest.

Demo. Spielen wir dieses Spiel. Ein Freiwilliger möge nach vorne kommen. Ich wähle sieben Wörter und schreibe sie so, dass alle im Publikum sie sehen können. Der Freiwillige steht mit dem Rücken zur Leinwand und kann die Wörter nicht sehen. Hier ist eine Beispieldatei:

german-words-7.txt

Dann drehen wir den Spieß um. Eine Freiwillige kommt nach vorne und schreibt sieben Wörter, so dass alle sie sehen können.

Übungsaufgabe Zeigen Sie: Bei sieben Wörtern kann man es immer mit höchstens drei Klicks schaffen.

Übungsaufgabe Zeigen Sie: Bei 63 Wörtern kann man es immer mit höchstens sechs Klicks schaffen.

Ist das optimal? Ich behaupte ja:

Behauptung Bei 63 Wörtern gibt es keine Strategie, die garantiert mit fünf Klicks das Wort findet.

Vergegenwärtigen Sie sich die grundlegende Schwierigkeit, zu etwas zu zeigen: wir müssten für jede Strategie mit 5 Klicks zeigen, dass sie auf mindestens einer Wortliste der Länge 63 fehlschlägt. Es gibt aber unglaublich viele verschiedene Strategien. Unmöglich, alle durchzugehen. Um dieser Explosion Herr zu werden, ändern wir das Spiel leicht: es geht nun in Runden vor.

  1. Der Gegner verkündet das gesuchte Wort.
  2. Nun wird folgendes wiederholt:
    1. Der Sucher klickt auf eine Karte
    2. Der Gegner verkündet das Wort auf der Karte
  3. Das Spiel endet, wenn das gesuchte Wort verkündert wird (dann gewinnt der Sucher) oder bei dem fünften Klick das gesuchte Wort immer noch nicht gefunden worden ist (dann gewinnt der Gegner).

Im Gegensatz zum obigen Spiel muss der Gegner sich nicht anfangs auf eine feste Liste festlegen. Er darf adaptiv in jeder Runde ein Wort wählen. Dabei muss er sicherstellen,

  1. dass die Wörter auf den angeklickten Kacheln auch alphabetisch sortiert sind und
  2. das gesuchte Wort immer noch irgendwo Platz hat; wenn also Pferd gesucht ist, dann kann er nicht für Kachel $47$ Palisade und für Kachel $48$ Pyramide verkünden.

Übungsaufgabe Spielen Sie das Spiel und zeigen Sie, dass der Gegner es immer gewinnen kann (wenn wir 63 Wörter und 5 Klicks haben).