Der Algorithmusbegriff

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

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.

Inhaltsverzeichnis

Der intuitive Algorithmusbegriff

Es ist recht schwierig, eine formal exakte Definition für den Begriff Algorithmus anzugeben.
Wir begnügen uns deshalb 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:
    • endliche Notation des Algorithmus,
    • Nutzung endlicher Ressourcen (z.B. begrenzter Arbeitsspeicher / begrenzte Rechenzeit),
    • endlich viele Abarbeitungsschritte (z.B. begrenzte Rekursionstiefe),
  2. Eindeutigkeit:
    • nach jedem Abarbeitungsschritt besteht höchstens eine Möglichkeit der Fortsetzung,
    • gleiche Eingabegrößen und Anfangsbedingungen liefern stets das gleiche Ergebnis (Determiniertheit),
  3. Ausführbarkeit:
    • jede Anweisung ist (z.B. für einen Prozessor) verständlich und ausführbar,
  4. Allgemeingültigkeit:
    • Anwendbarkeit auf gleiche Probleme einer Problemklasse.

Beispiele

Der Euklidische Algorithmus

Mit diesem Algorithmus, der nach dem griechischen Mathematiker Euklid von Alexandria (* um 360 v. Chr.; † um 280 v. Chr.) benannt ist, lässt sich der größte gemeinsame Teiler (ggT) zweier natürlicher Zahlen bestimmen.

Beschreibung:

  • Der größte gemeinsame Teiler der Zahlen $m$ und $n$ ist $m$, falls $n=0$ ist.
  • Anderenfalls berechnet er sich aus dem größten gemeinsamen Teiler von $n$ und dem Rest der ganzzahligen Division $\tfrac{m}{n}$.

Implementation:

 

Quelltext überprüfen:

Das Sieb des Eratosthenes

Der griechische Mathematiker, Geograph, Philosoph, Philologe und Dichter Eratosthenes von Kyrene (* zwischen 276 und 273 v. Chr.; † um 194 v. Chr.) war der erste Gelehrte der Antike, der durch eine wissenschaftlich fundierte Messung den Umfang der Erde mit erstaunlicher Genauigkeit bestimmt hat.
Auf ihn geht aber auch ein interessanter Algorithmus zur Bestimmung aller Primzahlen zurück.

Beschreibung:

  • Notiere die natürlichen Zahlen, beginne mit $2$.
$2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...$
  • Unterstreiche die $2$ und streiche alle Vielfachen von $2$.
$\underline{2}, 3, 4\!\!\!\!/, 5, 6\!\!\!\!/, 7, 8\!\!\!\!/, 9, 10\!\!\!\!\!\!/, 11, 12\!\!\!\!\!\!/, 13, 14\!\!\!\!\!\!/, 15, 16\!\!\!\!\!\!/, 17, 18\!\!\!\!\!\!/, 19, 20\!\!\!\!\!\!/, ...$
  • Unterstreiche die erste freie Zahl (in diesem Falle die Zahl $3$) und streiche deren Vielfachen.
$\underline{2}, \underline{3}, 4\!\!\!\!/, 5, 6\!\!\!\!/, 7, 8\!\!\!\!/, 9\!\!\!\!/, 10\!\!\!\!\!\!/, 11, 12\!\!\!\!\!\!/, 13, 14\!\!\!\!\!\!/, 15\!\!\!\!\!\!/, 16\!\!\!\!\!\!/, 17, 18\!\!\!\!\!\!/, 19, 20\!\!\!\!\!\!/, ...$
  • Verfahre mit allen weiteren freien Zahlen ebenso.
$\underline{2}, \underline{3}, 4\!\!\!\!/, \underline{5}, 6\!\!\!\!/, \underline{7}, 8\!\!\!\!/, 9\!\!\!\!/, 10\!\!\!\!\!\!/, \underline{11}, 12\!\!\!\!\!\!/, \underline{13}, 14\!\!\!\!\!\!/, 15\!\!\!\!\!\!/, 16\!\!\!\!\!\!/, \underline{17}, 18\!\!\!\!\!\!/, \underline{19}, 20\!\!\!\!\!\!/, ...$
  • Alle unterstrichenen Zahlen sind Primzahlen.

Implementation:
Zunächst scheint diese Beschreibung gegen die Forderung der Endlichkeit zu verstoßen: Bereits das Notieren der natürlichen Zahlen, beginnend mit $2$, wäre endlos.
Wir benutzen deshalb das Konzept der verzögerten Evaluation und repräsentieren die natürlichen Zahlen als Stream.
Das Streichen teilbarer Zahlen erfolgt mit der bekannten Prozedur stream-filter:

Man beachte, dass primzahlstream keine Prozedur ist. Vielmehr werden an diesen Namen alle, d.h. unendlich viele Primzahlen gebunden!

Aufgaben

  1. Geben Sie typische Algorithmen aus dem Alltag an.
  2. Beschreiben Sie Vorgänge oder Abläufe, auf die sich offensichtlich der intuitive Algorithmusbegriff nicht anwenden lässt. Begründen Sie.
  3. Begründen Sie, warum auch das Sieb des Eratosthenes als Algorithmus bezeichnet werden kann.

Zum Weiterarbeiten

Erstellen Sie für einen der nachfolgenden Algorithmen die entsprechende Seite im ProgrammingWiki.

Von „https://programmingwiki.de/Grundlagen_der_funktionsorientierten_Programmierung_mit_SCHEME/Der_Algorithmusbegriff“
Persönliche Werkzeuge