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
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.
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.
Fünf Strategien hinter den meisten Algorithmen
Älter als Computer
Algorithmen wurden auf Ton und Papyrus geschrieben, zweitausend Jahre bevor jemand eine Maschine baute, die sie ausführte.