Zum Inhalt springen

Digital Was ist ein Algorithmus?

Ob es um Data Mining, Big Data oder generell Computer- und Informations-Technologie geht: Der Begriff «Algorithmus» fällt früher oder später. Woher kommt er und was bedeutet er?

Schwarze und weisse Kreise und Dreiecke.
Legende: Ein Algorithmus, der Formen zeichnet: Mit allerlei Werten gefüttert, entstehen durch die Berechnung unterschiedliche Strukturen – mal geordnet, mal chaotisch. Flickr/jm_escalante

Wortherkunft

Das Wort «Algorithmus, Link öffnet in einem neuen Fenster» stammt vom Mathematiker und Universalgelehrten Abu Dscha'far Muhammad ibn Musa al-Chwarizmi. Al-Chwarizmi, Link öffnet in einem neuen Fenster lebte um 800 n. Chr. in Bagdad und verfasste ein Standardwerk mit einer Sammlung mathematischer Methoden. Er stammte aus Choresmien, Link öffnet in einem neuen Fenster, der Gegend südlich des Aral-Sees. Deshalb wurde er «al-Chwarizmi» genannt. Die lateinischen Übersetzer seines Werkes schrieben diesen Namen in «Algorismi» um. Mit «Rhythmus» hat Algorithmus also nichts zu tun.

Definition

Ein Algorithmus ist eine Handlungsanweisung, ein Rezept, um ein bestimmtes Problem zu lösen.

Die Anweisung muss eine endliche Anzahl einzelner Schritte haben: Sie muss irgendwann fertig werden. Nach dem Abschluss eines einzelnen Schrittes muss immer klar sein, welches der nächste Schritt ist. Ein einfacher Algorithmus soll ausserdem «determiniert» sein: Bei gleichen Anfangsbedingungen soll hinten das gleiche Ergebnis herauskommen (siehe dazu Diskussion unten).

Beispiel

Ein Verfahren von Euklid, Link öffnet in einem neuen Fenster gilt als der älteste überlieferte Algorithmus. Das damit zu lösende Problem: Den grössten gemeinsamen Teiler von zwei Zahlen zu finden. Man erinnernt sich vielleicht aus der Schule an diesen «GGT».

Die Anweisung geht so: Man nehme die grössere der zwei Zahlen, teile sie durch die kleinere und behalte den Rest. Dann nehme man den Teiler, teile diesen wiederum durch den soeben errechneten Rest und rechne auch hier den Rest aus. Das wiederhole man nun so lange, bis die Teilung aufgeht, also der Rest Null ist. Der letzte Teiler ist dann der grösste gemeinsame Teiler «GGT».

Euklid lieferte mit diesem Algorithmus also eine Schritt-für-Schritt-Anleitung, wie man den «GGT» ausrechnet.

Bedeutung

Algorithmen sind eng verknüpft mit der Entstehung der Computer. Die Countess of Lovelace, Augusta Ada Byron King – oder kürzer: Ada Lovelace , Link öffnet in einem neuen Fenster– gilt als die erste Programmiererin. Denn schon hundert Jahre bevor der erste Computer gebaut war, dachte sie sich einen Algorithmus spezifisch für einen solchen Computer aus.

Algorithmen beschäftigten auch die Mathematiker des 19. und 20. Jahrhunderts. Denn mathematisch war das Konzept schwer fassbar, zu ungenau definiert. Beispielsweise die Vorgabe, dass ein Algorithmus fertig werden muss: Wie kann man das eigentlich wissen? Also mathematisch beweisen, ob ein Algorithmus einfach sehr, sehr lange braucht, oder ob er unendlich lange läuft, also keine Antwort findet?

Auf der Suche nach der Lösung dieser und ähnlicher Fragen entwickelte der Brite Alan Turing die Turing-Maschine, Link öffnet in einem neuen Fenster. Und dieses abstrakte Konzept wurde dann in reale Maschinen umgesetzt, die ersten Computer der 40er-Jahre.

Ein Computerprogramm ist also ein Algorithmus – oder mehrere Algorithmen, die sich gegenseitig mit Ein- und Ausgaben füttern.

Heute und morgen

Seither sind Jahre vergangen und Computer schneller und schneller geworden. Entsprechend sind immer komplexere Algorithmen möglich. Und zwar nicht nur in der Art und Weise, wie sie rechnen; sondern auch darin, wie viel Eingabe sie verarbeiten können.

So arbeiten moderne Algorithmen nicht mehr nur mit ein, zwei Zahlen. Sondern sie verschlucken riesige Berge von Daten. Sie durchsuchen diese Daten, sortieren, gewichten. Wie Google, deren Algorithmen wissen, was wir suchen; oder Amazon, das uns Bücher vorschlägt; oder Facebook, das alte Freunde neu ausgräbt.

Und sie machen ein grosses Versprechen: Beim Durchwühlen dieser Datenberge können die Algorithmen Zusammenhänge entdecken, auf die wir selber nicht gestossen wären. Die Maschinen lernen: Sie zeigen uns Dinge, die wir ihnen nicht so beigebracht haben.

So kann ein komplexer Algorithmus im Datenberg Zusammenhänge entdecken und folglich auch Ereignisse vorhersagen, ohne zu wissen, warum sie genau passieren.

Das bedeutet, dass es eine Verschiebung weg von Kausalität hin zu Korrelation gibt. Es gilt nicht mehr: Weil A passiert, passiert auch B. Sondern nur noch: Passiert A, passiert wahrscheinlich auch B. Also beispielsweise so wie bei den Buchempfehlungen von Amazon: Der Algorithmus weiss, dass wir auch dieses Buch interessant finden. Aber nicht, warum.

Rechenbeispiel GGT

Was ist der GGT von 48 und 30?

48 / 30 = 1, Rest 18
30 / 18 = 1, Rest 12
18 / 12 = 1, Rest 6
12 / 6 = 2, Rest 0

Der GGT ist also: 6.

Big Data und Überwachung

Big Data und Überwachung

Das digitale Ich ist unser Doppelgänger im Datenmeer. Firmen, Staaten und auch Geheimdienste haben Zugriff auf unsere Daten. Was das bedeutet, beleuchtet unser Schwerpunkt.

8 Kommentare

Navigation aufklappen Navigation zuklappen

Sie sind angemeldet als Who ? (whoareyou) (abmelden)

Teilen Sie Ihre Meinung... anwählen um einen Kommentar zu schreiben

Wir haben Ihren Kommentar erhalten und werden ihn nach Prüfung freischalten.

Einen Kommentar schreiben

Bitte beachten Sie unsere Netiquette verfügbar sind noch 500 Zeichen

Es ist ein Fehler aufgetreten. Bitte versuchen Sie es erneut.

  • Kommentar von Daniel Specht, Zürich
    Die Aussage des Professors das die Computer uns gezwungen hätten Milliarden wegen dem Millennium-Problems zu investieren halte ich für etwas verzerrt. Anfang der 70er Jahre wählten die UNIX Macher den 1.1.70 als Ausgangspunkt für die Zeitrechnung in einem Computer. Dieser wird bis heute verwendet. Digitale Rechner zählen die Zeit die seither vergangen ist doch sie können nicht ewig zählen. Man könnte auch daher auch sagen das man es verpasst hat ein geeigneteres System zu entwickeln.
    Ablehnen den Kommentar ablehnen Antworten anwählen um auf den Kommentar zu antworten
  • Kommentar von Corrigendum, Zürich
    Da pflichte ich Ihnen bei! Ich denke aber, es spricht nichts dagegen, die Bedingung «determiniert» fallenzulassen. Ich traue mir zwar keine abschliessende Festlegung zu, würde aber sagen, dass Sie damit sämtliche Klassen abdecken.
    Ablehnen den Kommentar ablehnen Antworten anwählen um auf den Kommentar zu antworten
  • Kommentar von Corrigendum, Zürich
    Lieber Herr Berger, Ich mag Ihre Beiträge im Allgemeinen, in diesem spezifischen Fall stossen Sie aber wohl etwas an Ihre Grenzen: 1) Randomisierte Algorithmen, die eben gerade nicht determiniert sind, sind in Wissenschaft und Industrie extrem weit verbreitet. 2) Kausalität ist auch für uns Menschen nicht absolut feststellbar, unser Wissen basiert ebenfalls auf Korrelationen. Damit sollte auch klar sein, dass Ihr letzter Absatz der Mächtigkeit von Algorithmen nicht gerecht wird.
    Ablehnen den Kommentar ablehnen Antworten anwählen um auf den Kommentar zu antworten
    1. Antwort von Guido Berger
      Merci! Soviel ich weiss, gibt es bei verschiedenen modernen Formen des Algorithmus Diskussionen, ob die strenge Definition noch passt. Nicht nur bei solchen mit Zufallselementen, sondern auch bei solchen, die z.B. auf User-Input warten (womit auch unklar ist, wann sie fertig werden). Zumindest bei Zufalls-Generatoren könnte man die Definition doch retten, wenn man sagt, dass der Zufallsgenerator auch ein Algorithmus ist, der Input nimmt (geseedet wird), und einen Output generiert, der dann determiniert ist. Und dass die Grenze zwischen Kausalität und Korrelation möglicherweise fliessend ist, ist mir klar. Für die Diskussion scheint mir hier aber die Vereinfachung zulässig zu sein. Denn die Data Miner suchen (im Gegensatz zu traditioneller Wissenschaft) nicht mehr nach Erklärungen für eine Korrelation. Solange die Korrelation stark genug ist, ist man schon zufrieden.
      Ablehnen den Kommentar ablehnen
    2. Antwort von Corrigendum, Zürich
      Woher haben Sie denn Ihre Definition? Um mit randomisierten Algorithmen umzugehen, gibt es das Konzept der probabilistischen Turingmaschine; damit muss keine Implementation der Zufallselemente modelliert werden (was übrigens der Idee eines Algorithmus als idealisierte Vorschrift widerspräche). Den zweiten Einwand ziehe ich in Anbetracht Ihres Hinweises auf Vereinfachung zurück, obschon ich die Formulierung als irreführend empfinde.
      Ablehnen den Kommentar ablehnen
    3. Antwort von Guido Berger
      Wenn ich Sie richtig verstehe, stossen Sie sich an der Formulierung «Ein Algorithmus muss determiniert sein». Dagegen sehen Sie zwei Klassen von Algorithmen, eben determinierte und dazu randomisierte. Und ja, hier (und spätestens bei der probabilistischen Turingmaschine) streifen Sie meine Grenzen. Und zwar deshalb: Ist ein randomisierter Algorithmus und ein determinierter, der jedesmal leicht andere Ausgangswerte erhält, nicht das Gleiche? Ist das eine unzulässige Vereinfachung?
      Ablehnen den Kommentar ablehnen
    4. Antwort von Corrigendum, Zürich
      Stellen Sie sich eine Stadtkarte vor: Sie wollen von Punkt A nach Punkt B gelangen. Im deterministischen Fall stehen die Regeln (der Algorithmus), nach welchen Sie den Weg wählen, im Voraus fest; randomisieren Sie hingegen, beinflusst der Zufall Ihre Wahl des Weges mit. Dies mag sinnlos klingen, führt aber in vielen Fällen zu einer Effizienzsteigerung und/oder Vereinfachung des Verfahrens. Ihre Vereinfachung ist insofern unzulässig, als dass rand. Startpos. dies eben gerade nicht erreichen.
      Ablehnen den Kommentar ablehnen
    5. Antwort von Guido Berger
      Ok. Ich habe die absolute Formulierung des Satzes abgeschwächt, um andere Klassen von Algorithmen nicht auszuschliessen. Als weiterführende Frage (wenn Sie noch mögen): Ist es nicht störend, wenn es zwei, drei Klassen gibt, die man aufzählen muss? Müsste nicht eine Definition nicht möglich sein, die alle Klassen umfasst? Muss man zu diesem Zweck evtl. die Bedingung «determiniert» einfach ersatzlos streichen?
      Ablehnen den Kommentar ablehnen