Algorithmus
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.
Table of contents |
2 Geschichte 3 Formale Definition und Eigenschaften 5 Beispiele 6 Siehe auch 7 Literatur 8 Weblinks |
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:
Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus verwendet:
Ein Beispiel: der Euklidische Algorithmus
Ausführung:
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.
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.
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.
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.
Formal ist ein Algorithmus eine Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen. Dabei müssen folgende Bedingungen erfüllt sein:
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.
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.
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.
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.
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.
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.
Geschichte
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.Church-Turing These
Formale Definition und Eigenschaften
Eine Ausnahme bilden stochastische Algorithmen, bei denen der jeweils nächste Verfahrensschritt von einer Wahrscheinlichkeitsregel abhängen kann.Determiniertheit
Determinismus
Finitheit
Statische Finitheit
Dynamische Finitheit
Terminierung
Algorithmenanalyse
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.
Prozess | Ausführender | Algorithmus | Typische Anweisung |
---|---|---|---|
Kuchenbacken | Bäcker | Rezept | nimm 1 Pfund Mehl / rolle Teig aus |
Spielen einer Klaviersonate | Pianist | Partitur | |
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
Weblinks