Algorithmus

Ein Algorithmus ist eine schrittweise Sequenz von elementaren Anweisungen, die in Form eines Programms von einem Computer umgesetzt werden kann.

Eine Reihe von Anweisungen muss die folgenden Bedingungen erfüllen, um als Algorithmus zu gelten:

Endlichkeit

Der Algorithmus muss in endlich vielen Schritten beschrieben werden können.

Eindeutigkeit

Zu jedem Zeitpunkt in der Abarbeitung des Algorithmus muss klar sein, was der nächste Schritt ist.

Außerdem muss bei jedem Schritt eindeutig sein, wie dieser auszuführen ist. Das wird manchmal auch Ausführbarkeit genannt.

Terminiertheit

Wenn er ausgeführt wird, muss der Algorithmus zu einem Ende kommen.

Determiniertheit

Wenn ein Algorithmus zweimal dieselbe Eingabe bekommt, muss er zweimal dasselbe Ergebnis liefern.

Determinismus

Wenn ein Algorithmus zweimal dieselbe Eingabe bekommt, läuft er beide Male exakt gleich ab

Algorithmen können entweder textuell oder in einem Pseudocode beschrieben werden oder grafisch dargestellt werden, etwa in Form von Programmablaufplänen.

Beispiele

Ein schnelles Kuchenrezept

1. Nimm eine große Tasse.
2. Gib drei Esslöffel Kakaopulver in die Tasse.
3. Gib zwei Eier in die Tasse.
4. Gib vier Esslöffel Mehl in die Tasse.
5. Gib vier Esslöffel Zucker in die Tasse.
6. Gib vier Esslöffel Milch in die Tasse.
7. Gib vier Esslöffel in die Tasse.
8. Verrühre den Inhalt der Tasse gründlich.
9. Öffne die Mikrowelle.
10. Stelle die Tasse in die Mikrowelle.
11. Schließe die Mikrowelle.
12. Lass die Mikrowelle 5 Minuten lang bei 900 Watt laufen.
13. Öffne die Mikrowelle.
14. Nimm die Tasse aus der Mikrowelle.

Multiplizieren (wenn du nur addieren kannst)

Gegeben

Zwei Zahlen $a$ und $b$

1. Setze eine dritte Variable $c$ auf $0$.
2. Falls $b=0$ ist, gehe zu Schritt 6.
3. Addiere $a$ zu $c$ hinzu und speichere das Ergebnis in $c$.
4. Subtrahiere $1$ von $b$.
5. Gehe zu Schritt 2.
6. Gib $c$ aus.

Algorithmen auf Graphen

Suche: Breitensuche | Tiefensuche

Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus

Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus