Algorithmus: Unterschied zwischen den Versionen

Version vom 5. Oktober 2015, 08:36 Uhr

"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

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 ihn formulierte Anleitung exakt verstehen und durchführen können. Aus diesem Grund wird zur Formulierung eines Algorithmus meistens nicht direkt eine Darstellung in einer existenten Programmiersprache verwendet, sondern umgangssprachlich oder in sogenanntem "Pseudocode", welcher ein kompromiss aus Umgangs- und Programmiersprache darstellt.

Forderungen an einem 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 verbauchen
• 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

In der Vorlesung wurden Ihnen diese Punkte folgendermaßen präsentiert. Da diese Anforderungen sehr auf Basis wissenschaftlicher Aussagen basieren, werden hier diese Aussagen detailierter beschrieben.

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, welches er ausgibt. Wichtig hierbei ist: Nur weil ein Algorithmus eine Ausgabe hat, muss der Nutzer eines Programmes 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. An welcher Stelle 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 nachzuvollziehen sind, existieren höhere Programmiersprachen, welche dann von einem anderen Programm entweder interpretiert oder compiliert werden, um von einer Maschine ausgeführt werden zu können.

A3: Abfolge

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

Ein Algorithmus wird schrittweise ausgeführt, wobei in jedem Schritt die ausführende Maschine genau eine Elementaroperation ausführt. 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. So betrachten wir eine unendliche Folge von Anweisungen nicht als einen Algorithmus.

A5: Speicherplatz

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

Jeder reale Computer besitzt nur endlich viel Speicherplatz, weswegen ein Algorithmus, der unendlich viel Speicherplatz beläge, nicht umsetzbar wäre. Auch in der theoretischen Informatik beschäftigt man sich hauptsächlich nur mit Maschinenmodellen, die unter umständen beliebig viel, aber 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 es automatisch erkennbar ist, ob ein Programm terminieren kann, oder nicht (Spoilers: Kann man nicht!). Letztenendes muss ein Programm irgendwann beendet werden, spätestens, wenn man der Maschine den Strom abdreht. Ein Beispiel für ein nicht terminierendes Programm, welches 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 werden 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 Programmes ein, aber ist dem nicht der Fall, so muss ein Algorithmus für jede Eingabe eine eindeutige Ausgabe haben. Damit diese Eigenschaft gewahrt ist, wird z.B. der (zu Beginn nicht bekannte) Eingriff eines Benutzers mit zur Einagbe des Programmes 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 beistzen.

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 in Abhängikeit zu seiner Eingabe das Problem lösen. Ein Algorithmus, welcher 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: Effiezenz

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

Durch die Vermiedung unnötiger Schritte wird der Algorithmus kürzer und meist übersichtlicher. Zudem wird in der Informatik versucht, Probleme möglichst mit 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).

Sollte die Funktion, die ein Algorithmus berechnet, nicht total sein, 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 Programmes).

Rückgabe und Ausgabe

Der Unterschied zwischen den Begriffen der Rückgabe und der Ausgabe ist in der deutschen Sprache erfahrungsgemäß zu klein ausgefallen. 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 Paramteter erwartet und diese bei Aufruf mit sich selbst multipliziert und als Ergebnis zurück gibt. 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 Benutzerschnitstelle 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 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 Algorihtmus beschrieben, der eine Nachricht als Parameter erwartet und diese an verschiedene Empfänger verteilt. Eine 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 programmieren.

Programmpardigmen

Ein Programmparadigma ist ein Konzept zum Programmieren.

Die bekanntesten Programmparadigmen

• Imperative (prozedurale) Programmierung

• Funktionale Programmierung

• Logische Programmierung

• Objektorientierte Programmierung