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
Man kann einen Algorithmus mit einer Gebrauchsanleitung vergleichen: Es wird versucht, ein (mathematisches) Problem durch präzise Anweisungen theoretisch auf einem Computer zu lösen. Dabei wird Pseudocode, also eine vereinfachte und verkürzte Programmiersprache, verwendet.
Inhaltsverzeichnis
- 1 Forderungen an einem Algorithmus
- 1.1 A1: Relation
- 1.2 A2: Elementaroperationen
- 1.3 A3: Abfolge
- 1.4 A4: Beschreibung endlicher Länge
- 1.5 A5: Speicherplatz
- 1.6 A6: Terminierung
- 1.7 A7: Begrenzte Schrittanzahl
- 1.8 A8: Determiniertheit
- 1.9 A9: Determinismus
- 1.10 A10: Allgemeinheit
- 1.11 A11: Änderbarkeit
- 1.12 A12: Effiezenz
- 1.13 A13: Robustheit
- 2 Verständlichkeit eines Algorithmus
- 3 Vom Algorithmus zum Programm
- 4 Die bekanntesten Programmparadigmen
Forderungen an einem Algorithmus
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.
A2: Elementaroperationen
Ein Algorithmus setzt sich aus wohldefinierten Elementaroperationen zusammen, die auf einer geeigneten Maschine ausführbar sind.
A3: Abfolge
Ein Algorithmus legt die Abfolge der Schritte fest, wobei jeder Schritt genau eine Elementaroperation umfasst.
A4: Beschreibung endlicher Länge
Ein Algorithmus ist eine Beschreibung endlicher Länge.
A5: Speicherplatz
Ein Algorithmus benutzt nur endlich viele Speicherplätze zur Ablage von Zwischenergebnissen.
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. das Programm muss sich beenden. Würde ein Programm nicht terminieren und damit ist es nicht beendbar, dann hängt sich der Computer auf. Das Programm benutzt immer mehr Speicherplatz, bis dieser aufgebraucht ist. Ein Beispiel für solch ein Problem 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).
A8: Determiniertheit
Die Eingabe-Ausgabe-Relation (siehe A1) ist rechtseindeutig. Dies bedeutet, dass jeder Eingabe genau eine Ausgabe zugeordnet wird (Determiniertheit).
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).
A10: Allgemeinheit
Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen (Allgemeinheit).
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).
Verständlichkeit eines Algorithmus
Beispiel für ein unverständlichen Algorithmus:
public static void berechnen2(int c, int d){int erg=0;for(int i=0;i<c;i++){erg+=d;}System.out.println("Das Ergebnis ist: "+erg);}
Das gleiche Beispiel:
public static void berechnen(int a, int b)
{
int erg = 0;
for(int i = 0; i<a ; i++)
{
erg += b;
}
System.out.println("Das Ergebnis ist:" + erg);
}
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.
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.
