1. Suchen

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. Ganz konkret sehen wir uns mal die Datei german-english-1000.txt an (Quelle: strommeninc). Sie enthält die 1000 häufigsten deutschen Wörter und deren englische Übersetzung. Hier sehen Sie die ersten paar Zeilen.

Dieses Beispiel ist in einer gewissen Weise symmetrisch. Vielleicht haben Sie ein deutsches Wort und wollen das englische nachschlagen; vielleicht aber auch umgekehrt. Bei Telefonbüchern liegt jedoch meistens eine fundamentale Assymetrie vor: Sie haben einen Namen und wollen die Telefonnummer. In Ihrem Handy sieht das vielleicht so aus (alle Namen und Telefonnummern sind zufällig generiert mit www.fantasynamegenerators.com bzw. www.bestrandoms.com).

Vielleicht fällt Ihnen noch etwas auf: Ihr Adressbuch ist sortiert, und zwar alphabetisch. Der Zweck ist offensichtlich: so finden Sie die Nummern schneller. Diese Beobachtung ist wichtig. Wiederholen wir Sie noch einmal:

Selbst wenn Sie ein sehr sozialer Mensch sind, so ist Ihre Kontaktliste in Ihrem Handy wahrscheinlich so klein, dass es bei der Rechenkapazität Ihres Handys keinen Unterschied macht, ob die Daten sortiert oder unsortiert gespeichert sind. In beiden Fällen würde es die Nummer bei Eingabe des Namens schnell finden. Im Allgemeinen arbeiten Rechner jedoch mit viel größeren Datenmengen. Dabei ist eine gute Sortierung und schnelles Finden absolut entscheidend. Und genau damit werden wir uns in den ersten Kapiteln beschäftigen:

• wie man in sortierten Daten sucht;
• wie man sortiert;
• wie man eine sinnvolle Sortierung beibehält, wenn sich die Datenmenge dauernd ändert.

Für uns als Informatiker ist es erst einmal irrelevant, was die gespeicherten Daten repräsentieren; ob deutsche Wörter und deren englische Übersetzung im ersten Beispiel oder Namen und Telefonnummern im zweiten, die Aufgabe ist in beiden Fällen die gleiche: gegeben ein Schlüssel (key), finde den dazugehörigen Wert (value). Eine Datenstruktur, die beliebige key-value-Paare speichern kann, nennt man auch dictionary.

Dieser Kurs heißt theoretische Informatik. Und aus theoretischer Sicht, wo uns eher grundlegende Prinzipien und Laufzeitkomplexität interessieren, ist der value oft irrelevant; konkret hieße dass, anstatt die englische Übersetzung \(\beta\) eines deutschen Wortes \(\alpha\) finden zu wollen, wollen wir auf die Frage Enthält unsere Tabelle das Wort \(\alpha\) eine ja/nein-Antwort. Eine Datenstruktur, die derartige Fragen beantwortet, bezeichnet man als Menge oder Set. Da Sie ja bereits ein bisschen Java und Elm programmieren können, bietet es sich an, eine Signatur hinzuschreiben:

find: Dictionary a b -> a -> b 
contains: Set a -> a -> Bool

und dann hier ein Anwendungsbeispiel:

find dictionary "Hund"
"dog" : String
contains vocabularySet "Scwein"
False : Bool

oder in Java:

public class Dictionary <K, V> {
    public V find(K key);
}
public class Set <K> {
    public boolean contains (K key);
}