Wenn man sich die digitalen Errungenschaften der letzten 20 Jahre vor Augen hält, fallen einem sofort die ungeheuren Fortschritte in der Leistungsfähigkeit der Rechner und der Netze, und die geradezu grenzenlose Datenfülle auf. Dagegen sind die Algorithmen, die im Innern der digitalen Geräte ablaufen und alle digitalen Prozesse steuern, unsichtbar und daher für viele Menschen auch unverständlich; schon das Wort klingt unheimlich. Und wenn man sie schon nicht sehen und anfassen kann, so lassen sich zumindest Mutmaßungen über sie anstellen: Algorithmen wissen alles, manipulieren unsere Entscheidungen – oder treffen die Entscheidungen gleich selbst, bringen Finanzmärkte durcheinander, beeinflussen Wahlen… Algorithmen machen vielen Menschen Angst. Es wird Zeit für das einzig mögliche Gegenmittel: Aufklärung.
Zur Person
Ulrich Trottenberg (*1945) hat bis zum Jahr 2012 das Fraunhofer-Institut für Algorithmen und Wissenschaftliches Rechnen (SCAI) geleitet. Außerdem war er Inhaber des Lehrstuhls für Angewandte Mathematik und Wissenschaftliches Rechnen der Universität zu Köln. Der Mathematiker forscht unter anderem über Algorithmen und Rechnerarchitekturen.
Ich möchte den Mythos Algorithmus zurück auf den Boden der Tatsachen holen und das algorithmische Denken in den Kontext digitaler Bildung und Aufklärung stellen. Dazu zunächst eine elementare, nicht formale Definition:
Ein Algorithmus ist eine eindeutige Handlungsvorschrift, die aus endlich vielen präzise formulierten, wohldefinierten Einzelanweisungen besteht, zur Lösung eine Problems oder einer Problemklasse.
Man verlangt von einem Algorithmus auch, dass nach endlich vielen Einzelschritten das betreffende Problem gelöst ist (oder als unlösbar erkannt wird). Ein Computerprogramm ist ein in einer Programmiersprache formulierter Algorithmus, jede Software setzt sich aus einzelnen Algorithmen zusammen.
Das Verständnis für Algorithmen unterscheidet sich von der Fähigkeit zu programmieren insofern, als dass Algorithmen die Substanz dessen ausmachen, was digital (im Rechner oder in beliebigen anderen digitalen Geräten) passiert. Demgegenüber bleibt die Fähigkeit des Programmierens formal, wenn sie nicht durch ein Verständnis für Algorithmen fundiert wird. Wenn umgekehrt die Algorithmen nicht programmiert und auf Rechnern ausgeführt werden, bleibt ihre Kenntnis ein Stück weit abstrakt. Algorithmen sind unabhängig von einer konkreten Programmiersprache und können in verschiedenen Programmiersprachen codiert werden; in der Regel ist eine bestimmte Programmiersprache für einen Algorithmus aber mehr oder weniger geeignet.
Um zu zeigen, wie Algorithmen aufgebaut sind, erkläre ich Ihnen drei praktische Beispiele. Damit möchte ich deutlich machen, dass algorithmisches Denken gar nicht so abstrakt ist, wie es scheint.
1. Beispiel Sortieren. Jeder Mensch hat eine Vorstellung davon, wie Objekte sortiert werden können, seien es Spielkarten oder Namen (z.B. alphabetisch) oder Zahlen (z.B. in aufsteigender Reihenfolge). Nun stellen wir einem Rechner die Aufgabe, eine Sortierung, sagen wir von Namen einer Namensliste, vorzunehmen und wollen dafür einen einfachen Algorithmus entwerfen. Dazu nehmen wir an, dass der Algorithmus beim Vergleich von zwei Namen der Liste entscheidet, welcher Name vor den jeweils anderen platziert wird.
Wir fangen vorne bei der Liste an, vergleichen den ersten mit dem zweiten Namen, ordnen die beiden alphabetisch, vergleichen dann den (eventuell neuen) zweiten mit dem dritten Namen, ordnen die beiden alphabetisch, vergleichen den (eventuell neuen) dritten mit dem vierten, und fahren so fort, bis wir das Ende der Liste erreicht haben. Die neu entstandene Liste ist dann noch nicht vollständig alphabetisch geordnet (das wäre ein Zufall) – aber wir stellen fest, dass der letzte Name in der Liste wirklich an der richtigen Stelle steht! Es ist der letzte im Alphabet. Warum ist das so? Das ist eine kleine Denksportaufgabe.
Schritt 2: Kurze Wege
Wem diese Überlegung zu mühsam ist, der probiert es einfach aus. Aber sobald man dieses Ergebnis eingesehen hat, wird klar, wie es weiter gehen muss: Der Algorithmus fängt wieder vorne an, vergleicht und sortiert jeweils die nachfolgenden Namen, fährt fort wie im ersten Durchlauf, bis er am vorletzten Namen angekommen ist: Der ist dann auch der vorletzte im Alphabet – mit dem gleichen Argument wie oben. Im dritten Durchlauf ergibt sich als drittletzter Name der alphabetisch richtige. Und so geht es weiter, Durchlauf für Durchlauf, bis die ganze Liste sortiert ist. Genauer: Nach n-1 Durchläufen ist die Liste vollständig geordnet, wenn n die Anzahl der Namen in der Liste (die Länge der Liste) bezeichnet.
Die Erfahrung zeigt, dass schon Grundschulkinder diesen Algorithmus (in der Literatur als „Bubblesort“ bekannt) sehr schnell verstehen können. Der beschriebene Algorithmus spielt in der Praxis keine große Rolle, weil es andere, effizientere Sortieralgorithmen gibt. Er ist aber durchaus geeignet, eine Ahnung von algorithmischem Denken zu vermitteln. Er lässt sich in wenigen Zeilen programmieren.
2. Beispiel Kurze Wege: Bitte stellen Sie sich folgende Aufgabe vor: Finden Sie für eine Rundreise den kürzesten Weg, der eine Anzahl vorgegebener Städte so verbindet, dass jede Stadt genau einmal besucht wird. Auch dies ist ein unmittelbar verständliches Problem; und auch hier kommt man leicht auf folgende algorithmische Idee:
In der Stadt A startend besuche als erste die Stadt (nennen wir sie B) mit der kürzesten Entfernung von A, und dann als zweite die Stadt (C) mit der kürzesten Entfernung von B. Und so weiter: Besuche als nächste jeweils die Stadt mit der kürzesten Entfernung unter allen Städten, die noch nicht besucht worden sind. Am Ende geht es zurück nach A. (Bei gleichen Entfernungen wähle eine der gleich weit entfernten Städte, z.B. gemäß dem Stadtnamen im Alphabet).
Ist der so gefundene Rundreiseweg der kürzest mögliche? Anhand einfacher Beispiele mit wenigen Städten macht man sich leicht klar, dass der Algorithmus nicht unbedingt den kürzesten Gesamtweg liefert. Aber wie findet man den? Eine Möglichkeit ist, alle möglichen Wege auszuprobieren. Bei sechs Städten sind das schon 120 (= 5*4*3*2) Möglichkeiten, da kann man noch alle durchprobieren. Aber bei vielen Städten sind das ungeheuer viele Möglichkeiten: Wenn man annimmt, dass man für das Durchprobieren aller Möglichkeiten bei zehn Städten 0,1 Sekunden Rechenzeit benötigt, bräuchte man für 18 Städte schon mehr als drei Jahre Rechenzeit!
Die Anzahl der Möglichkeiten steigt unvorstellbar schnell (für mathematisch Interessierte: wie n!) an. Wegen dieser Eigenschaft ist das sogenannte Travelling Salesman Problem nicht nur praktisch wichtig, sondern auch in der mathematischen Theorie so prominent: Es ist bis heute kein Algorithmus bekannt, der das Problem für größere Anzahlen von Städten in vertretbarer Rechenzeit optimal löst. Aber akzeptable Lösungen lassen sich mit geeigneten Algorithmen dagegen durchaus berechnen.
Das folgende Beispiel des Page Ranking bei der Google-Suche ist ebenfalls von großer, sehr aktueller und enormer wirtschaftlicher Bedeutung – es war der Ausgangspunkt für den wirtschaftlichen Erfolg von Google. Für dieses Beispiel lässt sich ein einfacher Algorithmus nicht so leicht angeben wie für die beiden vorangehenden Beispiele; es erfolgreich zu behandeln erfordert dann doch schon mehr Mathematik, als wir hier vermitteln können. Was aber geht, ist, sich ein paar elementare algorithmische Prinzipien zu überlegen, die hier eine entscheidende Rolle spielen könnten.
Schritt 3: Page Ranking
3. Beispiel Page Ranking: Wenn man bei Google einen Begriff eingibt und dazu einschlägige Informationen erwartet – wie sortiert der „Google-Algorithmus“ die Seiten, die für diesen Begriff relevant sind? Welche Seite wird als Erste aufgeführt, welche als zweite usw., wie wird die Reihenfolge festgelegt? Natürlich kennen wir den Google-Algorithmus nicht in seinen spezifischen Details, er ist ein wohlgehütetes Geheimnis. Aber einiges ist bekannt und auch sehr plausibel – so plausibel, dass man durchaus selbst darauf kommen kann. Zunächst ist plausibel, dass eine Seite umso wichtiger ist, je mehr andere Seiten auf sie verweisen, mit anderen Worten: die Anzahl der „in-links“ ist relevant. Nun sind aber sicher nicht alle in-links gleich wichtig, sondern wiederum sind die links als wichtiger zu bewerten, die ihrerseits von einer „wichtigen“ Seite ausgehen.
Hier kommt eine Art „Rekursion“ ins Spiel, wodurch die Geschichte unübersichtlich wird: Die Wichtigkeiten, die man natürlich auch quantitativ erfassen möchte, hängen voneinander ab und werden von den Wichtigkeiten einer möglicherweise riesigen Anzahl vernetzter Seiten mitbestimmt. Beachtet man, dass es mittlerweile viele Milliarden von in Frage kommenden Seiten gibt, dann erkennt man, dass man es mit einem extrem großen System von quantitativ bewerteten links zu tun hat. Mit diesem System, das sich zudem wegen der Dynamik der Einträge im Internet dauernd verändert, muss ein sinnvoller Algorithmus fertig werden.
Die Annahmen, die wir hier gemacht haben, sind gegenüber den tatsächlichen Verhältnissen, stark vereinfachend. Sie geben trotzdem – im Sinne des algorithmischen Denkens - einen Eindruck von den Ansprüchen und Bedingungen, die ein geeigneter Algorithmus erfüllen muss. Und tatsächlich sind die realen, von Google eingesetzten Algorithmen in der Tat numerisch höchst anspruchsvoll und erfordern die schnellsten verfügbaren Rechner.
Ich möchte Ihnen mit den drei Beispielen eine Idee davon geben, was wir unter algorithmischem Denken verstehen. Es bedeutet zunächst, ein Problem präzise zu formulieren und Lösungsphantasie zu entwickeln. Es bedeutet dann auch, lösungsorientiert zu agieren, den Lösungsprozess in einzelne Schritte zu zerlegen – und technisch ein Verständnis zum Beispiel für Schleifen, Rekursionen, Verzweigungen zu entwickeln. Auch solche algorithmischen Prinzipien lassen sich gut an Beispielen demonstrieren.
Beim Erlernen einer Programmiersprache, sei es Python, Java, eine C-Variante, oder auch eines Tools wie Matlab (für numerische und ingenieurwissenschaftliche Anwendungen) erwirbt man eine formale digitale Qualifikation. Das ist mehr als der Erwerb einer Kompetenz im bloßen Umgang mit einem digitalen Gerät oder Medium. Das Programmieren erfordert und schult strukturiertes, logisches Denken. Eine spezielle mathematische Begabung dagegen benötigt der Programmierer nicht. Doch natürlich gibt es Begabungen und Minderbegabungen für das Erlernen einer Programmiersprache. Die Unterschiede in der Qualifikation professioneller Programmierer sind enorm, was etwa das effiziente, elegante, fehlervermeidende Programmieren angeht.
Warum sollten wir Programmieren als Schulfach einführen?
Wer programmieren kann, ist in der Lage, einen Algorithmus auf einen Rechner zu bringen und damit den Rechner anzuweisen, was zu tun ist. Dazu muss er den Algorithmus allerdings verstanden haben.
Nur mit algorithmischem Verständnis können schließlich die Unsicherheiten und Ängste überwunden werden, die durch unqualifizierte Presse- und Medienberichte eher verstärkt als relativiert werden. Algorithmen als solche sind so wertfrei wie mathematische Formeln. Erst durch ihre Anwendung, ihr Einsatzfeld entscheidet sich, ob sie von Nutzen sind und unser Leben erleichtern – oder ob sie Risiken, Gefahren und unerwünschte, womöglich inhumane Effekte nach sich ziehen.
