Algorithmus -Algorithm

Flussdiagramm eines Algorithmus ( Euklidischer Algorithmus ) zur Berechnung des größten gemeinsamen Teilers (ggT) zweier Zahlen a und b an Stellen namens A und B. Der Algorithmus fährt durch aufeinanderfolgende Subtraktionen in zwei Schleifen fort: WENN der Test B ≥ A "ja" ergibt oder "wahr" (genauer gesagt, die Zahl b an Ort B ist größer oder gleich der Zahl a an Ort A) DANN spezifiziert der Algorithmus B ← B − A (was bedeutet, dass die Zahl ba das alte b ersetzt). Ähnlich IF A > B, THEN A ← A − B. Der Prozess endet, wenn (der Inhalt von) B 0 ist, was den ggT in A ergibt. (Algorithmus abgeleitet von Scott 2009:13; Symbole und Zeichenstil von Tausworthe 1977) .
Ada Lovelaces Diagramm aus „Note G“, dem ersten veröffentlichten Computeralgorithmus

In der Mathematik und Informatik ist ein Algorithmus ( / ˈ æ l ɡ ə r ɪ ð əm / ( hören ) ) eine endliche Folge strenger Anweisungen , die typischerweise verwendet werden , um eine Klasse spezifischer Probleme zu lösen oder eine Berechnung durchzuführen . Algorithmen werden als Spezifikationen zur Durchführung von Berechnungen und Datenverarbeitung verwendet . Fortgeschrittenere Algorithmen können automatisierte Ableitungen durchführen (als automatisiertes Schließen bezeichnet ) und mathematische und logische Tests verwenden, um die Codeausführung über verschiedene Routen umzuleiten (als automatisierte Entscheidungsfindung bezeichnet ). Die metaphorische Verwendung menschlicher Eigenschaften als Deskriptoren von Maschinen wurde bereits von Alan Turing mit Begriffen wie „Memory“, „Search“ und „Stimulus“ praktiziert.

Im Gegensatz dazu ist eine Heuristik ein Ansatz zur Problemlösung, der möglicherweise nicht vollständig spezifiziert ist oder möglicherweise keine korrekten oder optimalen Ergebnisse garantiert, insbesondere in Problembereichen, in denen es kein genau definiertes korrektes oder optimales Ergebnis gibt.

Als effektive Methode kann ein Algorithmus innerhalb einer endlichen Menge an Raum und Zeit und in einer wohldefinierten formalen Sprache zum Berechnen einer Funktion ausgedrückt werden . Ausgehend von einem Anfangszustand und einer Anfangseingabe (möglicherweise leer ) beschreiben die Anweisungen eine Berechnung , die, wenn sie ausgeführt wird, eine endliche Anzahl von wohldefinierten aufeinanderfolgenden Zuständen durchläuft, schließlich eine "Ausgabe" erzeugt und an einem endgültigen Endzustand endet. Der Übergang von einem Zustand zum nächsten ist nicht unbedingt deterministisch ; Einige Algorithmen, die als randomisierte Algorithmen bezeichnet werden , enthalten zufällige Eingaben.

Geschichte

Das Konzept der Algorithmen existiert seit der Antike. Arithmetische Algorithmen, wie z. B. ein Divisionsalgorithmus , wurden von alten babylonischen Mathematikern verwendet c. 2500 v. Chr. und ägyptische Mathematiker c. 1550 v. Chr. Griechische Mathematiker verwendeten später 240 v. Chr. Algorithmen im Sieb von Eratosthenes , um Primzahlen zu finden, und den euklidischen Algorithmus , um den größten gemeinsamen Teiler zweier Zahlen zu finden. Arabische Mathematiker wie al-Kindi verwendeten im 9. Jahrhundert kryptografische Algorithmen zum Knacken von Codes , basierend auf Frequenzanalysen .

Das Wort Algorithmus leitet sich vom Namen des persischen Mathematikers Muhammad ibn Musa al-Khwarizmi aus dem 9. Jahrhundert ab . Al-Khwarizmi war 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 jetzt in Usbekistan liegt . Um das Jahr 825 schrieb al-Khwarizmi eine arabischsprachige Abhandlung über das hindu-arabische Zahlensystem , die im 12. Jahrhundert ins Lateinische übersetzt wurde. Das Manuskript beginnt mit dem Satz Dixit Algorizmi ("So sprach Al-Khwarizmi"), wobei "Algorizmi" die Lateinisierung des Namens von Al-Khwarizmi durch den Übersetzer war. Al-Khwarizmi war im späten Mittelalter der meistgelesene Mathematiker in Europa, vor allem durch ein anderes seiner Bücher, die Algebra . Im spätmittelalterlichen Latein bedeutete algorismus , englisch „ algorism “, die Verballhornung seines Namens, das „ dezimale Zahlensystem“. Im 15. Jahrhundert wurde unter dem Einfluss des griechischen Wortes ἀριθμός ( arithmos ), „Zahl“ ( vgl. „Arithmetik“), das lateinische Wort in algorithmus abgeändert , und der entsprechende englische Begriff „algorithm“ ist erstmals im 17. Jahrhundert bezeugt Jahrhundert; der moderne Sinn wurde im 19. Jahrhundert eingeführt.

Die indische Mathematik war überwiegend algorithmisch. Algorithmen, die repräsentativ für die indische mathematische Tradition sind, reichen von den alten Śulbasūtrās bis zu den mittelalterlichen Texten der Kerala-Schule .

Im Englischen wurde das Wort Algorithmus erstmals um 1230 und dann 1391 von Chaucer verwendet . Das Englische übernahm den französischen Begriff, aber erst im späten 19. Jahrhundert nahm „Algorithmus“ die Bedeutung an, die es im modernen Englisch hat.

Eine weitere frühe Verwendung des Wortes stammt aus dem Jahr 1240 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 heißt:

Algorismus ist die Kunst, mit der wir gegenwärtig diese indischen Zahlen verwenden, die zwei mal fünf zählen.

Das Gedicht ist einige hundert Zeilen lang und fasst die Kunst des Rechnens mit den neu gestalteten indischen Würfeln ( Tali Indorum ), den hinduistischen Ziffern, zusammen.

Eine partielle Formalisierung des modernen Algorithmusbegriffs begann mit Versuchen zur Lösung des Entscheidungsproblems von David Hilbert im Jahr 1928. Spätere Formalisierungen wurden als Versuche zur Definition von „ effektiver Berechenbarkeit “ oder „effektiver Methode“ umrahmt. Zu diesen Formalisierungen gehörten die rekursiven Gödel - Herbrand - Kleene -Funktionen von 1930, 1934 und 1935, der Lambda-Kalkül von Alonzo Church von 1936, die Formulierung 1 von Emil Post von 1936 und die Turing- Maschinen von Alan Turing von 1936–37 und 1939.

Informelle Definition

Eine informelle Definition könnte "ein Satz von Regeln sein, der eine Abfolge von Operationen genau definiert", was alle Computerprogramme (einschließlich Programme, die keine numerischen Berechnungen durchführen) und (zum Beispiel) alle vorgeschriebenen bürokratischen Verfahren oder Kochbuchrezepte umfassen würde .

Im Allgemeinen ist ein Programm nur dann ein Algorithmus, wenn es irgendwann aufhört – auch wenn sich Endlosschleifen manchmal als wünschenswert erweisen.

Ein prototypisches Beispiel für einen Algorithmus ist der Euklidische Algorithmus , der verwendet wird, um den maximalen gemeinsamen Teiler zweier ganzer Zahlen zu bestimmen; ein Beispiel (es gibt andere) wird durch das obige Flussdiagramm und als Beispiel in einem späteren Abschnitt beschrieben.

Boolos, Jeffrey & 1974, 1999 bieten eine informelle Bedeutung des Wortes "Algorithmus" im folgenden Zitat:

Kein Mensch kann schnell genug schreiben oder lange genug oder klein genug† ( †"kleiner und kleiner ohne Grenzen ... Sie würden versuchen, auf Moleküle, auf Atome, auf Elektronen zu schreiben"), um alle Mitglieder von an aufzulisten zählbare unendliche Menge, indem man ihre Namen nacheinander in irgendeiner Schreibweise ausschreibt. Aber Menschen können im Fall bestimmter aufzählbarer unendlicher Mengen etwas ebenso Nützliches tun: Sie können explizite Anweisungen zur Bestimmung des n -ten Mitglieds der Menge für beliebige endliche n geben . Solche Anweisungen müssen ganz explizit in einer Form gegeben werden, in der sie von einer Rechenmaschine oder von einem Menschen befolgt werden könnten, der nur sehr elementare Operationen an Symbolen ausführen kann.

Eine "aufzählbare unendliche Menge" ist eine, deren Elemente in eine Eins-zu-Eins-Korrespondenz 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, Ausgangs-Ganzzahlen „erzeugt“. Beispielsweise kann ein Algorithmus eine algebraische Gleichung wie y = m + n sein (dh zwei willkürliche "Eingabevariablen" m und n , die eine Ausgabe y erzeugen ), aber die Versuche verschiedener Autoren, den Begriff zu definieren, weisen darauf hin, dass das Wort impliziert viel mehr als das, 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 "Züge" "des Computers" (Maschine oder Mensch, ausgestattet mit den notwendigen intern enthaltenen Informationen und Fähigkeiten) angibt Finden, decodieren und verarbeiten Sie dann beliebige Eingabe-Ganzzahlen/Symbole m und n , Symbole + und = ... und erzeugen Sie "effektiv" in einer "angemessenen" Zeit eine Ausgabe-Ganzzahl y an einer bestimmten Stelle und in einem bestimmten Format.

Das Konzept des Algorithmus wird auch verwendet, um den Begriff der Entscheidbarkeit zu definieren – ein Begriff, der zentral ist, um zu erklären, wie formale Systeme ausgehend von einer kleinen Menge von Axiomen und Regeln entstehen. In der Logik kann die Zeit, die ein Algorithmus für die Ausführung benötigt, nicht gemessen werden, da sie anscheinend nicht mit der üblichen physikalischen Dimension zusammenhängt. Aus solchen Unsicherheiten, die die laufende Arbeit charakterisieren, ergibt sich die Nichtverfügbarkeit einer Definition des Begriffs Algorithmus , die sowohl der konkreten (in gewissem Sinne) als auch der abstrakten Verwendung des Begriffs entspricht.

Die meisten Algorithmen sollen als Computerprogramme implementiert werden . Algorithmen werden jedoch auch auf andere Weise implementiert, z. B. in einem biologischen neuronalen Netzwerk (z. B. das menschliche Gehirn , das Arithmetik ausführt , oder ein 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 sollte, um eine bestimmte Aufgabe auszuführen, z. B. das Berechnen der Gehaltsschecks der Mitarbeiter oder das Drucken der Zeugnisse der Schüler. Somit kann ein Algorithmus als jede Folge von Operationen angesehen werden, die von einem Turing-vollständigen 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 jedes Verfahren, das "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 sind schwer zu widerlegen". Gurevich: „… Turings informelles Argument zugunsten seiner 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“.

Turing-Maschinen können Rechenprozesse definieren, die nicht terminieren. Die informellen Definitionen von Algorithmen erfordern im Allgemeinen, dass der Algorithmus immer terminiert. Diese Anforderung macht die Aufgabe, zu entscheiden, 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 verknüpft ist, können Daten typischerweise von einer Eingabequelle gelesen, auf ein Ausgabegerät geschrieben und zur weiteren Verarbeitung gespeichert werden. Gespeicherte Daten werden als Teil des internen Zustands der den Algorithmus ausführenden Entität betrachtet. In der Praxis wird der Zustand in einer oder mehreren Datenstrukturen gespeichert .

Für einige dieser Rechenprozesse muss der Algorithmus streng definiert und so spezifiziert werden, dass er unter allen möglichen Umständen, die auftreten können, anwendbar ist. Das bedeutet, dass alle bedingten Schritte von Fall zu Fall systematisch behandelt werden müssen; die Kriterien für jeden Fall müssen klar (und berechenbar) sein.

Da ein Algorithmus eine genaue Liste präziser Schritte ist, ist die Reihenfolge der Berechnung immer entscheidend für das Funktionieren des Algorithmus. In der Regel wird davon ausgegangen, dass Anweisungen explizit aufgelistet sind und als „von oben“ beginnend und „nach unten“ verlaufend beschrieben werden – eine Idee, die formaler durch Kontrollfluss beschrieben wird .

Bisher ist die Diskussion um die Formalisierung eines Algorithmus von den Prämissen der imperativen Programmierung ausgegangen . Dies ist die gebräuchlichste Konzeption – eine, die versucht, eine Aufgabe mit diskreten, „mechanischen“ Mitteln zu beschreiben. Einzigartig an dieser Konzeption formalisierter Algorithmen ist die Zuweisungsoperation , die den Wert einer Variablen festlegt. Es leitet sich von der Intuition des „ Gedächtnisses “ als Notizblock ab. Ein Beispiel für eine solche Zuordnung finden Sie weiter unten.

Für einige alternative Konzepte dessen, was einen Algorithmus ausmacht, siehe funktionale Programmierung und logische Programmierung .

Algorithmen ausdrücken

Algorithmen können in vielen Arten von Notationen ausgedrückt werden, einschließlich natürlicher Sprachen , Pseudocode , Flussdiagramme , Drakon-Diagramme , Programmiersprachen oder Steuertabellen (verarbeitet durch Interpreter ). Natürlichsprachliche Ausdrücke von Algorithmen sind in der Regel ausführlich und mehrdeutig und werden selten für komplexe oder technische Algorithmen verwendet. Pseudocode, Flussdiagramme, Drakon-Diagramme und Steuertabellen sind strukturierte Wege, um Algorithmen auszudrücken, die viele der Mehrdeutigkeiten vermeiden, die in den auf natürlicher Sprache basierenden Aussagen üblich sind. Programmiersprachen sind in erster Linie dafür gedacht, Algorithmen in einer Form auszudrücken, die von einem Computer ausgeführt werden kann, werden aber auch oft verwendet, um Algorithmen zu definieren oder zu dokumentieren.

Es ist eine Vielzahl von Darstellungen möglich, und man kann ein bestimmtes Turing-Maschinenprogramm als eine Folge von Maschinentabellen (siehe Finite-State-Maschine , Zustandsübergangstabelle und Steuertabelle für mehr), als Flussdiagramme und Drakon-Diagramme (siehe Zustandsdiagramm für mehr) oder als eine Form von rudimentärem Maschinencode oder Assemblercode namens "Sätze von Quadrupeln" (siehe Turing-Maschine für mehr).

Darstellungen von Algorithmen können wie folgt in drei akzeptierte Ebenen der Beschreibung von Turing-Maschinen eingeteilt werden:

1 Allgemeine Beschreibung
"... um einen Algorithmus zu beschreiben, wobei die Implementierungsdetails ignoriert werden. Auf dieser Ebene müssen wir nicht erwähnen, wie die Maschine ihr Band oder ihren Kopf verwaltet."
2 Beschreibung der Implementierung
"... Prosa, die verwendet wird, um zu definieren, wie die Turing-Maschine ihren Kopf verwendet und wie sie Daten auf ihrem Band speichert. Auf dieser Ebene geben wir keine Details zu Zuständen oder Übergangsfunktionen an."
3 Formale Beschreibung
Am detailliertesten, "unterste Ebene", gibt die "Zustandstabelle" der Turing-Maschine an.

Ein Beispiel für den einfachen Algorithmus "Add m+n", der in allen drei Ebenen beschrieben wird, finden Sie unter Beispiele .

Entwurf

Algorithmendesign 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, wie z. B. Teile-und-Herrsche oder dynamische Programmierung im Rahmen von Operations Research . Techniken zum Entwerfen und Implementieren von Algorithmusentwürfen werden auch als Algorithmusentwurfsmuster bezeichnet, wobei Beispiele das Vorlagenmethodenmuster und das Dekorationsmuster umfassen.

Einer der wichtigsten Aspekte des Algorithmusdesigns ist die Ressourceneffizienz (Laufzeit, Speichernutzung); Die große O -Notation wird verwendet, um zB das Laufzeitwachstum eines Algorithmus zu beschreiben, wenn die Größe seiner Eingabe zunimmt.

Typische Schritte bei der Entwicklung von Algorithmen:

  1. Problem Definition
  2. Entwicklung eines Modells
  3. Spezifikation des Algorithmus
  4. Entwerfen eines Algorithmus
  5. Überprüfung der Korrektheit des Algorithmus
  6. Analyse des Algorithmus
  7. Implementierung des Algorithmus
  8. Programmtest
  9. Vorbereitung der Dokumentation

Computeralgorithmen

Logischer NAND- Algorithmus, der elektronisch im 7400 -Chip implementiert ist
Flussdiagrammbeispiele der kanonischen Böhm-Jacopini-Strukturen : die SEQUENCE (Rechtecke, die die Seite absteigen), das WHILE-DO und das IF-THEN-ELSE. Die drei Strukturen bestehen aus dem primitiven bedingten GOTO ( 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 Zuordnungsblöcken führt zu komplexen Diagrammen (vgl. Tausworthe 1977:100, 114).

"Elegante" (kompakte) Programme, "gute" (schnelle) Programme : Der Begriff "Einfachheit und Eleganz" taucht informell bei Knuth und genau bei Chaitin auf :

Knuth: " ... wir wollen gute Algorithmen in einem locker definierten ästhetischen Sinne. Ein Kriterium ... ist die Zeitdauer, die benötigt wird, um den Algorithmus auszuführen .... Andere Kriterien sind die Anpassbarkeit 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 tut."

Chaitin stellt seiner Definition voran: „Ich werde zeigen, dass Sie nicht beweisen können, dass ein Programm ‚elegant ist “ – ein solcher Beweis würde das Halteproblem lösen ( ebd.).

Algorithmus versus durch einen Algorithmus berechenbare Funktion : Für eine gegebene Funktion können mehrere Algorithmen existieren. Dies gilt auch ohne Erweiterung des verfügbaren Befehlssatzes, der dem Programmierer zur Verfügung steht. Rogers stellt fest, dass "es ... wichtig ist, zwischen dem Begriff des Algorithmus , dh der Prozedur, und dem Begriff der durch den Algorithmus berechenbaren Funktion , dh der durch die Prozedur erzeugten Abbildung, zu unterscheiden. Dieselbe Funktion kann mehrere unterschiedliche Algorithmen haben."

Leider kann es einen Kompromiss zwischen Güte (Geschwindigkeit) und Eleganz (Kompaktheit) geben – ein elegantes Programm benötigt möglicherweise mehr Schritte, um eine Berechnung abzuschließen, als ein weniger elegantes. Ein Beispiel, das den Euklid-Algorithmus verwendet, erscheint unten.

Computer (und Computer), Berechnungsmodelle : Ein Computer (oder menschlicher „Computer“) ist eine eingeschränkte Art von Maschine, ein „diskretes deterministisches mechanisches Gerät“, das blindlings seinen Anweisungen folgt. Die primitiven Modelle von Melzak und Lambek reduzierten diesen Begriff auf vier Elemente: (i) diskrete, unterscheidbare Orte , (ii) diskrete, nicht unterscheidbare Zähler , (iii) einen Agenten und (iv) eine Liste von Anweisungen, die relativ zu den Fähigkeiten des Agenten effektiv sind Agent.

Minsky beschreibt in seinen „Very Simple Bases for Computability “ eine kongenialere Variante von Lambeks „abacus“-Modell . Minskys Maschine geht sequentiell durch ihre fünf (oder sechs, je nachdem, wie man zählt) Anweisungen, es sei denn, entweder ein bedingtes IF-THEN GOTO oder ein unbedingtes GOTO verändert den Programmfluss aus der Reihenfolge. Neben HALT enthält Minskys Maschine drei Zuweisungsoperationen (Ersetzung, Substitution): ZERO (z. B. der Inhalt von Ort 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. Aber Minsky zeigt (ebenso wie Melzak und Lambek), dass seine Maschine Turing komplett ist, mit nur vier allgemeinen Arten von Anweisungen: bedingtes GOTO, unbedingtes GOTO, Zuweisung/Ersetzung/Substitution 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 ist etwas Sache des Designers. Das unbedingte GOTO ist praktisch; es kann konstruiert werden, indem eine dedizierte Stelle auf Null initialisiert wird, z. B. die Anweisung "Z ← 0"; danach ist die Anweisung IF Z=0 THEN GOTO xxx unbedingt.

Simulation eines Algorithmus: Computersprache : Knuth rät dem Leser, dass „der beste Weg, einen Algorithmus zu lernen, darin besteht, ihn auszuprobieren … nimm sofort Stift und Papier und arbeite ein Beispiel durch“. Aber was ist mit einer Simulation oder Ausführung der realen Sache? Der Programmierer muss den Algorithmus in eine Sprache übersetzen, die der Simulator/Computer/Computer effektiv ausführen kann. Stone gibt dafür ein Beispiel: Beim Berechnen der Wurzeln einer quadratischen Gleichung muss der Computer wissen, wie man eine Quadratwurzel zieht. Wenn dies nicht der Fall ist, muss der Algorithmus, um effektiv zu sein, eine Reihe von Regeln zum Ziehen einer Quadratwurzel bereitstellen.

Dies bedeutet, dass der Programmierer eine "Sprache" kennen muss, die relativ zu dem Ziel-Rechenagenten (Computer/Rechner) 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 Wahl eines Modells willkürlich. An diesem Punkt kommt der Begriff der Simulation ins Spiel". Bei der Geschwindigkeitsmessung kommt es auf den Befehlssatz an. Zum Beispiel würde das Unterprogramm in Euklids Algorithmus zur Berechnung des Rests viel schneller ausgeführt werden, wenn der Programmierer einen „ Modulus “-Befehl zur Verfügung hätte und nicht nur eine Subtraktion (oder noch 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 Turing-Vollständigkeit nur vier Anweisungstypen – bedingtes GOTO, unbedingtes GOTO, Zuweisung, HALT. Kemeny und Kurtz stellen fest, dass, während die „undisziplinierte“ Verwendung von unbedingten GOTOs und bedingten IF-THEN-GOTOs zu „ Spaghetti-Code “ führen kann, 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 Böhm-Jacopini-Strukturen : SEQUENCE, IF-THEN-ELSE und WHILE-DO um zwei weitere: DO-WHILE und CASE. Ein zusätzlicher Vorteil eines strukturierten Programms besteht darin, dass es sich für Korrektheitsbeweise mit mathematischer Induktion eignet .

Kanonische Flussdiagrammsymbole : Die als Flussdiagramm bezeichnete grafische Hilfe bietet eine Möglichkeit, einen Algorithmus (und ein entsprechendes Computerprogramm) zu beschreiben und zu dokumentieren. Wie der Programmablauf einer Minsky-Maschine beginnt ein Flussdiagramm immer oben auf einer Seite und setzt sich nach unten fort. Seine Hauptsymbole sind nur vier: der gerichtete Pfeil, der den Programmablauf anzeigt, das Rechteck (SEQUENCE, GOTO), die Raute (IF-THEN-ELSE) und der Punkt (ODER-Verknüpfung). Die kanonischen Strukturen von Böhm-Jacopini bestehen aus diesen primitiven Formen. Unterstrukturen können in Rechtecken "verschachtelt" werden, aber nur, wenn ein einziger Ausgang von der Überstruktur auftritt. Die Symbole und ihre Verwendung zum Aufbau der kanonischen Strukturen sind im Diagramm dargestellt.

Beispiele

Beispiel Algorithmus

Einer der einfachsten Algorithmen besteht darin, die größte Zahl in einer Liste von Zahlen in zufälliger Reihenfolge zu finden. Um die Lösung zu finden, müssen Sie sich jede Zahl in der Liste ansehen. Daraus folgt ein einfacher Algorithmus, der in einer High-Level-Beschreibung in englischer Prosa wie folgt angegeben werden kann:

Allgemeine Beschreibung:

  1. Wenn es keine Zahlen in der Menge gibt, dann gibt es keine höchste Zahl.
  2. Angenommen, die erste Zahl in der Menge ist die größte Zahl in der Menge.
  3. Für jede verbleibende Zahl in der Menge: Wenn diese Zahl größer als die derzeit größte Zahl ist, betrachten Sie diese Zahl als die größte Zahl in der Menge.
  4. Wenn in der Menge keine Zahlen übrig sind, über die iteriert werden kann, betrachten Sie die aktuell größte Zahl als die größte Zahl der Menge.

(Quasi-)formale Beschreibung: In Prosa geschrieben, aber viel näher an der Hochsprache eines Computerprogramms, folgt die formellere Codierung des Algorithmus in Pseudocode oder Pidgin-Code :

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.
if L.size = 0 return null
largestL[0]
for each item in L, do
    if item > largest, then
        largestitem
return largest
  • "←" bezeichnet Zuweisung . Zum Beispiel bedeutet " größterArtikel ", dass sich der Wert des größten gegenüber dem Wert von Artikel ändert .
  • " return " beendet den Algorithmus und gibt den folgenden Wert aus.

Euklids Algorithmus

In der Mathematik ist der euklidische Algorithmus oder der euklidische Algorithmus eine effiziente Methode zur Berechnung des größten gemeinsamen Teilers (ggT) zweier ganzer Zahlen (Zahlen), der größten Zahl, die sie beide ohne Rest teilt . Es ist nach dem antiken griechischen Mathematiker Euklid benannt , der es erstmals in seinen Elementen ( ca.  300 v . Chr .) beschrieb. Es ist einer der ältesten allgemein verwendeten Algorithmen. Es kann verwendet werden, um Brüche auf ihre einfachste Form zu reduzieren , und ist Teil vieler anderer zahlentheoretischer und kryptografischer Berechnungen.

Das Beispieldiagramm von Euklids Algorithmus von TL Heath (1908), mit weiteren Details hinzugefügt. Euklid geht nicht über eine dritte Messung hinaus und gibt keine Zahlenbeispiele. Nicomachus gibt das Beispiel von 49 und 21: "Ich ziehe das Kleinere vom Größeren ab; 28 bleibt übrig; dann ziehe ich davon wieder die gleiche 21 ab (denn dies ist möglich); 7 bleibt übrig; Ich ziehe dies von 21 ab, 14 ist links; davon ziehe ich wieder 7 ab (denn das ist möglich); 7 bleibt übrig, aber 7 kann nicht von 7 abgezogen werden." Heath kommentiert: "Der letzte Satz ist merkwürdig, aber seine Bedeutung ist offensichtlich genug, ebenso wie die Bedeutung des Satzes über das Ende 'bei ein und derselben Nummer'." (Heath 1908: 300).

Euklid stellt das Problem folgendermaßen: "Wenn zwei Zahlen gegeben sind, die nicht teilerfremd sind, um ihr größtes gemeinsames Maß zu finden". Er definiert „eine Zahl, die eine Vielzahl von Einheiten sein soll“: eine Zählzahl, eine positive ganze Zahl ohne Null. "Messen" bedeutet, eine kürzere Messlänge s sukzessive ( q Mal) entlang der längeren Länge l zu platzieren , bis der verbleibende Teil r kleiner als die kürzere Länge s ist . In modernen Worten, Rest r = lq × s , wobei q der Quotient ist, oder Rest r ist der "Modul", der ganzzahlige Bruchteil, der nach der Division übrig bleibt.

Damit Euklids Methode erfolgreich ist, müssen die Startlängen zwei Anforderungen erfüllen: (i) die Längen dürfen nicht Null sein UND (ii) die Subtraktion muss "richtig" sein; dh ein Test muss garantieren, dass die kleinere der beiden Zahlen von der größeren subtrahiert wird (oder die beiden können gleich sein, sodass ihre Subtraktion null ergibt).

Euklids Originalbeweis fügt eine dritte Anforderung hinzu: Die beiden Längen dürfen nicht teilerfremd sein. Euklid legte dies fest, damit er einen Beweis ad absurdum führen konnte , dass das gemeinsame Maß der beiden Zahlen tatsächlich das größte ist . Während der Algorithmus von Nicomachus derselbe ist wie der von Euklid, ergibt er die Zahl "1" für ihr gemeinsames Maß, wenn die Zahlen Primzahlen sind. Um genau zu sein, ist das Folgende wirklich der Algorithmus von Nicomachus.

Ein grafischer Ausdruck von Euklids Algorithmus, um den größten gemeinsamen Teiler für 1599 und 650 zu finden.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

Computersprache für Euklids Algorithmus

Es sind nur wenige Befehlstypen erforderlich , um den Euklid-Algorithmus auszuführen – einige logische Tests (bedingtes GOTO), unbedingtes GOTO, Zuweisung (Ersetzung) und Subtraktion.

  • Ein Ort wird durch Großbuchstaben symbolisiert, z. B. S, A usw.
  • Die variierende Menge (Anzahl) an einem Standort wird in Kleinbuchstaben geschrieben und (normalerweise) mit dem Namen des Standorts verknüpft. Zum Beispiel könnte die Position L am Anfang die Zahl l = 3009 enthalten.

Ein unelegantes Programm für Euklids Algorithmus

"Inelegant" ist eine Übersetzung von Knuths Version des Algorithmus mit einer auf Subtraktion basierenden Restschleife, die seine Verwendung der Division (oder einer "Modulus" -Anweisung) ersetzt. Abgeleitet von Knuth 1973: 2–4. Abhängig von den beiden Zahlen kann "Inelegant" den ggT in weniger Schritten berechnen als "Elegant".

Der folgende Algorithmus ist als Knuths vierstufige Version von Euklids und Nikomachos gerahmt, aber anstatt eine Division zu verwenden, um den Rest zu finden, verwendet er aufeinanderfolgende Subtraktionen der kürzeren Länge s von der verbleibenden Länge r , bis r kleiner als s ist . Die fett gedruckte Beschreibung auf hoher Ebene wurde von Knuth 1973: 2–4 übernommen:

EINGABE :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
R ← L

E0: [Sicherstellen, dass rs .]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
IF R > S THEN
the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
GOTO step 7
ELSE
swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5 R ← S
6 S ← L

E1: [Rest suchen] : Bis die Restlänge r in R kleiner ist als die kürzere Länge s in S, subtrahiere wiederholt die Maßzahl s in S von der Restlänge r in R.

7 IF S > R THEN
done measuring so
GOTO 10
ELSE
measure again,
8 R ← R − S
9 [Remainder-loop]:
GOTO 7.

E2: [Ist der Rest Null?] : ENTWEDER (i) der letzte Takt war exakt, der Rest in R ist Null und das Programm kann anhalten, ODER (ii) der Algorithmus muss fortgesetzt werden: der letzte Takt hat einen Rest in R hinterlassen kleiner als Messzahl in S.

10 IF R = 0 THEN
done so
GOTO step 15
ELSE
CONTINUE TO step 11,

E3: [Interchange s and r ] : Die Nuss von Euklids Algorithmus. Verwenden Sie den Rest r , um die zuvor kleinere Zahl s zu messen ; L dient als temporärer Standort.

11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]:
GOTO 7

AUSGANG :

15 [Done. S contains the greatest common divisor]:
PRINT S

FERTIG :

16 HALT, END, STOP.

Ein elegantes Programm für Euklids Algorithmus

Die folgende Version von Euklids Algorithmus benötigt nur sechs Kernanweisungen, um das zu tun, was dreizehn von "Inelegant" tun müssen; Schlimmer noch, "Inelegant" erfordert mehr Arten von Anweisungen. Das Flussdiagramm von „Elegant“ finden Sie oben in diesem Artikel. In der (unstrukturierten) Basic-Sprache sind die Schritte nummeriert, und die Anweisung ist die durch ← symbolisierte Zuweisungsanweisung. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT 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 PRINT A
  90 END

Funktionsweise von „Elegant“ : Anstelle einer äußeren „Euklid-Schleife“ wechselt „Elegant“ zwischen zwei „Co-Schleifen“, einer A > B-Schleife, die A ← A − B berechnet, und einer B ≤ A-Schleife hin und her das berechnet B ← B − A. Dies funktioniert, weil, wenn zuletzt der Minuend M kleiner oder gleich dem Subtrahend S ist (Differenz = Minuend − Subtrahend), der Minuend s (die neue Messlänge) werden kann und der Subtrahend kann das neue r werden (die zu messende Länge); mit anderen Worten kehrt sich der "Sinn" der Subtraktion um.

Die folgende Version kann mit Programmiersprachen aus der C-Familie verwendet werden :

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
     A = abs(A);
     B = abs(B);
     while (B != 0) {
          while (A > B) {
               A = A-B;
          }
          B = B-A;
     }
     return A;
}

Testen der Euclid-Algorithmen

Tut ein Algorithmus, was sein Autor will? Ein paar Testfälle geben normalerweise etwas Vertrauen in die Kernfunktionalität. Aber Tests sind nicht genug. Für Testfälle verwendet eine Quelle 3009 und 884. Knuth schlug 40902, 24140 vor. Ein weiterer interessanter Fall sind die beiden relativ Primzahlen 14157 und 5950.

Aber „Ausnahmefälle“ müssen identifiziert und getestet werden. Wird "Inelegant" richtig funktionieren, wenn R > S, S > R, R = S? Dito für "Elegant": B > A, A > B, A = B? (Ja zu allem). Was passiert, wenn eine Zahl null ist, beide Zahlen null sind? ("Inelegant" wird immer berechnet; "Elegant" wird immer berechnet, wenn A = 0.) Was passiert, wenn negative Zahlen eingegeben werden? Bruchzahlen? Wenn die Eingabezahlen, dh der Definitionsbereich der vom Algorithmus/Programm berechneten Funktion , nur positive ganze Zahlen einschließlich Null enthalten sollen, dann zeigen die Fehler bei Null an, dass der Algorithmus (und das Programm, das ihn instanziiert ) eher eine Teilfunktion ist als eine Gesamtfunktion . Ein bemerkenswerter Ausfall aufgrund von Ausnahmen ist der Raketenausfall von Ariane 5 Flight 501 (4. Juni 1996).

Beweis der Korrektheit des Programms durch mathematische Induktion : Knuth demonstriert die Anwendung der mathematischen Induktion auf eine "erweiterte" Version von Euklids Algorithmus und schlägt "eine allgemeine Methode vor, die anwendbar ist, um die Gültigkeit eines beliebigen Algorithmus zu beweisen". Tausworthe schlägt vor, dass ein Maß für die Komplexität eines Programms die Länge seines Korrektheitsbeweises ist.

Messen und Verbessern der Euklid-Algorithmen

Eleganz (Kompaktheit) gegen Güte (Schnelligkeit) : Mit nur sechs Kernanweisungen ist „Elegant“ der klare Sieger, verglichen mit „Inelegant“ mit dreizehn Anweisungen. "Inelegant" ist jedoch schneller (es erreicht HALT in weniger Schritten). Die Algorithmusanalyse zeigt, warum dies der Fall ist: "Elegant" führt in jeder Subtraktionsschleife zwei bedingte Tests durch, während "Inelegant" nur einen durchführt. Da der Algorithmus (normalerweise) viele Durchschleifungen erfordert, wird im Durchschnitt viel Zeit verschwendet, um ein "B = 0?" Test, der erst benötigt wird, nachdem der Rest berechnet wurde.

Können die Algorithmen verbessert werden? : Sobald der Programmierer ein Programm als „fit“ und „effektiv“ beurteilt – das heißt, es berechnet die von seinem Autor beabsichtigte Funktion – dann stellt sich die Frage, kann es verbessert werden?

Die Kompaktheit von "Inelegant" kann durch den Wegfall von fünf Stufen verbessert werden. Aber Chaitin bewies, dass das Komprimieren eines Algorithmus nicht durch einen verallgemeinerten Algorithmus automatisiert werden kann; vielmehr kann es nur heuristisch durchgeführt werden ; dh durch erschöpfende Suche (Beispiele finden Sie unter Busy Beaver ), Versuch und Irrtum, Klugheit, Einsicht, Anwendung induktiver Argumentation usw. Beachten Sie, dass die Schritte 4, 5 und 6 in den Schritten 11, 12 und 13 wiederholt werden. Vergleich mit „Elegant“ gibt einen Hinweis darauf, dass diese Schritte zusammen mit den Schritten 2 und 3 entfallen können. Dies reduziert die Anzahl der Kernanweisungen von dreizehn auf acht, was es mit neun Schritten "eleganter" als "Elegant" macht.

Die Geschwindigkeit von "Elegant" kann verbessert werden, indem Sie den Schalter "B=0?" Test außerhalb der beiden Subtraktionsschleifen. Diese Änderung erfordert die Hinzufügung von drei Anweisungen (B = 0?, A = 0?, GOTO). "Elegant" berechnet nun die Beispielzahlen schneller; ob dies für gegebene A, B und R, S immer der Fall ist, bedarf einer detaillierten Analyse.

Algorithmische Analyse

Häufig ist es wichtig zu wissen, wie viel von einer bestimmten Ressource (z. B. Zeit oder Speicherplatz) theoretisch für einen bestimmten Algorithmus benötigt wird. Es wurden Methoden zur Analyse von Algorithmen entwickelt , um solche quantitativen Antworten (Schätzungen) zu erhalten; Beispielsweise hätte ein Algorithmus, der die Elemente einer Liste von n Zahlen addiert, eine Zeitanforderung von O(n) , wobei die Notation Big O verwendet wird . Der Algorithmus muss sich immer nur zwei Werte merken: die Summe aller bisherigen Elemente und seine aktuelle Position in der Eingabeliste. Daher wird gesagt, dass es einen Platzbedarf von O(1) hat, wenn der zum Speichern der Eingabezahlen erforderliche Platz nicht gezählt wird, oder O(n) , wenn er gezählt wird.

Unterschiedliche Algorithmen können dieselbe Aufgabe mit einem anderen Satz von Anweisungen in weniger oder mehr Zeit, Platz oder „ Aufwand “ erledigen als andere. Beispielsweise übertrifft ein binärer Suchalgorithmus (mit Kosten O(log n) ) eine sequentielle Suche (Kosten O(n) ), wenn er für Tabellensuchen in sortierten Listen oder Arrays verwendet wird.

Formal versus empirisch

Die Analyse und Untersuchung von Algorithmen ist eine Disziplin der Informatik und wird oft abstrakt ohne die Verwendung einer bestimmten Programmiersprache oder Implementierung praktiziert. In diesem Sinne ähnelt die Algorithmenanalyse anderen mathematischen Disziplinen, da sie sich auf die zugrunde liegenden Eigenschaften des Algorithmus und nicht auf die Besonderheiten einer bestimmten Implementierung konzentriert. Üblicherweise wird zur Analyse Pseudocode verwendet, da dies die einfachste und allgemeinste Darstellung ist. Letztendlich werden die meisten Algorithmen jedoch normalerweise auf bestimmten Hardware-/Softwareplattformen implementiert und ihre algorithmische Effizienz wird schließlich mit echtem Code auf die Probe gestellt. Für die Lösung eines "einmaligen" Problems hat die Effizienz eines bestimmten Algorithmus möglicherweise keine signifikanten Konsequenzen (es sei denn, n ist extrem groß), aber für Algorithmen, die für eine schnelle interaktive, kommerzielle oder langlebige wissenschaftliche Verwendung ausgelegt sind, kann sie kritisch sein. Das Skalieren von kleinen n zu großen n legt häufig ineffiziente Algorithmen offen, die ansonsten harmlos sind.

Empirische Tests sind nützlich, da sie unerwartete Wechselwirkungen aufdecken können, die sich auf die Leistung auswirken. Benchmarks können verwendet werden, um mögliche Verbesserungen eines Algorithmus nach der Programmoptimierung vorher/nachher zu vergleichen. Empirische Tests können jedoch keine formale Analyse ersetzen und sind nicht trivial in fairer Weise durchzuführen.

Ausführungseffizienz

Um die potenziellen Verbesserungen zu veranschaulichen, die selbst bei etablierten Algorithmen möglich sind, kann eine kürzlich durchgeführte bedeutende Innovation in Bezug auf FFT - Algorithmen (die häufig im Bereich der Bildverarbeitung verwendet werden) die Verarbeitungszeit für Anwendungen wie die medizinische Bildgebung um das bis zu 1.000-fache verkürzen. Im Allgemeinen hängen Geschwindigkeitsverbesserungen von speziellen Eigenschaften des Problems ab, die in praktischen Anwendungen sehr häufig vorkommen. Beschleunigungen dieser Größenordnung ermöglichen es Computergeräten, die Bildverarbeitung umfassend nutzen (wie Digitalkameras und medizinische Geräte), weniger Strom zu verbrauchen.

Einstufung

Es gibt verschiedene Möglichkeiten, Algorithmen zu klassifizieren, jede mit ihren eigenen Vorzügen.

Durch Umsetzung

Eine Möglichkeit, Algorithmen zu klassifizieren, ist die Implementierung.

int gcd(int A, int B) {
    if (B == 0)
        return A;
    else if (A > B)
        return gcd(A-B,B);
    else
        return gcd(A,B-A);
}
Rekursive C -Implementierung des Euklid-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 Beendigungsbedingung bekannt) zutrifft, was eine Methode ist, die in der funktionalen Programmierung üblich ist . Iterative Algorithmen verwenden sich wiederholende Konstrukte wie Schleifen und manchmal zusätzliche Datenstrukturen wie Stapel , um die gegebenen Probleme zu lösen. Einige Probleme eignen sich natürlich für die eine oder andere Implementierung. Die Türme von Hanoi sind beispielsweise gut verständlich, wenn eine rekursive Implementierung verwendet wird. Jede rekursive Version hat eine äquivalente (aber möglicherweise mehr oder weniger komplexe) iterative Version und umgekehrt.
Logisch
Ein Algorithmus kann als kontrollierte logische Ableitung angesehen werden . Dieser Begriff kann ausgedrückt werden als: Algorithmus = Logik + Kontrolle . Die Logikkomponente drückt die Axiome aus, die bei der Berechnung verwendet werden können, und die Steuerkomponente bestimmt die Art und Weise, in der die Deduktion auf die Axiome angewendet wird. Dies ist die Grundlage für das logische Programmierparadigma . In rein logischen Programmiersprachen ist die Steuerkomponente festgelegt und Algorithmen werden spezifiziert, indem nur die Logikkomponente bereitgestellt wird. Der Reiz dieses Ansatzes liegt in der eleganten Semantik : Eine Änderung der Axiome erzeugt eine wohldefinierte Änderung des Algorithmus.
Seriell, parallel oder verteilt
Algorithmen werden normalerweise unter der Annahme diskutiert, dass Computer jeweils eine Anweisung eines Algorithmus ausführen. Diese Computer werden manchmal als serielle Computer bezeichnet. Ein für eine solche Umgebung entwickelter Algorithmus wird im Gegensatz zu parallelen Algorithmen oder verteilten Algorithmen als serieller Algorithmus bezeichnet . Parallele Algorithmen nutzen Computerarchitekturen, bei denen mehrere Prozessoren gleichzeitig an einem Problem arbeiten können, während verteilte Algorithmen mehrere Computer verwenden, die mit einem Computernetzwerk verbunden sind . Parallele oder verteilte Algorithmen unterteilen das Problem in symmetrischere oder asymmetrischere Teilprobleme und führen die Ergebnisse wieder zusammen. Der Ressourcenverbrauch in 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 Kommunikationsaufwand ist teuer. Iterative Algorithmen sind im Allgemeinen parallelisierbar. Einige Probleme haben keine parallelen Algorithmen und werden inhärent serielle Probleme genannt.
Deterministisch oder nicht deterministisch
Deterministische Algorithmen lösen das Problem mit exakter Entscheidung in jedem Schritt des Algorithmus, während nicht deterministische Algorithmen Probleme durch Vermuten lösen, obwohl typische Vermutungen durch die Verwendung von Heuristiken genauer gemacht werden .
Genau oder ungefähr
Während viele Algorithmen eine exakte Lösung erreichen, suchen Approximationsalgorithmen eine Annäherung, die näher an der wahren Lösung liegt. Die Annäherung kann erreicht werden, indem entweder eine deterministische oder eine zufällige Strategie verwendet wird. Solche Algorithmen haben praktischen Wert für viele schwierige Probleme. Eines der Beispiele für einen Näherungsalgorithmus ist das Knapsack-Problem , bei dem es eine Menge gegebener Elemente gibt. Sein Ziel ist es, den Rucksack zu packen, um den maximalen Gesamtwert zu erzielen. Jeder Gegenstand hat ein gewisses Gewicht und einen gewissen Wert. Das Gesamtgewicht, das getragen werden kann, ist nicht mehr als eine feste Zahl X. Daher muss die Lösung sowohl das Gewicht der Gegenstände als auch ihren Wert berücksichtigen.
Quantenalgorithmus
Sie laufen auf einem realistischen Modell der Quantenberechnung . Der Begriff wird normalerweise für solche Algorithmen verwendet, die von Natur aus quantenmechanisch erscheinen oder einige wesentliche Merkmale des Quantencomputing wie Quantenüberlagerung oder Quantenverschränkung verwenden .

Nach Designparadigma

Eine andere Art, Algorithmen zu klassifizieren, ist ihre Entwurfsmethodik oder ihr Paradigma . Es gibt eine bestimmte Anzahl von Paradigmen, die sich voneinander unterscheiden. Darüber hinaus enthält jede dieser Kategorien viele verschiedene Arten von Algorithmen. Einige gängige Paradigmen sind:

Brute-Force- oder erschöpfende Suche
Dies ist die naive Methode , jede mögliche Lösung auszuprobieren, um zu sehen, welche die beste ist.
Teile und herrsche
Ein Teile-und-Herrsche-Algorithmus reduziert wiederholt eine Instanz eines Problems auf eine oder mehrere kleinere Instanzen desselben Problems (normalerweise rekursiv ), bis die Instanzen klein genug sind, um sie leicht lösen zu können. Ein solches Beispiel für „Divide and Conquer“ ist das Merge-Sorting . Das Sortieren kann an jedem Datensegment durchgeführt werden, nachdem die Daten in Segmente unterteilt wurden, und das Sortieren ganzer Daten kann in der Eroberungsphase durch Zusammenführen der Segmente erhalten werden. Eine einfachere Variante von Teile und Herrsche wird als Abnahme-und-Herrsche-Algorithmus bezeichnet, der ein identisches Teilproblem löst und die Lösung dieses Teilproblems verwendet, um das größere Problem zu lösen. Divide and Conquer teilt das Problem in mehrere Teilprobleme auf und daher ist die Conquer-Phase komplexer als Algorithmen zum Verringern und Erobern. Ein Beispiel für einen Abnahme- und Eroberungsalgorithmus ist der binäre Suchalgorithmus .
Suche und Aufzählung
Viele Probleme (z. B. Schach spielen ) können als Probleme in Graphen modelliert werden . Ein Graphexplorationsalgorithmus spezifiziert Regeln zum Bewegen um einen Graphen herum und ist für solche Probleme nützlich. Diese Kategorie umfasst auch Suchalgorithmen , Branch-and-Bound - Enumeration und Backtracking .
Randomisierter Algorithmus
Solche Algorithmen treffen einige Entscheidungen zufällig (oder pseudozufällig). Sie können sehr nützlich sein, um ungefähre Lösungen für Probleme zu finden, bei denen das Finden exakter Lösungen unpraktisch sein kann (siehe heuristische Methode unten). Für einige dieser Probleme ist bekannt, dass die schnellsten Näherungen eine gewisse Zufälligkeit beinhalten müssen . Ob randomisierte Algorithmen mit polynomieller Zeitkomplexität die schnellsten Algorithmen für einige Probleme sein können, ist eine offene Frage, die als P-NP-Problem bekannt ist . Es gibt zwei große Klassen solcher Algorithmen:
  1. Monte-Carlo-Algorithmen geben mit hoher Wahrscheinlichkeit eine richtige Antwort zurück. ZB ist RP die Unterklasse von diesen, die in polynomieller Zeit laufen .
  2. Las-Vegas-Algorithmen liefern immer die richtige Antwort, ihre Laufzeit ist aber nur probabilistisch gebunden, zB 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 wir (hoffentlich) asymptotisch optimale Algorithmen haben. Das Ziel ist es, einen reduzierenden Algorithmus zu finden, dessen Komplexität nicht durch die resultierenden reduzierten Algorithmen dominiert wird. Beispielsweise beinhaltet ein Auswahlalgorithmus zum Finden des Medians in einer unsortierten Liste zuerst das Sortieren der Liste (der teure Teil) und dann das Herausziehen des mittleren Elements in der sortierten Liste (der billige Teil). Diese Technik ist auch als Transform and Conquer bekannt .
Zurückverfolgung
Bei diesem Ansatz werden mehrere Lösungen inkrementell erstellt und aufgegeben, wenn festgestellt wird, dass sie nicht zu einer gültigen vollständigen Lösung führen können.

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 fallen:

Lineares Programmieren
Bei der Suche nach optimalen Lösungen für eine lineare Funktion, die an lineare Gleichheits- und Ungleichungsbeschränkungen gebunden ist, können die Beschränkungen des Problems direkt zur Erzeugung der optimalen Lösungen verwendet werden. Es gibt Algorithmen, die jedes Problem in 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, dann wird es in die ganzzahlige Programmierung eingeordnet . Ein linearer Programmieralgorithmus kann ein solches Problem lösen, wenn bewiesen werden kann, dass alle Restriktionen für ganzzahlige Werte oberflächlich sind, dh die Lösungen diese Restriktionen ohnehin erfüllen. Im allgemeinen Fall wird je nach Schwierigkeit des Problems ein spezialisierter Algorithmus oder ein Algorithmus, der Näherungslösungen findet, verwendet.
Dynamische Programmierung
Wenn ein Problem optimale Unterstrukturen aufweist – was bedeutet, dass die optimale Lösung für ein Problem aus optimalen Lösungen für Unterprobleme konstruiert werden kann – und überlappende Unterprobleme aufweist , was bedeutet, dass dieselben Unterprobleme verwendet werden, um viele verschiedene Probleminstanzen zu lösen, vermeidet ein schnellerer Ansatz, der als dynamische Programmierung bezeichnet wird, die Neuberechnung von Lösungen wurden bereits berechnet. Zum Beispiel Floyd-Warshall-Algorithmus , der kürzeste Weg zu einem Ziel von einem Scheitelpunkt in einem gewichteten Diagramm kann gefunden werden, indem der kürzeste Weg zum Ziel von allen benachbarten Scheitelpunkten verwendet wird. Dynamische Programmierung und Speicherung gehören zusammen. Der Hauptunterschied zwischen dynamischer Programmierung und „Teile und Herrsche“ besteht darin, dass Teilprobleme bei „Teile und Herrsche“ mehr oder weniger unabhängig voneinander sind, während sich Teilprobleme bei dynamischer Programmierung überschneiden. Der Unterschied zwischen dynamischer Programmierung und einfacher Rekursion liegt in der Zwischenspeicherung oder Speicherung rekursiver Aufrufe. Wenn Teilprobleme unabhängig sind und es keine Wiederholung gibt, hilft das Auswendiglernen nicht; daher ist die dynamische Programmierung keine Lösung für alle komplexen Probleme. Durch die Verwendung von Memoisation 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 dynamischen Programmieralgorithmus darin, dass er Unterstrukturen untersucht, in diesem Fall nicht das Problem, sondern eine gegebene Lösung. Solche Algorithmen beginnen mit einer Lösung, die gegeben sein kann oder auf irgendeine Weise konstruiert wurde, und verbessern sie, indem sie kleine Modifikationen vornehmen. Bei manchen Problemen finden sie die optimale Lösung, bei anderen bleiben sie bei lokalen Optima stehen, also bei Lösungen, die durch den Algorithmus nicht verbessert werden können, aber nicht optimal sind. Die beliebteste Verwendung von Greedy-Algorithmen ist das Finden des minimalen Spannbaums, bei dem das Finden der optimalen Lösung mit dieser Methode möglich ist. Huffman Tree , Kruskal , Prim , Sollin sind gierige Algorithmen, die dieses Optimierungsproblem lösen können.
Die heuristische Methode
Bei Optimierungsproblemen können heuristische Algorithmen verwendet werden, um eine Lösung nahe der optimalen Lösung zu finden, wenn das Finden der optimalen Lösung unpraktisch ist. Diese Algorithmen funktionieren, indem sie der optimalen Lösung im Laufe ihres Fortschritts immer näher kommen. Im Prinzip finden sie bei unendlich langer Laufzeit die optimale Lösung. Ihr Verdienst ist, dass sie in relativ kurzer Zeit eine Lösung finden können, die der optimalen Lösung sehr nahe kommt. Solche Algorithmen beinhalten lokale Suche , Tabu-Suche , Simulated Annealing und genetische Algorithmen . Einige von ihnen, wie Simulated Annealing, sind nicht deterministische Algorithmen, während andere, wie Tabu-Suche, deterministisch sind. Wenn eine Fehlergrenze der nicht optimalen Lösung bekannt ist, wird der Algorithmus weiter als Approximationsalgorithmus kategorisiert .

Nach Studienrichtung

Jedes Wissenschaftsgebiet hat seine eigenen Probleme und braucht effiziente Algorithmen. Verwandte Probleme in einem Bereich werden oft gemeinsam untersucht. Einige beispielhafte Klassen sind Suchalgorithmen , Sortieralgorithmen , Zusammenführungsalgorithmen , numerische Algorithmen , Graphenalgorithmen , Zeichenfolgenalgorithmen , rechnerische geometrische Algorithmen , kombinatorische Algorithmen , medizinische Algorithmen , maschinelles Lernen , Kryptografie , Datenkomprimierungsalgorithmen und Parsing - Techniken .

Felder neigen dazu, einander zu überlappen, und Algorithmusfortschritte in einem Feld können die anderer, manchmal völlig unabhängiger Felder verbessern. Beispielsweise wurde die dynamische Programmierung zur Optimierung des Ressourcenverbrauchs in der Industrie erfunden, wird aber heute zur Lösung einer Vielzahl von Problemen in vielen Bereichen eingesetzt.

Nach Komplexität

Algorithmen können nach der Zeit, die sie für die Ausführung benötigen, im Vergleich zu ihrer Eingabegröße klassifiziert werden:

  • Konstante Zeit: wenn die vom Algorithmus benötigte Zeit unabhängig von der Eingabegröße gleich ist. ZB ein Zugriff auf ein Array - Element.
  • Logarithmische Zeit: wenn die Zeit eine logarithmische Funktion der Eingabegröße ist. ZB binärer Suchalgorithmus .
  • Lineare Zeit: wenn die Zeit proportional zur Eingabegröße ist. ZB das Durchlaufen einer Liste.
  • Polynomzeit: wenn die Zeit eine Potenz der Eingabegröße ist. Beispielsweise hat der Bubble-Sort- Algorithmus eine quadratische Zeitkomplexität.
  • Exponentialzeit: wenn die Zeit eine Exponentialfunktion der Eingabegröße ist. ZB Brute-Force-Suche .

Einige Probleme können mehrere Algorithmen unterschiedlicher Komplexität haben, während andere Probleme möglicherweise keine Algorithmen oder keine bekannten effizienten Algorithmen haben. Es gibt auch Zuordnungen von einigen Problemen zu anderen Problemen. Aus diesem Grund hat es sich als geeigneter herausgestellt, die Probleme selbst anstelle der Algorithmen anhand der Komplexität der für sie bestmöglichen Algorithmen in Äquivalenzklassen einzuteilen.

Kontinuierliche Algorithmen

Das Adjektiv „kontinuierlich“, wenn es auf das Wort „Algorithmus“ angewendet wird, kann Folgendes bedeuten:

Rechtsfragen

Algorithmen an sich sind in der Regel nicht patentierbar. In den Vereinigten Staaten stellt ein Anspruch, der ausschließlich aus einfachen Manipulationen abstrakter Konzepte, Zahlen oder Signale besteht, keine „Prozesse“ dar (USPTO 2006), und daher sind Algorithmen nicht patentierbar (wie in Gottschalk v. Benson ). Praktische Anwendungen von Algorithmen sind jedoch manchmal patentierbar. Beispielsweise wurde im Fall Diamond v. Diehr die Anwendung eines einfachen Rückkopplungsalgorithmus zur Unterstützung der Aushärtung von synthetischem Kautschuk als patentierbar erachtet. Die Patentierung von Software ist sehr umstritten, und es gibt stark kritisierte Patente, die Algorithmen betreffen, insbesondere Datenkomprimierungsalgorithmen , wie das LZW-Patent von Unisys .

Außerdem haben einige kryptografische Algorithmen Exportbeschränkungen (siehe Export von Kryptografie ).

Geschichte: Entwicklung des Begriffs „Algorithmus“

Alter Orient

Die frühesten Beweise für Algorithmen finden sich in der babylonischen Mathematik des alten Mesopotamien (moderner Irak). Eine sumerische Tontafel, die in Shuruppak in der Nähe von Bagdad gefunden und auf etwa 2500 v. Chr. datiert wurde, beschrieb den frühesten Teilungsalgorithmus . Während der Hammurabi-Dynastie um 1800-1600 v. Chr. wurden auf babylonischen Tontafeln Algorithmen zur Berechnung von Formeln beschrieben . Algorithmen wurden auch in der babylonischen Astronomie verwendet . Babylonische Tontafeln beschreiben und verwenden algorithmische Verfahren, um Zeit und Ort bedeutender astronomischer Ereignisse zu berechnen.

Algorithmen für die Arithmetik finden sich auch in der altägyptischen Mathematik , die auf den Rhind Mathematical Papyrus um 1550 v. Chr. zurückgeht. Algorithmen wurden später in der antiken hellenistischen Mathematik verwendet . Zwei Beispiele sind das Sieb des Eratosthenes , das in der Einführung in die Arithmetik von Nicomachus beschrieben wurde, und der euklidische Algorithmus , der erstmals in Euklids Elementen ( ca.  300 v . Chr .) beschrieben wurde.

Diskrete und unterscheidbare Symbole

Zählzeichen: Um ihre Herden, ihre Getreidesäcke und ihr Geld im Auge zu behalten, benutzten die Alten das Zählen: Sie sammelten Steine ​​oder Markierungen, die auf Stöcke geritzt wurden, oder machten diskrete Symbole in Ton. Durch die babylonische und ägyptische Verwendung von Zeichen und Symbolen entwickelten sich schließlich römische Ziffern und der Abakus (Dilson, S. 16–41). Zählstriche erscheinen prominent in der Arithmetik von einstelligen Zahlensystemen, die in Berechnungen mit Turing-Maschinen und Post-Turing-Maschinen verwendet werden.

Manipulation von Symbolen als "Platzhalter" für Zahlen: Algebra

Muhammad ibn Mūsā al-Khwārizmī , ein persischer Mathematiker , schrieb den Al-jabr im 9. Jahrhundert. Die Begriffe „ Algorismus “ und „Algorithmus“ leiten sich vom Namen al-Khwārizmī ab, während der Begriff „ Algebra “ aus dem Buch Al-jabr stammt . In Europa wurde das Wort "Algorithmus" ursprünglich verwendet, um sich auf die Sätze von Regeln und Techniken zu beziehen, die von Al-Khwarizmi zum Lösen algebraischer Gleichungen verwendet wurden, bevor es später verallgemeinert wurde, um sich auf einen Satz von Regeln oder Techniken zu beziehen. Dies gipfelte schließlich in Leibniz 'Begriff des calculus ratiocinator ( ca.  1680 ):

Gut anderthalb Jahrhunderte seiner Zeit voraus schlug Leibniz eine Algebra der Logik vor, eine Algebra, die die Regeln für die Manipulation logischer Konzepte in der Weise spezifizieren würde, wie die gewöhnliche Algebra die Regeln für die Manipulation von Zahlen spezifiziert.

Kryptographische Algorithmen

Der erste kryptografische Algorithmus zum Entschlüsseln verschlüsselter Codes wurde von Al-Kindi , einem arabischen Mathematiker des 9. Jahrhunderts , in A Manuscript On Deciphering Cryptographic Messages entwickelt . Er gab die erste Beschreibung der Kryptoanalyse durch Frequenzanalyse , dem frühesten Codebreaking - Algorithmus.

Mechanische Vorrichtungen mit diskreten Zuständen

Die Uhr : Bolter schreibt die Erfindung der gewichtsgetriebenen Uhr als „die Schlüsselerfindung [Europas im Mittelalter]“ zu, insbesondere die Randhemmung , die uns das Ticken und Tack einer mechanischen Uhr liefert. „Die genaue automatische Maschine“ führte ab dem 13. Jahrhundert sofort zu „mechanischen Automaten “ und schließlich zu „Rechenmaschinen“ – der Differenzmaschine und den analytischen Maschinen von Charles Babbage und Gräfin Ada Lovelace , Mitte des 19. Jahrhunderts. Lovelace wird die erste Entwicklung eines Algorithmus zugeschrieben, der für die Verarbeitung auf einem Computer bestimmt ist – Babbages Analyse-Engine, das erste Gerät, das als echter Turing-kompletter Computer statt nur als Taschenrechner angesehen wird – und wird daher manchmal als „erster Programmierer der Geschichte“ bezeichnet. obwohl eine vollständige Implementierung von Babbages zweitem Gerät erst Jahrzehnte nach ihrem Leben realisiert werden würde.

Logische Maschinen 1870 – Stanley Jevons „logischer Abakus“ und „logische Maschine“ : Das technische Problem bestand darin, Boolesche Gleichungen zu reduzieren , wenn sie in einer Form präsentiert wurden, die den heutigen Karnaugh-Karten ähnelt . Jevons (1880) beschreibt zuerst einen einfachen "Abakus" aus "mit Stiften versehenen Holzstreifen, die so konstruiert sind, dass jeder Teil oder jede Klasse der [logischen] Kombinationen mechanisch herausgegriffen werden kann ... In jüngerer Zeit habe ich die jedoch reduziert System in eine vollständig mechanische Form gebracht und somit den gesamten indirekten Folgerungsprozess in etwas verkörpert, das man eine logische Maschine nennen könnte ein Klavier [etc.] ...". Mit dieser Maschine konnte er einen „ Syllogismus oder irgendein anderes einfaches logisches Argument“ analysieren.

Diese Maschine stellte er 1870 vor den Fellows der Royal Society aus. Ein anderer Logiker , John Venn , richtete jedoch in seinem Buch Symbolic Logic von 1881 einen voreingenommenen Blick auf diese Bemühungen: „Ich selbst schätze das Interesse oder die Bedeutung dessen, was manchmal als logische Maschinen bezeichnet wird, nicht hoch ein … so scheint es mir nicht alle derzeit bekannten oder wahrscheinlich zu entdeckenden Vorrichtungen verdienen wirklich den Namen logischer Maschinen“; siehe mehr unter Algorithmuscharakterisierungen . Aber um nicht übertroffen zu werden, präsentierte auch er "einen Plan, der, wie ich befürchte, etwas analog zu Prof. Jevons Abakus ist ... [Und] [a] Gain, entsprechend der logischen Maschine von Prof. Jevon , kann die folgende Erfindung beschrieben werden. Ich bevorzuge es um es lediglich eine logische Diagrammmaschine zu nennen ... aber ich nehme an, dass es sehr gut alles tun könnte, was rational von einer logischen Maschine erwartet werden kann.

Jacquard-Webstuhl, Hollerith-Lochkarten, Telegraphie und Telefonie – das elektromechanische Relais : Bell und Newell (1971) weisen darauf hin, dass der Jacquard-Webstuhl (1801), Vorläufer der Hollerith-Karten (Lochkarten, 1887), und „Telefonvermittlungstechnologien“ die Wurzeln waren eines Baumes, der zur Entwicklung der ersten Computer führte. Mitte des 19. Jahrhunderts war der Telegraf , der Vorläufer des Telefons, weltweit im Einsatz, seine diskrete und unterscheidbare Codierung von Buchstaben als "Punkte und Striche" ein allgemeiner Ton. Bis zum Ende des 19. Jahrhunderts wurde das Tickerband ( um  1870 ) verwendet, ebenso wie die Verwendung von Hollerith-Karten bei der US-Volkszählung von 1890. Dann kam der Fernschreiber ( um  1910 ) mit seiner Verwendung von Baudot-Code auf Lochstreifen .

Telefonvermittlungsnetzwerke aus elektromechanischen Relais (erfunden 1835) standen hinter der Arbeit von George Stibitz (1937), dem Erfinder des digitalen Addiergeräts. Als er in den Bell Laboratories arbeitete, beobachtete er die „mühsame“ Verwendung mechanischer Taschenrechner mit Zahnrädern. „Eines Abends im Jahr 1937 ging er nach Hause, um seine Idee zu testen … Als das Basteln beendet war, hatte Stibitz ein binäres Addiergerät konstruiert.“ .

Der Mathematiker Martin Davis bemerkt die besondere Bedeutung des elektromechanischen Relais (mit seinen zwei "binären Zuständen" offen und geschlossen ):

Erst mit der Entwicklung von elektromechanischen Rechnern mit elektrischen Relais ab den 1930er Jahren wurden Maschinen mit dem Umfang gebaut, den Babbage sich vorgestellt hatte.

Mathematik im 19. Jahrhundert bis Mitte des 20. Jahrhunderts

Symbole und Regeln : In rascher Folge reduzierte die Mathematik von George Boole (1847, 1854), Gottlob Frege (1879) und Giuseppe Peano (1888–1889) die Arithmetik auf eine Folge von Symbolen, die durch Regeln manipuliert wurden. Peanos Die Prinzipien der Arithmetik, vorgestellt durch eine neue Methode (1888) war „der erste Versuch einer Axiomatisierung der Mathematik in einer symbolischen Sprache “.

Aber Heijenoort gibt Frege (1879) dieses Lob: Freges ist „vielleicht das wichtigste Einzelwerk, das jemals in Logik geschrieben wurde , "für reines Denken", das heißt, frei von rhetorischen Verzierungen ... konstruiert aus bestimmten Symbolen, die nach bestimmten Regeln manipuliert werden". Die Arbeit von Frege wurde von Alfred North Whitehead und Bertrand Russell in ihren Principia Mathematica weiter vereinfacht und erweitert (1910–1913).

Die Paradoxe : Zur gleichen Zeit tauchten in der Literatur eine Reihe beunruhigender Paradoxe auf, 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 Aufsatz (1931) – er zitiert ausdrücklich das Paradoxon des Lügners –, der 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 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 war ). In rascher Folge erschienen: Alonzo Church , Stephen Kleene und JB Rossers λ - Kalkül, eine fein geschliffene Definition der „allgemeinen Rekursion“ aus der Arbeit von Gödel, die auf Anregungen von Jacques Herbrand (vgl. Gödels Princeton-Vorlesungen von 1934) zurückgreift nachträgliche Vereinfachungen von Kleene. Churchs Beweis, dass das Entscheidungsproblem unlösbar war, Emil Posts Definition effektiver Berechenbarkeit als Arbeiter, der gedankenlos einer Liste von Anweisungen folgt, sich nach links oder rechts durch eine Abfolge von Räumen bewegt und dabei entweder ein Papier markiert oder löscht oder das Papier beobachtet und macht eine Ja-Nein-Entscheidung über die nächste Anweisung. Alan Turings Beweis, dass das Entscheidungsproblem mit Hilfe seiner „a-[automatic-] machine“ unlösbar war – praktisch identisch mit Posts „Formulierung“, J. Barkley Rossers Definition von „effektiver Methode“ im Sinne von „a Maschine". Kleenes Vorschlag eines Vorläufers der „ Kirchenthese “, die er „These I“ nannte, und einige Jahre später Kleenes Umbenennung seiner These in „Kirchenthese“ und der Vorschlag von „Turings These“.

Emil Post (1936) und Alan Turing (1936–37, 1939)

Emil Post (1936) beschrieb die Handlungen eines "Computers" (Mensch) wie folgt:

„...es handelt sich um zwei Begriffe: den eines Symbolraums, in dem die Arbeit vom Problem zur Antwort durchgeführt werden soll, und einen festen, unveränderlichen Satz von Richtungen .

Sein Symbolraum wäre

„eine endlose Zwei-Wege-Folge von Räumen oder Kästchen … Der Problemlöser oder Arbeiter muss sich in diesem Symbolraum bewegen und darin arbeiten, in der Lage sein, sich in nur einem Kästchen gleichzeitig aufzuhalten und darin zu arbeiten … ein Kästchen besteht darin, nur zwei mögliche Bedingungen zuzulassen, dh leer oder unmarkiert zu sein und eine einzige Markierung darin zu haben, sagen wir einen vertikalen Strich.
„Ein Kästchen soll herausgegriffen und als Ausgangspunkt bezeichnet werden. … soll ein konkretes Problem symbolisch angegeben werden, indem endlich viele Kästchen [also INPUT] mit einem Strich markiert werden. Ebenso soll die Antwort [also , OUTPUT] soll in symbolischer Form durch eine solche Anordnung markierter Kästchen gegeben werden...
„Ein Satz von Anweisungen, die auf ein allgemeines Problem anwendbar sind, setzt einen deterministischen Prozess in Gang, wenn er auf jedes spezifische Problem angewendet wird. Dieser Prozess endet nur, wenn es um die Richtung des Typs (C) [dh STOP] geht.“ Weitere Informationen finden Sie unter Post-Turing-Maschine
Alan Turings Statue im Bletchley Park

Alan Turings Werk ging dem von Stibitz (1937) voraus; Es ist nicht bekannt, ob Stibitz von Turings Werk wusste. Turings Biograf glaubte, dass Turings Verwendung eines schreibmaschinenähnlichen Modells von einem jugendlichen Interesse herrührte: „Alan hatte als Junge davon geträumt, Schreibmaschinen zu erfinden; Mrs. Turing hatte eine Schreibmaschine, und er hätte gut damit beginnen können, sich zu fragen, was mit anrufen gemeint war eine 'mechanische ' Schreibmaschine ". Angesichts der damaligen Verbreitung von Morsezeichen, Telegrafie, Laufbandmaschinen und Fernschreibern ist es durchaus möglich, dass sie alle Turing in seiner Jugend beeinflusst haben.

Turing – sein Berechnungsmodell wird jetzt als Turing-Maschine bezeichnet – beginnt, wie Post, mit einer Analyse eines menschlichen Computers, die er auf einen einfachen Satz grundlegender Bewegungen und „Geisteszustände“ reduziert. Aber er geht noch einen Schritt weiter und erschafft eine Maschine als Rechenmodell für Zahlen.

„Berechnungen werden normalerweise durchgeführt, indem bestimmte Symbole auf Papier geschrieben werden. Wir können annehmen, dass dieses Papier in Quadrate unterteilt ist wie ein Rechenbuch eines Kindes … Ich nehme dann an, dass die Berechnung auf eindimensionalem Papier ausgeführt wird, dh auf einem geteilten Band in Quadrate. Ich nehme auch an, dass die Anzahl der Symbole, die gedruckt werden können, endlich ist ...
„Das Verhalten des Computers in jedem Moment wird durch die Symbole bestimmt, die er beobachtet, und durch seinen „Geisteszustand“ in diesem Moment. Wir können annehmen, dass es eine Grenze B für die Anzahl der Symbole oder Quadrate gibt, die der Computer verarbeiten kann in einem Moment beobachten. Wenn er mehr beobachten möchte, muss er aufeinanderfolgende Beobachtungen verwenden. Wir werden auch annehmen, dass die Anzahl der zu berücksichtigenden Geisteszustände 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, sie sich weiter zu unterteilen vorzustellen."

Turings Reduktion liefert folgendes:

„Die einfachen Operationen müssen daher umfassen:
"(a) Änderungen des Symbols auf einem der beobachteten Quadrate
„(b) Änderungen eines der beobachteten Quadrate zu einem anderen Quadrat innerhalb von L Quadraten eines der zuvor beobachteten Quadrate.

„Es kann sein, dass einige dieser Änderungen notwendigerweise eine Änderung der Einstellung 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 Geisteszustands.
"(B) Eine mögliche Änderung (b) der beobachteten Quadrate zusammen mit einer möglichen Änderung des Geisteszustands"
"Wir können jetzt eine Maschine bauen, die die Arbeit dieses Computers erledigt."

Einige Jahre später erweiterte Turing seine Analyse (These, Definition) um diesen eindringlichen Ausdruck:

"Eine Funktion wird als "effektiv berechenbar" bezeichnet, wenn ihre Werte durch einen rein mechanischen Prozess gefunden werden können. Obwohl es ziemlich einfach ist, ein intuitives Verständnis dieser Idee zu erlangen, ist es dennoch wünschenswert, eine eindeutigere, mathematisch ausdrückbare Definition zu haben ... [er diskutiert die Geschichte der Definition ziemlich genau wie oben dargestellt in Bezug auf Gödel, Herbrand, Kleene, Church, Turing und Post] ... 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 zur Definition einer berechenbaren Funktion durch den Autor und zu deren Identifizierung Berechenbarkeit † mit effektiver Berechenbarkeit...
„† Wir werden den Ausdruck „berechenbare Funktion“ verwenden, um eine von einer Maschine berechenbare Funktion zu bezeichnen, und „effektiv berechenbar“ beziehen wir uns auf die intuitive Idee ohne besondere Identifikation mit irgendeiner dieser Definitionen.“

JB Rosser (1939) und SC Kleene (1943)

J. Barkley Rosser definierte eine "effektive [mathematische] Methode" folgendermaßen (Kursivschrift hinzugefügt):

‚Wirksame Methode‘ wird hier in dem ziemlich speziellen Sinn einer Methode verwendet, bei der jeder Schritt genau bestimmt ist und die mit Sicherheit die Antwort in einer endlichen Anzahl von Schritten hervorbringen wird. Mit dieser besonderen Bedeutung wurden drei verschiedene genaue Definitionen gegeben [seine Fußnote Nr. 5; siehe Diskussion unmittelbar unten] Die am einfachsten zu formulierende (aufgrund von Post und Turing) besagt im Wesentlichen, dass eine effektive Methode zur Lösung bestimmter Probleme existiert, wenn man eine Maschine bauen kann, die es dann tut Lösen Sie jedes Problem des Satzes ohne menschliches Eingreifen, außer die Frage einzufügen und (später) die Antwort zu lesen . Alle drei Definitionen sind gleichwertig, daher spielt es keine Rolle, welche verwendet wird. Außerdem ist die Tatsache, dass alle drei gleichwertig sind, a sehr starkes Argument für die Richtigkeit von irgendjemandem." (Rosser 1939: 225–226)

Rossers Fußnote Nr. 5 verweist auf die Arbeit von (1) Church und Kleene und ihre Definition der λ-Definabilität, insbesondere auf Churchs Verwendung davon in seinem Werk An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand und Gödel und ihre Verwendung von Rekursion, insbesondere Gödels Verwendung in seiner berühmten Arbeit On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931); und (3) Post (1936) und Turing (1936–37) in ihren Mechanismus-Modellen der Berechnung.

Stephen C. Kleene definierte seine inzwischen berühmte „These I“, die als Church-Turing-These bekannt ist . Aber er tat dies in folgendem Zusammenhang (im Original fett gedruckt):

"12. Algorithmische Theorien ... Beim Aufstellen einer vollständigen algorithmischen Theorie beschreiben wir ein Verfahren, das für jeden Satz von Werten der unabhängigen Variablen durchführbar ist und das zwangsläufig endet, und zwar so, dass wir es aus dem Ergebnis heraus können Lesen Sie eine eindeutige Antwort, „ja“ oder „nein“, auf die Frage „ist der Prädikatswert wahr?““ (Kleene 1943:273)

Geschichte nach 1950

Eine Reihe von Bemühungen wurde auf eine weitere Verfeinerung der Definition von "Algorithmus" gerichtet, und es werden Aktivitäten fortgesetzt, insbesondere wegen Fragen im Zusammenhang mit Grundlagen der Mathematik (insbesondere der Church-Turing-These ) und der Philosophie des Geistes (insbesondere Argumente über künstliche Intelligenz ). Weitere Informationen finden Sie unter Charakterisierungen von Algorithmen .

Siehe auch

Anmerkungen

Literaturverzeichnis

Weiterlesen

Externe Links

Algorithmus-Repositories