ALGORITHMUS

Algorịthmus

 

[in Anlehnung an griechisch arithmós »Zahl«, entstellt aus dem Namen des persisch-arabischen Mathematikers al-Charismi] der, -/...men, Mathematik: ursprünglich das um 1600 in Europa eingeführte Rechnen mit Dezimalzahlen, heute jedes Rechenverfahren, das nach einem festgelegten, auch wiederholbaren eindeutigen Schema in einer Folge von endlich vielen, elementaren Schritten abläuft.Die Zahl der Verarbeitungsschritte, die ein Algorithmus zur Lösung eines mathematischen Problems benötigt, ist ein Maß für seine Komplexität (Komplexitätstheorie). Wesentliche Eigenschaften des insbesondere von A. Turing, A.Church und A.A. Markow geprägten modernen Algorithmusbegriffs sind dessen Determiniertheit, Allgemeinheit und Endlichkeit; eine Erweiterung bilden die nichtdeterminierten Algorithmen (z. B. stochastische Algorithmen), die bei gleichen Startbedingungen unterschiedliche Ergebnisse liefern können.

 

Beispiele für endliche Algorithmen sind die Algorithmen für die vier Grundrechenarten und der auf Intervallschachtelung beruhende Algorithmus des Wurzelziehens im Dezimalsystem, der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers, der gaußsche Algorithmus zur Auflösung von linearen Gleichungssystemen, das Horner-Schema zur Berechnung der Funktionswerte ganzrationaler Funktionen, das Sieb des Eratosthenes zur Bestimmung von Primzahlen sowie der Simplexalgorithmus der linearen Optimierung. Ein nicht abbrechender Algorithmus kann bei seiner Anwendung beliebig weit fortgesetzt werden, z. B. die Bestimmung der Dezimalbruchentwicklung der irrationalen Zahl durch Intervallschachtelung oder der transzendentenZahl π durch die Exhaustionsmethode. - Die Darstellung eines mathematischen oder logischen Problems als Algorithmus ist die Voraussetzung für dessen automatische Lösbarkeit mithilfe von Rechenanlagen.

 

Mathematische Logik:

 

Ein Algorithmus in einem formalen System bezeichnet ein Verfahren zur schrittweisen Gewinnung und Umformung von Zeichenreihen u. a. formalen Ausdrücken, der der Bildung des formalen Systems selbst zugrunde liegende Algorithmus wird als Kalkül bezeichnet. Die Untersuchung solcher Verfahren hat zur Entwicklung der Rekursionstheorie geführt.

 

Informatik:

 

allgemein eine in einer geeigneten formalisierten Sprache angegebene Folge von exakten Arbeitsanweisungen (Rechenanweisungen) an einen Computer, durch die der Lösungsweg eines mathematischen oder logischen Problems in endlich vielen ausführbaren elementaren Verarbeitungsschritten (Befehl, Anweisung) eindeutig beschrieben wird. Für derartige algorithmische Programmierungen von Rechenprozessen geeignete formalisierte Sprachen (algorithmische Sprachen) reichen von Maschinensprachen, Assemblersprachen bis zu höheren Programmiersprachen.

 

Literatur:

 

E. Horowitz u. S. Sahni: Algorithmen (a. d. Amerikan., 1981);

 F. L. Bauer u. H. Wössner: Algorithm. Sprache u. Programmentwicklung (²1984).

Algorithmus

 

Informatik: eine Folge von Anweisungen, die eine eindeutige Beschreibung der Arbeitsschritte zur Lösung eines Problems darstellt. Jedes Problem, dessen Lösung durch einen Algorithmus beschrieben werden kann, ist im Prinzip auch durch einen Computer lösbar, wobei jedoch folgende grundlegenden Anforderungen an den Algorithmus gestellt werden: Finitheit (der Algorithmus ist mit endlichen Mitteln realisierbar), Effektivität (jeder Arbeitsschritt muss richtig interpretiert und ausgeführt werden können), Terminierung (der Algorithmus muss in einer endlichen Zeit ausgeführt werden können), Determinismus (der Algorithmus muss für das gleiche Problem immer das gleiche Ergebnis liefern).

 

In der Entwurfsphase kann ein Algorithmus in beliebiger Form notiert werden. Zur Ausführung des Algorithmus auf einem Computer muss dieser in ein Programm überführt werden, wozu man sich einer entsprechenden Programmiersprache bedient. Bezüglich der Art des Algorithmus unterscheidet man zwischen iterativem, rekursivem und generischem Algorithmus. Ein iterativer Algorithmus ist dadurch charakterisiert, dass die Problemlösung aufgrund mehrfachen Durchlaufens einer oder mehrerer Schleifen erzeugt wird. Die Idee des rekursiven Algorithmus ist es, eine Funktion durch sich selbst zu beschreiben, d. h. die Funktion ruft sich immer wieder selbst auf (Rekursion). Üblicherweise sind Algorithmen in Programmen für spezielle Datentypen ausgelegt. Ein generischer Algorithmus ist so aufgebaut, dass er mit verschiedenen Datentypen arbeiten kann. Meist werden generische Algorithmen in den Standardbibliotheken verschiedener Programmiersprachen zur Verfügung gestellt und dienen z. B. zum Sortieren von Feldern oder zum Verwalten von Listen.

Algorithmus,

 

eindeutig festgelegtes Verfahren, formalisierte (Rechen)anweisung. Algorithmen gewinnen z. B. im Rahmen von Klassifikationssystemen psychischer Störungen (Zuordnung bestimmter Syndrome zu verschiedenen Diagnosesystemen beziehungsweise -kategorien) zunehmend an Bedeutung.

Algorithmus

 

[in Anlehnung an griech. arithmos »Zahl«, oder verändert hervorgegangen aus dem Namen des persisch-arabischen Mathematikers »Al-Charismi«; engl. algorithm] der, in der EDV eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie von einem mechanisch oder elektronisch arbeitenden Gerät ausgeführt werden kann. Ein Algorithmus gibt demzufolge an, wie Eingabedaten schrittweise in Ausgabedaten umgewandelt werden. Er kann in natürlicher Sprache oder in einer Programmiersprache formuliert sein oder auch in Form eines Programmablaufplans bzw. einesStruktogramms dargestellt werden. Für die Lösung ein und desselben Problems existieren meist mehrere Algorithmen, die sich in ihrer Länge sowie der für die Ausführung benötigten Zeit unterscheiden. Häufig verwendete Algorithmen zur Sortierung von Daten sind etwa Bubble Sort, Heap Sort und Quick Sort.

 

Algorithmen besitzen einige charakteristische Eigenschaften:

 

- Ein Algorithmus löst i. A. eine Klasse von Problemen. Die Lösung eines einzelnen Problems aus dieser Klasse wird durch Eingabe der entsprechenden Parameter gefunden.

 

- Algorithmen sind determiniert, d. h., sie liefern stets das gleiche Ergebnis, wenn ein Algorithmus mit den gleichen Eingabewerten und Startbedingungen wiederholt wird. Eine Erweiterung bilden sog. nicht determinierte Algorithmen (z. B. die stochastischen Algorithmen), die bei gleichen Startbedingungen unterschiedliche Ergebnisse (u. U. auch falsche) liefern können.

 

- Die Beschreibung eines Algorithmus besitzt eine endliche Länge. Ferner darf der Algorithmus einschließlich seiner bearbeiteten Daten zu jedem Zeitpunkt nur endlich viel Platz belegen.

 

- Für die Praxis sind meist nur solche Algorithmen von Bedeutung, die für jede Eingabe nach endlich vielen Schritten ein Resultat liefern und anhalten. Ausnahmen sind z. B. Steuerungsalgorithmen wie das zentrale Steuerprogramm eines Rechnersystems (Betriebssystem).

 

- Ein Algorithmus heißt deterministisch, wenn zu jedem Zeitpunkt seiner Ausführung höchstens eine Möglichkeit der Fortsetzung besteht. So stellen z. B. Programme in imperativen Programmiersprachen meist deterministische Algorithmen dar. Hat ein Algorithmus an gewissen Stellen mehrere Möglichkeiten der Fortsetzung, von denen man nach Belieben eine auswählen kann, so heißt er nicht deterministisch. Bei stochastischen Algorithmen kann man den Fortsetzungsmöglichkeiten Wahrscheinlichkeiten zuordnen.