Algorithmus

"Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems durch eine Abfolge bekannter Befehle/Operationen."

Ein Algorithmus ist zudem ein Verfahren zur Lösung von Einzelproblemen einer definierten Problemklasse.

Man kann einen Algorithmus mit einer Gebrauchsanleitung vergleichen: Es wird versucht, ein (mathematisches) Problem durch präzise Anweisungen zu lösen. Ein Algorithmus muss eindeutig ausführbar sein.

Algorithmen werden meistens nicht direkt in einer existenten Programmiersprachen dargestellt, sondern umgangssprachlich oder im sogenannten Pseudocode. Dieser ist ein Kompromiss aus Umgangs- und Programmiersprache.

Anforderungen an einen Algorithmus

In der Vorlesung wurden Ihnen formale Anforderungen an einen Algorithmus vorgestellt. In Kürze sind diese:

• A1: Ein Algorithmus muss für jede Eingabe eine Ausgabe besitzen.
• A2 bis A4: Ein Algorithmus muss durch eine endliche Folge sogenannter elementarer Operatoren beschrieben werden können.
• A5: Ein Algorithmus darf nur endlich viel Speicherplatz für Zwischenergebnisse verbrauchen.
• A6: Ein Algorithmus sollte terminieren.
• A7 bis A9: Aus dem Zustand eines Algorithmus sollte sein nächster Zustand eindeutig definiert sein.
• A10: Ein Algorithmus sollte eine Problemgruppe lösen und nicht nur ein Einzelproblem.
• A11: Ein Algorithmus sollte leicht anpassbar sein.
• A12: Ein Algorithmus sollte effizient sein.
• A13: Ein Algorithmus sollte auf jeden möglichen Fehler vorbereitet sein.

Diese Anforderungen basieren auf wissenschaftlichen Aussagen, die im Folgenden detaillierter beschrieben werden.

A1: Relation

Erläuterung

Ein Algorithmus beschreibt eine Relation über dem Kreuzprodukt einer Eingabe- und einer Ausgabemenge. Dadurch werden für jede Eingabe die zulässigen Ausgaben festgelegt.

Umgangssprachlich lässt sich "Relation" als "Zusammenhang" interpretieren. In der Mathematik ist der Begriff der Relation definiert als eine Menge von Tupeln (x,y). Eine Relation ist z.B. die Menge aller (x,y) für die gilt, dass x = y ist (Gleichheit). Für unseren Zusammenhang ist ein Tupel die Werte (x, f(x)) für eine Funktion x, gesprochen: "f(x) ist das Ergebnis von x unter Ausführung von f", z.B. (1,2) für "2 ist das Ergebnis von 1 unter Ausführung der Operation +1".

Das Kreuzprodukt zweier Mengen ist die Kombination aller Elemente der einen Menge zu allen Elementen der anderen Menge zu einer Menge von Tupeln.

Beispiel

Es seien M={2,4,6} und N={1,2,3}, dann entspricht das Kreuzprodukt der beiden der Menge MxN={(2,1),(2,2),(2,3),(4,1),(4,2),(4,3),(6,1),(6,2),(6,3)}. Man kombiniert also jedes Element aus der Menge M jeweils mit einem Element der Menge N.

Es sei nun x ein beliebiges Element aus M und y aus N. Untersucht man diese beiden Mengen wie im obigen Beispiel auf "Gleichheit" ihrer Elemente, so gibt es nur ein Tupel, für welches ein Element x aus der Menge M denselben Wert hat, wie das Element y aus N, nämlich (2,2).

Das heißt, ein Algorithmus beschreibt mathematisch eine totale Funktion aus der Menge der Eingaben in die Menge der Ausgaben.

Noch einfacher: Ein Algorithmus berechnet zu jeder Eingabe ein Ergebnis, das er ausgibt. Wichtig hierbei ist: Nur weil ein Algorithmus eine Ausgabe hat, muss der Nutzer eines Programms diese Ausgabe nicht unbedingt sehen! Die gebräuchliche Literatur benutzt die Begriffe "Ergebnis der Berechnung eines Algorithmus" und "Ausgabe eines Algorithmus" synonym.

A2: Elementaroperationen

Ein Algorithmus setzt sich aus wohldefinierten Elementaroperationen zusammen, die auf einer geeigneten Maschine ausführbar sind.

Jeder Algorithmus muss formalisiert und niedergeschrieben werden können. Elementaroperationen sind die kleinsten Einheiten eines Algorithmus. Diese Operationen sind so grundlegend, dass weitere Beschreibungen nicht notwendig und auch gar nicht möglich sind.

Wie diese Elementaroperationen aussehen, ist von Maschine zu Maschine und von Programmiersprache zu Programmiersprache unterschiedlich. Eine beliebige Maschine sollte jedoch nach Fertigstellung der Programmierung die Befehle eines Algorithmus verstehen und ausführen können. Da direkte Befehle an eine Maschine für einen Menschen ab einer gewissen Komplexität nicht mehr nachvollziehbar sind, existieren höhere Programmiersprachen. Diese werden dann von einem anderen Programm entweder interpretiert oder compiliert, bevor sie von einer Maschine ausgeführt werden.

A3: Abfolge

Ein Algorithmus legt die Abfolge der Schritte fest, wobei jeder Schritt genau eine Elementaroperation umfasst.

Ein Algorithmus wird schrittweise ausgeführt. In jedem Schritt führt die Maschine genau eine Elementaroperation aus. Dieses Verhalten wird in vielen Programmiersprachen durch die Notation eines Algorithmus als Anweisungsfolgen repräsentiert. Dies ist allerdings nicht immer der Fall, so z.B. in funktionalen Programmiersprachen.

Ist die Abfolge der Schritte nicht festgelegt, handelt es sich um einen nebenläufigen Algorithmus.

Bei einem sequentiellen Algorithmus hingegen ist die Reihenfolge (eine Operation nach der anderen) eindeutig.

Bei paralleler Ausführung werden die Operationen gleichzeitig ausgeführt.

A4: Beschreibung endlicher Länge

Ein Algorithmus ist eine Beschreibung endlicher Länge.

Ein Algorithmus muss niedergeschrieben werden können und seine Beschreibung muss mit einer endlichen Anzahl an Anweisungen formulierbar sein. Eine unendliche Folge von Anweisungen wird nicht als Algorithmus betrachtet.

A5: Speicherplatz

Ein Algorithmus benutzt nur endlich viele Speicherplätze zur Ablage von Zwischenergebnissen.

Jeder reale Computer besitzt nur endlich viel Speicherplatz. Daher ist ein Algorithmus, der unendlich viel Speicherplatz belegt, nicht umsetzbar. Auch in der theoretischen Informatik beschäftigt man sich hauptsächlich mit Maschinenmodellen, die unter Umständen beliebig viel, aber immer endlich viel Speicherplatz für ihre Berechnungen benötigen.

A6: Terminierung

Für jede (!) Eingabe endet die Ausführung des Algorithmus nach endlich vielen Schritten (Terminierung).

Jedes Programm muss nach endlich vielen Schritten terminieren, d.h. der Algorithmus muss ein Ergebnis liefern. Würde ein Programm nicht terminieren, so läge nie ein Ergebnis vor und die ausführende Maschine würde niemals anhalten. Ein Beispiel für ein nicht terminierendes Programm, das von außen abgebrochen werden muss, ist eine Endlosschleife.

A7: Begrenzte Schrittanzahl

Für jede (!) Eingabe wird die zugehörige Ausgabe spätestens nach Ausführung einer vorgegebenen Schrittanzahl n geliefert. Wenn ein Rechensystem für jeden Schritt höchstens die Zeit s benötigt, dann wird die Ausgabe spätestens nach Verstreichen der begrenzten Antwortzeit t = s * n geliefert (Begrenzte Schrittanzahl).

Diese zusätzliche Anforderung beschreibt die Tatsache, dass ein Algorithmus möglichst effizient ein Ergebnis liefern soll. Tut er dies nach einer gewissen Zeit nicht, so muss er abgebrochen und das Ergebnis als "nicht definiert" deklariert werden.

A8: Determiniertheit

Die Eingabe-Ausgabe-Relation (siehe A1) ist rechtseindeutig. Dies bedeutet, dass jeder Eingabe genau eine Ausgabe zugeordnet wird (Determiniertheit).

Auf eine bestimmte Eingabe folgt immer dieselbe Ausgabe. Das wird Determiniertheit genannt. Der Algorithmus führt unabhängig von Maschine, Zeit, Ort und ähnlichem immer dieselbe Berechnung aus. Auf die Eingabe "√4" folgt zum Beispiel immer die Ausgabe "2".

Determiniertheit hängt eng mit Determinismus zusammen.

A9: Determinismus

In jedem Zustand, der bei Ausführung des Algorithmus erreicht wird, ist jeweils nur ein einziger Folgeschritt als nächster ausführbar (Determinismus).

Jedes Programm in Ausführung lässt sich durch einen Zustand repräsentieren (Werte von Variablen, Codezeile in Ausführung, uvm.). In Abhängigkeit dieses Zustandes muss ein Algorithmus einen einzigen eindeutig definierten Folgezustand nach Ausführung einer Elementaroperation besitzen.

Ein nichtdeterministischer oder nichtdeterminierter Algorithmus lässt hingegen mehrere Folgekandidaten zu, unter denen ausgewählt werden kann.

A10: Allgemeinheit

Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen (Allgemeinheit).

Ein Algorithmus sollte ein Problem in Abhängigkeit zu seiner Eingabe lösen. Ein Algorithmus, der zum Beispiel zu jeder Eingabe die Ausgabe "1" besitzt, kann auch direkt durch den Ausdruck "1" ersetzt werden und hat keinen Mehrwert durch seine Existenz.

A11: Änderbarkeit

Ein Algorithmus soll sich leicht modifizieren lassen, um ihn an eine veränderte Aufgabenstellung anzupassen (Änderbarkeit).

A12: Effizienz

Für eine gegebene Eingabe soll die Anzahl der benötigten Schritte möglichst gering sein (Effizienz).

Durch die Vermeidung unnötiger Schritte soll der Algorithmus kürzer und übersichtlicher werden. Die Informatik hat zum Ziel, Probleme mit möglichst geringer Laufzeit, also schnell, und mit möglichst geringem Speicherplatzverbrauch zu lösen. Anhand der Maße der Zeitkomplexität und der Raumkomplexität kann also beurteilt werden, ob ein Algorithmus effizient arbeitet.

A13: Robustheit

Der Algorithmus soll sich möglichst auch dann wohldefiniert verhalten, wenn eine unzulässige Eingabe (die nicht Element der Eingabemenge ist) vorliegt oder eine sonstige unvorhergesehene Situation auftritt (Robustheit).

Wenn die Funktion, die ein Algorithmus berechnet, nicht total ist, so sollte ein Algorithmus im Falle einer Eingabe, zu der seine intendierte Funktion kein Ergebnis liefern kann (z.B. Division durch Null), dennoch eine vorhersehbare Funktionalität liefern (z.B. die Ausgabe einer Fehlermeldung und anschließender Abbruch der gesamten Ausführung des Programms).

Rückgabe und Ausgabe

Erläuterung

Der Unterschied zwischen den Begriffen Rückgabe und Ausgabe ist in der deutschen Sprache erfahrungsgemäß zu gering. Dies führt häufig zu Missverständnissen und Fehlern beim Lesen und Bearbeiten von Übungsaufgaben. Aus diesem Grund definieren wir hier die folgenden Grundlagen:

Beschreibt ein Text einen Algorithmus, der etwas ausgibt (engl. print), so meinen wir das Anzeigen eines Ergebnisses auf einer Benutzerschnittstelle.

Beschreibt ein Text einen Algorithmus, der etwas zurückgibt (engl. return), so meinen wir das Übergeben des Ergebnisses an eine aufrufende Funktion.

Beschreibt ein Text die Ausgabe (engl. output) eines Algorithmus im Zusammenhang mit einer Eingabe (input), so ist von dem Ergebnis, bzw. den Parametern der vom Programm beschriebenen Funktion die Rede.

Beispiele

Spezifikation:

Eingabe: Eine Zahl
Ausgabe: Die Zahl, multipliziert mit sich selbst

Hier wird ein Algorithmus beschrieben, der eine Zahl als Parameter erwartet und diese bei Aufruf mit sich selbst multipliziert und als Ergebnis zurückgibt. Eine Ausgabe auf dem Bildschirm wird hier nicht erwartet.

Der Algorithmus nimmt zwei Zahlen entgegen und gibt das Produkt dieser Zahlen aus.

Hier wird ein Algorithmus beschrieben, der zwei Zahlen als Parameter erwartet und diese bei Aufruf miteinander multipliziert. Das Ergebnis dieser Multiplikation wird anschließend auf einer Benutzerschnittstelle ausgegeben. Ein aufrufender Algorithmus erwartet kein Ergebnis von diesem.

Der Algorithmus nimmt eine Zahl n entgegen und gibt den Wert 2 ^ n zurück.

Hier wird ein Algorithmus beschrieben, der eine Zahl als Parameter erwartet und diesen als Teil seiner Berechnung verwendet. Das Ergebnis dieser Berechnung wird an die aufrufende Funktion zurückgegeben. Eine Ausgabe auf dem Bildschirm wird hier nicht erwartet.

Der Algorithmus nimmt eine Nachricht s entgegen, verschickt diese Nachricht an alle aktiven Verbindungen,
gibt dabei eine Information über den Empfänger der Nachricht aus
und gibt die Anzahl der versendeten Nachrichten zurück.

Hier wird ein Algorithmus beschrieben, der eine Nachricht als Parameter erwartet und diese an verschiedene Empfänger verteilt. Die Information über den Versand der Nachricht wird für jeden Empfänger auf einer Benutzerschnittstelle ausgegeben. Die aufrufende Funktion erhält als Ergebnis der Berechnung die Anzahl der versendeten Nachrichten.

Vom Algorithmus zum Programm

Programm/Programmieren

Die Formulierung eines Algorithmus heißt Programm. Das Entwerfen eines Programms heißt programmieren.

Programmierparadigmen

Ein Programmierparadigma ist ein Konzept zum Programmieren.

Die bekanntesten Programmierparadigmen sind:

• Imperative (prozedurale) Programmierung

• Funktionale Programmierung

• Logische Programmierung

• Objektorientierte Programmierung