Algorithmen - Handlungsanweisungen für Computer
Der Begriff »Algorithmus« ist inzwischen zwar gängiger als noch vor ein paar Jahren, aber für viele immer noch ungewohnt. Ich habe sogar hochrangige Führungskräfte schon von »Alogorithmen« sprechen hören. Ob hinter diesem Lapsus wohl die Hoffnung auf eine Herleitung des Begriffs aus dem Altgriechischen steckt? Wobei sich Algorithmen ja logisch verhalten und nicht unlogisch. Da kommt’s also nicht her.
Schmerzhaft und Zahl
Donald E. Knuth, der berühmteste Algorithmiker der Welt, berichtet in seinem Buch "The Art of Computer Programming", dass frühe Linguisten den Begriff tatsächlich aus dem Griechischen herleiteten, und zwar aus álgiros (schmerzhaft) und arithmós (Zahl). Auch diese Herleitung sagt wohl mehr über die Linguisten und ihre Haltung gegenüber den furchterregenden Algorithmen aus, als über den wirklichen Ursprung des Begriffs. Das Wort "Algorithmus" ist tatsächlich deswegen so schwer merkbar, weil es sich von dem Namen eines arabischen Mathematikers namens Al-Chwarizmi ableitet, der im 9. Jahrhundert ein mathematisches Lehrbuch verfasste. Als dieses drei Jahrhunderte später ins Lateinische übersetzt wurde, passte man den Namen des Verfassers kurzerhand an die vermeintliche Wurzel aus dem Lateinischen oder Altgriechischen an. Es besteht daher Verwechslungsgefahr mit dem Logarithmus und mit Rhythmus, die aber etymologisch nicht mit dem Begriff "Algorithmus" verwandt sind.
Und was ist das nun, ein Algorithmus? Viele sind etwas enttäuscht, wenn sie hören, dass Algorithmen nichts weiter als festgelegte Handlungsanweisungen sind, um klar definierte mathematische Probleme zu lösen. Das mathematische Problem legt dabei fest, welche Informationen der Problemlöser kennt und welche Eigenschaften ein Resultat haben muss, um als Lösung des Problems zu gelten. Das Problem definiert also die Beziehung zwischen Input (eingegebene Informationen) und Output (gewünschte Lösung). Daher sprechen wir in der Informatik auch immer davon, was "gegeben" ist (welche Information vorliegt) und was "gesucht" ist. Und hier ein Beispiel, damit das nicht so abstrakt bleibt: Das Navigationsgerät löst das "kürzeste-Wege-Problem": Gegeben eine Straßenkarte, Start- und Zielpunkt, sucht es diejenige Route, deren Länge am kürzesten ist.
Neuling im Beruf
Ein Algorithmus ist dann eine detaillierte Handlungsanweisung dafür, wie man die gewünschte Lösung tatsächlich findet, wenn alle dafür nötigen Informationen bekannt sind. Im Wesentlichen ist ein Algorithmus also das, was wir jedem Neuling in unserem Beruf erklären, der zum allerersten Mal eine für den Beruf typische Aufgabe alleine lösen soll. Um wirklich als Algorithmus zu gelten, muss die Handlungsanweisung allerdings so klar sein, dass sie in eine Programmiersprache übersetzt werden kann. Diesen Schritt nennt man Implementierung.
Mathematische Rätsel sehen oft auch ein bisschen aus wie ein mathematisches Problem, zum Beispiel dieses hier: "Welche vier Zahlen ergeben in der Summe 45 und gleichzeitig genau dieselbe Zahl, wenn man zur ersten Zahl 2 addiert, von der zweiten 2 abzieht, die dritte durch 2 teilt und die vierte mit 2 multipliziert?" Die "Eingabe" ist also die 45, und an die Lösung, nämlich die vier Zahlen, werden bestimmte Anforderungen gestellt. Wie kommt man jetzt zur Lösung? Durch ein paar kleine Überlegungen kann man erst die Kandidaten eingrenzen und dann durchprobieren: Man stellt zuerst fest, dass der Unterschied zwischen den beiden ersten Zahlen 4 sein muss, da ja die Addition von 2 zur kleineren dieselbe Zahl ergeben muss wie das Abziehen von 2 von der größeren. Daraus folgt auch, dass entweder beide Zahlen gerade oder beide ungerade sein müssen. Für die anderen beiden Zahlen muss gelten, dass das Vierfache der kleineren Zahl die größere ergibt – da das Zweifache der vierten Zahl dieselbe Zahl wie die Hälfte der dritten Zahl ist. Das Vierfache einer Zahl ist immer gerade – damit die Summe aller vier Zahlen ungerade sein kann, muss also die vierte Zahl notwendigerweise ungerade sein. Sie könnte also 1, 3, 5, 7, … sein, die anderen Zahlen ergeben sich zwangsläufig, wenn diese Zahl gesetzt ist. Wenn die vierte Zahl 1 ist, dann ist die dritte Zahl 4, die erste und zweite sind 0 und 4. Damit ist aber die Summe 9. Durch solches Herumprobieren finden wir heraus, dass die vierte Zahl 5 sein muss: Dann ist die dritte Zahl 20, die erste ist 8, und die zweite ist 12, in der Summe also 45.
Ameisen und Duftstoffe
Nun, "Herumprobieren" ist kein Algorithmus – es ist eine sogenannte Heuristik. Das kommt vom altgriechischen Wort heurískein, das "finden" oder "entdecken" bedeutet. Heuristiken sind Strategien, die wir entwickeln, um Lösungen für ein Problem zu finden. Diese Strategien haben sich bislang bewährt, bieten aber keine Garantie, dass sich damit eine Lösung finden lässt, die alle an sie gestellten Bedingungen erfüllt. Beim "kürzesten-Wege-Problem" kann man bei Ameisen eine interessante Heuristik finden. Sie gehen erst ziemlich zufällig in der Gegend herum und hinterlassen dabei einen Duftstoff auf dem Boden. Wenn sie dabei über etwas Leckeres stolpern, finden sie mit diesem Duftstoff wieder zurück ins Nest. Je leckerer das Essen ist und je mehr davon da war, desto mehr Duftstoff setzt die Ameise dabei auch auf dem Rückweg ab. Damit können nun auch andere Ameisen das Essen finden – diese verstärken die Duftspur dann weiter. Da sich der Duftstoff in alle Richtungen gleichmäßig verteilt, ist er innerhalb einer Kurve konzentrierter als direkt an ihrem Rand. Das ist so ähnlich wie bei Ihrem Parfüm: Wenn Sie es auf Brust und Handgelenke sprühen, riecht die Person in der U-Bahn am stärksten, die Ihnen gegenübersteht, und nicht die, die neben Ihnen steht. Daher werden die Ameisen von der Mitte der Kurve etwas mehr angezogen als vom Rand und die ursprünglichen Schleifen des zufälligen Herumwanderns immer stärker abgekürzt. Ganz am Ende entsteht dadurch tatsächlich ein Weg, der relativ kurz, aber nicht notwendigerweise der allerkürzeste ist. Der Begriff der Heuristik wird Ihnen nachher im Kapitel "Computerintelligenz" wieder begegnen, da die meisten Methoden dort gar keine Algorithmen sind. Spezialwissen, mit dem Sie in jeder Quizsendung punkten können! Es ist aber auch deswegen wichtig, weil nur Algorithmen garantiert die beste Lösung finden – Heuristiken können das nicht versprechen.
Solange es nur um einen Einzelfall wie in dem kleinen Zahlenrätsel geht, lohnt es sich aber auch nicht, einen generell gültigen Algorith- mus für die Lösung von solchen mathematischen Rätseln zu entwickeln. Erst allgemeine mathematische Probleme, die immer wieder auftreten, bekommen unsere Aufmerksamkeit. Beispiele dafür sind die Fragen nach der Wurzel einer beliebigen Zahl oder dem Produkt beliebig vieler Zahlen, aber auch die Frage an eine Datenbank nach allen Käufen, die ein Kunde in einem gegebenen Jahr getätigt hat. Damit haben wir nun alles zusammen, um den Begriff "Algorithmus" zu klären:
Ein Algorithmus ist eine für jede erfahrene Programmiererin und jeden erfahrenen Programmierer ausreichend detaillierte und systematische Handlungsanweisung für die Lösung eines mathematischen Problems, sodass bei korrekter Implementierung (Übersetzung in Code) der Computer für jede korrekte Inputmenge den korrekten Output berechnet.
Als Informatiker fügen wir noch gerne hinzu, dass der Algorithmus bitte auch in "endlicher Zeit" seine Lösung berechnet haben soll. Es erscheint doch wenig zweckmäßig, wenn wir bis zum Ende des Universums auf unser Ergebnis warten müssten.
Das Buch "Ein Algorithmus hat kein Taktgefühl" von Katharina Zweig ist am 14. Oktober2019 im Heyne Verlag erschienen. Der Textauszug stammt aus dem dritten Kapitel "Algorithmen: Handlungsanweisungen für Computer".
