.
Читать онлайн книгу.
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«.
Programmierst du noch, oder modellierst du schon?
Ein Modell ist an sich eine vereinfachte Abbildung der Realität, oder besser gesagt: ein Ausschnitt der beobachtbaren Realität. Modelle helfen uns dabei, durch Vereinfachung die Realität besser zu verstehen, sie sind aber nicht die Realität – so wie sich das Modellhaus einer Architektin von einem richtigen Haus unterscheidet. Wir nutzen Modelle, um eine Art Laborsituation zu schaffen, in der wir bestimmte Aspekte der Realität kontrolliert messen und prüfen zu können. Die Architektin nutzt ihr Modell, um dem Bauherrn sein zukünftiges Haus zu zeigen, damit dieser entscheiden kann, wo nun der Balkon gebaut werden sollte. Sollte er sich kurz vor dem Bau umentscheiden, wäre das beim Modell kein Problem, ein paar Klicks im 3D-Simulationsprogramm, und schon ist der Balkon woanders. Würde das Haus ohne Modell gebaut, wäre solch ein Umentscheiden sehr teuer oder unmöglich – sofern der Bauherr nicht zwei Balkone möchte.
Was hat das nun mit dem Buch-Sortier-Modell von meinem Schwiegervater zu tun? Also, in diesem Fall handelt es sich um ein mathematisches Modell, das eine besondere Voraussetzung erfüllen muss: Reicht die Zeit, um alle Bücher alphabetisch zu sortieren, ohne das Putzen zu vernachlässigen? Da er die Antwort nicht empirisch ermitteln kann, also mehrere Methoden durchprobieren und schauen, welche wie viel Zeit in Anspruch nimmt (dann könnte er es auch gleich selbst machen), versucht er, das Ganze also zu modellieren. Nachdem die Aufgabe klar beschrieben ist, kommt der nächste Schritt: vereinfachen. Wir denken oft, dass die Realität doch im Grunde ganz einfach ist, wenn man jedoch genauer hinsieht, stellt man fest, wie komplex die Dinge in der Regel sind. Da wir beim Modellieren nur ein Abbild oder einen Ausschnitt nehmen, müssen wir Annahmen treffen, um die Aufgabe einfacher (und lösbarer) zu gestalten. Die Annahmen meines Schwiegervaters wären zum Beispiel: Es gibt keine Unterbrechungen (das Telefon klingelt, der Postbote läutet etc.), es fallen keine Bücher plötzlich vom Regal runter oder aus der Hand, es gibt keine Kaffee- oder Toilettenpausen, und es erscheint auch keine Maus aus der hinteren linken Ecke. Prozessual nehmen wir an, dass es am schnellsten geht, wenn alle Bücher auf den Tisch gelegt, sortiert und wieder in die Regale eingeräumt werden (was bei der Vielzahl an Büchern unrealistisch ist, aber egal). Jetzt müssen die Schritte mathematisiert werden.
Für das Ausbreiten der Bücher auf dem Tisch nehmen wir einen Zeitaufwand von 30 Minuten an, für das Einräumen in die Regale noch einmal 30 Minuten. Wie lange brauchen wir für das Sortieren? Gute Frage, denn hier gibt es verschiedene Möglichkeiten, wie wir oben gesehen haben, und je nach Algorithmus dauert es länger oder kürzer.