LERNLEITFADEN · ETWA 12 MIN LESEZEIT

Algorithmen

Ein Algorithmus ist ein genaues Rezept zur Lösung eines Problems. Ein guter macht aus hundert Schritten sieben. Wählen Sie eine geheime Zahl und sehen Sie zu, wie die binäre Suche sie findet, indem sie den Bereich jedes Mal halbiert.

BINÄRE SUCHE · 1 BIS 100
1100
Bereich 1-100. Erster Tipp: die Mitte.
Nie mehr als 7 Tipps für 100 Zahlen.

Was ein Algorithmus ist, kurz gesagt

Ein Algorithmus ist eine endliche, eindeutige Folge von Schritten, die eine Eingabe in eine Ausgabe verwandelt, etwa eine Liste in eine sortierte Liste oder zwei Orte in den kürzesten Weg dazwischen. Algorithmen zu studieren heißt, diese Schritte zu entwerfen und zu messen, wie ihr Aufwand mit der Eingabegröße wächst.

Das Wort stammt von al-Chwārizmī, einem persischen Mathematiker des 9. Jahrhunderts in Bagdad, dessen latinisierter Name Algoritmi zum Begriff für das Rechnen mit indisch-arabischen Ziffern wurde.

Muss sein
Endlich, präzise, ausführbar, mit klarer Ein- und Ausgabe
Gemessen an
Zeit und Speicher bei wachsender Eingabe (O-Notation)
Ältester bekannter
Euklids ggT-Verfahren, um 300 v. Chr.
Nicht dasselbe wie
Ein Programm, das nur eine Umsetzung davon ist
KERNKONZEPT

Dieselbe Liste, drei Arten, sie zu sortieren

Sortieren ist das klassische Algorithmenproblem. Wählen Sie ein Verfahren und spielen Sie es ab. Beobachten Sie die Zähler: Verschiedene Strategien leisten bei denselben zehn Zahlen sehr unterschiedlich viel Arbeit.

62941017385
Zehn unsortierte Zahlen. Drücken Sie Play oder gehen Sie schrittweise vor.
0Vergleiche
0Tausche
BubblesortWiederholt Nachbarn vergleichen und tauschen, wenn sie falsch herum stehen. Große Zahlen „blubbern“ ans Ende.O(n²): einfach, aber langsam
Vergleichan endgültiger Stellewartet
O-NOTATION

Warum Wachstum wichtiger ist als Tempo

Die O-Notation beschreibt, wie die Zahl der Schritte mit der Eingabegröße n wächst. Schieben Sie n hoch und sehen Sie, wie lange jede Art von Algorithmus auf einem Rechner mit einer Milliarde Schritten pro Sekunde bräuchte.

O(1)Array-Zugriff1 ns
O(log n)binäre Suche6 ns
O(n)lineare Suche86 ns
O(n log n)Mergesort553 ns
O(n²)Bubblesort7.4 µs
O(2ⁿ)Brute-Force-Teilmengen10^9 years
Die Balken nutzen eine logarithmische Skala; sonst wären alle außer dem letzten unsichtbar. Die Zeiten setzen genau n, n² usw. Schritte bei 10⁹ Schritten pro Sekunde voraus.
ENTWURFSPARADIGMEN

Fünf Strategien hinter den meisten Algorithmen

STRATEGIEDIE IDEEBEGEGNET IHNEN IN
Teile und herrscheDas Problem halbieren, jede Hälfte lösen, die Antworten zusammenführen.Mergesort, binäre Suche, schnelle Multiplikation
GierigIn jedem Schritt die beste Option wählen und nie zurückschauen. Schnell, aber nicht immer optimal.Wechselgeld mit Münzen, Dijkstras kürzeste Wege
Dynamische ProgrammierungEin Problem in überlappende Teilprobleme zerlegen und jede Antwort speichern, damit sie nur einmal berechnet wird.Editierdistanz bei der Rechtschreibprüfung, Routenplanung, DNA-Alignment
GraphensucheVerbindungen systematisch erkunden, in die Breite oder in die Tiefe.Karten, soziale Netzwerke, Labyrinthe und Rätsel
Brute ForceJede Möglichkeit ausprobieren. Funktioniert garantiert, ist oft viel zu langsam.Kurze Passwörter knacken, kleine Rätsel, andere Algorithmen testen

Älter als Computer

Algorithmen wurden auf Ton und Papyrus geschrieben, zweitausend Jahre bevor jemand eine Maschine baute, die sie ausführte.

um 1600 v. Chr.Babylonische TontafelnSchrittweise Verfahren für Division und Quadratwurzeln, in Ton gedrückt.
um 300 v. Chr.Euklidischer AlgorithmusFindet den größten gemeinsamen Teiler zweier Zahlen. Wird bis heute in der Kryptografie genutzt.
c. 820Al-KhwārizmīSeine Bücher über indisch-arabisches Rechnen gaben uns das Wort „Algorithmus“.
1959QuicksortTony Hoares Sortierverfahren, in der Praxis noch immer eines der schnellsten.
1977RSADie Public-Key-Verschlüsselung von Rivest, Shamir und Adleman machte sichere Onlinezahlungen möglich.
1998PageRankLarry Page und Sergey Brin ordneten Webseiten nach den Links, die auf sie zeigen.

Weiterlesen

Introduction to Algorithms· Cormen, Leiserson, Rivest & Stein1990
The Art of Computer Programming· Donald Knuth1968-
Grokking Algorithms· Aditya Bhargava2016
Algorithms to Live By· Brian Christian & Tom Griffiths2016

Algorithmisches Denken ist logisches Denken. Messen Sie Ihres.

Unser vollständiger IQ-Test deckt logisches, numerisches, sprachliches und räumliches Denken ab: 60 Fragen, etwa 30 Minuten.

Vollständigen IQ-Test machen