Algorithmus: Unterschied zwischen den Versionen

Version vom 17. Juli 2015, 15:56 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).

Verständlichkeit eines Algorithmus

Ein wichtiges Merkmal für einen Algorithmus ist die Möglichkeit für einen menschlichen Leser den Algorithmus lesen und verstehen zu können, obwohl er nicht in umgangssprachlicher Form vorliegt.

Als Beispiel sei folgender Algorithmus gegeben, der zwei Zahlen miteinander multipliziert, ohne explizit einen Multiplikationsoperator zu verwenden:

Eingabe: Zwei ganze Zahlen a und b
Ausgabe: Produkt aus a und b
Vorgehensweise:
    Initialisiere das Ergebnis mit 0
    Addiere a mal b auf das Ergebnis
    Gebe das Ergebnis zurück

Beispiel für eine unverständliche Formulierung des Algorithmus':

  public static int berechnen2(int c, int d){int erg=0;for(int i=0;i<c;i++){erg+=d;}return erg;}
  

Das gleiche Beispiel, lesbarer und mit Syntaxhighlighting hervorgehoben:

public static int berechnen(int a, int b)
  {
    int erg = 0;
    for(int i = 0; i<a ; i++)
    {
        erg += b;
    }
  }

Beide Programme führen das gleiche aus. Beide berechnen das Produkt von a und b bzw. c und d, ohne zu mutipliezieren. Sie addieren b bzw. d a- bzw c-mal auf eine Ergebnisvariablen auf, Genaueres s. Schleifen. Diese Variable wird zum Schluss ausgegeben.

Rückgabe und Ausgabe

In der deutschen Sprache der Unterschied zwischen dem sogenannten Ausgeben (engl. print) eines Wertes auf einer Benutzerschnittstelle (z.B. dem Bildschirm) und dem Zurückgeben (engl. return) eines Wertes an ein aufrufendes Programm leicht zu verwechseln, gerade da in manchen Spezifikationen eines Algorithmus zusätzlich die Begriffe Eingabe (engl. input) und Ausgabe (engl. output) verwendet werden.

Aus diesem Grund legen wir in der Formulierung von Algorithmen folgende Grundlagen fest:

Wenn in der Spezifikation eines Algorithmus von Ausgabe oder Rückgabe die Rede ist, ist das Ergebnis der Berechnung gemeint.

Wenn in der Ausführungsbeschreibung eines Algorithmus von Ausgabe die Rede ist, ist immer eine Ausgabe auf dem Bildschirm gemeint.

Wenn in der Ausführungsbeschreibung eines Algorithmus von Rückgabe die Rede ist, ist immer das beenden des Algorithmus mit dem liefern eines Ergebnisses gemeint.

Beispiele

Spezifikation:

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

Der Algorithmus berechnet ein Ergebnis und informiert den Benutzer nicht über die Berechnung.

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

Der Algorithmus berechnet ein Ergebnis und informiert den Benutzer über das Ergebnis.

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

Der Algorithmus berechnet nur ein Ergebnis und informiert den Benutzer nicht über die Berechnung.

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.

Der Algorithmus berechnet ein Ergebnis (die Anzahl der versendeten Nachrichten) und informiert den Benutzer über jede versendete Nachricht.

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