Was ein Algorithmus ist

Das Verfahren für den größten gemeinsamen Teiler aus Buch VII von Euklids Elementen, geschrieben vor etwa 2300 Jahren, läuft bis heute in Computern.

Ein Verfahren, das immer funktioniert

Angenommen, du suchst die größte Zahl, die sowohl 1071 als auch 462 teilt. Du könntest jede Zahl von 462 abwärts bis 1 probieren und bei der ersten aufhören, die beide teilt. Das funktioniert, braucht aber vielleicht Hunderte Versuche. Es geht kürzer. Teile 1071 durch 462 und behalte den Rest, 147. Teile jetzt 462 durch 147 und behalte den Rest, 21. Teile 147 durch 21: Der Rest ist 0, also ist die Antwort 21. Drei Divisionen statt mehrerer Hundert.

Dieser kürzere Weg ist ein Algorithmus: eine endliche Liste genauer Schritte, die eine Eingabe nimmt und die richtige Ausgabe liefert. Dieser hier ist der euklidische Algorithmus für den größten gemeinsamen Teiler, und er steht in Buch VII der Elemente, geschrieben um 300 v. Chr. Euklid beschrieb ihn mit wiederholtem Abziehen von Strecken statt mit Division, aber die Idee ist dieselbe, und die Version mit Resten verwenden Programme heute.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // Rest
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

Was eine Liste von Schritten zum Algorithmus macht

Lehrbücher wie das von Cormen, Leiserson, Rivest und Stein beschreiben einen Algorithmus als genau festgelegtes Verfahren, das eine Eingabe in eine Ausgabe verwandelt. In dieser Beschreibung stecken drei Dinge, und jedes zählt, wenn du Code schreibst.

• Genau. Jeder Schritt bedeutet eine Sache. „Teile a durch b und behalte den Rest“ ist genau, „mach die Zahlen irgendwie kleiner“ nicht.
• Endlich. Er muss anhalten. Beim euklidischen Algorithmus ist der Rest immer kleiner als die Zahl, durch die geteilt wurde. Er schrumpft also jede Runde und muss 0 erreichen.
• Korrekt. Für jede erlaubte Eingabe ist die Ausgabe die richtige Antwort, nicht nur für die Beispiele, die du ausprobiert hast.

Oft wird ein Kochrezept als Alltagsbeispiel genannt, und das passt: Die Zutaten sind die Eingabe, das Gericht die Ausgabe, und die Schritte haben eine Reihenfolge. Der Unterschied ist, wie viel der Leser selbst ergänzt. Ein Koch entscheidet, was „eine Prise“ bedeutet. Ein Computer entscheidet nichts. Deshalb werden Algorithmen für Computer mit jedem Schritt ausgeschrieben.

Gleiches Problem, verschiedene Algorithmen

Für ein Problem gibt es meist viele korrekte Algorithmen, und sie können sich enorm darin unterscheiden, wie viel Arbeit sie machen. Für den größten gemeinsamen Teiler von 1071 und 462 braucht das Durchprobieren jeder Zahl ab 462 abwärts 442 Versuche, bis es bei 21 ankommt, das Verfahren von Euklid dagegen 3 Divisionen. Beide sind korrekt. Nur eines ist schnell. Um diese zweite Frage geht es in diesem Kurs zu einem großen Teil: Wenn ein Verfahren korrekt ist, wie viele Schritte braucht es, und wie wächst diese Zahl, wenn die Eingabe größer wird?

Um das zu beantworten, zählen Informatiker Grundschritte (einen Vergleich, eine Vertauschung, eine Division) statt Sekunden. Sekunden hängen von der Maschine ab. Die Zahl der Schritte hängt nur vom Algorithmus und von der Eingabe ab, damit lassen sich zwei Verfahren fair vergleichen. Das Labor unten zählt beim Sortieren einer Reihe von Balken die Vergleiche für dich. Probier dieselbe Startreihenfolge mit zwei verschiedenen Verfahren und beobachte die Zähler.

Eingaben, Ausgaben und die Schritte dazwischen

Bevor du einen Algorithmus schreibst, schreib genau auf, was hineingeht und was herauskommen muss. Beim größten gemeinsamen Teiler: Die Eingabe sind zwei positive ganze Zahlen, die Ausgabe ist eine ganze Zahl, die beide teilt, wobei keine größere Zahl das auch tut. Diese Beschreibung sagt dir, wie du das Ergebnis testest, und deutet oft schon die Schritte an. Sie zeigt auch die Randfälle: Was, wenn eine Zahl 0 ist? (Die Schleife oben gibt dann die andere Zahl zurück, und das ist die richtige Antwort.) Was, wenn beide Zahlen gleich sind? Wer vor dem Ausführen über Randfälle nachdenkt, findet viele Fehler.