Algorithmen sind in unserem Alltag nicht mehr wegzudenken. Sie werden tagtäglich überall eingesetzt und bestimmen bis zu einem gewissen Grad unseren Alltag. Da ist es gut zu wissen wie sie funktionieren.
Algorithmen 101
Auch für Non-Techies verständlich erklärt
Was sind Algorithmen? Ein Algorithmus ist eine Reihe von Anweisungen zur Ausführung einer Aufgabe. Dies kann bei alltäglichen Dingen genutzt werden (wie z.B. ein Kochrezept) bis zu sehr komplexen Sachverhalten (z.B. Follower Wachstum bei Sozialen Medien). In diesem Artikel gebe ich eine kurze Einführung in Algorithmen (auch für Non-Techies verständlich).
Und wofür brauchen wir die? In unserem Alltag sind Algorithmen nicht mehr wegzudenken. Sie bestimmen mehr oder weniger unser Leben und sind an verschiedensten Orten anzutreffen. Wenn ich ein Videospiel entwickle, kann ich ein KI-System erstellen, welches den Benutzer mithilfe von Graphalgorithmen folgt. Oder ich kann mit "K-Nächste-Nachbarn-Algorithmus" ein Empfehlungssystem entwickeln.
Ein weiteres Beispiel aus dem Alltag: mithilfe des programmierten Algorithms berechnet dein Navigationsgerät die schnellste/kürzeste Route zu deinem Ziel. Und wenn du weniger in Staus stehst, dann hast du das dem Algo zu verdanken, denn der prognostiziert Staus und lässt dich diese vorher umfahren (funktioniert leider nicht immer so gut wie erwünscht).
Besonders oft begegnest du dem Algorithmus auf Sozialen Medien wie Facebook, Instagram & Co. Wenn man z.B. viele Katzenbilder liked, dann "merkt" sich das der Algorithmus. Dieser empfiehlt dir dann weiteren Inhalt, welche Katzenbilder enthält.
Und wer hats erfunden? In diesem Fall kein Schweizer. Das Wort Algorithmus ist eine lateinische Abwandlung des persischen Astronomen und Rechenmeisters Muhammad al-Khwarizmi ("Algorismi"), der im 9. Jahrhundert n. Chr. gelebt hat. Sein Lehrbuch "Über die indischen Ziffern", gilt als die wichtigste Quelle des indisch-arabischen Zahlensystems und des schriftlichen Rechnens. Ada Lovelace war 1843 dann die erste Person, die einen für einen Computer gedachten Algorithmus niederschrieb. Sie gilt als die erste Programmiererin der Geschichte.
Heute sind Algorithmen eines der wichtigsten Themen der Informatik und Mathematik. Schlaue Köpfe programmieren sie und geben vor wie sie in Form von Programmen und elektronischen Schaltkreisen Computer und Maschinen steuern sollen. Vor allem werden Algorithmen genutzt, um Probleme zu lösen. Oder bestehende Lösungen effizienter zu gestalten. Damit Sie sich ein besseres Bild davon machen können, stelle ich Ihnen zwei einfache Algorithmen vor und deren Nutzen. Es handelt sich dabei um den 'Simple Search' und 'Binary Search' Algorithmus.
Simple Search
Stupid search würde besser passen
Gehen wir davon aus, ich muss einen Freund anrufen, nennen wir ihn Larry. Ich habe seine Telefonnummer nicht in meinem Gedächtnis gespeichert (wer macht das schon?). Ich suche im Telefonbuch nach Larry's Nummer. Man könnte nun von der ersten Seite anfangen und von da an jede Seite einzeln blättern bis ich bei Larry bin. Aber wahrscheinlicher ist, dass ich das Telefonbuch etwa in der Mitte aufschlage und von dort aus suche. Da ich weiss, dass das Telefonbuch nach Alphabet sortiert ist und der Buchstabe "L" etwa in der Mitte ist.
Oder gehen wir davon aus ich suche ein Wort in einem Wörterbuch welches mit "M" anfängt. Auch hier sind die Chancen hoch, dass ich in der Mitte anfange und nicht zu Beginn.
Ein gängigeres Szenario. Ich logge mich bei Facebook ein um mir ein paar Katzenvideos anzusehen. Mein Benutzername ist the-notorious-c.a.t. Nun muss Facebook verifizieren, dass es mich unter diesem Benutzernamen gibt. Und somit sucht es nach diesem Namen in der Datenbank. Auch hier könnte Facebook bei "A" beginnen und von dort aus suchen. Da Facebook mittlerweile 2.936 Milliarden Nutzer hat, könnte dies etwas länger dauern (und ich habe wenig Geduld).
Nun eine kleine Aufgabe, welche man mit Simple Search lösen könnte:
Ich denke mir eine Zahl aus zwischen 1 und 100 (inklusive). Du musst jetzt raten welche Zahl ich ausgesucht habe. Dein Ziel ist es mit so wenig Schätzungen wie möglich meine Zahl zu erraten. Ich werde immer nur antworten, ob die geschätzte Zahl zu hoch oder zu tief ist. Nun mit dem Simple Search Algorithmus kann man einfach bei 1 beginnen und raufzählen bis zur gedachten Zahl. Oder man beginnt bei 100 und zählt von dort rückwärts. Blöd nur, dass man mit diesem Algorithmus im schlimmsten Fall 100 mal raten muss. Sprich 100 Schritte. Das heisst, bei Simple Search wächst die Anzahl an Schritten mit der Anzahl an Elementen (in den meisten Fällen Reihen in einer Datenbank). Im Falle von Facebook wären das 2.936 Milliarden Schätzungen!
Binary Search
Der erfolgreiche und besser aussehende Bruder von Simple Search
Der Binary Search (zu Deutsch: Binär Suche) ist der etwas effizientere Algorithmus verglichen zum Simple Search. Der Input ist eine sortierte Liste von Elementen. Ich erkläre gleich warum die Liste sortiert sein muss. Wenn das gesuchte Element in der Liste existiert, erhält man die Position. Wenn nicht, returned der Algorithmus null.
Der Binary Search wurde so getauft weil er immer die Hälfte der Liste nimmt und fragt, ob das Element dort drinnen ist. Wenn ja verwirft er die andere Hälfte. Wenn nein verwirft er diese Hälfte und behält die andere. Testen wir den Binary Search mit der oben genannten Aufgabe von Simple Search.
Ich denke mir wieder eine Zahl zwischen 1 und 100 (inklusive) aus. Diesmal springt der Algorithmus direkt in die Mitte bei 50. Ich sage z.B. zu tief und der Algorithmus wirft die Zahlen 1 - 50 weg. Die Hälfte der Elemente wurden gerade eliminiert! Nun die nächste Schätzung ist 75 (die Mitte von 51 - 100). Ich sage zu hoch. Und wieder wirft er die Hälfte der Zahlen weg (75 - 100). Dieses Spiel machen wir weiter bis die Zahl gefunden wurde. Gratuliere, du hast deinen ersten Algorithmus gelernt (Simple Search zählt nicht).
Was ist nun der grosse Unterschied? Bei Simple Search hat man in diesem Beispiel bis zu 100 Schritten um das Element zu finden. Bei Binary Search sind es maximal 7 Schritte! Das sind 93 Schritte weniger. Aber der Binary Search entfaltet seine Macht bei grösseren Mengen. Zum Beispiel bei 240'000 Elementen. Mit Simple Search hätte man hier im schlimmsten Fall 240'000 Schritte. Mit dem Binary sind es maximal 18. What?!
Generell gesehen für eine Liste mit n Elementen, braucht der Binary Search log2 n Schritte im schlimmsten Fall. Der Simple Search braucht hingegen n Schritte im schlimmsten Fall (also so gross wie die Liste selbst). Dies funktioniert aber nur wenn die Liste sortiert ist. Im Beispiel von der Zahlenfolge 1 - 100 würde der Algorithmus "brechen" da in der Mitte vielleicht die Zahl 32 wäre.
Running Time
Wie siehts in der Praxis aus?
Die Laufzeit (engl.: Running Time) bei Algorithmen wächst mit unterschiedlichen Raten. Was das heisst? Ein kleines Beispiel: Sophie schreibt einen Algorithmus für die NASA. Ihr Algorithmus startet wenn die Rakete auf dem Mond landet, und hilft bei Kalkulationen wo das Ding landen soll. Sophie muss sich zwischen Simple Search und Binary Search entscheiden. Der Algorithmus muss schnell und exakt (korrekt) sein.
Einerseits ist Binary Search schneller. Und Sophie hat nur 10 Sekunden um herauszufinden wo es landen soll, ansonsten verliert die Rakete den Kurs. Andererseits ist Simple Search einfacher zu programmieren und ist weniger anfällig für Bugs. Und Sophie will wirklich keine Bugs in ihrem Code, welche eine Rakete landen soll! Um ganz sicher zu gehen, testet sie beide Algorithmen aus.
Gehen wir davon aus, dass es 1 Millisekunde dauert um ein Element zu prüfen. Mit Simple Search muss Sophie 100 Elemente prüfen. Somit dauert dies 100 ms. Mit Binary Search muss sie 7 Elemente prüfen (log2 100 ist etwa 7). Das sind 7 ms mit dem Binary Search. Realistisch gesehen wird die Liste aber um die 1 Milliarde Elemente besitzen. Wie lange wird das für die beiden Algorithmen dauern? Mit dem Binary Search sind es 30 ms (log2 1'000'000'000 sind etwa 30). Ein Denkfehler der sich hier einschleichen könnte, wäre zu glauben, dass Binary Search 15 Mal schneller ist als Simple Search.
Weil bei 100 Elementen der Binary Search 15 Mal schneller war als der Simple Search. Und somit wären das 450 (30 x 15) ms bei 1 Milliarde Elementen, oder? Nicht einmal vielleicht. Erinnern wir uns, dass der Simple Search im schlimmsten Fall n Schritte braucht, also so gross wie die Liste. Bei 1 Milliarde Elementen sind das 1 Milliarde Schritte, resp. Millisekunden. Das sind 11 Tage!
Die Entscheidung ist nach diesen Zahlen leichter gefallen.
Abschluss
Heute etwas gelernt?
Ich hoffe mit diesem Artikel konnte ich eine angenehme Einführung in Algorithmen bieten. Nun hast du nicht nur gelernt was Algorithmen sind und wo wir sie brauchen sondern kennst auch zwei bei ihrem Namen. Hiermit hast du intellektuellen Erzählstoff für das Feierabend Bier (thank me later).
Leseratte? Hier haben wir noch weitere spannende Artikel von unserem Redaktionsteam:
ISO 9001:2015 an me - it's complicated...