Handlungsvorschriften zur Lösung eines Problems (oder einer Klasse von Problemen), die ausführbar, eindeutig und endlich sind, werden Algorithmen genannt. Ausführbarkeit verlangt, dass der Effekt jeder Anweisung eindeutig festgelegt ist. Eindeutigkeit verlangt, dass zu jedem Zeitpunkt der Ausführung die nächste Anweisung eindeutig festgelegt ist. Endlichkeit verlangt, dass die Beschreibung des Algorithmus endlich ist. Eine zusätzliche Forderung wäre Terminierung, d.h., dass jede Ausführung des Algorithmus nach endlich vielen Schritten endet.
Die Untersuchung konkreter Algorithmen sowie der Methoden zur Formulierung von Algorithmen in Programmiersprachen ist zentrale Aufgabe der Praktischen Informatik. Die Komplexität konkreter Algorithmen sowie abstrakte Klassen zur Einteilung von Algorithmen bezüglich ihrer Komplexität werden in der Theoretischen Informatik untersucht.
Ein interessantes Ergebnis der Theoretischen Informatik ist, dass das sogenannte Halteproblem nicht entscheidbar ist, d.h., dass es keinen Algorithmus gibt, der zu einem beliebigen gegebenen Algorithmus mit Eingabe entscheidet, ob dieser Algorithmus mit der Eingabe terminiert.
Algorithmen, die auf einem Computer ausgeführt werden können, heißen Computer-Programme oder kurz Programme.
Im Folgenden beschreiben wir einige Algorithmen zum Zeichnen geometrischer Figuren unter Verwendung einer beispielhaft eingeführten Notation.
Einen Algorithmus zum Zeichnen einer aus fünf Punkten im Abstand vom einem Zentimeter gezeichneten Linie notieren wir wie folgt.
LINIE:
einen Zentimeter vorwärts
Punkt zeichnen
fünf Mal wiederholen
Die Beschreibung zum Zeichnen einer solchen Linie ist endlich (sie hat vier Zeilen). Wenn wir vorraussetzen, dass festgelegt ist, wie die primitiven Anweisungen (z.B. Punkt zeichnen) ausgeführt werden, ist der Algorithmus ausführbar. Es ist auch eindeutig festgelegt, welche Anweisung auf welche andere folgt. Schließlich bemerken wir, dass der Algorithmus terminiert, denn es werden zehn Schritte (fünf mal zwei) ausgeführt.
Die folgende “Grafik” illustriert die Ausführung der Anweisung LINIE zeichnen:
* * * * *
Dadurch, dass wir den Algorithmus LINIE genannt haben, können wir ihn als Anweisung in anderen Algorithmen verwenden. Als Beispiel definieren wir einen Algorithmus zum Zeichnen eines Quadrats:
QUADRAT:
LINIE zeichnen
rechts rum drehen
vier mal wiederholen
Im Algorithmus QUADRAT ist die Bedeutung der Anweisung LINIE zeichnen ebenso vorausgesetzt, wie im Algorithmus LINIE die Bedeutung der Anweisung Punkt zeichnen. Allerdings haben wir die komplexe Anweisung LINIE zeichnen explizit als Algorithmus definiert, während die Bedeutung der primitiven Anweisung Punkt zeichnen implizit vorausgesetzt wird.
Die Benennung von Algorithmen und deren Wiederverwendung in anderen Algorithmen ist eine wichtige Form der Abstraktion bei der Lösung von Problemen, da es dadurch überflüssig wird, häufig wiederkehrende Anweisungsfolgen immer wieder zu notieren.
Die folgende Grafik verdeutlicht die Ausführung der Anweisung QUADRAT zeichnen:
* * * * * *
* *
* *
* *
* *
* * * * * *
Zur Definition des QUADRAT-Algorithmus haben wir implizit angenommen, dass die Anweisung rechts rum drehen eine Drehung um genau 90 Grad beschreibt. Wenn wir beliebige Drehungen zulassen, können wir auch Kreise zeichnen.
Der folgende Algorithmus beschreibt das Zeichnen eines Kreises mit einem Radius von fünf Zentimetern:
KREIS_5:
fünf Zentimeter vor
Punkt zeichnen
fünf Zentimeter zurück
ein Grad nach rechts drehen
360 mal wiederholen
Veranschaulichen Sie sich die Ausführung der Anweisung KREIS_5 zeichnen, indem Sie entsprechend der Definition von KREIS_5 Punkte auf ein Blatt Papier zeichnen.
Um einen Kreis mit dem Radius zehn (statt fünf) zu zeichnen, können wir in der ersten und dritten Anweisung das Wort fünf durch zehn ersetzen. Der Rest der Definition bleibt dabei unverändert. Statt für jeden konkreten Radius einen eigenen Algorithmus zu definieren, können wir aber auch einen einzigen Algorithmus zum Lösen der Problemklasse “Kreis mit gegebenem Radius zeichnen” angeben. Dazu fügen wir hinter dem Namen des Algorithmus in Klammern einen Parameter ein, der den Radius des gezeichneten Kreises festlegt:
KREIS(RADIUS):
RADIUS Zentimeter vor
Punkt zeichnen
RADIUS Zentimeter zurück
ein Grad nach rechts drehen
360 mal wiederholen
Die Verallgemeinerung eines konkreten Problems zu einer Problemklasse durch Parametrisierung ist (wie die Wiederverwendung benannter Algorithmen als komplexe Anweisungen) eine wichtige Form der Abstraktion zur Lösung von Problemen. Sie erlaubt (potentiell unendlich!) viele gleichartige Handlungsvorschriften mit Hilfe eines einzigen Algorithmus zu beschreiben.