Riese, Vieta,
Galilei, Archimedes,
Fermat, Descartes,
Thales, Euler,
Pythagoras, Gödel,
Euklid, Leibniz, Newton,
Heron, Bernoulli,
Cardano, Tartaglia, Taylor,
Lagrange, Strassen,
Fourier, Bolyai, Gauss,
Abel, Noether,
Hilbert, Tarski,
Cantor, Steiner, Klein,
Poincaré, Dedekind,
Apollonius, Pan
RIESIGE FIRMEN verfügen in der Regel über riesige Datenlisten; Kundendateien, Lagerbestands- und Artikellisten sind nur Beispiele. In der Regel sollten solche Listen unbedingt sortiert vorliegen, will man effizient auf sie zugreifen können. Und somit stellt sich die Frage, welche Probleme wohl zu meistern sind, wenn man eine grosse Liste sortieren will. Die ausweichende Antwort lautet: Der Computer sortiert die Daten auf Knopfdruck. Allerdings muss jemand diese Programme schreiben, bevor sie im Alltag nützlich und selbstverständlich werden, und hierzu sind nebst Informatikkenntnissen Kenntnisse in Mathematik nötig.
WENN EIN MATHEMATIKER nach einem Sortierverfahren sucht, dann sucht er nach einem «Algorithmus». Algorithmen sind automatisierbare (und meist programmierbare) Verfahren, die bei einer Problemstellung eines genau definierten Typs durch eine endliche Abfolge unzweideutiger Schritte in endlicher Zeit zu einer Lösung gelangen. Angenommen, wir wollen eine Zahlenliste mit 1000 Einträgen sortieren. Wie lässt sich das bewerkstelligen? Wir können zuerst die erste mit der zweiten Zahl vergleichen und uns die kleinere davon merken. Dann vergleichen wir diese mit der dritten Zahl und merken uns wiederum die kleinere aus diesem Vergleich. Diese vergleichen wir dann mit der vierten Zahl und so weiter. Nach 999 Vergleichen wissen wir auf alle Fälle, welches die kleinste Zahl überhaupt ist, und wir entfernen sie aus der Liste und legen sie beiseite.
DIE LISTE ENTHÄLT nun noch 999 Einträge, und wir können dasselbe Verfahren benutzen, um daraus die kleinste (also die zweitkleinste Zahl überhaupt) zu ermitteln, wozu 998 Vergleiche nötig sind. Alles in allem benötigt dieser Algorithmus (wie man nachrechnen kann) 499 500 Schritte, um die ganze Liste zu sortieren.
IST DAS SCHNELL? Wenn wir annehmen, dass ein Computer pro Sekunde eine Milliarde solcher Schritte ausführen kann, dann ist das überaus schnell. Was aber, wenn die Liste eine Milliarde Einträge enthält? Eine einfache Rechnung zeigt, dass dann 499 999 999 500 000 000 Schritte auszuführen sind, und damit wäre unser Computer über 15 Jahre lang beschäftigt! Daraus wird deutlich: Wir dürfen nicht zufrieden damit sein, für ein bestimmtes Problem einen Algorithmus gefunden zu haben; er muss so gut und so schnell sein, dass er auch beim grössten zu erwartenden Input erfolgreich ist. Der menschlichen Kreativität sind also keine Grenzen gesetzt, wenn es darum geht, noch raffiniertere, noch schnellere Verfahren zu entwickeln zur Lösung all der zahllosen technischen Probleme, die uns im Alltag umgeben.
ÜBRIGENS: Wie viele Schritte benötigen Sie, um die abgebildete Liste berühmter Mathematiker zu sortieren?
Lösung der Kolumne vom 15. Dezember 2009: Jedes primitive Dreieck hat Flächeninhalt 0,5, unabhängig von seiner Form.