Algorithmus

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

aus: Grumm/Sommer: Einführung in die Informatik

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. Jemand, der den Algorithmus liest, muss die durch diesen formulierte Anleitung exakt verstehen und durchführen können. Aus diesem Grund wird der Algorithmus meist nicht direkt in einer existenten Programmiersprache 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 kurz sind diese:

• Ein Algorithmus muss für jede Eingabe eine Ausgabe besitzen
• Ein Algorithmus muss aus einer endlichen Folge sog. elementaren Operatoren beschrieben werden können
• Ein Algorithmus darf nur endlich viel Speicherplatz für Zwischenergebnisse verbrauchen
• Ein Algorithmus sollte terminieren
• Aus dem Zustand eines Algorithmus sollte sein nächster Zustand eindeutig definiert sein
• Ein Algorithmus sollte eine Problemgruppe lösen und nicht nur ein Einzelproblem
• Ein Algorithmus sollte leicht anpassbar sein
• Ein Algorithmus sollte effizient sein
• Ein Algorithmus sollte auf jeden möglichen Fehler vorbereitet sein

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

A1: Relation

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 ebenso 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.

Die obrige Aussage möchte also nichts weiter sagen, als dass ein Algorithmus mathematisch eine totale Funktion aus der Menge der Eingaben in die Menge der Ausgaben beschreibt.

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. Inwiefern man sagen kann, dass weitere Beschreibung nicht mehr von nöten ist, definieren die Elementaroperationen eines Algorithmus, aus welchem ein jeder Algorithmus zusammengesetzt werden kann. Wie diese Elementaroperationen aussehen, ist von Maschine zu Maschine und von Programmiersprache zu Programmiersprache unterschiedlich, jedoch sollte am Ende eine Maschine 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 durch Anweisungsfolgen repräsentiert. Dies ist allerdings nicht immer der Fall, so z.B. in funktionalen Programmiersprachen.

A4: Beschreibung endlicher Länge

Ein Algorithmus ist eine Beschreibung endlicher Länge.

Ein Algorithmus muss niedergeschrieben werden können und seine Beschreibung muss in 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 endlichen 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 theoretische ausführende Maschine würde niemals anhalten. In der theoretischen Informatik beschäftigt man sich z.B. mit der Frage, ob automatisch erkennbar ist, ob ein Programm terminieren kann oder nicht (Spoilers: Kann man nicht!). Letztendlich muss ein Programm irgendwann beendet werden. Spätestens, wenn der Maschine der Strom abdreht wird. 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).

In der Praxis greift natürlich ein Benutzer in den Ablauf eines Programms ein. Ist dem nicht der Fall, so muss ein Algorithmus für jede Eingabe eine eindeutige Ausgabe haben. Damit diese Eigenschaft gewahrt bleibt, zählt z.B. der (zu Beginn nicht bekannte) Eingriff eines Benutzers mit zur Eingabe des Programms, um die Wohldefiniertheit dieser Anforderung zu wahren.

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 eindeutig definierten Folgezustand nach Ausführung einer Elementaroperation besitzen.

A10: Allgemeinheit

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

Ein Algorithmus sollte ein Problem lösen und zwar in Abhängigkeit zu seiner Eingabe. Ein Algorithmus, der z.B. 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 wird der Algorithmus kürzer und meist übersichtlicher. Zudem ist es ein Ziel der Informatik, Probleme mit möglichst geringer Laufzeit, also schnell, und möglichst geringem Speicherplatzverbrauch zu lösen.

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

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 eine 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.

Programmparadigmen

Ein Programmparadigma ist ein Konzept zum Programmieren.

Die bekanntesten Programmparadigmen

• Imperative (prozedurale) Programmierung

• Funktionale Programmierung

• Logische Programmierung

• Objektorientierte Programmierung