Wikipedia

Algorithmus

endliche, eindeutige Handlungsvorschrift zur Lösung eines Problems
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 27. Juni 2004 um 22:28 Uhr durch 217.224.160.170 (Diskussion) (→Determinismus). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Ein Algorithmus ist eine genau definierte Verarbeitungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen. Typischerweise wird ein Algorithmus durch eine endliche Folge von Anweisungen beschrieben, die nacheinander ausgeführt und oft in festgelegter Weise wiederholt werden.

Im täglichen Leben kommen Algorithmen sehr häufig vor. Zum Beispiel ist ein Kochrezept ein Algorithmus. Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum Ausfüllen von Formularen sind in der Regel Algorithmen. Sehr verbreitet sind Algorithmen in der Informatik: Dort steuern sie, in der Form von Computerprogrammen oder elektronischen Schaltkreisen, Rechner und Maschinen.

Die Theoretische Informatik beschäftigt sich u.a. mit der Frage, welche Problemstellungen algorithmisch, d.h. mittels genau definierter Handlungsanweisungen, gelöst werden können und wie rechenaufwendig Lösungen gegebener Probleme mindestens sind.

Ein Beispiel: der Euklidische Algorithmus

Der Euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, dient zur Ermittlung des größten gemeinsamen Teilers zweier natürlicher Zahlen A und B:

  1. Sei A die größere der beiden Zahlen A und B (entsprechend vertauschen, falls dies nicht bereits so ist)
  2. Setze A = A – B
  3. Wenn A und B ungleich sind, dann fahre fort mit Schritt 1, wenn sie gleich sind, dann beende den Algorithmus: Diese Zahl ist der größte gemeinsame Teiler.

Ausführung:

Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus verwendet:

A B A-B
1. 14 8 6
2. 8 6 2
3. 6 2 4
4. 4 2 2
5. 2 2 gleich


Das Ergebnis ist also 2.

Geschichte

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens Muhammad ibn Musa al-Chwarizmi (* ca. 783, † ca. 850), des Autors des Buchs Hisab al-dschabr wa-l-muqabala (825, Regeln zur Wiederherstellung und Reduktion), durch das die Algebra im Westen verbreitet wurde. Die lateinische Fassung beginnt mit: "Dixit Algorithmi..." womit der Autor gemeint war. Das Wort Algebra stammt ebenfalls (al-Jabr – "Einrenkung") aus dem Titel des Buchs. Ursprünglich stand das Wort Algorism nur für die Regeln zur Arithmetik mit arabischen Ziffern. Heute steht es für alle geregelten Prozeduren, mit denen Probleme aller Art gelöst werden können.

Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace, in ihren Notizen zu Charles Babbage's Analytical Engine, festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Exaktere Definitionen

Die mangelnde mathematische Genauigkeit in der gängigen Definition eines Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. Insbesondere steht die natürliche Sprache mit ihren Unschärfen und Widersprüchlichkeiten der Forderung nach Eindeutigkeit und Widerspruchsfreiheit im Wege.

In der ersten Hälfte des 20. Jahrhunderts wurden eine ganze Reihe von Ansätzen entwickelt, um zu einer genauen Definition zu kommen. Der bekannteste ist wohl Alan Turings Konzept der Turing-Maschine als ein abstraktes Modell eines Computers.

Andere gängige Konzepte sind beispielsweise rekursive Funktionen, Zeichen-Ersetzungssysteme wie Markov-Algorithmen oder Chomsky-Grammatiken oder verallgemeinerte abstrakte Programmiersprachen mit den Grundelementen Schrittsequenz, Bedingungsanweisung und Schleife.

Church-Turing These

Um die Mitte des 20. Jahrhunderts konnte, unter maßgeblicher Beteiligung von Alan Turing selbst, gezeigt werden, dass all diese Methoden ebenso leistungsfähig sind wie eine Turing-Maschine: Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren.

Aus diesem Grunde ist heutzutage die Church-Turing-These, jeder Algorithmus kann durch eine Turingmaschine ausgeführt werden, allgemein akzeptiert. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen zu einer Turing-Maschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache.

Formale Definition und Eigenschaften

Formal ist ein Algorithmus eine Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen. Dabei müssen folgende Bedingungen erfüllt sein:

  1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
  2. Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).
  3. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
  4. Das Verfahren darf zum Ausführen nicht unendlich viel Speicherplatz benötigen (Dynamische Finitheit).
  5. Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein. (Ausführbarkeit)
  6. Der Algorithmus darf nur endlich viele Schritte benötigen. Jeder einzelne Schritt muss in endlicher Zeit ausführbar sein. (Terminierung)

Eine Ausnahme bilden stochastische Algorithmen, bei denen der jeweils nächste Verfahrensschritt von einer Wahrscheinlichkeitsregel abhängen kann.

Determiniertheit

Algorithmen sind determiniert: Werden sie mit gleichen Parametern und Startwerten aufgerufen, liefern sie stets das gleiche Resultat. Ausnahme bilden randomisierte und stochastische Algorithmen, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.

Determinismus

kurz: es darf nur immer eine Möglichkeit vorhanden sein (--> sonst stochastisch)

Deterministisch heißen alle Algorithmen, bei denen zu jedem Zeitpunkt der Ausführung maximal eine Möglichkeit der Programmfortsetzung besteht. Gibt es mehrere Möglichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen, so spricht man von stochastischen, randomisierten oder probabilistischen Algorithmen. In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus, der aber in praktischen Algorithmen nicht vorkommen kann.

Finitheit

Statische Finitheit

Die Beschreibung eines Algorithmus ist nicht unendlich groß. Als statische Finitheit wird die Endlichkeit des Quelltextes bezeichnet. Der Quelltext darf nur begrenzten, wenn auch bei Bedarf sehr viel Speicherplatz in Anspruch nehmen.

Dynamische Finitheit

Zu jedem Zeitpunkt der Ausführung darf der von einem Algorithmus benötigte Speicherbedarf nur endlich groß sein. Andernfalls wäre der Algorithmus nicht ausführbar. Dies wird als dynamische Finitheit bezeichnet.

Terminierung

Algorithmen sind terminierend, sie kommen nach einer endlichen Zahl von Schritten zu einem Ergebis. Die tatsächliche Zahl der Schritte kann jedoch willkürlich groß sein. Steuerungssysteme und Betriebssysteme erfüllen diese Eigenschaft nicht. Donald Knuth schlägt vor nicht terminierende Algorithmen als rechnergestützte Methoden ("Computational Methods") zu bezeichnen.

Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in einer Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in theoretischen Pseudosprachen (Pseudocode) geschrieben und untersucht.

Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorie behandelt, die Ergebnisse werden als asymptotische Laufzeiten angegeben. Das Verhalten bezüglich Terminierung, d.h. ob der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

Beispiele

In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Übersicht gibt die Liste von Algorithmen.

Siehe auch

Literatur

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Algorithmus&oldid=1660012“