Kapitel 1:
Einführung in Algorithmen

In diesem Kapitel:

• Die Grundlagen für das Verständnis dieses Buchs.

• Du wirst einen ersten Suchalgorithmus programmieren (eine binäre Suche).

• Du wirst erfahren, wie man die Laufzeit eines Algorithmus mit der Landau-Notation beschreibt.

1.1  Einführung

Ein Algorithmus? ist eine Reihe von Anweisungen, die eine Aufgabe ausführen. Man könnte eigentlich jeden Codeschnipsel als Algorithmus bezeichnen, aber dieses Buch befasst sich mit den interessanteren Aspekten. Die Algorithmen in diesem Buch habe ich ausgewählt, weil sie schnell sind, interessante Aufgabenstellungen lösen oder beides. Hier sind einige der Highlights:

• Dieses Kapitel beschreibt die binäre Suche und führt vor, wie ein Algorithmus deinen Code beschleunigen kann. In einem der Beispiele wird die Anzahl der erforderlichen Schritte von 4 Milliarden auf nur 32 reduziert!

• Ein GPS-Empfänger verwendet Graphenalgorithmen (die in Kapitel 6, Kapitel 9 und Kapitel 10 erörtert werden), um die kürzeste Route zu einem Ziel zu berechnen.

• Du kannst die dynamische Programmierung (siehe Kapitel 11) dazu verwenden, einen Algorithmus zu schreiben, der Dame spielt.

Ich werde hierfür jeweils einen Algorithmus erläutern und ein Beispiel dafür zeigen. Anschließend betrachten wir die Laufzeit des Algorithmus mithilfe der Landau-Notation (Landau-Symbole). Und schließlich erfährst du, welche anderen Aufgabenstellungen mit demselben Algorithmus gelöst werden können.

1.1.1  Performance

Die gute Nachricht ist, dass Implementierungen der Algorithmen, die in diesem Buch beschrieben werden, sehr wahrscheinlich in deiner Lieblingsprogrammiersprache verfügbar sind. Du musst die Algorithmen also nicht alle selbst schreiben! Allerdings sind diese Implementierungen nutzlos, wenn du deren Vor- und Nachteile nicht verstehst. In diesem Buch lernst du, die Vor- und Nachteile verschiedener Algorithmen miteinander zu vergleichen: Solltest du für eine bestimmte Aufgabe Mergesort oder lieber Quicksort verwenden? Ist ein Array oder eine Liste besser geeignet? Die Verwendung einer anderen Datenstruktur kann einen sehr großen Unterschied ausmachen.

1.1.2  Problemlösungen

Du wirst zudem Verfahren zur Problemlösung für Aufgaben kennenlernen, an die du dich bislang vielleicht nicht herangetraut hast. Einige Beispiele:

• Falls du Videospiele magst, kannst du ein System für die Künstliche Intelligenz (KI) programmieren, das Graphenalgorithmen verwendet und das den User im Spiel verfolgt.

• Du wirst erfahren, wie du mit dem k-Nächste-Nachbarn-Algorithmus (k-Nearest-Neighbors-Algorithmus) ein Empfehlungssystem entwickeln kannst.

• Manche Aufgaben lassen sich nicht in angemessen kurzer Zeit lösen. Der Abschnitt des Buchs über NP-vollständige Probleme beschreibt, wie du solche Probleme erkennen kannst und stellt einen Algorithmus vor, der dir eine Näherungslösung liefert.

Allgemeiner formuliert: Nach der Lektüre dieses Buchs werden dir einige der meisten verbreiteten und für sehr viele Fälle anwendbaren Algorithmen vertraut sein. Mit dem Wissen aus diesem Buch kannst du dich spezielleren Algorithmen für die KI, für Datenbanken usw. zuwenden oder dich noch größeren Herausforderungen stellen.

Erforderliche Kenntnisse

Für die weitere Lektüre des Buchs benötigst du Grundkenntnisse der Algebra?. Betrachte beispielsweise die folgende Funktion: f(x) = x × 2. Welchen Wert besitzt dann f(5)? Wenn deine Antwort 10 lautet, bist du bereit.

Darüber hinaus ist dieses Kapitel (wie das ganze Buch) leichter verständlich, wenn dir eine Programmiersprache vertraut ist. Die Beispiele in diesem Buch sind in Python geschrieben. Falls du noch keine Programmiersprache kennst und eine erlernen möchtest, solltest du Python wählen - die Sprache ist hervorragend für Anfänger geeignet. Wenn du eine andere dir bekannte Programmiersprache (wie z.B. Ruby) verwenden möchtest, ist das problemlos möglich.

1.2  Binäre Suche

Nehmen wir an, du suchst in einem Telefonbuch nach einer Person (wie altmodisch das klingt!). Der Name beginnt mit K. Du könntest nun am Anfang des Telefonbuchs loslegen und so lange blättern, bis du zum Buchstaben K gelangst. Wahrscheinlich wirst du mit der Suche jedoch eher in der Mitte anfangen, weil du weißt, dass sich die Einträge mit K ungefähr in der Mitte des Telefonbuchs befinden.

Oder du stellst dir vor, dass du einen Begriff, der mit dem Buchstaben O beginnt, in einem Wörterbuch suchst. Auch in diesem Fall wirst du mit der Suche in der Nähe der Mitte beginnen.

Und nun stelle dir vor, dass du dich bei Facebook anmeldest. Facebook muss dann überprüfen, ob du ein Konto besitzt und dementsprechend in einer Datenbank nach deinem Namen suchen. Nehmen wir an, dein Username lautet karlmageddon. Facebook könnte nun beim Buchstaben A mit der Suche anfangen - allerdings ist es sinnvoller, irgendwo in der Mitte anzufangen.

Bei dieser Aufgabe handelt es sich um eine Suche. Zur Lösung solcher Aufgaben kommt stets der gleiche Algorithmus zum Einsatz: die binäre Suche.??

Die binäre Suche ist ein Algorithmus, dessen Eingabe aus einer sortierten Liste von Elementen besteht. (Ich erkläre später, warum die Liste sortiert sein muss.) Wenn das gesuchte Element in dieser Liste enthalten ist, liefert die binäre Suche die Position zurück, an der es sich befindet. Andernfalls gibt die binäre Suche den Wert null zurück.

Zum Beispiel:

Hier ist ein Beispiel für die Funktionsweise der binären Suche. Ich denke an eine Zahl zwischen 1 und 100.

Du musst nun meine Zahl mit möglichst wenigen Versuchen erraten. Ich sage dir jeweils, ob die geratene Zahl zu groß, zu klein oder richtig ist.

Nehmen wir an, du nennst die Zahlen der Reihe nach: 1, 2, 3, 4, ... Das sähe dann folgendermaßen aus:

Hierbei handelt es sich um eine einfache Suche?? (vielleicht wäre eintönige Suche in diesem Fall eine passendere Bezeichnung). Mit jedem Versuch schließt du nur eine einzige Zahl aus. Wenn ich an die Zahl 99 gedacht hätte, würdest du 99 Versuche benötigen, um meine Zahl zu erraten!

1.2.1  Eine bessere Suchmethode

Ein besseres Verfahren ist das folgende: Fang mit der Zahl 50 an.

Diese ist zu klein, allerdings hast du soeben die Hälfte aller Zahlen ausgeschlossen! Du weißt nun, dass alle Zahlen von 1 bis 50 zu klein sind. Nächster Versuch: 75.

Zu groß, aber du hast wieder die Hälfte der verbliebenen Zahlen ausgeschlossen! Bei einer binären Suche nennst du die Zahl in der Mitte und schließt dadurch jeweils die Hälfte der noch vorhandenen Zahlen aus. Nun ist 63 an der Reihe (die Mitte zwischen 50 und 75).

So funktioniert die binäre Suche. Du hast soeben deinen ersten Algorithmus erlernt! So viele Zahlen kannst du mit jedem Rateversuch ausschließen:

An welche Zahl ich denke, spielt keine Rolle: Du benötigst höchstens 7 Versuche, um sie zu erraten, weil bei jedem Rateversuch so viele Zahlen ausgeschlossen werden.

Nehmen wir wieder an, du suchst nach einem Begriff in einem Wörterbuch, das 240.000 Einträge enthält. Was meinst du, wie viele Schritte für eine Suche im Worst Case, also im ungünstigsten Fall, nötig sind?

Bei der einfachen Suche können 240.000 Schritte notwendig sein, sofern sich das gesuchte Wort ganz am Ende des Wörterbuchs befindet. Bei der binären Suche hingegen wird bei jedem Schritt die Anzahl der verbliebenen Wörter halbiert, bis schließlich nur noch ein Wort übrig ist.

Bei der binären Suche sind also 18 Schritte erforderlich - ein riesiger Unterschied! Verallgemeinert bedeutet das: Bei einer Liste der Länge n benötigt die binäre Suche im Worst Case log2 n Schritte, bei einer einfachen Suche sind hingegen n Schritte erforderlich.

Logarithmen

Vielleicht erinnerst du dich nicht mehr daran, was Logarithmen? sind, aber du weißt vermutlich noch, was Exponentialfunktionen? sind. Der Ausdruck log10 100 entspricht der Frage: »Wie viele Zehnen muss man miteinander multiplizieren, um 100 zu erhalten?«. Die Antwort lautet 2: 10 × 10 = 100. Also ist log10 100 = 2. Logarithmen sind die Umkehrfunktionen? von Exponentialfunktionen.

Wenn es in diesem Buch um die Laufzeit und die Landau-Notation (die in Kürze erklärt wird) geht, bedeutet log stets log2. Wenn du für die Suche nach einem Element eine einfache Suche verwendest, musst du im Worst Case jedes einzelne Element überprüfen. Bei einer Liste von 8 Zahlen musst du höchstens 8 Zahlen überprüfen. Bei einer binären Suche musst du im Worst Case log n Elemente überprüfen. Für eine Liste mit 8 Elementen gilt log 8 == 3, denn 23 == 8. Du musst also höchstens 3 Zahlen überprüfen (und dann kannst du mit dem 4. Versuch das richtige Ergebnis nennen). Für eine Liste mit 1.024 Elementen gilt log 1.024 == 10, denn 210 == 1.024. Bei einer Liste von 1.024 Zahlen musst...