Algorithmus

mini|Al-Chwarizmi, der aus Choresmien stammende Namensgeber des Algorithmus, auf einer 1983 herausgegebenen sowjetischen Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums

Ein Algorithmus (benannt nach dem Mathematiker und Universalgelehrten al-Chwarizmi, von arabisch: ) ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten.Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, S. 2. Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.

Definition Ein Algorithmus ist eine klare, endliche Abfolge von Anweisungen, die ein Problem löst oder eine Aufgabe ausführt. Um dies jedoch mit mathematischer Strenge zu definieren, benötigt man ein mathematisches Modell, welches beschreibt, wie mathematische Funktionen eine Eingabe in eine Ausgabe umwandeln, sogenannte Berechenbarkeitsmodelle. Das Referenz-Modell ist die Turingmaschine.Vorlesungsskriptum Theoretische Informatik 1, Institut für Grundlagen der Informationsverarbeitung Technische Universität Graz, März 2016, abrufbar unter

https://igi-web.tugraz.at/lehre/TI1/skriptum/ti1-skriptum-160303.pdf

Turingmaschinen und Algorithmusbegriff Der Mangel an mathematischer Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts, weswegen in der ersten Hälfte des 20. Jahrhunderts eine ganze Reihe von Ansätzen entwickelt wurde, die zu einer genauen Definition führen sollten. Eine zentrale Rolle nimmt hier der Begriff der Turingmaschine von Alan Turing ein. Weitere Formalisierungen des Berechenbarkeitsbegriffs sind die Registermaschinen, der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken (siehe Chomsky-Hierarchie) und Markow-Algorithmen.

Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden die gleiche Berechnungsstärke besitzen (gleich mächtig sind). Sie können durch eine Turingmaschine emuliert werden, und sie können umgekehrt eine Turingmaschine emulieren.

Formale Definition Mit Hilfe des Begriffs der Turingmaschine 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.“

Eigenschaften des Algorithmus Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:

Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit). Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit). Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität). 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:

Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit). Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

Church-Turing-These Die Church-Turing-These besagt, dass jedes intuitiv berechenbare Problem durch eine Turingmaschine gelöst werden kann. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turingmaschine ä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, das heißt, wenn eine entsprechend programmierte Turingmaschine das Problem in endlicher Zeit lösen könnte.

Es sei bemerkt, dass die Ambiguität des Begriffs „intuitiv berechenbares Problem“ den mathematischen Beweis dieser These unmöglich macht. Es ist also theoretisch denkbar, dass intuitiv berechenbare Probleme existieren, die nach dieser Definition nicht als „berechenbar“ gelten. Bis heute wurde jedoch noch kein solches Problem gefunden.

Abstrakte Automaten Turingmaschinen harmonieren gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.

Diese Maschinen weichen etwa in der Mächtigkeit der Befehle ab; statt der einfachen Operationen der Turingmaschine können sie teilweise mächtige Operationen, wie etwa Fourier-Transformationen, in einem Rechenschritt ausführen.

Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen parallele Operationen, wie etwa die Addition zweier Vektoren in einem Schritt.

Ein Modell einer echten Maschine ist die (kurz )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 etwa 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).

Informatik und Mathematik Algorithmen sind eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der theoretischen Informatik, der Komplexitätstheorie und der Berechenbarkeitstheorie, mitunter ist ihnen ein eigener Fachbereich Algorithmik oder Algorithmentheorie gewidmet. In Form von Computerprogrammen und elektronischen Schaltungen steuern Algorithmen Computer und andere Maschinen.

Algorithmus und Programme Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktem Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (das heißt, 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, das heißt, einer idealen mathematischen Maschine).

Ein Algorithmus beschreibt eine Vorgehensweise in ihren Teilschritten, zu deren Erledigung wiederum Algorithmen benötigt werden. Beispielsweise werden für die Lösung Quadratischer Gleichungen die Grundrechenarten verwendet. Entsprechend wird in Programmen auf Operatoren zurückgegriffen, welche in die Programmiersprache integriert sind, oder auf Programmbibliotheken. Guter Programmcode zeichnet sich dadurch aus, dass der Teil mit dem eigentlichen Algorithmus kompakt und nachvollziehbar bleibt, während nebensächliche Details in Unterprogramme ausgliedert sind (Modularisierung).

Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch dargestellt werden.

Erster Computeralgorithmus Der erste für einen Computer gedachte Algorithmus (zur Berechnung von Bernoullizahlen) wurde 1843 von Ada Lovelace in ihren Notizen zu Charles Babbages Analytical Engine festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Heutige Situation mini|Prinzipbild des Rete-Algorithmus für Expertensystem; veröffentlicht: 1979

Algorithmen für Computer sind heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz im Kfz über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von Algorithmen. Hinsichtlich der Ideen und Grundsätze, die einem Computerprogramm zugrunde liegen, wird einem Algorithmus in der Regel urheberrechtlicher Schutz versagt.Deutschland: Abs. (2) UrhG. Je nach nationaler Ausgestaltung der Immaterialgüterrechte sind Algorithmen der Informatik jedoch dem Patentschutz zugänglich, so dass urheberrechtlich freie individuelle Werke, als Ergebnis eigener geistiger Schöpfung, wirtschaftlich trotzdem nicht immer frei verwertet werden können. Dies betrifft oder betraf z. B. Algorithmen, die auf der Mathematik der Hough-Transformation (Jahrzehnte alt, aber mehrfach aktualisiertes Konzept mit Neu-Anmeldung) aufbauen, Programme, die das Bildformat GIF lesen und schreiben wollten, oder auch Programme im Bereich der Audio- und Video-Verarbeitung, da die zugehörigen Algorithmen, wie sie in den zugehörigen Codecs umgesetzt sind, oftmals nicht frei verfügbar sind. Die entsprechenden Einsparpotentiale für alle Anwender weltweit (für den Rete-Algorithmus wurde einst eine Million USD auf DEC XCON genannt) dürften heute problemlos die Grenze von einer Milliarde USD im Jahr um ein Zigfaches überschreiten.

Populärer Gebrauch des Begriffs Der Begriff des Algorithmus hat seit etwa 2015 im Kontext des Online-Marketing Einzug in die Presse- und Alltagssprache gehalten. Algorithmen bestimmen insbesondere bei werbefinanzierten Angeboten, welche Inhalte und welche Werbeanzeigen dem Anwender gezeigt werden. Ziel dieser Algorithmen ist es, den Anwender lange auf der jeweiligen Plattform zu halten und ihm solche Anzeigen einzublenden, bei denen die Wahrscheinlichkeit eines Klicks am höchsten ist. Der Begriff „Algorithmus“ fällt auch allgemein, wenn eine Software nach unbekannten, aber offensichtlich komplexen Regeln entscheidet. Beispielsweise, welche Ergebnisse von einer Suchmaschine angezeigt werden. Dabei schwingt häufig ein gewisses Unbehagen mit, eben weil der Algorithmus nicht transparent ist.

In der Diskussion nicht scharf davon abgegrenzt ist der Begriff „Künstliche Intelligenz“. Sie bedient sich ebenfalls Algorithmen zur Lösung vorgegebener Probleme. Von künstlicher Intelligenz wird aber im Allgemeinen nur gesprochen, wenn zusätzlich auf einen Vorrat zuvor erlernten Wissens zugegriffen wird, wobei in der Lernphase charakteristische Muster identifiziert und eingeordnet werden. Mit einer passenden Wissensbasis ist es geeigneten Algorithmen beispielsweise möglich, natürliche geschriebene und gesprochene Sprache zu verarbeiten, Gesichter oder beliebige Objekte zu identifizieren, oder Texte zu formulieren.

Abgrenzung zur Heuristik

Der Übergang zwischen Algorithmus und Heuristik ist fließend: Eine Heuristik ist eine Methode, aus unvollständigen Eingangsdaten zu möglichst sinnvollen Ergebnissen zu gelangen. Viele heuristische Vorgehensweisen sind selbst exakt definiert und damit Algorithmen. Bei manchen ist jedoch nicht in jedem Schritt genau festgelegt, wie vorzugehen ist – der Anwender muss „günstig raten“. Sie können nicht (vollständig) als Algorithmus formuliert werden.

Eigenschaften Determiniertheit Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.

Determinismus Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist. Wenn an mindestens einer Stelle mehr als eine Möglichkeit besteht (ohne Vorgabe, welche zu wählen ist), dann ist der gesamte Algorithmus nichtdeterministisch.