In der vergangenen Woche haben wir uns ganz allgemein mit Algorithmen beschäftigt. Doch wie werden Algorithmen konstruiert? Wie sind sie aufgebaut? Das wollen wir an Hand von zwei Anwendungen erläutern und in Teil 2 unserer prisma-Serie deutlich machen, dass man sich algorithmisches Verständnis und eine algorithmische Denkweise recht einfach zu eigen machen kann.
Ein praktisches Beispiel für die Arbeit von Algorithmen ist das Sortieren. Jeder Mensch hat eine intuitive Vorstellung davon, wie Objekte sortiert werden können, seien es Spielkarten, Namen oder Zahlen. Wir stellen jetzt unserem Computer die Aufgabe, die Bücher in einem Regal alphabetisch nach Autorennamen zu sortieren. Klingt einfach. Ist es eigentlich auch.
Dazu brauchen wir einen Algorithmus. Als Erstes muss der beim Vergleich von zwei Namen entscheiden können, welcher Name vor dem anderen platziert wird. Dann können wir wie folgt verfahren: Wir fangen vorne an, vergleichen den ersten mit dem zweiten Namen, ordnen sie alphabetisch, vergleichen dann den (eventuell neuen) zweiten mit dem dritten Namen, ordnen sie alphabetisch, vergleichen den (eventuell neuen) dritten mit dem vierten und fahren so fort, bis wir das Ende der Liste erreicht haben.
Die neue Liste ist nun noch nicht vollständig alphabetisch, aber wir stellen fest, dass der letzte Name wirklich der alphabetisch gesehen letzte ist. Dass das so sein muss, ist eine kleine Denksportaufgabe: Wem diese Überlegung zu mühsam ist, der probiert es einfach aus – etwa mit Namenskärtchen oder Spielkarten. Nun muss der Algorithmus mit der Liste wieder vorne anfangen. Er vergleicht und sortiert den ersten und den zweiten Namen, den zweiten und den dritten und so weiter, bis er am vorletzten Namen angekommen ist: Der ist dann auch der vorletzte im Alphabet – mit der gleichen Überlegung wie oben. Im dritten Durchlauf ergibt sich dann als drittletzter Name der alphabetisch richtige. Und so geht es weiter, Durchlauf für Durchlauf, bis am Ende nur noch der erste mit dem zweiten Namen verglichen und eventuell vertauscht wird. Damit ist der Algorithmus beendet – und die Liste ist vollständig sortiert.
Googles berühmter “PageRank”
Die Erfahrung zeigt, dass Schüler diesen Algorithmus (in der Informatik als “Bubblesort” bekannt) schon in der Grundschule verstehen können und dass ihn meist einige von ihnen sogar selbst “erfinden”. In der Praxis aber spielt er keine große Rolle, weil es bessere, schnellere Algorithmen für die gleiche Aufgabe gibt. Bubblesort ist aber geeignet, eine Ahnung von der algorithmischen Denkweise zu vermitteln, und lässt sich mit einer Programmiersprache in wenigen Zeilen programmieren.
Ein weiteres Beispiel für einen Algorithmus ist der sogenannte “PageRank”. Gibt man bei Goo gle einen Begriff ein, sortiert der “Google-Algorithmus” die Seiten, die für diesen Begriff von Bedeutung sind. Doch wie wird die Reihenfolge der Suchergebnisse festgelegt? Natürlich kennen wir den “Page Rank”- Algorithmus nicht in all seinen Details, er ist ein von Google wohlgehütetes Betriebsgeheimnis. Aber einiges ist bekannt und 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 wesentlich. 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 etwas ins Spiel, das die Informatiker “Rekursion” nennen, wodurch die Angelegenheit unübersichtlich zu werden scheint: Die Wichtigkeiten hängen voneinander ab – und werden von den Wichtigkeiten einer möglicherweise riesigen Anzahl vernetzter Seiten mitbestimmt. Macht man sich klar, dass es mittlerweile viele Milliarden von in Frage kommenden Seiten gibt, kann man sich vorstellen, dass man es mit einem extrem großen System von bewerteten Links zu tun hat. Mit diesem System, das sich zudem wegen der Dynamik des Internets dauernd verändert, muss ein brauchbarer Algorithmus fertig werden.
Auch Algorithmen können lernen
Die Annahmen, die wir hier gemacht haben, sind stark vereinfacht. Die tatsächlichen Algorithmen berücksichtigen eine Vielzahl (Hunderte) weiterer Bedingungen (“Parameter”). Schließlich – und das ist faszinierend und in seinen Auswirkungen zugleich vielleicht nicht unbedenklich – berücksichtigen sie die Vorgeschichte, das individuelle Suchverhalten – und damit die Gewohnheiten und die vermuteten Interessen des Nutzers. Mit diesem Element der Individualisierung, das wir von der – vielleicht oft nützlichen, aber manchmal auch nervigen – Empfehlungsformulierung “Das könnte Sie auch interessieren …” kennen, gehört der entsprechend erweiterte PageRank-Algorithmus zu den sich anpassenden, “selbstlernenden” Algorithmen.
