Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens von Muhammed Al Chwarizmi (* ca. 783; † ca. 850), einem Perser, dessen arabisches Lehrbuch Über das Rechnen mit indischen Ziffern (um 825) in der mittelalterlichen lateinischen Übersetzung mit den Worten "Dixit Algorismi" begann. Im Mittelalter wurde daraus lat. algorismus (mit lat. Varianten wie alchorismus, algoarismus, altfranzösisch algorisme, argorisme, mittel-englisch augrim, augrym) als Bezeichnung für die Kunst des Rechnens mit den arabischen Ziffern und als Titel für Schriften über diese Kunst.
Die lateinischen Autoren pflegten zu erklären, dass das Wort 'algorismus' aus dem Namen des Erfinders dieser Kunst, einem Philosophen namens Algus, und dem griechischen Wort rismus (rhythmós) für 'Zahl' zusammengesetzt sei. Dabei wurde Algus von einigen als Araber, von anderen als Grieche oder zumindest griechisch schreibender Autor, oder gelegentlich auch als 'König von Kastilien' (Johannes von Norfolk) betrachtet. In der volkssprachlichen Tradition erscheint dieser 'Meister Algus' dann zuweilen in einer Reihe mit großen antiken Schriftstellern wie Platon, Aristoteles und Euklid, so im altfranzösischen Roman de la Rose, während das altitalienische Gedicht Il Fiore ihn sogar als Erbauer des Schiffes Argo ausgibt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab.
Durch Gräzisierung der Schreibweise des angenommen griechischen Wortbestandteiles rismus hat sich dann in der lateinischen Wissenschaftssprache die Schreibung 'algorithmus' ergeben, und in dieser Form hat sich das Wort später als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme eingebürgert.
Informatik und Mathematik [Bearbeiten]
Vor allem aber sind Algorithmen eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, wie der Algorithmentheorie, der Komplexitätstheorie und der Berechenbarkeitstheorie. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern sie Computer und andere Maschinen.
Algorithmus und Programm [Bearbeiten]
Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktes Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (d. h., die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von Turingmaschinen (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, d. h., einer idealen mathematischen Maschine).
Erster Computeralgorithmus [Bearbeiten]
Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace in ihren Notizen zu Charles Babbages 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.
Definition [Bearbeiten]
Die mangelnde mathematische Genauigkeit des Begriffs 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.
Turingmaschinen und Algorithmusbegriff [Bearbeiten]
In der ersten Hälfte des 20. Jahrhunderts wurde eine ganze Reihe von Ansätzen entwickelt, um zu einer genauen Definition zu kommen. Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing), der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen.
Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden ebenso leistungsfähig (gleich mächtig) sind. Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren.
Mit Hilfe des Begriffs der Turing-Maschine kann folgende formale Definition des Begriffs formuliert werden:
Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.
Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:
1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
2. Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein (Ausführbarkeit).
3. Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität).
4. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität).
Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:
1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
2. Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).
Church-Turing-These [Bearbeiten]
Die Church-Turing-These lautet: „Jedes intuitiv berechenbare Problem kann durch eine Turingmaschine gelöst werden.“ 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 – die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben.
Der Begriff der Berechenbarkeit ist dadurch dann so definiert, dass ein Problem genau dann berechenbar ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, d. h. wenn eine entsprechend programmierte Turing-Maschine das Problem in endlicher Zeit lösen könnte.
Abstrakte Automaten [Bearbeiten]
Turingmaschinen harmonieren sehr gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.
Diese Maschinen weichen z. B. in der Mächtigkeit der Befehle ab; anstatt den einfachen Operationen der Turingmaschine können sie z. T. sehr mächtige Operationen, wie z. B. Fouriertransformationen, in einem Rechenschritt ausführen.
Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen sehr parallele Operationen, wie z. B. die Addition zweier Vektoren in einem Schritt.
Ein Modell einer realeren Maschine ist die Sequential Abstract State Machine (seq. ASM) mit folgenden Eigenschaften:
Ein Algorithmus einer seq. ASM soll
* durch einen endlichen Programmtext spezifiziert werden können
* schrittweise ausgeführt werden können
* für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären z. B. ein Programm das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
* nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
* nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration)
Eigenschaften [Bearbeiten]
Nichtdeterministische Algorithmen finden vor allem in der Theoretischen Informatik Anwendung, so, dass in anderen Bereichen oft vorausgesetzt wird, dass es sich um einen deterministischen Algorithmus handelt. Eine Ausnahme bilden sogenannte stochastische randomisierte oder probabilistische Algorithmen, in die absichtlich ein Zufallsfaktor eingebaut wurde. Solche Algorithmen sind demnach nicht deterministisch und auch nicht determiniert. Stochastische Algorithmen dagegen sind im Allgemeinen deterministisch, orientieren sich aber an Erfahrungswerten.
Die verschiedenen formalen Eigenschaften in Kürze:
Determiniertheit [Bearbeiten]
Kurz: Bei jeder Ausführung mit gleichen Startwerten muss das gleiche Ergebnis berechnet werden.
Algorithmen sind determiniert, wenn sie bei gleichen Parametern und Startwert stets das gleiche Resultat liefern. Das trifft zum Beispiel nicht für randomisierte Algorithmen zu, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.
Determinismus [Bearbeiten]
Kurz: Es darf immer nur eine Möglichkeit vorhanden sein.
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 der Praxis kaum Verwendung findet. Zusätzliche Bedeutung bekommen solche nichtdeterministische Algorithmen allerdings durch den Einsatz von Quantencomputern, welche auch solche Algorithmen erfolgreich ausführen.
Es gilt übrigens: Jeder deterministische Algorithmus ist auch determiniert. Nicht jeder determinierte Algorithmus ist jedoch deterministisch.
Finitheit [Bearbeiten]
Statische Finitheit [Bearbeiten]
Kurz: Die Beschreibung ist endlich.
Die Beschreibung eines Algorithmus darf nicht unendlich groß sein. Als statische Finitheit wird die Endlichkeit des Quelltextes bezeichnet. Der Quelltext darf nur eine begrenzte Anzahl, wenn auch bei Bedarf sehr viele Regeln enthalten.
Dynamische Finitheit [Bearbeiten]
Ein Algorithmus benötigt zu jedem Zeitpunkt seiner Ausführung nur endlich viel Speicherplatz. Diese Bedingung ist notwendig, da keinem Algorithmus unendlich viel Speicherplatz zur Verfügung steht.
Terminiertheit [Bearbeiten]
Kurz: Der Algorithmus bricht nach endlicher Zeit kontrolliert ab.
Algorithmen sind terminierend, wenn sie für jede mögliche Eingabe nach einer endlichen Zahl von Schritten zu einem Ergebnis kommen. Die tatsächliche Zahl der Schritte kann dabei beliebig groß sein.
Steuerungssysteme und Betriebssysteme und auch viele Programme, die auf Interaktion mit dem Benutzer aufbauen, erfüllen diese Eigenschaft nicht: Wenn der Benutzer keinen Befehl zum Beenden gibt, läuft das Programm endlos weiter. Donald Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden ("Computational Methods") zu bezeichnen.
Es ist übrigens im Allgemeinen nicht für jeden beliebigen Algorithmus möglich zu bestimmen, ob er terminiert oder nicht - siehe Halteproblem.
Algorithmenanalyse [Bearbeiten]
Die Erforschung und Analyse von Algorithmen ist eine Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine 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 eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik 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. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, d. h. die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren größter gemeinsamer Teiler gesucht wird, oder wie viele Elemente sortiert werden müssen etc.
Das Verhalten bezüglich der Terminierung, d. h. ob der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.
Beispiele [Bearbeiten]
Algorithmen in der Wikipedia [Bearbeiten]
In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Übersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus.
Algorithmen im Alltag [Bearbeiten]
Auch im Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten:
Prozess Ausführender Algorithmus Typische Anweisung
Kuchenbacken Bäcker Rezept nimm 1 Pfund Mehl / rolle Teig aus
Spielen einer Melodie Sänger, Instrumentalist Tonfolge Bild:Notengruppe.png
Bedienung eines Handys Anrufer Bedienungsanleitung drücke die Taste #
Bau eines Radios Radiobastler Schaltplan und Montageanleitung verbinde die Basis von Transistor T1 mit dem Kollektor von T5
Kassieren im Supermarkt Kassiererin an Registrierkasse Bedienungsanleitung für Registrierkasse, Funktionsplan der Registrierkasse Eintippen von 17,82 +
|
1 |
2
Thread abonnieren
