Algorithmusbegriff

Aus ProgrammingWiki

Betrachtet bitte folgende Vorgänge:

1. "Koffer packen"
2. "einchecken am Flughafen"
3. "Castingshow"
4. "Fußballregeln, z.B. Abseits und Foul"

• Formuliert jeweils einen Ablaufplan zum Vorgang (oder als Skizze darstellen).
• Entscheidet anhand der unten aufgeführten Eigenschaften, ob es sich bei dem Vorgang um einen Algorithmus handelt oder nicht.
• Begründet kurz.

Der Algorithmusbegriff

Die Bezeichnung Algorithmus geht auf den Namen Muhammad ibn Musa, Abu Dscha'far al-Chwarizmi (* um 780; † um 850), einem persischen Mathematiker, Astronomen und Geographen, zurück. Diesem Universalgelehrten verdanken wir nicht nur die Einführung der Null aus dem indischen in das arabische Zahlensystem, sondern auch das Wort "Algebra", das der lateinischen Übersetzung seines Buches Kitāb al-muchtasar fi hisab al-dschabr wa-l-muqabala ("Rechnen durch Ergänzung und Ausgleich") entnommen ist.

Es existiert eine Vielzahl von Versuchen einer Definition für den Begriff Algorithmus.
zum Beispiel:

1. Als ”Algorithmus [..] bezeichnet [man] heute in der Arithmetik einen Rechenvorgang (bzw. die ihn beschreibenden Regeln) der nach einem bestimmten sich wiederholenden Schema abläuft" (Meyers Enzyklopädie, 1971)
2. ”Ein Algorithmus [..] ist eine vollständige, präzise und in einer Notation oder Sprache mit exakter Definition abgefasste, endliche Beschreibung eines schritt- weisen Problemlösungsverfahrens zur Ermittlung gesuchter Datenobjekte (ihrer Werte) aus gegebenen Werten von Datenobjekten, in dem jeder Schritt aus einer Anzahl ausführbarer, eindeutiger Aktionen und einer Angabe über den nächsten Schritt besteht.”(Pomberger, Gustav; Dobler, Heinz: Algorithmen und Datenstrukturen - Eine systematische Einführung in die Programmierung. München : Pearson Education Deutschland GmbH, 2008)
3. ”Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems.”(Gumm, Heinz P.; Sommer, Manfred: Einführung in die Informatik. München : Oldenbourg Wissenschaftsverlag, 2006)

Wir begnügen uns mit einer anschaulichen (intuitiven) Erklärung:

Ein Algorithmus ist eine endliche Folge von eindeutigen und ausführbaren Anweisungen zur Lösung eines allgemeinen Problems.

Eigenschaften von Algorithmen

1. Endlichkeit: (Finitheit)
   • endliche Notation des Algorithmus, (statische Endlichkeit)
   • Nutzung endlicher Ressourcen (z.B. begrenzter Arbeitsspeicher / begrenzte Rechenzeit) - dynamische Endlichkeit
2. Terminiertheit
   • endlich viele Abarbeitungsschritte - Endlichkeit im Ablauf (z.B. begrenzte Rekursionstiefe), der Algorithmus liefert also bei jeder Anwendung nach endlich vielen Verarbeitungsschritten ein Resultat
     
   • Bei Nichterfüllung: Endlosschleife (Ausnahmen: OS; interaktive Programme)
3. Deterministisch
   • Nach jedem Abarbeitungsschritt besteht höchstens eine Möglichkeit der Fortsetzung.
4. Eindeutigkeit: (Determiniertheit)
   • Gleiche Eingabegrößen und Anfangsbedingungen liefern stets das gleiche Ergebnis.
5. Ausführbarkeit:
   • Jede Anweisung ist (z.B. für einen Prozessor) verständlich und ausführbar.
6. Allgemeingültigkeit:
   • Anwendbarkeit auf gleiche Probleme einer Problemklasse