Algorithmus
In der Mathematik und Informatik ist ein Algorithmus (/ˈælɡərɪðəm/ (
listen)) ist eine endliche Folge strikter Anweisungen, die in der Regel zur Lösung einer Klasse spezifischer Probleme oder zur Durchführung einer Berechnung verwendet werden. Algorithmen werden als Spezifikationen für die Durchführung von Berechnungen und die Datenverarbeitung verwendet. Durch den Einsatz künstlicher Intelligenz können Algorithmen automatische Schlussfolgerungen ziehen (als automatisches Denken bezeichnet) und mathematische und logische Tests verwenden, um die Ausführung des Codes auf verschiedene Wege zu lenken (als automatische Entscheidungsfindung bezeichnet). Die Verwendung menschlicher Eigenschaften zur Beschreibung von Maschinen in metaphorischer Weise wurde bereits von Alan Turing mit Begriffen wie "Gedächtnis", "Suche" und "Stimulus" praktiziert. ⓘ
Im Gegensatz dazu ist eine Heuristik ein Ansatz zur Problemlösung, der möglicherweise nicht vollständig spezifiziert ist oder keine korrekten oder optimalen Ergebnisse garantiert, insbesondere in Problembereichen, in denen es kein klar definiertes korrektes oder optimales Ergebnis gibt. ⓘ
Als wirksame Methode kann ein Algorithmus innerhalb einer endlichen Menge an Raum und Zeit und in einer wohldefinierten formalen Sprache zur Berechnung einer Funktion ausgedrückt werden. Ausgehend von einem anfänglichen Zustand und einer anfänglichen (vielleicht leeren) Eingabe beschreiben die Anweisungen eine Berechnung, die bei ihrer Ausführung eine endliche Anzahl wohldefinierter aufeinanderfolgender Zustände durchläuft, schließlich eine "Ausgabe" erzeugt und in einem endgültigen Endzustand endet. Der Übergang von einem Zustand zum nächsten ist nicht notwendigerweise deterministisch; einige Algorithmen, die als randomisierte Algorithmen bekannt sind, beinhalten eine zufällige Eingabe. ⓘ
.png)
Geschichte
Das Konzept des Algorithmus gibt es schon seit der Antike. Arithmetische Algorithmen, wie z. B. ein Divisionsalgorithmus, wurden von altbabylonischen Mathematikern um 2500 v. Chr. und ägyptischen Mathematikern um 1550 v. Chr. verwendet. Griechische Mathematiker verwendeten Algorithmen 240 v. Chr. im Sieb des Eratosthenes, um Primzahlen zu finden, und im euklidischen Algorithmus, um den größten gemeinsamen Teiler zweier Zahlen zu bestimmen. Arabische Mathematiker wie al-Kindi verwendeten im 9. Jahrhundert kryptografische Algorithmen zum Entschlüsseln von Codes, die auf einer Frequenzanalyse beruhten. ⓘ
Das Wort Algorithmus leitet sich vom Namen des persischen Mathematikers Muḥammad ibn Mūsā al-Khwārizmī aus dem 9. Jahrhundert ab, dessen nisba (die ihn als aus Khwarazm stammend ausweist) als Algoritmi (arabisiertes Persisch الخوارزمی um 780-850) latinisiert wurde. Muḥammad ibn Mūsā al-Khwārizmī war ein Mathematiker, Astronom, Geograph und Gelehrter im Haus der Weisheit in Bagdad, dessen Name "der Eingeborene von Khwarazm" bedeutet, einer Region, die Teil des Großiran war und heute in Usbekistan liegt. Um 825 schrieb al-Khwarizmi eine arabischsprachige Abhandlung über das hindu-arabische Zahlensystem, die im 12. Das Manuskript beginnt mit dem Satz Dixit Algorizmi ("So sprach Al-Khwarizmi"), wobei "Algorizmi" die Latinisierung des Namens von Al-Khwarizmi durch den Übersetzer war. Al-Khwarizmi war der meistgelesene Mathematiker im Europa des späten Mittelalters, vor allem durch ein weiteres seiner Bücher, die Algebra. Im spätmittelalterlichen Latein bedeutete algorismus, die Verballhornung seines Namens, einfach das "Dezimalzahlensystem". Im 15. Jahrhundert wurde das lateinische Wort unter dem Einfluss des griechischen Wortes ἀριθμός (arithmos), "Zahl" (vgl. "arithmetisch"), in algorithmus umgewandelt, und der entsprechende englische Begriff "algorithm" ist erstmals im 17. ⓘ
Die indische Mathematik war überwiegend algorithmisch. Algorithmen, die für die indische mathematische Tradition repräsentativ sind, reichen von den antiken Śulbasūtrās bis zu den mittelalterlichen Texten der Kerala-Schule. ⓘ
Im Englischen wurde das Wort Algorithmus erstmals um 1230 und dann von Chaucer im Jahr 1391 verwendet. Das Englische übernahm den französischen Begriff, aber erst im späten 19. Jahrhundert erhielt "Algorithmus" die Bedeutung, die er im modernen Englisch hat. ⓘ
Eine weitere frühe Verwendung des Wortes stammt aus dem Jahr 1240, und zwar in einem Handbuch mit dem Titel Carmen de Algorismo, das von Alexandre de Villedieu verfasst wurde. Es beginnt mit:
Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
was übersetzt soviel bedeutet wie:
Der Algorismus ist die Kunst, mit der wir gegenwärtig die indischen Zahlen verwenden, die zwei mal fünf sind. ⓘ
Das Gedicht ist einige hundert Zeilen lang und fasst die Kunst des Rechnens mit den neuartigen indischen Würfeln (Tali Indorum), den hinduistischen Ziffern, zusammen. ⓘ
Eine teilweise Formalisierung des modernen Konzepts des Algorithmus begann mit Versuchen, das Entscheidungsproblem zu lösen, das David Hilbert 1928 stellte. Spätere Formalisierungen wurden als Versuche zur Definition von "effektiver Berechenbarkeit" oder "effektiver Methode" formuliert. Zu diesen Formalisierungen gehörten die rekursiven Funktionen von Gödel-Herbrand-Kleene aus den Jahren 1930, 1934 und 1935, das Lambda-Kalkül von Alonzo Church aus dem Jahr 1936, die Formulierung 1 von Emil Post aus dem Jahr 1936 und die Turing-Maschinen von Alan Turing aus den Jahren 1936-37 und 1939. ⓘ
In der mittelalterlichen Überlieferung wurde das Wort bald als erklärungsbedürftig empfunden und dann seit dem 13. Jahrhundert zumeist als Zusammensetzung aus einem Personennamen Algus und aus einem aus dem griechischen ῥυσμός (Nebenform von ῥυθμός) in der Bedeutung „Zahl“ entlehnten Wortbestandteil -rismus interpretiert. ⓘ
Algus, der vermutete Erfinder dieser Rechenkunst, wurde hierbei von einigen als Araber, von anderen als Grieche oder zumindest griechisch schreibender Autor, 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 Denkern wie Platon, Aristoteles und Euklid, so im altfranzösischen Roman de la Rose, während das altitalienische Gedicht Il Fiore ihn sogar mit dem Erbauer des Schiffes Argo gleichsetzt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab. ⓘ
Auf der para-etymologischen Zurückführung des zweiten Bestandteils -rismus auf griech. ῥυσμός, ῥυθμός beruht dann auch die präzisierende lateinische Wortform algorithmus, die seit der Frühen Neuzeit, anfangs auch mit der Schreibvariante algorythmus, größere Verbreitung erlangte und zuletzt die heute übliche Wortbedeutung als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme annahm. ⓘ
Informelle Definition
Eine informelle Definition könnte lauten: "ein Satz von Regeln, der eine Abfolge von Operationen genau festlegt", was alle Computerprogramme (einschließlich der Programme, die keine numerischen Berechnungen durchführen) und (zum Beispiel) jedes vorgeschriebene bürokratische Verfahren einschließen würde oder Kochbuchrezepte. ⓘ
Im Allgemeinen ist ein Programm nur dann ein Algorithmus, wenn es irgendwann aufhört - auch wenn sich Endlosschleifen manchmal als wünschenswert erweisen können. ⓘ
Ein prototypisches Beispiel für einen Algorithmus ist der euklidische Algorithmus, der zur Bestimmung des größten gemeinsamen Teilers zweier ganzer Zahlen verwendet wird; ein Beispiel (es gibt noch weitere) wird im Flussdiagramm oben und als Beispiel in einem späteren Abschnitt beschrieben. ⓘ
Boolos, Jeffrey & 1974, 1999 bieten eine informelle Bedeutung des Wortes "Algorithmus" in dem folgenden Zitat:
Kein Mensch kann schnell genug oder lang genug oder klein genug schreiben† ( †"immer kleiner und kleiner ohne Ende ... man würde versuchen, auf Moleküle, auf Atome, auf Elektronen zu schreiben"), um alle Mitglieder einer aufzählbar unendlichen Menge aufzulisten, indem man ihre Namen, einen nach dem anderen, in irgendeiner Notation aufschreibt. Aber der Mensch kann etwas ebenso Nützliches tun, wenn es sich um bestimmte aufzählbar unendliche Mengen handelt: Er kann explizite Anweisungen zur Bestimmung des n-ten Mitglieds der Menge für ein beliebiges endliches n geben. Solche Anweisungen müssen ganz explizit gegeben werden, und zwar in einer Form, in der sie von einer Rechenmaschine oder von einem Menschen, der nur sehr elementare Operationen mit Symbolen durchführen kann, befolgt werden können. ⓘ
Eine "abzählbar unendliche Menge" ist eine Menge, deren Elemente in eins-zu-eins-Entsprechung mit den ganzen Zahlen gebracht werden können. Boolos und Jeffrey sagen also, dass ein Algorithmus Anweisungen für einen Prozess impliziert, der aus einer beliebigen "Eingabe"-Ganzzahl oder Ganzzahlen, die theoretisch beliebig groß sein können, Ausgabe-Ganzzahlen "erzeugt". Ein Algorithmus kann zum Beispiel eine algebraische Gleichung wie y = m + n sein (d. h. zwei beliebige "Eingabevariablen" m und n, die eine Ausgabe y erzeugen), aber die Definitionsversuche verschiedener Autoren deuten darauf hin, dass das Wort viel mehr als das impliziert, etwas in der Größenordnung von (für das Additionsbeispiel):
- Präzise Anweisungen (in einer Sprache, die "der Computer" versteht) für einen schnellen, effizienten, "guten" Prozess, der die "Schritte" des "Computers" (Maschine oder Mensch, ausgestattet mit den notwendigen intern enthaltenen Informationen und Fähigkeiten) spezifiziert, um beliebige Eingabe-Ganzzahlen/Symbole m und n, Symbole + und = ... zu finden, zu dekodieren und dann zu verarbeiten und "effektiv" in einer "angemessenen" Zeit die Ausgabe-Ganzzahl y an einem bestimmten Ort und in einem bestimmten Format zu erzeugen. ⓘ
Das Konzept des Algorithmus wird auch verwendet, um den Begriff der Entscheidbarkeit zu definieren - ein Begriff, der von zentraler Bedeutung ist, um zu erklären, wie formale Systeme ausgehend von einem kleinen Satz von Axiomen und Regeln entstehen. In der Logik kann die Zeit, die ein Algorithmus benötigt, um abgeschlossen zu werden, nicht gemessen werden, da sie offensichtlich nicht mit der üblichen physikalischen Dimension in Verbindung steht. Aus diesen Unsicherheiten, die die laufenden Arbeiten kennzeichnen, ergibt sich, dass es keine Definition des Algorithmus gibt, die sowohl der konkreten (in gewissem Sinne) als auch der abstrakten Verwendung des Begriffs gerecht wird. ⓘ
Die meisten Algorithmen sind dazu bestimmt, als Computerprogramme implementiert zu werden. Algorithmen werden jedoch auch auf andere Weise implementiert, z. B. in einem biologischen neuronalen Netz (z. B. im menschlichen Gehirn, das Arithmetik ausführt, oder in einem Insekt, das nach Nahrung sucht), in einem elektrischen Schaltkreis oder in einem mechanischen Gerät. ⓘ
Formalisierung
Algorithmen sind für die Art und Weise, wie Computer Daten verarbeiten, unerlässlich. Viele Computerprogramme enthalten Algorithmen, die die spezifischen Anweisungen beschreiben, die ein Computer in einer bestimmten Reihenfolge ausführen soll, um eine bestimmte Aufgabe zu erfüllen, wie z. B. die Berechnung der Gehaltsabrechnungen von Angestellten oder das Drucken der Zeugnisse von Schülern. Ein Algorithmus kann also als eine beliebige Folge von Operationen betrachtet werden, die von einem Turing-kompletten System simuliert werden kann. Zu den Autoren, die diese These vertreten, gehören Minsky (1967), Savage (1987) und Gurevich (2000):
Minsky: "Aber wir werden mit Turing auch behaupten, ... dass jede Prozedur, die "natürlich" als effektiv bezeichnet werden könnte, tatsächlich von einer (einfachen) Maschine realisiert werden kann. Obwohl dies extrem erscheinen mag, sind die Argumente ... zu seinen Gunsten schwer zu widerlegen". ⓘ Gurevich: "... Turings informelles Argument für seine These rechtfertigt eine stärkere These: jeder Algorithmus kann von einer Turing-Maschine simuliert werden ... nach Savage [1987] ist ein Algorithmus ein Rechenprozess, der von einer Turing-Maschine definiert wird".
Turingmaschinen können Rechenprozesse definieren, die nicht enden. Die informellen Definitionen von Algorithmen setzen im Allgemeinen voraus, dass der Algorithmus immer abschließt. Diese Anforderung macht die Entscheidung, ob ein formales Verfahren ein Algorithmus ist, im allgemeinen Fall unmöglich - aufgrund eines wichtigen Theorems der Berechenbarkeitstheorie, das als Halteproblem bekannt ist. ⓘ
Wenn ein Algorithmus mit der Verarbeitung von Informationen verbunden ist, können die Daten in der Regel von einer Eingabequelle gelesen, auf ein Ausgabegerät geschrieben und zur weiteren Verarbeitung gespeichert werden. Gespeicherte Daten werden als Teil des internen Zustands der Einheit betrachtet, die den Algorithmus ausführt. In der Praxis wird der Zustand in einer oder mehreren Datenstrukturen gespeichert. ⓘ
Für einige dieser Rechenprozesse muss der Algorithmus genau definiert werden, d. h. er muss so spezifiziert werden, dass er unter allen möglichen Umständen anwendbar ist, die auftreten können. Das bedeutet, dass alle bedingten Schritte systematisch und von Fall zu Fall behandelt werden müssen; die Kriterien für jeden Fall müssen klar (und berechenbar) sein. ⓘ
Da es sich bei einem Algorithmus um eine genaue Auflistung präziser Schritte handelt, ist die Reihenfolge der Berechnung immer entscheidend für das Funktionieren des Algorithmus. In der Regel wird davon ausgegangen, dass die Anweisungen explizit aufgelistet sind, und sie werden so beschrieben, dass sie "von oben" beginnen und "nach unten" gehen - eine Idee, die durch den Kontrollfluss formaler beschrieben wird. ⓘ
Bislang wurde bei der Diskussion über die Formalisierung eines Algorithmus von den Prämissen der imperativen Programmierung ausgegangen. Dies ist die am weitesten verbreitete Auffassung, die versucht, eine Aufgabe mit diskreten, "mechanischen" Mitteln zu beschreiben. Einzigartig in dieser Auffassung von formalisierten Algorithmen ist die Zuweisungsoperation, die den Wert einer Variablen festlegt. Sie leitet sich von der Intuition des "Speichers" als Notizblock ab. Ein Beispiel für eine solche Zuweisung finden Sie weiter unten. ⓘ
Für einige alternative Vorstellungen davon, was einen Algorithmus ausmacht, siehe funktionale Programmierung und logische Programmierung. ⓘ
Ausdruck von Algorithmen
Algorithmen können in vielen verschiedenen Notationen ausgedrückt werden, darunter natürliche Sprachen, Pseudocode, Flussdiagramme, Drakon-Diagramme, Programmiersprachen oder (von Interpretern verarbeitete) Steuertabellen. Algorithmen in natürlicher Sprache sind in der Regel langatmig und mehrdeutig und werden selten für komplexe oder technische Algorithmen verwendet. Pseudocode, Flussdiagramme, Drakon-Charts und Steuertabellen sind strukturierte Möglichkeiten, Algorithmen auszudrücken, die viele der Mehrdeutigkeiten vermeiden, die in den auf natürlicher Sprache basierenden Aussagen üblich sind. Programmiersprachen sind in erster Linie dazu gedacht, Algorithmen in einer Form auszudrücken, die von einem Computer ausgeführt werden kann, werden aber auch häufig als Mittel zur Definition oder Dokumentation von Algorithmen verwendet. ⓘ
Es gibt eine Vielzahl von Darstellungsmöglichkeiten, und man kann ein gegebenes Turing-Maschinenprogramm als eine Folge von Maschinentabellen (siehe endliche Maschine, Zustandsübergangstabelle und Kontrolltabelle für mehr), als Flussdiagramme und Drakon-Diagramme (siehe Zustandsdiagramm für mehr) oder als eine Form von rudimentärem Maschinencode oder Assemblercode, genannt "Sets of Quadruples", ausdrücken (siehe Turing-Maschine für mehr). ⓘ
Die Darstellungen von Algorithmen lassen sich in drei akzeptierte Ebenen der Turing-Maschinenbeschreibung einteilen, wie folgt:
- 1 High-Level-Beschreibung
- "...Prosa zur Beschreibung eines Algorithmus, ohne Berücksichtigung der Implementierungsdetails. Auf dieser Ebene brauchen wir nicht zu erwähnen, wie die Maschine ihr Band oder ihren Kopf verwaltet."
- 2 Beschreibung der Implementierung
- "...Prosa zur Beschreibung der Art und Weise, wie die Turing-Maschine ihren Kopf verwendet und wie sie Daten auf ihrem Band speichert. Auf dieser Ebene geben wir keine Details über Zustände oder Übergangsfunktionen an."
- 3 Formale Beschreibung
- Die detaillierteste, "niedrigste Ebene", enthält die "Zustandstabelle" der Turingmaschine. ⓘ
Ein Beispiel für den einfachen Algorithmus "Addiere m+n", der auf allen drei Ebenen beschrieben wird, finden Sie unter Beispiele. ⓘ
Entwurf
Der Algorithmusentwurf bezieht sich auf eine Methode oder einen mathematischen Prozess zur Problemlösung und Entwicklung von Algorithmen. Der Entwurf von Algorithmen ist Teil vieler Lösungstheorien der Operationsforschung, wie z. B. dynamische Programmierung und Divide-and-Conquer. Techniken für den Entwurf und die Implementierung von Algorithmusentwürfen werden auch als Algorithmusentwurfsmuster bezeichnet; Beispiele hierfür sind das Template-Methodenmuster und das Dekoratormuster. ⓘ
Einer der wichtigsten Aspekte des Algorithmusentwurfs ist die Ressourceneffizienz (Laufzeit, Speicherverbrauch); die Notation Big O wird verwendet, um z. B. das Laufzeitwachstum eines Algorithmus bei zunehmender Größe seiner Eingabe zu beschreiben. ⓘ
Typische Schritte bei der Entwicklung von Algorithmen:
- Problemdefinition
- Entwicklung eines Modells
- Spezifikation des Algorithmus
- Entwerfen eines Algorithmus
- Prüfen der Korrektheit des Algorithmus
- Analyse des Algorithmus
- Implementierung des Algorithmus
- Testen des Programms
- Vorbereitung der Dokumentation ⓘ
Computer-Algorithmen
IF test THEN GOTO step xxx, dargestellt als Raute), dem unbedingten GOTO (Rechteck), verschiedenen Zuweisungsoperatoren (Rechteck) und HALT (Rechteck). Die Verschachtelung dieser Strukturen innerhalb von Zuweisungsblöcken führt zu komplexen Diagrammen (vgl. Tausworthe 1977:100, 114). ⓘ"Elegante" (kompakte) Programme, "gute" (schnelle) Programme : Der Begriff der "Einfachheit und Eleganz" taucht informell bei Knuth und präzise bei Chaitin auf:
- Knuth: " ... wir wollen gute Algorithmen in einem locker definierten ästhetischen Sinn. Ein Kriterium ... ist die Zeit, die für die Ausführung des Algorithmus benötigt wird .... Andere Kriterien sind die Anpassungsfähigkeit des Algorithmus an Computer, seine Einfachheit und Eleganz, usw." ⓘ
- Chaitin: " ... ein Programm ist 'elegant', womit ich meine, dass es das kleinstmögliche Programm ist, um die Ausgabe zu erzeugen, die es macht. ⓘ
Chaitin leitet seine Definition mit ein: "Ich werde zeigen, dass man nicht beweisen kann, dass ein Programm 'elegant' ist" - ein solcher Beweis würde das Halting-Problem lösen (ebd.). ⓘ
Algorithmus versus durch einen Algorithmus berechenbare Funktion: Für eine bestimmte Funktion können mehrere Algorithmen existieren. Dies gilt selbst dann, wenn man den Befehlssatz, der dem Programmierer zur Verfügung steht, nicht erweitert. Rogers merkt an, dass "es ... wichtig ist, zwischen dem Begriff des Algorithmus, d.h. der Prozedur, und dem Begriff der durch einen Algorithmus berechenbaren Funktion, d.h. der durch eine Prozedur erzeugten Abbildung, zu unterscheiden. Dieselbe Funktion kann mehrere verschiedene Algorithmen haben". ⓘ
Leider kann es einen Kompromiss zwischen Güte (Geschwindigkeit) und Eleganz (Kompaktheit) geben - ein elegantes Programm kann mehr Schritte benötigen, um eine Berechnung abzuschließen, als ein weniger elegantes. Ein Beispiel, das den Algorithmus von Euklid verwendet, finden Sie unten. ⓘ
Computer (und Computer), Modelle der Berechnung: Ein Computer (oder menschlicher "Computor") ist eine eingeschränkte Art von Maschine, ein "diskretes deterministisches mechanisches Gerät", das blind seinen Anweisungen folgt. Die primitiven Modelle von Melzak und Lambek reduzierten diesen Begriff auf vier Elemente: (i) diskrete, unterscheidbare Orte, (ii) diskrete, ununterscheidbare Zähler, (iii) einen Agenten und (iv) eine Liste von Anweisungen, die im Verhältnis zu den Fähigkeiten des Agenten wirksam sind. ⓘ
Minsky beschreibt in seinem Buch "Very Simple Bases for Computability" eine kongenialere Variante von Lambeks "Abakus"-Modell. Minskys Maschine geht sequentiell durch ihre fünf (oder sechs, je nachdem, wie man zählt) Instruktionen, es sei denn, entweder ein bedingtes IF-THEN GOTO oder ein unbedingtes GOTO ändert den Programmablauf außerhalb der Reihenfolge. Neben HALT enthält Minskys Maschine drei Zuweisungsoperationen (Ersatz, Substitution): NULL (z.B. der Inhalt der Stelle wird durch 0 ersetzt: L ← 0), SUCCESSOR (z.B. L ← L+1) und DECREMENT (z.B. L ← L - 1). Selten muss ein Programmierer "Code" mit einem so begrenzten Befehlssatz schreiben. Minsky zeigt jedoch (ebenso wie Melzak und Lambek), dass seine Maschine mit nur vier allgemeinen Arten von Befehlen Turing-komplett ist: bedingtes GOTO, unbedingtes GOTO, Zuweisung/Ersetzung/Ersatz und HALT. Für die Turing-Vollständigkeit sind jedoch auch einige andere Zuweisungsanweisungen (z. B. DECREMENT, INCREMENT und ZERO/CLEAR/EMPTY für eine Minsky-Maschine) erforderlich; ihre genaue Spezifikation bleibt dem Konstrukteur überlassen. Das unbedingte GOTO ist eine Bequemlichkeit; es kann konstruiert werden, indem eine bestimmte Stelle auf Null initialisiert wird, z. B. mit der Anweisung " Z ← 0 "; danach ist die Anweisung IF Z=0 THEN GOTO xxx unbedingend. ⓘ
Simulation eines Algorithmus: Computer (Computor) Sprache: Knuth rät dem Leser, dass "der beste Weg, einen Algorithmus zu lernen, darin besteht, ihn auszuprobieren ... nehmen Sie sofort Stift und Papier und arbeiten Sie ein Beispiel durch". Aber wie sieht es mit einer Simulation oder Ausführung der realen Sache aus? Der Programmierer muss den Algorithmus in eine Sprache übersetzen, die der Simulator/Computer/Rechner effektiv ausführen kann. Stone gibt dazu ein Beispiel: Bei der Berechnung der Wurzeln einer quadratischen Gleichung muss der Rechner wissen, wie man die Quadratwurzel zieht. Wenn dies nicht der Fall ist, muss der Algorithmus, um effektiv zu sein, eine Reihe von Regeln für die Extraktion der Quadratwurzel bereitstellen. ⓘ
Das bedeutet, dass der Programmierer eine "Sprache" beherrschen muss, die in Bezug auf den Zielcomputer (Computer/Computer) effektiv ist. ⓘ
Aber welches Modell soll für die Simulation verwendet werden? Van Emde Boas stellt fest: "Selbst wenn wir die Komplexitätstheorie auf abstrakte statt auf konkrete Maschinen stützen, bleibt die Willkür bei der Wahl des Modells bestehen. An diesem Punkt kommt der Begriff der Simulation ins Spiel". Bei der Messung der Geschwindigkeit spielt der Befehlssatz eine Rolle. Beispielsweise würde das Unterprogramm in Euklids Algorithmus zur Berechnung des Rests viel schneller ablaufen, wenn dem Programmierer ein "Modulus"-Befehl zur Verfügung stünde und nicht nur die Subtraktion (oder schlimmer: nur Minskys "Dekrement"). ⓘ
Strukturierte Programmierung, kanonische Strukturen: Gemäß der Church-Turing-These kann jeder Algorithmus durch ein Modell berechnet werden, das als Turing-vollständig bekannt ist, und gemäß Minskys Demonstrationen erfordert die Turing-Vollständigkeit nur vier Befehlstypen - bedingtes GOTO, unbedingtes GOTO, Zuweisung, HALT. Kemeny und Kurtz stellen fest, dass die "undisziplinierte" Verwendung von unbedingten GOTOs und bedingten IF-THEN GOTOs zwar zu "Spaghetti-Code" führen kann, dass aber ein Programmierer strukturierte Programme schreiben kann, die nur diese Anweisungen verwenden; andererseits "ist es auch möglich und nicht allzu schwer, schlecht strukturierte Programme in einer strukturierten Sprache zu schreiben". Tausworthe erweitert die drei kanonischen Strukturen von Böhm-Jacopini: SEQUENCE, IF-THEN-ELSE, und WHILE-DO, um zwei weitere: DO-WHILE und CASE. Ein zusätzlicher Vorteil eines strukturierten Programms ist, dass es sich für Korrektheitsbeweise mittels mathematischer Induktion eignet. ⓘ
Kanonische Flussdiagrammsymbole: Das grafische Hilfsmittel, das Flussdiagramm, bietet eine Möglichkeit, einen Algorithmus (und ein Computerprogramm) zu beschreiben und zu dokumentieren. Wie der Programmablauf einer Minsky-Maschine beginnt ein Flussdiagramm immer am oberen Rand einer Seite und verläuft nach unten. Es gibt nur vier Hauptsymbole: den gerichteten Pfeil, der den Programmfluss anzeigt, das Rechteck (SEQUENCE, GOTO), die Raute (IF-THEN-ELSE) und den Punkt (OR-tie). Die kanonischen Böhm-Jacopini-Strukturen werden aus diesen primitiven Formen gebildet. Unterstrukturen können in Rechtecken "verschachtelt" werden, aber nur, wenn ein einziger Ausgang aus der Oberstruktur vorhanden ist. Die Symbole und ihre Verwendung zum Aufbau der kanonischen Strukturen sind im Diagramm dargestellt. ⓘ
Beispiele
Beispiel für einen Algorithmus
Einer der einfachsten Algorithmen besteht darin, die größte Zahl in einer Liste von Zahlen mit zufälliger Reihenfolge zu finden. Um die Lösung zu finden, muss man sich jede Zahl in der Liste ansehen. Daraus ergibt sich ein einfacher Algorithmus, der in einer High-Level-Beschreibung in englischer Prosa wie folgt angegeben werden kann: Beschreibung auf hoher Ebene:
- Wenn es keine Zahlen in der Menge gibt, dann gibt es auch keine höchste Zahl.
- Angenommen, die erste Zahl in der Menge ist die größte Zahl in der Menge.
- Für jede verbleibende Zahl in der Menge gilt: Wenn diese Zahl größer ist als die aktuell größte Zahl, dann ist diese Zahl die größte Zahl in der Menge.
- Wenn es in der Menge keine Zahlen mehr gibt, über die man iterieren kann, wird die aktuell größte Zahl als größte Zahl der Menge betrachtet. ⓘ
(Quasi-)formale Beschreibung: In Prosa geschrieben, aber viel näher an der Hochsprache eines Computerprogramms, ist das Folgende die formalere Kodierung des Algorithmus in Pseudocode oder Pidgin-Code:
Algorithmus GrößteZahl Eingabe: Eine Liste von Zahlen L. Ausgabe: Die größte Zahl in der Liste L.
if L.size = 0 return null größte ← L[0] für jedes Element in L, do wenn Element > größte, dann größte ← Element return größte
- "←" bezeichnet eine Zuweisung. Zum Beispiel bedeutet "largest ← item", dass der Wert von largest sich in den Wert von item ändert.
- "return" beendet den Algorithmus und gibt den folgenden Wert aus. ⓘ
Euklidscher Algorithmus
In der Mathematik ist der Euklidische Algorithmus oder Euklids Algorithmus eine effiziente Methode zur Berechnung des größten gemeinsamen Teilers (GCD) zweier ganzer Zahlen, d. h. der größten Zahl, die beide Zahlen ohne Rest teilt. Er ist nach dem antiken griechischen Mathematiker Euklid benannt, der ihn erstmals in seinen Elementen (ca. 300 v. Chr.) beschrieben hat. Er ist einer der ältesten gebräuchlichen Algorithmen. Er kann verwendet werden, um Brüche auf ihre einfachste Form zu reduzieren, und ist Bestandteil vieler anderer zahlentheoretischer und kryptografischer Berechnungen. ⓘ
Euklid stellt das Problem folgendermaßen dar: "Gegeben zwei Zahlen, die nicht primär zueinander sind, ihr größtes gemeinsames Maß zu finden". Er definiert "eine Zahl [als] eine aus Einheiten zusammengesetzte Menge": eine zählende Zahl, eine positive ganze Zahl ohne Null. Messen" bedeutet, eine kürzere Messlänge s nacheinander (q-mal) entlang der längeren Länge l zu platzieren, bis der verbleibende Teil r kleiner ist als die kürzere Länge s. In modernen Worten: Rest r = l - q×s, wobei q der Quotient ist, oder Rest r ist der "Modulus", der ganzzahlige Bruchteil, der nach der Division übrig bleibt. ⓘ
Damit die Euklid-Methode erfolgreich ist, müssen die Ausgangslängen zwei Bedingungen erfüllen: (i) die Längen dürfen nicht gleich Null sein, UND (ii) die Subtraktion muss "richtig" sein; d.h. ein Test muss garantieren, dass die kleinere der beiden Zahlen von der größeren subtrahiert wird (oder die beiden können gleich sein, so dass ihre Subtraktion Null ergibt). ⓘ
In Euklids ursprünglichem Beweis kommt noch eine dritte Bedingung hinzu: Die beiden Längen dürfen nicht primär zueinander sein. Euklid stellte diese Bedingung, damit er einen reductio ad absurdum-Beweis konstruieren konnte, dass das gemeinsame Maß der beiden Zahlen tatsächlich das größte ist. Der Algorithmus von Nikomachos ist derselbe wie der von Euklid, aber wenn die Zahlen Primzahlen sind, ergibt er die Zahl "1" für ihr gemeinsames Maß. Um genau zu sein, handelt es sich also um den Algorithmus des Nikomachos. ⓘ
1599 = 650×2 + 299
650 = 299×2 + 52
299 = 52×5 + 39
52 = 39×1 + 13
39 = 13×3 + 0 <span title="Aus: Englische Wikipedia, Abschnitt "Euclid's algorithm"" class="plainlinks">[https://en.wikipedia.org/wiki/Algorithm#Euclid's_algorithm <span style="color:#dddddd">ⓘ</span>]</span>Computersprache für Euklids Algorithmus
Zur Ausführung von Euklids Algorithmus sind nur wenige Befehlstypen erforderlich - einige logische Tests (bedingtes GOTO), unbedingtes GOTO, Zuweisung (Ersetzung) und Subtraktion.
- Eine Stelle wird durch einen oder mehrere Großbuchstaben symbolisiert, z. B. S, A, usw.
- Die variierende Menge (Zahl) an einem Ort wird in Kleinbuchstaben geschrieben und (normalerweise) mit dem Namen des Ortes verbunden. Zum Beispiel könnte der Ort L am Anfang die Zahl l = 3009 enthalten. ⓘ
Ein unelegantes Programm für den Euklidschen Algorithmus
Der folgende Algorithmus ist als Knuths vierstufige Version des Algorithmus von Euklid und Nikomachos angelegt, verwendet aber statt der Division zur Ermittlung des Rests sukzessive Subtraktionen der kürzeren Länge s von der verbleibenden Länge r, bis r kleiner ist als s. Die fettgedruckte Beschreibung auf hoher Ebene ist Knuth 1973:2-4 entnommen: EINGABE:
1 [Geben Sie an zwei Stellen L und S die Zahlen l und s ein, die die beiden Längen darstellen]: EINGABE L, S 2 [R initialisieren: die verbleibende Länge r gleich der Start-/Initial-/Eingabelänge l machen]: R ← L ⓘ
E0: [Sicherstellen, dass r ≥ s.]
3 [Sicherstellen, dass die kleinere der beiden Zahlen in S und die größere in R ist]: IF R > S THEN der Inhalt von L ist die größere Zahl, also überspringe die Austausch-Schritte 4, 5 und 6: GOTO Schritt 7 ELSE Tausche den Inhalt von R und S. 4 L ← R (dieser erste Schritt ist überflüssig, aber für die spätere Diskussion nützlich). 5 R ← S 6 S ← L ⓘ
E1: [Rest finden]: Bis die verbleibende Länge r in R kleiner ist als die kürzere Länge s in S, subtrahiere wiederholt die Messzahl s in S von der verbleibenden Länge r in R.
7 WENN S > R DANN Messung beendet, also GOTO 10 ELSE erneut messen, 8 R ← R - S 9 [Verbleibende Schleife]: GOTO 7. ⓘ
E2: [Ist der Rest null?]: ENTWEDER (i) die letzte Messung war exakt, der Rest in R ist Null, und das Programm kann anhalten, ODER (ii) der Algorithmus muss fortgesetzt werden: die letzte Messung hat einen Rest in R hinterlassen, der kleiner ist als die Messzahl in S.
10 WENN R = 0 DANN erledigt, also GOTO Schritt 15 ELSE WEITER ZU SCHRITT 11, ⓘ
E3: [Austausch von s und r]: Die Nuss des Euklidschen Algorithmus. Benutze den Rest r, um zu messen, was vorher die kleinere Zahl s war; L dient als temporärer Ort.
11 L ← R 12 R ← S 13 S ← L 14 [Wiederholen Sie den Messvorgang]: GOTO 7 ⓘ
OUTPUT:
15 [Fertig. S enthält den größten gemeinsamen Teiler]: DRUCKEN S ⓘ
FERTIG:
16 HALT, END, STOP. ⓘ
Ein elegantes Programm für den Euklidschen Algorithmus
Die folgende Version von Euklids Algorithmus benötigt nur sechs Kernbefehle, um das zu tun, wofür "Inelegant" dreizehn benötigt; schlimmer ist, dass "Inelegant" mehr Befehlstypen benötigt. Das Flussdiagramm von "Elegant" finden Sie am Anfang dieses Artikels. In der (unstrukturierten) Basic-Sprache sind die Schritte nummeriert, und die Anweisung LET [] = [] ist die Zuweisungsanweisung, symbolisiert durch ←.
5 REM Euklidscher Algorithmus für den größten gemeinsamen Teiler
6 PRINT "Gib zwei ganze Zahlen größer als 0 ein"
10 EINGABE A,B
20 IF B=0 THEN GOTO 80
30 IF A > B THEN GOTO 60
40 LET B=B-A
50 GOTO 20
60 LET A=A-B
70 GOTO 20
80 DRUCKEN A
90 ENDEWie "Elegant" funktioniert: Anstelle einer äußeren "Euklid-Schleife" wechselt "Elegant" zwischen zwei "Co-Schleifen" hin und her, einer A > B-Schleife, die A ← A - B berechnet, und einer B ≤ A-Schleife, die B ← B - A berechnet. Dies funktioniert, weil, wenn schließlich der Minuend M kleiner oder gleich dem Subtrahend S ist (Differenz = Minuend - Subtrahend), der Minuend zu s (der neuen Messlänge) und der Subtrahend zum neuen r (der zu messenden Länge) werden kann; mit anderen Worten kehrt sich der "Sinn" der Subtraktion um. ⓘ
Die folgende Version kann mit Programmiersprachen aus der C-Familie verwendet werden:
// Euklids Algorithmus für den größten gemeinsamen Teiler
int euclidAlgorithmus (int A, int B){
A=abs(A);
B=abs(B);
while (B!=0){
while (A>B) A=A-B;
B=B-A;
}
return A;
} <span title="Aus: Englische Wikipedia, Abschnitt "An elegant program for Euclid's algorithm"" class="plainlinks">[https://en.wikipedia.org/wiki/Algorithm#An_elegant_program_for_Euclid's_algorithm <span style="color:#dddddd">ⓘ</span>]</span>Testen der Euklid-Algorithmen
Tut ein Algorithmus das, was sein Autor will? Ein paar Testfälle geben in der Regel ein gewisses Vertrauen in die Kernfunktionalität. Aber Tests sind nicht genug. Eine Quelle verwendet 3009 und 884 als Testfälle. Knuth schlug 40902 und 24140 vor. Ein weiterer interessanter Fall sind die beiden relativen Primzahlen 14157 und 5950. ⓘ
Aber "Ausnahmefälle" müssen identifiziert und getestet werden. Wird "Inelegant" richtig funktionieren, wenn R > S, S > R, R = S? Das Gleiche gilt für "Elegant": B > A, A > B, A = B? (Ja zu allen). Was geschieht, wenn eine Zahl gleich Null ist und beide Zahlen gleich Null sind? ("Inelegant" rechnet in allen Fällen für immer; "Elegant" rechnet für immer, wenn A = 0.) Was geschieht, wenn negative Zahlen eingegeben werden? Bruchteile von Zahlen? Wenn die eingegebenen Zahlen, d. h. der Bereich der vom Algorithmus/Programm berechneten Funktion, nur positive ganze Zahlen einschließlich Null umfassen soll, dann deuten die Ausfälle bei Null darauf hin, dass der Algorithmus (und das Programm, das ihn instanziiert) eher eine Teilfunktion als eine Gesamtfunktion ist. Ein bemerkenswertes Versagen aufgrund von Ausnahmen ist das Versagen der Rakete des Ariane-5-Flugs 501 (4. Juni 1996). ⓘ
Beweis der Korrektheit von Programmen durch mathematische Induktion: Knuth demonstriert die Anwendung der mathematischen Induktion auf eine "erweiterte" Version des Euklidschen Algorithmus und schlägt "eine allgemeine Methode vor, die zum Beweis der Gültigkeit jedes Algorithmus anwendbar ist". Tausworthe schlägt vor, dass ein Maß für die Komplexität eines Programms die Länge seines Korrektheitsbeweises ist. ⓘ
Messung und Verbesserung der Euklid-Algorithmen
Eleganz (Kompaktheit) versus Güte (Geschwindigkeit): Mit nur sechs Kerninstruktionen ist "Elegant" der klare Sieger, verglichen mit "Inelegant" mit dreizehn Instruktionen. Allerdings ist "Inelegant" schneller (es kommt in weniger Schritten zu HALT). Die Algorithmusanalyse zeigt, warum dies der Fall ist: "Elegant" führt in jeder Subtraktionsschleife zwei Bedingungstests durch, während "Inelegant" nur einen durchführt. Da der Algorithmus (in der Regel) viele Schleifendurchläufe erfordert, wird im Durchschnitt viel Zeit mit einem "B = 0?"-Test verschwendet, der erst nach der Berechnung des Rests benötigt wird. ⓘ
Können die Algorithmen verbessert werden? Wenn der Programmierer ein Programm für "geeignet" und "effektiv" hält - d. h. wenn es die vom Autor beabsichtigte Funktion berechnet -, stellt sich die Frage, ob es verbessert werden kann. ⓘ
Die Kompaktheit von "Inelegant" kann durch die Eliminierung von fünf Schritten verbessert werden. Chaitin hat jedoch bewiesen, dass die Kompaktheit eines Algorithmus nicht durch einen verallgemeinerten Algorithmus automatisiert werden kann, sondern nur heuristisch, d. h. durch erschöpfende Suche (Beispiele finden Sie bei Busy Beaver), Versuch und Irrtum, Cleverness, Einsicht, Anwendung induktiver Schlussfolgerungen usw. Beachten Sie, dass die Schritte 4, 5 und 6 in den Schritten 11, 12 und 13 wiederholt werden. Der Vergleich mit "Elegant" gibt einen Hinweis darauf, dass diese Schritte zusammen mit den Schritten 2 und 3 eliminiert werden können. Dadurch verringert sich die Anzahl der Kernbefehle von dreizehn auf acht, was ihn "eleganter" macht als "Elegant" mit neun Schritten. ⓘ
Die Geschwindigkeit von "Elegant" kann verbessert werden, indem der "B=0?"-Test außerhalb der beiden Subtraktionsschleifen verlegt wird. Diese Änderung erfordert das Hinzufügen von drei Anweisungen (B = 0?, A = 0?, GOTO). Jetzt berechnet "Elegant" die Beispielzahlen schneller; ob dies für jedes gegebene A, B und R, S immer der Fall ist, würde eine detaillierte Analyse erfordern. ⓘ
Algorithmische Analyse
Häufig ist es wichtig zu wissen, wie viel einer bestimmten Ressource (z. B. Zeit oder Speicher) theoretisch für einen bestimmten Algorithmus benötigt wird. Es wurden Methoden für die Analyse von Algorithmen entwickelt, um solche quantitativen Antworten (Schätzungen) zu erhalten; ein Algorithmus, der die Elemente einer Liste von n Zahlen addiert, würde beispielsweise einen Zeitbedarf von O(n) haben, wobei die Notation big O verwendet wird. Der Algorithmus muss sich zu jedem Zeitpunkt nur zwei Werte merken: die Summe aller bisherigen Elemente und seine aktuelle Position in der Eingabeliste. Man spricht daher von einem Platzbedarf von O(1), wenn der für die Speicherung der Eingabezahlen benötigte Platz nicht gezählt wird, oder von O(n), wenn er gezählt wird. ⓘ
Verschiedene Algorithmen können dieselbe Aufgabe mit einer anderen Menge von Anweisungen in weniger oder mehr Zeit, Platz oder "Aufwand" erledigen als andere. So ist beispielsweise ein binärer Suchalgorithmus (mit Kosten O(log n)) einer sequentiellen Suche (Kosten O(n) ) überlegen, wenn er für die Suche nach Tabellen in sortierten Listen oder Feldern verwendet wird. ⓘ
Formal versus empirisch
Die Analyse und das Studium von Algorithmen ist eine Disziplin der Informatik und wird oft auf abstrakte Weise praktiziert, ohne dass eine bestimmte Programmiersprache oder Implementierung verwendet wird. In diesem Sinne ähnelt die Algorithmusanalyse anderen mathematischen Disziplinen, da sie sich auf die zugrunde liegenden Eigenschaften des Algorithmus und nicht auf die Besonderheiten einer bestimmten Implementierung konzentriert. In der Regel wird für die Analyse Pseudocode verwendet, da er die einfachste und allgemeinste Darstellung ist. Letztendlich werden die meisten Algorithmen jedoch auf bestimmten Hardware-/Softwareplattformen implementiert, und ihre algorithmische Effizienz wird schließlich anhand von echtem Code auf die Probe gestellt. Für die Lösung eines "einmaligen" Problems hat die Effizienz eines bestimmten Algorithmus möglicherweise keine bedeutenden Auswirkungen (es sei denn, n ist extrem groß), aber für Algorithmen, die für den schnellen interaktiven, kommerziellen oder langlebigen wissenschaftlichen Einsatz konzipiert sind, kann sie entscheidend sein. Bei der Skalierung von kleinem n auf großes n werden häufig ineffiziente Algorithmen aufgedeckt, die ansonsten unbedenklich sind. ⓘ
Empirische Tests sind nützlich, weil sie unerwartete Wechselwirkungen aufdecken können, die die Leistung beeinträchtigen. Benchmarks können verwendet werden, um mögliche Verbesserungen eines Algorithmus nach einer Programmoptimierung vorher/nachher zu vergleichen. Empirische Tests können jedoch eine formale Analyse nicht ersetzen und sind nicht trivial, um sie auf faire Weise durchzuführen. ⓘ
Ausführungseffizienz
Zur Veranschaulichung der potenziellen Verbesserungen, die selbst bei gut etablierten Algorithmen möglich sind, kann eine jüngste bedeutende Innovation im Zusammenhang mit FFT-Algorithmen (die häufig in der Bildverarbeitung eingesetzt werden) die Verarbeitungszeit für Anwendungen wie die medizinische Bildgebung um das bis zu 1000-fache verringern. Im Allgemeinen hängen die Geschwindigkeitsverbesserungen von speziellen Eigenschaften des Problems ab, die in praktischen Anwendungen sehr häufig vorkommen. Durch Geschwindigkeitssteigerungen dieser Größenordnung können Computergeräte, die in großem Umfang Bildverarbeitung nutzen (wie Digitalkameras und medizinische Geräte), weniger Strom verbrauchen. ⓘ
Klassifizierung
Der älteste bekannte nicht-triviale Algorithmus ist der euklidische Algorithmus. Spezielle Algorithmus-Typen sind der randomisierte Algorithmus (mit Zufallskomponente), der Approximationsalgorithmus (als Annäherungsverfahren), die evolutionären Algorithmen (nach biologischem Vorbild) und der Greedy-Algorithmus. ⓘ
Eine weitere Übersicht geben die Liste von Algorithmen und die Kategorie Algorithmus. ⓘ
Es gibt verschiedene Möglichkeiten, Algorithmen zu klassifizieren, jede mit ihren eigenen Vorzügen. ⓘ
Nach Implementierung
Eine Möglichkeit, Algorithmen zu klassifizieren, ist die Art der Implementierung. ⓘ
int gcd(int A, int B) {
wenn (B == 0)
A zurückgeben;
sonst wenn (A > B)
return gcd(A-B,B);
sonst
return gcd(A,B-A);
} <span title="Aus: Englische Wikipedia, Abschnitt "By implementation"" class="plainlinks">[https://en.wikipedia.org/wiki/Algorithm#By_implementation <span style="color:#dddddd">ⓘ</span>]</span> |
| Rekursive C-Implementierung des Euklidschen Algorithmus aus dem obigen Flussdiagramm |
- Rekursion
- Ein rekursiver Algorithmus ist ein Algorithmus, der sich selbst wiederholt aufruft (auf ihn verweist), bis eine bestimmte Bedingung (auch als Abbruchbedingung bekannt) erfüllt ist; diese Methode ist in der funktionalen Programmierung üblich. Iterative Algorithmen verwenden sich wiederholende Konstrukte wie Schleifen und manchmal zusätzliche Datenstrukturen wie Stapel, um die gegebenen Probleme zu lösen. Einige Probleme sind von Natur aus für die eine oder andere Implementierung geeignet. Das Problem der Türme von Hanoi zum Beispiel lässt sich gut mit einer rekursiven Implementierung lösen. Jede rekursive Version hat eine äquivalente (aber möglicherweise mehr oder weniger komplexe) iterative Version, und umgekehrt.
- Logisch
- Ein Algorithmus kann als kontrollierte logische Deduktion betrachtet werden. Dieser Begriff lässt sich wie folgt ausdrücken: Algorithmus = Logik + Kontrolle. Die Logikkomponente drückt die Axiome aus, die in der Berechnung verwendet werden können, und die Kontrollkomponente bestimmt die Art und Weise, in der die Deduktion auf die Axiome angewendet wird. Dies ist die Grundlage für das Paradigma der logischen Programmierung. In reinen Logikprogrammiersprachen ist die Kontrollkomponente fest vorgegeben, und Algorithmen werden nur durch die Angabe der Logikkomponente spezifiziert. Der Reiz dieses Ansatzes liegt in der eleganten Semantik: Eine Änderung der Axiome bewirkt eine wohldefinierte Änderung des Algorithmus.
- Seriell, parallel oder verteilt
- Bei der Erörterung von Algorithmen wird gewöhnlich davon ausgegangen, dass Computer jeweils eine Anweisung eines Algorithmus ausführen. Diese Computer werden manchmal als serielle Computer bezeichnet. Ein Algorithmus, der für eine solche Umgebung entwickelt wurde, wird als serieller Algorithmus bezeichnet, im Gegensatz zu parallelen oder verteilten Algorithmen. Parallele Algorithmen nutzen die Vorteile von Computerarchitekturen, bei denen mehrere Prozessoren gleichzeitig an einem Problem arbeiten können, während verteilte Algorithmen mehrere über ein Computernetz verbundene Rechner verwenden. Parallele oder verteilte Algorithmen unterteilen das Problem in mehrere symmetrische oder asymmetrische Teilprobleme und fassen die Ergebnisse wieder zusammen. Der Ressourcenverbrauch bei solchen Algorithmen besteht nicht nur aus Prozessorzyklen auf jedem Prozessor, sondern auch aus dem Kommunikationsaufwand zwischen den Prozessoren. Einige Sortieralgorithmen können effizient parallelisiert werden, aber ihr Kommunikations-Overhead ist teuer. Iterative Algorithmen sind im Allgemeinen parallelisierbar. Einige Probleme haben keine parallelen Algorithmen und werden als inhärent serielle Probleme bezeichnet.
- Deterministisch oder nicht-deterministisch
- Deterministische Algorithmen lösen das Problem mit einer exakten Entscheidung bei jedem Schritt des Algorithmus, während nicht-deterministische Algorithmen das Problem durch Raten lösen, wobei die typischen Raten durch den Einsatz von Heuristiken genauer gemacht werden.
- Exakt oder approximativ
- Während viele Algorithmen eine exakte Lösung anstreben, wird bei Approximationsalgorithmen eine Annäherung an die wahre Lösung gesucht. Die Annäherung kann entweder durch eine deterministische oder eine zufällige Strategie erreicht werden. Solche Algorithmen sind für viele schwierige Probleme von praktischem Wert. Eines der Beispiele für einen Näherungsalgorithmus ist das Knapsack-Problem, bei dem eine Menge von Gegenständen gegeben ist. Ziel ist es, den Sack so zu packen, dass der maximale Gesamtwert erreicht wird. Jeder Gegenstand hat ein bestimmtes Gewicht und einen bestimmten Wert. Das Gesamtgewicht, das transportiert werden kann, ist nicht größer als eine feste Zahl X. Die Lösung muss also sowohl die Gewichte der Gegenstände als auch ihren Wert berücksichtigen.
- Quanten-Algorithmus
- Sie laufen auf einem realistischen Modell der Quantenberechnung. Der Begriff wird in der Regel für Algorithmen verwendet, die von Natur aus quantenmechanisch zu sein scheinen oder einige wesentliche Merkmale der Quanteninformatik nutzen, wie z. B. Quantenüberlagerung oder Quantenverschränkung. ⓘ
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. ⓘ
Beispiele für deterministische Algorithmen sind Bubblesort und der euklidische Algorithmus. Dabei gilt, dass jeder deterministische Algorithmus determiniert ist, während aber nicht jeder determinierte Algorithmus deterministisch ist. So ist Quicksort mit zufälliger Wahl des Pivotelements ein Beispiel für einen determinierten, aber nicht deterministischen Algorithmus, da sein Ergebnis bei gleicher Eingabe und eindeutiger Sortierung immer dasselbe ist, der Weg dorthin jedoch zufällig erfolgt. ⓘ
Nichtdeterministische Algorithmen können im Allgemeinen mit keiner realen Maschine (auch nicht mit Quantencomputern) direkt umgesetzt werden. ⓘ
Beispiel für einen nichtdeterministischen Algorithmus wäre ein Kochrezept, das mehrere Varianten beschreibt. Es bleibt dem Koch überlassen, welche er durchführen möchte. Auch das Laufen durch einen Irrgarten lässt an jeder Verzweigung mehrere Möglichkeiten, und neben vielen Sackgassen können mehrere Wege zum Ausgang führen. ⓘ
Nach Entwurfsparadigma
Eine weitere Möglichkeit, Algorithmen zu klassifizieren, ist ihre Entwurfsmethodik oder ihr Paradigma. Es gibt eine bestimmte Anzahl von Paradigmen, die sich alle voneinander unterscheiden. Außerdem umfasst jede dieser Kategorien viele verschiedene Arten von Algorithmen. Einige gängige Paradigmen sind:
- Brute-Force- oder erschöpfende Suche
- Dies ist die naive Methode, bei der alle möglichen Lösungen ausprobiert werden, um die beste zu finden.
- Teilen und Bezwingen
- Ein Divide-and-Conquer-Algorithmus reduziert eine Instanz eines Problems wiederholt auf eine oder mehrere kleinere Instanzen desselben Problems (in der Regel rekursiv), bis die Instanzen klein genug sind, um sie leicht zu lösen. Ein Beispiel für einen Divide-and-Conquer-Algorithmus ist das Merge-Sortieren. Die Sortierung kann für jedes Datensegment durchgeführt werden, nachdem die Daten in Segmente aufgeteilt wurden, und die Sortierung der gesamten Daten kann in der Eroberungsphase durch Zusammenführen der Segmente erreicht werden. Eine einfachere Variante des Divide-and-Conquer-Algorithmus ist der Decrease-and-Conquer-Algorithmus, der ein identisches Teilproblem löst und die Lösung dieses Teilproblems zur Lösung des größeren Problems verwendet. Beim Divide-and-Conquer-Algorithmus wird das Problem in mehrere Teilprobleme unterteilt, so dass die Eroberungsphase komplexer ist als beim Decrease-and-Conquer-Algorithmus. Ein Beispiel für einen Algorithmus zur Verringerung und Überwindung ist der binäre Suchalgorithmus.
- Suche und Aufzählung
- Viele Probleme (wie z. B. das Schachspiel) können als Probleme auf Graphen modelliert werden. Ein Graph-Explorationsalgorithmus legt Regeln für die Bewegung in einem Graphen fest und ist für solche Probleme nützlich. Zu dieser Kategorie gehören auch Suchalgorithmen, Branch-and-Bound-Aufzählung und Backtracking.
- Randomisierter Algorithmus
- Solche Algorithmen treffen einige Entscheidungen nach dem Zufallsprinzip (oder pseudozufällig). Sie können sehr nützlich sein, um ungefähre Lösungen für Probleme zu finden, bei denen die Suche nach exakten Lösungen unpraktisch ist (siehe heuristische Methode unten). Für einige dieser Probleme ist bekannt, dass die schnellsten Annäherungen mit einem gewissen Maß an Zufälligkeit verbunden sein müssen. Ob randomisierte Algorithmen mit polynomialer Zeitkomplexität die schnellsten Algorithmen für einige Probleme sein können, ist eine offene Frage, die als P versus NP-Problem bekannt ist. Es gibt zwei große Klassen von Algorithmen dieser Art:
- Monte-Carlo-Algorithmen liefern mit hoher Wahrscheinlichkeit eine richtige Antwort. RP ist z. B. die Unterklasse dieser Algorithmen, die in polynomieller Zeit ablaufen.
- Las Vegas-Algorithmen liefern immer die richtige Antwort, aber ihre Laufzeit ist nur probabilistisch begrenzt, z. B. ZPP.
- Reduktion der Komplexität
- Bei dieser Technik wird ein schwieriges Problem gelöst, indem es in ein besser bekanntes Problem umgewandelt wird, für das es (hoffentlich) asymptotisch optimale Algorithmen gibt. Ziel ist es, einen reduzierenden Algorithmus zu finden, dessen Komplexität nicht von der des resultierenden reduzierten Algorithmus dominiert wird. Ein Auswahlalgorithmus zum Auffinden des Medians in einer unsortierten Liste besteht beispielsweise darin, die Liste zunächst zu sortieren (der teure Teil) und dann das mittlere Element aus der sortierten Liste herauszuziehen (der billige Teil). Diese Technik wird auch als Transformieren und Erobern bezeichnet.
- Rückverfolgung
- Bei diesem Ansatz werden mehrere Lösungen schrittweise aufgebaut und aufgegeben, wenn festgestellt wird, dass sie nicht zu einer gültigen Gesamtlösung führen. ⓘ
Optimierungsprobleme
Für Optimierungsprobleme gibt es eine spezifischere Klassifizierung von Algorithmen; ein Algorithmus für solche Probleme kann in eine oder mehrere der oben beschriebenen allgemeinen Kategorien sowie in eine der folgenden Kategorien fallen:
- Lineare Programmierung
- Bei der Suche nach optimalen Lösungen für eine lineare Funktion, die an lineare Gleichheits- und Ungleichheitsbedingungen geknüpft ist, können die Bedingungen des Problems direkt zur Ermittlung der optimalen Lösungen verwendet werden. Es gibt Algorithmen, die jedes Problem dieser Kategorie lösen können, wie z. B. der beliebte Simplex-Algorithmus. Zu den Problemen, die mit linearer Programmierung gelöst werden können, gehört das Problem des maximalen Flusses für gerichtete Graphen. Wenn ein Problem zusätzlich erfordert, dass eine oder mehrere der Unbekannten eine ganze Zahl sein müssen, wird es der ganzzahligen Programmierung zugeordnet. Ein Algorithmus der linearen Programmierung kann ein solches Problem lösen, wenn bewiesen werden kann, dass alle Einschränkungen für ganzzahlige Werte oberflächlich sind, d. h. die Lösungen diese Einschränkungen ohnehin erfüllen. Im allgemeinen Fall wird je nach Schwierigkeitsgrad des Problems ein spezialisierter Algorithmus oder ein Algorithmus, der Näherungslösungen findet, verwendet.
- Dynamische Programmierung
- Wenn ein Problem optimale Unterstrukturen aufweist - d. h. die optimale Lösung eines Problems kann aus optimalen Lösungen für Teilprobleme konstruiert werden - und sich überschneidende Teilprobleme, d. h. dieselben Teilprobleme werden zur Lösung vieler verschiedener Problemfälle verwendet, vermeidet ein schnellerer Ansatz, der als dynamische Programmierung bezeichnet wird, die erneute Berechnung bereits berechneter Lösungen. Der Floyd-Warshall-Algorithmus zum Beispiel findet den kürzesten Weg zu einem Ziel von einem Knoten in einem gewichteten Graphen, indem er den kürzesten Weg zum Ziel von allen benachbarten Knoten aus verwendet. Dynamische Programmierung und Memoisierung gehen Hand in Hand. Der Hauptunterschied zwischen dynamischer Programmierung und Divide & Conquer besteht darin, dass die Teilprobleme bei Divide & Conquer mehr oder weniger unabhängig sind, während sich die Teilprobleme bei der dynamischen Programmierung überschneiden. Der Unterschied zwischen dynamischer Programmierung und einfacher Rekursion liegt in der Zwischenspeicherung oder Memoisierung von Rekursionsaufrufen. Wenn die Teilprobleme unabhängig sind und es keine Wiederholungen gibt, ist die Memoisierung nicht hilfreich; daher ist die dynamische Programmierung keine Lösung für alle komplexen Probleme. Durch Memoisierung oder das Führen einer Tabelle mit bereits gelösten Teilproblemen reduziert die dynamische Programmierung die exponentielle Natur vieler Probleme auf polynomiale Komplexität.
- Die gierige Methode
- Ein Greedy-Algorithmus ähnelt einem Algorithmus der dynamischen Programmierung insofern, als er Unterstrukturen untersucht, in diesem Fall nicht des Problems, sondern einer gegebenen Lösung. Solche Algorithmen beginnen mit einer Lösung, die gegeben sein kann oder auf irgendeine Weise konstruiert wurde, und verbessern sie durch kleine Änderungen. Bei einigen Problemen können sie die optimale Lösung finden, während sie bei anderen bei lokalen Optima aufhören, d. h. bei Lösungen, die durch den Algorithmus nicht verbessert werden können, aber nicht optimal sind. Am häufigsten werden gierige Algorithmen bei der Suche nach dem minimalen Spannbaum eingesetzt, wo mit dieser Methode die optimale Lösung gefunden werden kann. Huffman Tree, Kruskal, Prim, Sollin sind gierige Algorithmen, die dieses Optimierungsproblem lösen können.
- Die heuristische Methode
- Bei Optimierungsproblemen können heuristische Algorithmen eingesetzt werden, um eine Lösung zu finden, die der optimalen Lösung nahe kommt, wenn die Suche nach der optimalen Lösung unpraktisch ist. Diese Algorithmen arbeiten so, dass sie sich der optimalen Lösung immer weiter annähern. Im Prinzip finden sie, wenn sie unendlich lange laufen, die optimale Lösung. Ihr Vorteil ist, dass sie in relativ kurzer Zeit eine Lösung finden können, die der optimalen Lösung sehr nahe kommt. Zu diesen Algorithmen gehören die lokale Suche, die Tabusuche, das simulierte Glühen und die genetischen Algorithmen. Einige von ihnen, wie das simulierte Annealing, sind nicht-deterministische Algorithmen, während andere, wie die Tabu-Suche, deterministisch sind. Wenn eine Begrenzung des Fehlers der nicht optimalen Lösung bekannt ist, wird der Algorithmus weiter als Approximationsalgorithmus eingestuft. ⓘ
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.“ ⓘ
Nach Fachgebiet
Jedes wissenschaftliche Fachgebiet hat seine eigenen Probleme und benötigt effiziente Algorithmen. Verwandte Probleme in einem Bereich werden oft gemeinsam untersucht. Einige Beispiele sind Suchalgorithmen, Sortieralgorithmen, Zusammenführungsalgorithmen, numerische Algorithmen, Graphenalgorithmen, String-Algorithmen, geometrische Berechnungsalgorithmen, kombinatorische Algorithmen, medizinische Algorithmen, maschinelles Lernen, Kryptographie, Datenkomprimierungsalgorithmen und Parsing-Techniken. ⓘ
Die Bereiche überschneiden sich in der Regel, und die Fortschritte bei den Algorithmen in einem Bereich können die Algorithmen in anderen, manchmal völlig unabhängigen Bereichen verbessern. So wurde beispielsweise die dynamische Programmierung für die Optimierung des Ressourcenverbrauchs in der Industrie erfunden, wird aber heute für die Lösung einer Vielzahl von Problemen in vielen Bereichen eingesetzt. ⓘ
Nach Komplexität
Algorithmen können nach dem Zeitaufwand klassifiziert werden, den sie im Vergleich zur Größe ihrer Eingabe benötigen:
- Konstante Zeit: wenn die vom Algorithmus benötigte Zeit unabhängig von der Größe der Eingabe gleich ist. Z.B. ein Zugriff auf ein Array-Element.
- Logarithmische Zeit: wenn die Zeit eine logarithmische Funktion der Eingabegröße ist. Z.B. binärer Suchalgorithmus.
- Lineare Zeit: wenn die Zeit proportional zur Größe der Eingabe ist. Z.B. das Durchlaufen einer Liste.
- Polynomielle Zeit: wenn die Zeit eine Potenz der Eingabegröße ist. Z.B. hat der Bubble-Sort-Algorithmus eine quadratische Zeitkomplexität.
- Exponentialzeit: wenn die Zeit eine Exponentialfunktion der Eingabegröße ist. Z.B. Brute-force-Suche. ⓘ
Für einige Probleme gibt es möglicherweise mehrere Algorithmen mit unterschiedlicher Komplexität, während für andere Probleme keine Algorithmen oder keine effizienten Algorithmen bekannt sind. Außerdem gibt es Übertragungen von einigen Problemen auf andere Probleme. Aus diesem Grund hat es sich als geeigneter erwiesen, die Probleme selbst anstelle der Algorithmen in Äquivalenzklassen zu klassifizieren, die auf der Komplexität der bestmöglichen Algorithmen für sie basieren. ⓘ
Kontinuierliche Algorithmen
Das Adjektiv "kontinuierlich" kann in Verbindung mit dem Wort "Algorithmus" Folgendes bedeuten:
- Ein Algorithmus, der mit Daten arbeitet, die kontinuierliche Größen darstellen, auch wenn diese Daten durch diskrete Näherungen dargestellt werden - solche Algorithmen werden in der numerischen Analyse untersucht; oder
- ein Algorithmus in Form einer Differentialgleichung, der kontinuierlich auf die Daten einwirkt und auf einem Analogrechner läuft. ⓘ
Alltagsformen von Algorithmen
Rechenvorschriften sind eine Untergruppe der Algorithmen. Sie beschreiben Handlungsanweisungen in der Mathematik bezüglich Zahlen. Andere Algorithmen-Untergruppen sind z. B. (Koch-)Rezepte, Gesetze, Regeln, Verträge, Montage-Anleitungen. ⓘ
Rechtliche Fragen
Algorithmen an sich sind normalerweise nicht patentierbar. In den Vereinigten Staaten gilt ein Anspruch, der nur aus einfachen Manipulationen von abstrakten Konzepten, Zahlen oder Signalen besteht, nicht als "Verfahren" (USPTO 2006), so dass Algorithmen nicht patentierbar sind (wie im Fall Gottschalk gegen Benson). Praktische Anwendungen von Algorithmen sind jedoch manchmal patentierbar. So wurde beispielsweise in der Rechtssache Diamond gegen Diehr die Anwendung eines einfachen Rückkopplungsalgorithmus zur Unterstützung der Aushärtung von synthetischem Kautschuk für patentierbar erklärt. Die Patentierung von Software ist sehr umstritten, und es gibt stark kritisierte Patente, die Algorithmen betreffen, insbesondere Algorithmen zur Datenkompression, wie das LZW-Patent von Unisys. ⓘ
Außerdem unterliegen einige kryptografische Algorithmen Exportbeschränkungen (siehe Export von Kryptografie). ⓘ
Geschichte: Entwicklung des Begriffs "Algorithmus"
Alter Naher Osten
Die frühesten Belege für Algorithmen finden sich in der babylonischen Mathematik des alten Mesopotamiens (des heutigen Irak). Eine sumerische Tontafel, die in Shuruppak in der Nähe von Bagdad gefunden und auf ca. 2500 v. Chr. datiert wurde, beschreibt den frühesten Divisionsalgorithmus. Während der Hammurabi-Dynastie (ca. 1800-1600 v. Chr.) beschrieben babylonische Tontafeln Algorithmen zur Berechnung von Formeln. Algorithmen wurden auch in der babylonischen Astronomie verwendet. Babylonische Tontafeln beschreiben und verwenden algorithmische Verfahren zur Berechnung von Zeit und Ort bedeutender astronomischer Ereignisse. ⓘ
Algorithmen für die Arithmetik finden sich auch in der altägyptischen Mathematik, die auf den mathematischen Papyrus von Rhind um 1550 v. Chr. zurückgeht. Später wurden Algorithmen in der antiken hellenistischen Mathematik verwendet. Zwei Beispiele sind das Sieb des Eratosthenes, das in der Einführung in die Arithmetik von Nikomachos beschrieben wurde, und der euklidische Algorithmus, der erstmals in Euklids Elementen (ca. 300 v. Chr.) beschrieben wurde. ⓘ
Diskrete und unterscheidbare Symbole
Strichmännchen: Um den Überblick über ihre Herden, ihre Getreidesäcke und ihr Geld zu behalten, nutzten die Alten das Strichmännchen: Sie sammelten Steine oder auf Stöcke geritzte Zeichen oder formten diskrete Symbole aus Ton. Aus der babylonischen und ägyptischen Verwendung von Zeichen und Symbolen entwickelten sich schließlich die römischen Ziffern und der Abakus (Dilson, S. 16-41). Strichmännchen tauchen in der Arithmetik des unären Zahlensystems auf, das in den Berechnungen der Turing-Maschinen und Post-Turing-Maschinen verwendet wird. ⓘ
Manipulation von Symbolen als "Platzhalter" für Zahlen: Algebra
Muhammad ibn Mūsā al-Khwārizmī, ein persischer Mathematiker, schrieb das Al-jabr im 9. Die Begriffe "Algorismus" und "Algorithmus" leiten sich von dem Namen al-Khwārizmī ab, während der Begriff "Algebra" auf das Buch Al-jabr zurückgeht. In Europa wurde das Wort "Algorithmus" ursprünglich für die von Al-Khwarizmi verwendeten Regeln und Techniken zur Lösung algebraischer Gleichungen verwendet, bevor es später verallgemeinert wurde und sich auf alle Regeln und Techniken bezog. Dies gipfelte schließlich in Leibniz' Begriff des Kalküls ratiocinator (ca. 1680):
Gut anderthalb Jahrhunderte vor seiner Zeit schlug Leibniz eine Algebra der Logik vor, eine Algebra, die die Regeln für den Umgang mit logischen Konzepten so spezifizieren würde, wie die gewöhnliche Algebra die Regeln für den Umgang mit Zahlen spezifiziert. ⓘ
Kryptographische Algorithmen
Der erste kryptografische Algorithmus zur Entschlüsselung verschlüsselter Codes wurde von Al-Kindi, einem arabischen Mathematiker aus dem 9. Jahrhundert, in seinem Manuskript A Manuscript On Deciphering Cryptographic Messages entwickelt. Er beschrieb erstmals die Kryptoanalyse durch Frequenzanalyse, den frühesten Algorithmus zum Entschlüsseln von Codes. ⓘ
Mechanische Vorrichtungen mit diskreten Zuständen
Die Uhr: Bolter bezeichnet die Erfindung der gewichtsgetriebenen Uhr als "die wichtigste Erfindung [Europas im Mittelalter]", insbesondere die Spindelhemmung, die uns das Ticken und Tacken einer mechanischen Uhr ermöglicht. Die "präzise automatische Maschine" führte unmittelbar zu "mechanischen Automaten" ab dem 13. Jahrhundert und schließlich zu "Rechenmaschinen" - der Differenzmaschine und den analytischen Maschinen von Charles Babbage und der Gräfin Ada Lovelace, Mitte des 19. Lovelace wird die erste Entwicklung eines Algorithmus zugeschrieben, der für die Verarbeitung auf einem Computer bestimmt war - Babbages analytische Maschine, das erste Gerät, das als echter Turing-Computer und nicht nur als Rechenmaschine betrachtet wurde - und wird deshalb manchmal als "erste Programmiererin der Geschichte" bezeichnet, obwohl eine vollständige Implementierung von Babbages zweitem Gerät erst Jahrzehnte nach ihrem Leben realisiert werden sollte. ⓘ
Logische Maschinen 1870 - Stanley Jevons' "logischer Abakus" und "logische Maschine": Das technische Problem bestand darin, boolesche Gleichungen zu reduzieren, wenn sie in einer Form dargestellt wurden, die den heute bekannten Karnaugh-Maps ähnelte. Jevons (1880) beschreibt zunächst einen einfachen "Abakus" aus "mit Stiften versehenen Holzstücken, die so konstruiert sind, dass jeder Teil oder jede Klasse der [logischen] Kombinationen mechanisch herausgegriffen werden kann ... In jüngerer Zeit habe ich das System jedoch auf eine vollständig mechanische Form reduziert und so den gesamten indirekten Prozess der Schlussfolgerung in etwas verkörpert, das man als logische Maschine bezeichnen kann" Seine Maschine war mit "bestimmten beweglichen Holzstäben" ausgestattet und "am Fuß befinden sich 21 Tasten, wie die eines Klaviers [usw.] ...". Mit dieser Maschine konnte er einen "Syllogismus oder jedes andere einfache logische Argument" analysieren. ⓘ
Diese Maschine stellte er 1870 vor den Fellows der Royal Society vor. Ein anderer Logiker, John Venn, betrachtete diesen Versuch in seiner 1881 erschienenen Schrift Symbolic Logic jedoch mit Argwohn: "Ich selbst schätze das Interesse oder die Bedeutung dessen, was manchmal als logische Maschinen bezeichnet wird, nicht hoch ein ... es scheint mir nicht, dass irgendwelche gegenwärtig bekannten oder wahrscheinlich zu entdeckenden Erfindungen wirklich den Namen logische Maschinen verdienen"; siehe mehr unter Algorithmus-Charakterisierungen. Aber auch er ließ sich nicht lumpen und präsentierte "einen Plan, der, wie ich annehme, in gewisser Weise dem Abakus von Prof. Jevon entspricht ... [Und] [a]nalog zu Prof. Jevons' logischer Maschine kann die folgende Vorrichtung beschrieben werden. Ich ziehe es vor, sie lediglich eine logische Diagramm-Maschine zu nennen ... aber ich nehme an, dass sie sehr vollständig alles tun könnte, was man von einer logischen Maschine vernünftigerweise erwarten kann". ⓘ
Jacquard-Webstuhl, Hollerith-Lochkarten, Telegrafie und Telefonie - das elektromechanische Relais: Bell und Newell (1971) weisen darauf hin, dass der Jacquard-Webstuhl (1801), der Vorläufer der Hollerith-Karten (Lochkarten, 1887) und die "Telefonvermittlungstechnologien" die Wurzeln eines Baumes sind, der zur Entwicklung der ersten Computer führt. Mitte des 19. Jahrhunderts war der Telegraf, der Vorläufer des Telefons, in der ganzen Welt im Einsatz, und seine diskrete und unterscheidbare Codierung von Buchstaben als "Punkte und Striche" war ein gängiger Klang. Ende des 19. Jahrhunderts wurde das Lochstreifenband (ca. 1870) verwendet, ebenso wie die Verwendung von Hollerith-Karten bei der Volkszählung von 1890. Dann kam der Fernschreiber (ca. 1910) mit seiner Verwendung von Baudot-Code auf Lochstreifen. ⓘ
Telefon-Schaltnetze mit elektromechanischen Relais (erfunden 1835) standen hinter der Arbeit von George Stibitz (1937), dem Erfinder des digitalen Addierers. Bei seiner Arbeit in den Bell Laboratories beobachtete er den "lästigen" Gebrauch von mechanischen Rechenmaschinen mit Zahnrädern. "Eines Abends im Jahr 1937 ging er nach Hause, um seine Idee zu testen... Als die Tüftelei vorbei war, hatte Stibitz ein binäres Addiergerät konstruiert". ⓘ
Der Mathematiker Martin Davis weist auf die besondere Bedeutung des elektromechanischen Relais (mit seinen beiden "binären Zuständen" offen und geschlossen) hin:
- Erst mit der Entwicklung von elektromechanischen Rechenmaschinen mit elektrischen Relais ab den 1930er Jahren wurden Maschinen in dem Umfang gebaut, wie Babbage sie sich vorgestellt hatte." ⓘ
Mathematik im 19. Jahrhundert bis zur Mitte des 20.
Symbole und Regeln: In rascher Folge reduzierten die Mathematiker George Boole (1847, 1854), Gottlob Frege (1879) und Giuseppe Peano (1888-1889) die Arithmetik auf eine Folge von Symbolen, die durch Regeln manipuliert werden. Peanos Die Prinzipien der Arithmetik, dargestellt durch eine neue Methode (1888) war "der erste Versuch einer Axiomatisierung der Mathematik in einer symbolischen Sprache". ⓘ
Aber Heijenoort gibt Frege (1879) diese Anerkennung: Freges Werk ist "vielleicht das wichtigste Einzelwerk, das je in der Logik geschrieben wurde. ... in dem wir eine 'Formelsprache' sehen, d.h. eine lingua characterica, eine mit speziellen Symbolen geschriebene Sprache, "für reines Denken", d.h. frei von rhetorischen Ausschmückungen ... konstruiert aus spezifischen Symbolen, die nach bestimmten Regeln manipuliert werden". Das Werk von Frege wurde von Alfred North Whitehead und Bertrand Russell in ihren Principia Mathematica (1910-1913) weiter vereinfacht und erweitert. ⓘ
Die Paradoxien: Zur gleichen Zeit erschienen in der Literatur eine Reihe beunruhigender Paradoxa, insbesondere das Burali-Forti-Paradoxon (1897), das Russell-Paradoxon (1902-03) und das Richard-Paradoxon. Die daraus resultierenden Überlegungen führten zu Kurt Gödels Arbeit (1931) - er zitiert ausdrücklich das Paradoxon des Lügners -, die die Rekursionsregeln vollständig auf Zahlen reduziert. ⓘ
Effektive Berechenbarkeit: In dem Bemühen, das von Hilbert 1928 präzise definierte Entscheidungsproblem zu lösen, machten sich die Mathematiker zunächst daran, zu definieren, was unter einer "effektiven Methode" oder "effektiven Berechnung" oder "effektiven Berechenbarkeit" (d. h. einer Berechnung, die gelingen würde) zu verstehen sei. In rascher Folge erschienen die folgenden: Alonzo Church, Stephen Kleene und J.B. Rossers λ-Kalkül, eine fein geschliffene Definition der "allgemeinen Rekursion" aus der Arbeit von Gödel, die auf Anregungen von Jacques Herbrand zurückgeht (vgl. Gödels Princeton-Vorlesungen von 1934), und spätere Vereinfachungen durch Kleene. Churchs Beweis, dass das Entscheidungsproblem unlösbar ist, Emil Posts Definition der effektiven Berechenbarkeit als ein Arbeiter, der gedankenlos einer Liste von Anweisungen folgt, sich nach links oder rechts durch eine Reihe von Räumen zu bewegen und dort entweder ein Papier zu markieren oder zu löschen oder das Papier zu beobachten und eine Ja-Nein-Entscheidung über die nächste Anweisung zu treffen. Alan Turings Beweis, dass das Entscheidungsproblem mit Hilfe seiner "a- [automatischen-] Maschine" unlösbar war - im Grunde fast identisch mit Post's "Formulierung", J. Barkley Rossers Definition von "effektiver Methode" im Sinne von "einer Maschine". Kleenes Vorschlag eines Vorläufers der "Church-These", den er "These I" nannte, und einige Jahre später Kleenes Umbenennung seiner These in "Church's Thesis" und sein Vorschlag der "Turing-These". ⓘ
Emil Post (1936) und Alan Turing (1936-37, 1939)
Emil Post (1936) beschrieb die Handlungen eines "Computers" (eines Menschen) wie folgt:
- "...es handelt sich um zwei Konzepte: das eines Symbolraums, in dem die Arbeit, die vom Problem zur Antwort führt, ausgeführt werden soll, und das einer festen, unveränderlichen Menge von Richtungen. ⓘ
Sein Symbolraum wäre
- "eine in zwei Richtungen unendliche Folge von Räumen oder Kästchen... Der Problemlöser oder Arbeiter soll sich in diesem Symbolraum bewegen und arbeiten, wobei er in der Lage ist, sich jeweils nur in einem Kästchen aufzuhalten und dort zu arbeiten.... ein Kästchen soll nur zwei mögliche Zustände zulassen, nämlich leer oder unmarkiert zu sein und eine einzige Markierung, z.B. einen vertikalen Strich, zu haben. ⓘ
- "Ein Kästchen ist auszuwählen und als Ausgangspunkt zu bezeichnen. ...ein bestimmtes Problem wird in symbolischer Form durch eine endliche Anzahl von Kästchen [d.h. INPUT] dargestellt, die mit einem Strich markiert sind. Ebenso ist die Antwort [d.h. OUTPUT] in symbolischer Form durch eine solche Anordnung von markierten Kästchen zu geben... ⓘ
- "Eine Reihe von Anweisungen, die auf ein allgemeines Problem anwendbar sind, setzen einen deterministischen Prozess in Gang, wenn sie auf jedes spezifische Problem angewendet werden. Dieser Prozess endet nur, wenn er auf die Richtung des Typs (C ) [d.h. STOP] trifft". Siehe mehr unter Post-Turing-Maschine ⓘ
Alan Turings Arbeit ging der von Stibitz (1937) voraus; es ist nicht bekannt, ob Stibitz die Arbeit von Turing kannte. Turings Biograph glaubte, dass Turings Verwendung eines schreibmaschinenähnlichen Modells auf ein jugendliches Interesse zurückzuführen war: "Alan hatte als Junge davon geträumt, Schreibmaschinen zu erfinden; Mrs. Turing hatte eine Schreibmaschine, und er könnte sich zunächst gefragt haben, was es bedeutet, eine Schreibmaschine 'mechanisch' zu nennen". In Anbetracht der Verbreitung von Morsezeichen, Telegrafie, Lochstreifenmaschinen und Fernschreibern zu dieser Zeit ist es durchaus möglich, dass all dies Turing in seiner Jugend beeinflusst hat. ⓘ
Turing - sein Rechenmodell wird heute als Turing-Maschine bezeichnet - beginnt, wie auch Post, mit der Analyse eines menschlichen Computers, den er auf eine einfache Reihe von Grundbewegungen und "Geisteszuständen" herunterbricht. Aber er geht noch einen Schritt weiter und schafft eine Maschine als Modell für die Berechnung von Zahlen. ⓘ
- "Rechnen geschieht normalerweise durch das Schreiben bestimmter Symbole auf Papier. Wir können annehmen, dass dieses Papier in Quadrate unterteilt ist, wie das Rechenbuch eines Kindes...Ich nehme also an, dass die Berechnung auf eindimensionalem Papier durchgeführt wird, d.h. auf einem in Quadrate unterteilten Band. Ich nehme auch an, dass die Anzahl der Symbole, die gedruckt werden können, endlich ist... ⓘ
- "Das Verhalten des Computers zu jedem Zeitpunkt wird durch die Symbole, die er beobachtet, und seinen "Geisteszustand" in diesem Moment bestimmt. Wir können annehmen, dass es eine Grenze B für die Anzahl der Symbole oder Quadrate gibt, die der Computer zu einem bestimmten Zeitpunkt beobachten kann. Wenn er mehr beobachten möchte, muss er aufeinanderfolgende Beobachtungen durchführen. Wir nehmen auch an, dass die Anzahl der Geisteszustände, die berücksichtigt werden müssen, endlich ist... ⓘ
- "Stellen wir uns vor, dass die vom Computer ausgeführten Operationen in 'einfache Operationen' aufgeteilt werden, die so elementar sind, dass es nicht leicht ist, sich ihre weitere Aufteilung vorzustellen." ⓘ
Turings Reduktion führt zu folgendem Ergebnis:
- "Zu den einfachen Operationen müssen also gehören:
- "a) Änderungen des Symbols auf einem der beobachteten Quadrate
- "(b) Veränderungen eines der beobachteten Quadrate zu einem anderen Quadrat innerhalb von L Quadraten eines der zuvor beobachteten Quadrate.
"Es mag sein, dass einige dieser Änderungen notwendigerweise eine Änderung des Geisteszustandes hervorrufen. Die allgemeinste einzelne Operation muss daher als eine der folgenden angesehen werden:
- "(A) Eine mögliche Änderung (a) des Symbols zusammen mit einer möglichen Änderung des Geisteszustandes.
- "B) Eine mögliche Änderung (b) der beobachteten Quadrate, zusammen mit einer möglichen Änderung des Geisteszustandes. ⓘ
- "Wir können nun eine Maschine konstruieren, die die Arbeit dieses Computers erledigt." ⓘ
Ein paar Jahre später erweiterte Turing seine Analyse (These, Definition) mit dieser eindringlichen Formulierung:
- "Man sagt, eine Funktion sei "effektiv berechenbar", wenn ihre Werte durch einen rein mechanischen Prozess gefunden werden können. Obwohl es ziemlich einfach ist, ein intuitives Verständnis dieser Idee zu bekommen, ist es dennoch wünschenswert, eine genauere, mathematisch ausdrückbare Definition zu haben ... [er erörtert die Geschichte der Definition ziemlich genau so, wie sie oben in Bezug auf Gödel, Herbrand, Kleene, Church, Turing und Post dargestellt wurde] ... Wir können diese Aussage wörtlich nehmen und unter einem rein mechanischen Prozess einen verstehen, der von einer Maschine ausgeführt werden könnte. Es ist möglich, eine mathematische Beschreibung der Strukturen dieser Maschinen in einer bestimmten Normalform zu geben. Die Entwicklung dieser Ideen führt zu der Definition des Autors einer berechenbaren Funktion und zu einer Identifizierung der Berechenbarkeit † mit der effektiven Berechenbarkeit...
- "† Wir werden den Ausdruck "berechenbare Funktion" verwenden, um eine von einer Maschine berechenbare Funktion zu bezeichnen, und wir lassen "effektiv berechenbar" sich auf die intuitive Idee beziehen, ohne sich mit einer dieser Definitionen zu identifizieren". ⓘ
J.B. Rosser (1939) und S.C. Kleene (1943)
J. Barkley Rosser definierte eine "effektive [mathematische] Methode" auf folgende Weise (Kursivschrift hinzugefügt):
- "'Effektive Methode' wird hier in der etwas speziellen Bedeutung einer Methode verwendet, bei der jeder Schritt genau bestimmt ist und die sicher ist, die Antwort in einer endlichen Anzahl von Schritten zu liefern. Mit dieser speziellen Bedeutung wurden bisher drei verschiedene präzise Definitionen gegeben. [seine Fußnote #5; siehe Diskussion gleich unten]. Die einfachste dieser Definitionen (die auf Post und Turing zurückgeht) besagt im Wesentlichen, dass eine effektive Methode zur Lösung bestimmter Problemmengen existiert, wenn man eine Maschine bauen kann, die dann jedes Problem der Menge löst, ohne dass ein Mensch eingreifen muss, außer die Frage einzugeben und (später) die Antwort zu lesen. Alle drei Definitionen sind gleichwertig, so dass es keine Rolle spielt, welche verwendet wird. Außerdem ist die Tatsache, dass alle drei äquivalent sind, ein sehr starkes Argument für die Korrektheit einer der Definitionen." (Rosser 1939:225-226) ⓘ
Rosser's Fußnote Nr. 5 bezieht sich auf die Arbeiten von (1) Church und Kleene und ihre Definition der λ-Definierbarkeit, insbesondere auf Churchs Verwendung in seinem An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand und Gödel und ihre Verwendung der Rekursion, insbesondere Gödels Verwendung in seinem berühmten Aufsatz On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); und (3) Post (1936) und Turing (1936-37) in ihren Mechanismus-Modellen des Rechnens. ⓘ
Stephen C. Kleene definierte seine inzwischen berühmte "These I", die als Church-Turing-These bekannt ist. Er tat dies jedoch in folgendem Zusammenhang (Fettdruck im Original):
- "12. Algorithmische Theorien... Bei der Aufstellung einer vollständigen algorithmischen Theorie geht es darum, eine Prozedur zu beschreiben, die für jeden Satz von Werten der unabhängigen Variablen durchführbar ist, welche Prozedur notwendigerweise endet und zwar so, dass wir aus dem Ergebnis eine eindeutige Antwort, "ja" oder "nein", auf die Frage "ist der Prädikatswert wahr?" ablesen können" (Kleene 1943:273) ⓘ
Geschichte nach 1950
Eine Reihe von Anstrengungen wurde unternommen, um die Definition des Begriffs "Algorithmus" weiter zu verfeinern, und die Aktivitäten sind aufgrund von Fragen im Zusammenhang mit den Grundlagen der Mathematik (insbesondere der Church-Turing-These) und der Philosophie des Geistes (insbesondere Argumente zur künstlichen Intelligenz) noch nicht abgeschlossen. Weitere Informationen finden Sie unter Algorithmus-Charakterisierungen. ⓘ
Definition
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. ⓘ
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). ⓘ
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 Sequential Abstract State Machine (kurz 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 Schaltkreisen 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). ⓘ
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 Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert. ⓘ
Heutige Situation
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. 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. ⓘ
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. ⓘ
Finitheit
Statische Finitheit
Die Beschreibung des Algorithmus besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeichen bestehen. ⓘ
Dynamische Finitheit
Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen. ⓘ
Terminiertheit
Ein Algorithmus ‚terminiert überall‘ oder ‚ist terminierend‘, wenn er nach endlich vielen Schritten anhält (oder kontrolliert abbricht) – für jede mögliche Eingabe. Ein nicht-terminierender Algorithmus (somit zu keinem Ergebnis kommend) gerät (für manche Eingaben) in eine so genannte Endlosschleife. ⓘ
Für manche Abläufe ist ein nicht-terminierendes Verhalten gewünscht, z. B. Steuerungssysteme, Betriebssysteme und Programme, die auf Interaktion mit dem Benutzer aufbauen. Solange der Benutzer keinen Befehl zum Beenden eingibt, laufen diese Programme beabsichtigt endlos weiter. Donald E. Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden (Computational Methods) zu bezeichnen. ⓘ
Darüber hinaus ist die Terminierung eines Algorithmus (das Halteproblem) nicht entscheidbar. Das heißt, das Problem, festzustellen, ob ein (beliebiger) Algorithmus mit einer beliebigen Eingabe terminiert, ist nicht durch einen Algorithmus lösbar. ⓘ
Effektivität
Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein. ⓘ
Beispiele für (weitere) Eigenschaften von Algorithmen
- Einfache Grundoperation: „Öffne die Flasche Wein.“ – Hierbei wird das Wissen um das Öffnen vorausgesetzt.
- Sequentieller Algorithmus: „Bier auf Wein, lass' das sein.“ – Beiden Operationen ist eine Reihenfolge vorgegeben.
- Nebenläufiger Algorithmus: „Getrunken wird Apfelsaft und Sprudel.“ – Die Reihenfolge ist nicht vorgegeben und kann auch gleichzeitig erfolgen.
- Parallele Ausführung: „Mit Sekt anstoßen“ – dies kann nur gleichzeitig (parallel) ausgeführt werden und nicht hintereinander (sequentiell).
- Nichtdeterministischer/nichtdeterminierter Algorithmus: „Füge dem Teig 200 ml Bier oder Wasser hinzu.“ – Das Ergebnis kann sich unterscheiden, je nachdem welche Alternative man wählt. ⓘ
Algorithmenanalyse
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 manchen 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 meist asymptotisch (z. B. als asymptotische Laufzeit) angegeben. Der Ressourcenbedarf wird dabei im Allgemeinen in Abhängigkeit von der Länge der Eingabe ermittelt, das heißt, der Ressourcenbedarf hängt meist davon ab, wie viele Eingabewerte verarbeitet werden müssen, „wie ‚groß‘ die Eingabe(menge) ist“.
- Das Verhalten bezüglich der Terminierung, ob also der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie. ⓘ
Geschichte des Algorithmus
Geschichtliche Entwicklung
Schon mit der Entwicklung der Sprache ersannen die Menschen für ihr Zusammenleben in größeren Gruppen Verhaltensregeln, Gebote, Gesetze – einfachste Algorithmen. Mit der Sprache ist auch eine geeignete Möglichkeit gegeben, Verfahren und Fertigkeiten weiterzugeben – komplexere Algorithmen. Aus der Spezialisierung einzelner Gruppenmitglieder auf bestimmte Fertigkeiten entstanden die ersten Berufe. ⓘ
Der Algorithmusbegriff als abstrakte Sicht auf Aufgabenlösungswege trat zuerst im Rahmen der Mathematik, Logik und Philosophie ins Bewusstsein der Menschen. Ein Beispiel für einen mathematischen Algorithmus aus dem Altertum ist der Euklidische Algorithmus. ⓘ