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.
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
kurz: wenn gleiche Startwerte vorhanden sind, muss das gleiche Ergebnis raus kommen 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
kurz: die Beschreibung ist endlich 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
kurz: Fülle an Datenstrukturen und Zwischenspeicherungen sind zu jeder Zeit endlich 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
kurz: bricht nach absehbarer Zeit kontrolliert ab (Ausnahme z. B. Betriebssystem)
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
Algorithmen in der Wikipedia
In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Übersicht gibt die Liste von Algorithmen.
Algorithmen im Alltag
Auch im Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten:
Dieser Beitrag ist aus der XML-Version der deutschen WikiPedia® entwickelt worden und unterliegt inhaltlich den GNU FDL-Lizenzbestimmungen. Linkziele außerhalb der wikipedia-Inhalte unterliegen den Urheberrechten der jeweiligen Anbieter
( DirectDownloads ) Kalenderblätter druckfertig aufbereitet für Schmuckblätter zum Selbstdrucken im Word DOC6/RTF Format, je Euro 5 über Click&BuyJAN | FEB | MÄRZ APRIL | MAI | JUNI JULI | AUG | SEPT OKT | NOV | DEZ
Das Geschenk für jeden Anlass, nicht nur bei 'runden' Jubiläen Andere Einzeltage oder Zahlungsarten bitte HIER bestellen
Diese Web Site verdient ihr Geld durch Produktverkäufe (CD-ROM, downloads) und in erster Linie durch Anzeigen. Wenn Sie als Webmaster zuverlässige Partner suchen für Ihr eigenes Anzeigenschäft, dürfen Sie sich gerne auf unsere Empfehlungen stützen:
z.B.: GigaCash & ProfiWin
