Zum Inhalt springen

Algorithmus

Links bearbeiten
Diese Seite befindet sich derzeit im Review-Prozess
aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 9. Oktober 2004 um 16:16 Uhr durch Dirk Beyer~dewiki (Diskussion | Beiträge) (Anweisung -> Regel, Tippfehler). 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. Ein Algorithmus wird durch eine endliche Menge von Regeln definiert, die nacheinander angewendet und oft nach bestimmten Bedingungen wiederholt werden. Ein Algorithmus terminiert, d.h. nach endlich vielen Schritten wird ein Ergebnis ausgegeben. Transformationsprogramme, die nach dem Prinzip Eingabe-Verarbeitung-Ausgabe arbeiten, haben diese Eigenschaft. Bei Steuerungsprogrammen, wie zum Beispiel in Bargeldautomaten, ist diese Eigenschaft nicht erwuenscht.

Im täglichen Leben lassen sich leicht Beispiele für Algorithmen finden: Zum Beispiel ist ein Kochrezept ein Algorithmus - zumindest dann, wenn alle Angaben genau genug sind und es für alle "Unterprogramme" wie Braten, Rühren, etc ebenfalls Algorithmen gibt. Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum Ausfüllen von Formularen sind in der Regel Algorithmen. Ein weiteres, etwas präziseres Beispiel sind Waschmaschinenprogramme.

Vor allem aber sind Algorithmen eine der zentralen Themen der Informatik und 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.

In der Informatik entspricht jeder Algorithmus einer formalen Grammatik, das zu lösende Problem entspricht der formalen Sprache, die durch diese Grammatik definiert ist. Der Algorithmus kann dann als Programm für ein bestimmtes Maschinenmodell formuliert werden, so dass der resultierende Automat die gewünschte Sprache akzeptiert.

Ein Beispiel: der Euklidische Algorithmus

Der Euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, dient zur Ermittlung des größten gemeinsamen Teilers (ggT) 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.

Beispiel:

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 abstraktes Modell eines Computers.

Andere gängige Konzepte sind beispielsweise rekursive Funktionen, insbesondere der Lambda-Kalkül, Zeichen-Ersetzungssysteme wie Markov-Algorithmen oder Chomsky-Grammatiken oder verallgemeinerte abstrakte Programmiersprachen mit den Grundelementen Sequenz, Auswahl und Wiederholung.

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 (gleich mächtig) 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 lautet heutzutage die Church-Turing-These: "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 berechenbar ist genau dann 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.

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. 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).

Die meisten nützlichen Algorithmen erfüllen zudem folgende Eigenschaften:

  1. Der Algorithmus darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität)
  2. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
  3. Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

In einigen Bereichen werden algorithmen, die bestimmte dieser Anforderungen nicht erfüllen, gar nicht als Algorithmen bezeichnet. Vor allem die Terminiertheit wird häufig als notwendige Eigenschaft vorausgesetzt. 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 so genannte 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

kurz: wenn gleiche Startwerte vorhanden sind, muss das gleiche Ergebnis raus kommen

Algorithmen sind determiniert, wenn sie stets das gleiche Resultat liefern wenn man sie mit gleichen Parametern und Startwerten aufgerufen. Das trifft zum Beispiel nicht für randomisierte Algorithmen zu, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.

Es gibt übrigens: jeder deterministische Algorithmus ist auch determiniert. Nicht jeder determinierte Algorithmus ist jedoch deterministisch.

Determinismus

kurz: es darf nur immer 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 Algorithmen kaum verwendung findet. Zusätzliche bedeutung bekommt solche nichtderteministischen Algorithmen allerdings durch die Möglichkeit von Quantencomputern, auch solche Algorithmen erfolgreich auszuführen.

Es gibt übrigens: jeder deterministische Algorithmus ist auch determiniert. Nicht jeder determinierte Algorithmus ist jedoch deterministisch.

Finitheit

Statische Finitheit

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

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.

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 möglich, für einen Algorithmus zu bestimmen, ob er terminiert oder nicht - siehe Halteproblem.

Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist 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 ggT 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

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 und die Kategorie Algorithmus.

Algorithmen im Alltag

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 Klaviersonate Pianist Partitur Datei:Notengruppe.png
Bedienung eines Handys Anrufer Bedienungsanleitung drücke die # Taste
Bau eines Radios Radiobastler Schaltplan und Montageanleitung verbinde Transistor T1 mit T5
Kassieren im Supermarkt Kassiererin an Registrierkasse Bedienungsanleitung für Registrierkasse, Funktionsplan der Registrierkasse Eintasten von 17,82 +

Siehe auch

Literatur

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