Algorithmus: Unterschied zwischen den Versionen

Version vom 3. Juli 2015, 16:20 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

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

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

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

Beispiele für die Eigenschaften von Algorithmen

• Einfache Grundoperation

• Sequenzieller Algorithmus

• Nebenläufiger Algorithmus

• Parallele Ausführung

• Nichtdeterministischer Algorithmus

Vom Algorithmus zum Programm

Programm/Programmieren

Programmpardigmen

Die bekanntesten Programmparadigmen

• Imperative (prozedurale) Programmierung

• Funktionale Programmierung

• Logische Programmierung

• Objektorientierte Programmierung