Lernziele
- Sie haben ein Bewusstsein für den Algorithmus-Begriff gebildet
- Sie kennen verschiedene Beispielformen, einen Ablauf zu beschreiben
- Sie erkennen «Kontrollstrukturen» und «Variablen», zur Behandlung von zukünftigen Situationen
- (eventuell: Sie begreifen den Sinn der Reduktion von Komplexität durch Modularisierung)
Definitionen
Ein Algorithmus beschreibt die Methode, mit der eine Aufgabe gelöst wird.
Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten.
Eigenschaften
- Allgemeinheit
- bedeutet, dass nicht nur ein einzelnes Problem, sondern eine ganze Klasse von Problemen gelöst werden soll.
- Nur weil man weiss, dass 7 + 4 elf ergibt, kann man noch nicht addieren. Erst wer alle möglichen Zahlen addieren kann, hat die Addition allgemein begriffen.
- Eindeutigkeit
- bedeutet, dass die Abfolge der einzelnen Schritte genau festgelegt ist.
- Zwar gibt es mit Verzweigungen und Schleifen die Möglichkeit, (potentielle) Änderungen dieser Reihenfolge einzubauen, aber wann das passiert, ist ebenfalls eindeutig festgelegt. Die Möglichkeit, dass mehrere Varianten gleichzeitig ausgeführt werden, gibt es in klassischen Algorithmen nicht.
- Ausführbarkeit
- bedeutet, dass ein Prozessor jeden Einzelschritt des Algorithmus ausführen kann.
- Hier geht es also darum, was genau als «einzelner Schritt» gilt. Genau genommen hängt das natürlich vom Prozessor (oder vom Vorwissen des Lesers) ab. Bei der Formulierung von Algorithmen lässt man hier meist gesunden Menschenverstand walten: Jeder Schritt muss so klar und eindeutig formuliert sein, dass alle ihn gleich verstehen.
- Endlichkeit
- bedeutet, dass der Algorithmus immer mit einer endlichen Anzahl Schritte zu einer Lösung kommt.
- Gerade mit Schleifen kann es schnell passieren, dass Algorithmen sehr viele Schritte haben. Eine unendliche Schleife darf jedoch unter keinen Umständen vorkommen, auch nicht für einen Sonderfall innerhalb der Problemklasse.
- Korrektheit
- bedeutet, dass der Algorithmus für alle möglichen Eingaben (bzw. für alle Probleme innerhalb der Problemklasse) in endlicher Zeit zu einer korrekten Lösung kommt.
- Die allgemeine Korrektheit eines Algorithmus zu verifizieren ist oft nicht einfach, vergleichbar mit Korrektheitsbeweisen in der Mathematik.