Algorithmen: die Rezepte der Informatik

Mai ist Rhabarberzeit. Ich liebe Rhabarber. Besonders Rhabarberkuchen. Grund genug so oft wie möglich den Schneebesen zu schwingen, die Hände in den Teig zu stecken und den leckersten Kuchen der Welt zu backen.

Stopp mal. Wird das jetzt hier ein FoodBlog? Tatsächlich backe und koche ich sehr gerne und stöbere auf einigen FoodBlogs rum. Mein liebstes Rhabarberkuchenrezept ist das von Bines Blog was eigenes:

Rezept Rhabarberkuchen

• 120 g Butter schaumig schlagen
• 80 g Zucker dazu
• 200 g Mehl mit 2 EL Speisestärke und 1 TL Backpulver mischen
• 3 Eigelb dazu
• kräftig durchkneten, zur Kugel formen und für etwa 20-30 Minuten in den Kühlschrank legen
• Boden einer Springform mit dem Teig auslegen
• Rhabarber (ca. 3-5 Stangen, je nach Dicke) ungezuckert in Stückchen auf den Teig legen, bzw. leicht eindrücken
• im Ofen (Ober-Unterhitze) bei 200° Grad ca. 20-25 Min. backen
• 3 Eiweisse schlagen und wenn der Eischnee fast steif ist
• 150 g Zucker & 1 Messerspitze Mondamin einrieseln lassen
• Baiser auf dem gebackenen Kuchen verteilen
• nochmal ca. 10 Minuten bei 200° Grad gold-gelb backen

So ein Backrezept ist nix anderes als eine Anleitung, was ich zu tun habe, um ein Problem zu lösen: „Wie erhalte ich meinen Lieblingskuchen?“. Und da hat der Kochbuch-Autor plötzlich was mit dem Informatiker gemeinsam: sie entwickeln Anleitungen, um Probleme zu lösen. In der Informatik nennt man diese Anleitungen Algorithmen.

Der Begriff Algorithmus ist aus dem Namen des Autors eines Mathematiklehrbuchs entstanden: Abu Dscha’far Muhammad ibn Musa al-Chwarizmi. Aus al-Chwarizmi wurde „Algorismi“, die Bezeichnung für die von al-Chwarizmi gelehrte Kunst des Rechnens.

Max Mustermann soll backen

Für Algorithmen gelten aber noch ein paar Bedingungen mehr als für Backrezepte. Die Beschreibung jedes einzelnen Schritts muss eindeutig sein. Viele Anweisungen im Rhabarberkuchenrezept sind nicht eindeutig und können von einem unerfahrenen Bäcker falsch verstanden werden. Wann ist Butter schaumig? Wann ist der Eischnee steif? Wie groß muss die Springform sein? Wie lang muss der Kuchen genau backen? Wir können das Backrezept umschreiben, sodass es aus eindeutigen Basisanweisungen besteht, die jeder (auch Max Mustermann) versteht:

• Gib 120 g Butter in ein Gefäß A und schlage sie mit dem Handrührgerät für 3 Minuten
• Gib 80 g Zucker in das Gefäß A.
• Gib 200 g Mehl, 2 Esslöffel Speisestärke und 1 Teelöffel Backpulver in ein Gefäß B.
• Verühre die Zutaten in Gefäß B für 20 Sekunden mit einem Löffel.
• Fülle die Zutaten aus Gefäß B in Gefäß A.

und so weiter.

Endlich ist nicht gleich endlich

Algorithmen müssen außerdem endlich sein. Das bedeutet, dass wir sie als endlichen Text aufschreiben können, aber auch, dass sie nach endlich vielen Schritten zur Lösung führen. Ist das nicht das gleiche? Endlicher Text und endlich viele Schritte? Nicht ganz. In Algorithmen kann es zum Beispiel auch Anweisungen für Wiederholungen geben. Um an die drei Eigelb für den Kuchenteig zu gelangen, muss ich drei Eier trennen. Das mache ich natürlich nicht gleichzeitig, sondern nacheinander:

• Wiederhole
  • Schlage ein Ei auf
  • Trenne das Eiweiß vom Eigelb
  • Gebe das Eigelb in Gefäß A
  • Gebe das Eiweiß in Gefäß C

So formuliert, würde ich unendlich viele Eier aufschlagen (das geht natürlich nicht, da es nicht unendlich viele Eier auf der Welt gibt) und niemals einen Kuchen backen. Ich brauche also eine Abbruchbedingung für meine Wiederholung, zum Beispiel „Wiederhole bis 3 Eigelb in Gefäß A sind“.

Problem vs Problemfall

Ein Rezept beschreibt für eine festgelegte Menge an Zutaten, wie daraus ein leckerer Kuchen wird. Mein Rhabarberkuchen reicht etwa für acht Personen. Aber da der Kuchen ja so verdammt lecker ist, wollen vielleicht noch mehr Leute etwas davon haben. Für 16 Personen backe ich eben einfach zwei Kuchen. Aber was ist, wenn zehn Leute Kuchen essen wollen? Hier liegt der Unterschied zwischen einem generellen Problem „Ich brauche Rhabarberkuchen für x Personen“ und einem einzelnen Problemfall „Ich brauche Rhabarberkuchen für 10 Personen“. Ein Algorithmus für ein Problem, muss für jeden einzelnen Problemfall das richtige Ergebnis liefern. Für unser Rhabarberkuchenrezept bedeutet das, dass zum Beispiel die Menge der Zutaten, die Größe der Backform und die Backdauer abhängig von der Anzahl der Personen geändert werden müssen.

Wann ist ein Rezept ein Algorithmus?

Gehen wir mal weg vom Kuchen und rein in die Grundschulmathematik. Damals haben wir gelernt, wie wir schriftlich zwei Zahlen miteinander multiplizieren. Auch das ist ein Berechnungsverfahren, ein Algorithmus. Auch hier soll für die gleichen Eingabezahlen immer das selbe Ergebnis rauskommen. Wie aber kann man überhaupt wissen, ob ein Berechnungsverfahren deterministisch ist? Oder ob es korrekt ist? Oder ob es endlich ist? Vielleicht braucht der Algorithmus ja auch einfach nur sehr lange, um eine Lösung zu finden.

Alan Turing war einer der ersten, der sich mit diesen Fragen beschäftigte. Er entwickelte das Konzept der Turing-Maschine, eine Art einfaches Modell eines Computers. Dieses Modell ermöglicht es zu testen, ob eine Berechnungsvorschrift wirklich die Bedingungen für einen Algorithmus erfüllt. Eine Turing-Maschine kann nur wenige unterschiedliche Operationen ausführen, mit denen man den Algorithmus beschreiben können muss. Wenn man eine Berechnungsvorschrift als solch eine Turing-Maschine formulieren kann und diese für jede Eingabe, die eine Lösung besitzt, stoppt, dann spricht man von einem Algorithmus.

Damit hat Turing eine der Grundsäulen der theoretischen Informatik geschaffen. Nebenbei hat er übrigens auch mal eben die Enigma-Verschlüsselung der deutschen Funksprüche im zweiten Weltkrieg geknackt. Wer mehr darüber erfahren will, dem sei der Film „The Imitation Game“ wärmstens empfohlen.

Vom Algorithmus zum Programm

Alles was ich euch bis hier über Algorithmen erzählt habe ist völlig abstrakt und hat noch nix mit Computern zu tun. Algorithmen sind aber natürlich prädestiniert dafür, automatisiert zu werden. Ein Programm ist eine für den Computer verständliche Darstellung eines Algorithmus. Der erste für einen Computer gedachte Algorithmus wurde bereits 1843 von einer Frau veröffentlicht: Augusta Ada Byron King, Countess of Lovelace (oder kurz Ada Lovelace). Das Programm sollte der Berechnung von Bernoullizahlen auf einem mechanischen Computer dienen. Dieser wurde jedoch nie fertiggestellt und der Algorithmus nie darauf implementiert. Trotzdem gilt Ada Lovelace als Pionierin der Programmierung. Als Programmieren bezeichnen wir die Tätigkeit, einen Algorithmus in ein Programm umzuschreiben. Ein Algorithmus muss nicht zwangsläufig in der formalen Sprache eines Rechners geschrieben sein. Soll der Rechner den Algorithmus ausführen, müssen wir ihn jedoch in eine solche Programmiersprache übersetzen. Ein Programm hingegen muss nicht unbedingt auf einem Algorithmus basieren, sondern kann auch aus sinnlos aneinandergereihten Operationen bestehen.

Algorithmen im Alltag

Unser Alltag steckt voller Algorithmen. Den Algorithmus zum schriftlichen Multiplizieren zweier Zahlen benutzt ihr vermutlich schon lange nicht mehr. Warum auch, es gibt ja Taschenrechner, die das automatisiert für euch erledigen. Und habt ihr euch heute schon von eurem Handy von A nach B navigieren lassen? Dann schaut euch doch mal den Dijkstra-Algorithmus an. Und hat Amazon euch heute schon einen neuen Kaufvorschlag gemacht? Nachdem ein Algorithmus aus riesigen Datenmengen errechnet hat, was euch wahrscheinlich gefällt. Und habt ihr heute schon auf Google gesucht? Nach Alan Turing oder Ada Lovelace vielleicht? Und der PageRank-Algorithmus hat euch gleich als erstes die entsprechenden Wikipedia-Beiträge geliefert? Und hat Facebook euch heute schon neue alte Freunde vorgeschlagen, die ihr schon längst aus den Augen verloren habt?

Algorithmen stecken überall, und manche bergen sicher Gefahren. Vor Algorithmen im allgemeinen sollte man aber keine Angst haben, denn sie sind letztendlich doch nur das Backbuch des Computers. Übrigens: auch das Essen eines Kuchens lässt sich wunderbar als Algorithmus formulieren!