Читать книгу Keine Panik, ist nur Technik - Kenza Ait Si Abbou - Страница 20

Algorithmen sind nichts anderes als eine Reihung von einzelnen Schritten, um eine bestimmte Aufgabe zu lösen. Es handelt sich um eindeutige Handlungsvorschriften zur Lösung eines Problems. Für die Maschine ist ein Algorithmus etwas Abstraktes, deswegen brauchen wir Code, um die Handlungsvorschriften zur Lösung des Problems für die Maschine verständlich zu machen. Ein Algorithmus hat also keine Form, es kann mündlich mitgeteilt werden, in Form eines Flussdiagramms (wie in der nächsten Abbildung) oder in Form von Code. Bei Maria und ihren Tinder-Dates, zum Beispiel, geht es darum, den anderen auf Äußerlichkeiten zu bewerten, bevor das Treffen stattfindet. Der »Erstes Date«- Algorithmus könnte also so aussehen:

Abbildung 11: Der »Erstes Date«-Algorithmus

Hier sind die Schritte aufgelistet, die Tom abarbeiten möchte, wenn er Maria zum ersten Mal trifft. Ähnlich wie in diesem Beispiel, führen wir alle täglich solche Algorithmen durch. Ein Koch- oder Backrezept ist ein klassischer Algorithmus, auch dort werden die einzelnen Schritte nacheinander festgelegt. Da die Kochkünste nicht bei allen gleich ausgeprägt sind, ist es wichtig, die Schritte genau und eindeutig zu beschreiben, damit es zu keinen Missinterpretationen kommen kann. Im besten Fall ist das Rezept so geschrieben, dass es vollkommen egal ist, wer kocht, und das Ergebnis immer ein gleich leckeres Essen ist. Dafür sollten die Schritte immer in derselben Reihenfolge umgesetzt werden, und das Kochen sollte auch mal ein Ende haben – »Ordnung muss sein« und »In der Kürze liegt die Würze«. Damit hätten wir die vier erforderlichen Eigenschaften für einen guten Algorithmus erfüllt:

1 Determiniertheit: Bei jeder Ausführung mit gleichen Zutaten und Handlungen kommen wir zum gleichen Ergebnis. Wenn wir das Rezept für Reiscurry befolgen, kommt am Ende immer ein Reiscurry dabei heraus.

2 Determinismus: Zu jedem Zeitpunkt, von vorne bis hinten, ist immer klar, was als Nächstes zu tun ist. Zuerst die einzelnen Zutaten raussuchen, wiegen, schnippeln und erst dann kochen. Sollten wir hier Varianten erlauben, wäre unser Algorithmus nichtdeterministisch. Der »Erstes Date«-Algorithmus, zum Beispiel, ist ein nichtdeterministischer Algorithmus, da ich zwei Ergebnis-Möglichkeiten habe: »Triff dein Date« oder »Renn weg«.

3 Terminiertheit: Alle Kochrezepte haben ein Ende, das heißt, wir werden irgendwann fertig und können unseren Hunger stillen. Endlosschleifen kann keiner gebrauchen, wenn der Magen knurrt. Andere Algorithmen, etwa zur Wetterbeobachtung, hören nicht auf, weil auch das Wetter nie aufhört zu existieren.

4 Effektivität: Unser Rezept war effektiv, wenn wir am Ende ein eindeutiges Ergebnis auf dem Tisch haben, das der Spezifikation (dem Versprechen des Rezepts) entspricht. Wenn wir ein Rezept für Reiscurry befolgen und am Ende Spaghetti mit Tomatensauce auf dem Tisch stehen, sollten wir das Rezept in die Tonne werfen!

Ähnlich wie Köche, die Rezepte für andere Menschen schreiben, schreiben Programmiererinnen Algorithmen für Maschinen, damit diese bestimmte Aufgaben richtig für uns lösen. Dabei werden die unterschiedlichsten Arten von Algorithmen unterschieden. Es gibt zum Beispiel Entscheidungsalgorithmen (wie den »Erstes Date«-Algorithmus: entweder treffe ich mein Date oder ich renne weg). Oder Optimierungsalgorithmen (wie mein Reiscurry-Rezept, wenn ich mit den gleichen Zutaten das beste Reiscurry kochen möchte). Die Liste der unterschiedlichen Kriterien und der dazugehörigen Algorithmen ist quasi unendlich: Es gibt Algorithmen für Geometrie- und Grafikaufgaben, für Kalenderrechnung, Bioinformatik, Kompression, Klassifikation, Clusteranalyse, Kryptografie, Prüfsummenverfahren, Numerik, Sortieralgorithmen, Suchalgorithmen und, und, und. Picken wir uns doch mal den Sortieralgorithmus als Beispiel heraus.

Der Sortieralgorithmus hat das Ziel, gegebene Elemente in eine bestimmte Reihenfolge zu bringen. Unser Freund Carlos sortiert seine Bücher nach Farben, und die Haushaltshilfe meiner Schwiegereltern hat einmal alle Bücher im Haus alphabetisch geordnet, mit dem Ergebnis, dass mein Schwiegervater, ein Journalist, in seinem Arbeitszimmer gar nichts mehr gefunden hat. Das Sortierkriterium muss also vorgegeben werden und eindeutig sein, sonst kommt nichts Gutes dabei heraus. Dafür stehen uns verschiedene Algorithmen zur Verfügung, die sich für unterschiedliche Sortierkriterien eignen. Einige erledigen die Aufgabe schneller, andere langsamer, einige gründlicher, andere mit bestimmten Tricks.

Da ist zum Beispiel Bubblesort, das ist ein Algorithmus, der Elemente paarweise sortiert. Nehmen wir an, wir wollen unsere Bücher alphabetisch sortieren. Dafür legen wir alle Bücher auf einen Tisch, wir gehen von links nach rechts und schauen uns das erste Paar, also die ersten beiden Bücher, an. Sollte die alphabetische Reihenfolge richtig sein, lassen wir sie so liegen und gehen zum nächsten Paar, also das zweite und dritte Buch. Sollte die Reihenfolge falsch sein, vertauschen wir die Position dieses Bücherpaares. Dann vergleichen wir Buch drei und Buch vier, und immer so weiter, bis zum letzten Bücherpaar und dann wieder beim (neuen) ersten Paar. Dieses Procedere wiederholen wir so lange, bis bei einem Durchgang kein Paar mehr vertauscht werden muss – fertig ist die alphabetische Sortierung. Ihr könnt euch bei diesem Vorgehen vorstellen, dass es nicht schnell geht, gerade wenn es wirklich viele Bücher sind.

Das Ganze können wir auch etwas anders machen, indem wir diesmal das erste Buch als Referenz festlegen und das nächste Buch dann an die richtige alphabetische Position im Vergleich zu unserem Referenzbuch einordnen, also entweder rechts oder links davon. Im nächsten Schritt legen wir das zweite Buch als das neue Referenzbuch fest und wiederholen den Vorgang. Das machen wir so weiter, bis alle sortiert sind. Damit hätten wir den Einfügesortieralgorithmus verwendet, den Insertionsort.

Noch schneller geht es, wenn wir ein Buch zufällig aussuchen und alle Bücher, die im Alphabet davor kommen, links davon ablegen und alle Bücher, die im Alphabet danach kommen, rechts davon. Dann kleben wir ein Post-it auf das erste Buch und wissen, dass dieses richtig einsortiert wurde. Das Prinzip der Aufteilung in kleinere und dadurch besser handhabbare Gruppen heißt »teile und herrsche«. Dann wiederholen wir das gleiche Spiel mit der linken Gruppe Bücher, bis nach und nach auf allen Post-its kleben, und natürlich auch mit der rechten Gruppe Bücher. Damit hätten wir den Quicksort-Algorithmus verwendet. Auch wenn dieses Verfahren erst einmal komplex erscheint, ist es für sehr große Elementmengen, also etwa Tausende oder Millionen von Büchern, viel schneller als die ersten zwei. Bei solchen Mengen überlassen wir in der Regel die Aufgabe ja auch einer Maschine und lassen ihn automatisiert ablaufen, bevor wir uns die Finger wund sortieren.

Da die Maschine keine Emotionen kennt und stur unsere Handlungsanweisungen verfolgt, ist es ihr egal, welchen Algorithmus wir programmieren.

Für uns Menschen ist der Einfügesortieralgorithmus meist intuitiver. Denn genau dieses Vorgehen setzen wir zum Beispiel um, wenn wir beim Kartenspielen eine Karte aufnehmen und rechts oder links auf unserer Hand einsortieren.

An dieser Stelle frage ich mich jedes Mal, welchen Algorithmus die Haushaltshilfe meiner Schwiegereltern damals gewählt hat, und vor allem, wie ihre Reaktion ausgesehen hätte, hätte ich ihr auf die Schulter geschaut und gesagt, dass sie gerade diesen oder jenen Algorithmus verwendet. Amüsante Vorstellung, nicht wahr? Mein Schwiegervater fand das Ganze damals leider überhaupt nicht lustig, er hat wochenlang gebraucht, um alle seine Bücher in die ursprüngliche thematische Sortierung zurückzubringen, der Arme.

Damit die Aktion nicht ganz umsonst war, nutzen wir sie für ein Gedankenexperiment: Stellt euch vor, er hätte diese alphabetische Sortierung gewollt und die Haushaltshilfe damit beauftragt. Bei den vollgepackten Regalen hätte er wissen müssen, wie lange das in etwa dauert, denn das Zeitbudget der Haushaltshilfe ist begrenzt, und die restlichen Räumlichkeiten des Hauses müssen auch noch gereinigt werden. Also überlegt er sich einen Plan, wie das alles realisiert werden könnte. Diesen Plan nennen wir Programmierer »Modell«.