Algorithmus

Flussdiagramm eines Algorithmus (Euclids Algorithmus) zur Berechnung des größten gemeinsamen Divisors (G.C.D.) von zwei Zahlen a und b an Orten mit dem Namen A und B. Der Algorithmus fährt in zwei Schleifen fort: Wenn der Test B ≥ A "Ja" oder "wahr" ergibt (genauer gesagt, die Nummer b in Ort b ist größer als oder gleich dem Nummer a In Ort a) gibt der Algorithmus B ← B - A an (was bedeutet die Zahl b − a ersetzt das alte b). In ähnlicher Weise, wenn a> b, dann ← A - B. Der Prozess endet, wenn (der Inhalt von) b 0 ist und die G.C.D. in A. (Algorithmus abgeleitet von Scott 2009: 13; Symbole und Zeichenstil aus Tausworth 1977).

Ada LovelaceDas Diagramm von "Note G", dem ersten veröffentlichten Computeralgorithmus,

Im Mathematik und Informatik, ein Algorithmus (/ˈælɡərɪðəm/ (Hören)) ist eine endliche Folge von streng Anweisungen, die typischerweise verwendet werden, um eine Klasse von spezifisch zu lösen Probleme oder um eine auszuführen Berechnung.^[1] Algorithmen werden als Spezifikationen für die Durchführung verwendet Berechnungen und Datenverarbeitung. Durch Gebrauch von künstliche IntelligenzAlgorithmen können automatisierte Abzüge durchführen (bezeichnet als als automatisierte Argumentation) und verwenden Sie mathematische und logische Tests, um die Codeausführung über verschiedene Routen abzulenken (bezeichnet als als automatisierte Entscheidungsfindung). Die Verwendung menschlicher Eigenschaften als Deskriptoren von Maschinen auf metaphorische Weise wurde bereits von praktiziert Alan Turing mit Begriffen wie "Speicher", "Suche" und "Stimulus".^[2]

Dagegen a Heuristik ist ein Ansatz zur Problemlösung, der möglicherweise nicht vollständig angegeben ist oder nicht korrekte oder optimale Ergebnisse garantiert, insbesondere in Problembereichen, in denen kein gut definiertes korrektes oder optimales Ergebnis vorliegt.^[3]

Als an Effektive Methode, ein Algorithmus kann innerhalb einer begrenzten Menge an Raum und Zeit ausgedrückt werden.^[4] und in einer gut definierten formalen Sprache^[5] zur Berechnung a Funktion.^[6] Ausgehend von einem Anfangszustand und anfänglichen Eingaben (vielleicht leer),^[7] Die Anweisungen beschreiben a Berechnung das, wann hingerichtet, fährt durch eine endliche^[8] Anzahl der gut definierten aufeinanderfolgenden Zustände, die schließlich "Output" erzeugen^[9] und in einem endgültigen Endzustand enden. Der Übergang von einem Zustand zum nächsten ist nicht unbedingt deterministisch; Einige Algorithmen, bekannt als Randomisierte Algorithmen, integrieren Sie zufällige Eingabe.^[10]

Geschichte

Das Konzept des Algorithmus existiert seit der Antike. Arithmetik Algorithmen wie a Divisionalgorithmus, wurden von der Antike verwendet Babylonische Mathematiker c. 2500 v. Chr. Und Ägyptische Mathematiker c. 1550 v. Chr.^[11] Griechische Mathematiker später verwendete Algorithmen in 240 v. Chr. In der Sieb von Eratosthenes für die Suche nach Primzahlen und die Euklidischer Algorithmus für das Finden der größter gemeinsamer Teiler von zwei Zahlen.^[12] Arabische Mathematiker wie zum Beispiel al-kindi im 9. Jahrhundert verwendet kryptografisch Algorithmen für Code knacken, bezogen auf Frequenzanalyse.^[13]

Das Wort Algorithmus leitet sich aus dem Namen des persischen Mathematikers des 9. Jahrhunderts ab Muḥammad ibn mūsā al-khwārizmī, Deren Nisba (Ihn wie aus Khwarazm) wurde latinisiert als Algoritmi (Arabized persisch الخوارزمی c. 780–850).^[14][15] Muḥammad ibn mūsā al-khwārizmī war ein Mathematiker, Astronom, Geographund Gelehrter in der Haus der Weisheit in Bagdad, dessen Name bedeutet "der Eingeborene von Khwarazm', eine Region, die Teil davon war Großer Iran und ist jetzt in Usbekistan.^[16][17] Um 825 schrieb al-Khwarizmi eine arabische Sprache Abhandlung über die Hindu -arabisches Ziffernungssystem, was übersetzt wurde Latein Im 12. Jahrhundert. Das Manuskript beginnt mit dem Ausdruck Dixit Algorizmi ('So sprach al-khwarizmi'), wo "Algorizmi" der Übersetzer war Latinisierung von al-khwarizmis Namen.^[18] Al-Khwarizmi war im späten Mittelalter der am häufigsten gelesene Mathematiker in Europa, vor allem durch ein anderes seiner Bücher, die Algebra.^[19] Im spätmittelalterlichen lateinischen, Algorismus, Englisch 'Algorismus', Die Korruption seines Namens bedeutete einfach das "Dezimalzahlsystem".^[20] Im 15. Jahrhundert unter dem Einfluss des griechischen Wortes ἀριθμatter (Arithmos), 'Nummer' (vgl. "Arithmetik"), das lateinische Wort wurde verändert Algorithmusund der entsprechende englische Begriff "Algorithmus" wird erstmals im 17. Jahrhundert bestätigt; Der moderne Sinn wurde im 19. Jahrhundert eingeführt.^[21]

Indische Mathematik war überwiegend algorithmisch. Algorithmen, die für die indische mathematische Tradition repräsentativ sind Śulbasūtrās zu den mittelalterlichen Texten der Kerala School.^[22]

Auf Englisch das Wort Algorithmus wurde zuerst um 1230 und dann von verwendet Chaucer 1391 übernahm Englisch den französischen Begriff, aber erst im späten 19. Jahrhundert übernahm "Algorithmus" die Bedeutung, die es im modernen Englisch hat.^[23]

Eine weitere frühzeitige Verwendung des Wortes ist 1240 in einem Handbuch mit dem Titel " Carmen de Algorismo zusammengestellt von Alexandre de Villedieu. Es beginnt mit:

Haec algorismus ars praesens dicitur, in qua / talibus indorum fruimur bis quinque figuris.

was übersetzt:

Algorismus ist die Kunst, durch die wir derzeit diese indischen Figuren verwenden, die zweimal fünf.

Das Gedicht ist ein paar hundert Zeilen lang und fasst die Kunst der Berechnung mit den neuen indischen Würfel zusammen (Tali Indorum) oder hinduistische Ziffern.^[24]

Eine teilweise Formalisierung des modernen Algorithmus -Konzepts begann mit Versuchen, die zu lösen Entscheidungsproblem (Entscheidungsproblem) von David Hilbert Im Jahr 1928 wurden spätere Formalisierungen als Versuche zu definieren "eingestuft"Wirksame Berechnbarkeit"^[25] oder "effektive Methode".^[26] Diese Formalisierungen beinhalteten die Gödel–Herbrand–Kleene rekursive Funktionen von 1930, 1934 und 1935,, Alonzo -Kirche's Lambda -Kalkül von 1936, Emil Post's Formulierung 1 von 1936 und Alan Turing's Turing -Maschinen von 1936–37 und 1939.

Informelle Definition

Eine informelle Definition könnte "eine Reihe von Regeln sein, die genau eine Abfolge von Operationen definieren",^{[27][benötigen Zitat, um dies zu überprüfen]} Dies umfasst alle Computerprogramme (einschließlich Programme, die keine numerischen Berechnungen durchführen) und (zum Beispiel) alle vorgeschriebenen bürokratisch Verfahren^[28] oder Kochbuch Rezept.^[29]

Im Allgemeinen ist ein Programm nur ein Algorithmus, wenn es irgendwann aufhört^[30]-wenngleich Unendliche Schleifen kann sich manchmal als wünschenswert erweisen.

Ein prototypisches Beispiel eines Algorithmus ist das Euklidischer Algorithmus, mit der verwendet wird, um den maximalen gemeinsamen Teiler von zwei Ganzzahlen zu bestimmen; Ein Beispiel (es gibt andere) wird von der beschrieben Flussdiagramm oben und als Beispiel in einem späteren Abschnitt.

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

Kein Mensch kann schnell genug oder lang genug schreiben oder klein genug † († "kleiner und kleiner ohne Grenzen ... Sie würden versuchen, auf Moleküle, auf Atomen, auf Elektronen") zu schreiben, um alle Mitglieder von einem aufzulisten In einer Notation auffließend unendlich eingestellt, indem ihre Namen nacheinander ausgeschrieben werden. Aber Menschen können etwas gleich Nützliches tun, wenn bestimmte auffließend unendliche Sätze sind: Sie können geben explizite Anweisungen zur Bestimmung der nTH Mitglied des Setsfür willkürliche endliche n. Solche Anweisungen sollen in einer Form, in der Sie könnten von einer Computermaschine folgen, oder von a Mensch, der in der Lage ist, nur sehr elementare Operationen für Symbole durchzuführen.^[31]

Ein "Aufzählbar unendlich eingestuft" ist einer, dessen Elemente mit den Ganzzahlen in eins zu eins Korrespondenz gebracht werden können. So sagen Boolos und Jeffrey, dass ein Algorithmus Anweisungen für einen Prozess impliziert willkürlich "Input" Integer oder Ganzzahlen, die theoretisch willkürlich groß sein können. Zum Beispiel kann ein Algorithmus eine algebraische Gleichung sein, wie z. y = m + n (d. H. Zwei willkürliche "Eingangsvariablen" m und n das erzeugt einen Ausgang y), aber die Versuche verschiedener Autoren, den Begriff zu definieren, zeigen, dass das Wort viel mehr als dieses impliziert, etwas in der Reihenfolge (für das Additionsbeispiel):

Präzise Anweisungen (in einer Sprache, die "dem Computer" verstanden wird)^[32] für eine schnelle, effiziente, "gut"^[33] Prozess, der die "Bewegungen" des "Computers" spezifiziert (Maschine oder Mensch, ausgestattet mit den notwendigen intern enthaltenen Informationen und Funktionen)^[34] um beliebige Eingänge/Symbole zu finden, zu dekodieren und dann beliebige Eingänge zu verarbeiten m und n, Symbole + und = ... und "effektiv"^[35] in einer "vernünftigen" Zeit produzieren,^[36] Ausgangsintenzer y an einem bestimmten Ort und in einem bestimmten Format.

Das Konzept von Algorithmus wird auch verwendet, um den Begriff von zu definieren Dekidabilität- Eine Vorstellung, die zentral ist, wie er erklärt, wie formelle Systeme von einem kleinen Satz von ausgehen Axiome und Regeln. Im Logik, Die Zeit, die ein Algorithmus zum Fertigstellen erfordert, kann nicht gemessen werden, da er offenbar nicht mit der üblichen physikalischen Dimension zusammenhängt. Aus solchen Unsicherheiten, die die laufende Arbeit charakterisieren, ist die Nichtverfügbarkeit einer Definition von Algorithmus Das passt sowohl konkret (in gewissem Sinne) als auch die abstrakte Verwendung des Begriffs.

Die meisten Algorithmen sollen sein implementiert wie Computerprogramme. Algorithmen werden jedoch auch mit anderen Mitteln implementiert, z. B. in a Biologisches neuronales Netzwerk (zum Beispiel die menschliches Gehirn Implementierung Arithmetik oder ein Insekt auf der Suche nach Nahrung) in einem Stromkreisoder in einem mechanischen Gerät.

Formalisierung

Algorithmen sind für die Art und Weise, wie Computerdaten verarbeiten. Viele Computerprogramme enthalten Algorithmen, die die spezifischen Anweisungen, die ein Computer in einer bestimmten Reihenfolge ausführen sollte, detailliert beschreiben, um eine bestimmte Aufgabe auszuführen, z. Somit kann ein Algorithmus als jede Abfolge von Operationen angesehen werden, die durch a simuliert werden können Turing-Complete System. Autoren, die diese These geltend machen, umfassen Minsky (1967), Savage (1987) und Gurevich (2000):

MINSKY: "Aber wir werden auch mit Turing aufrechterhalten ... dass jedes Verfahren, das" natürlich "als wirksam bezeichnet werden könnte, tatsächlich von einer (einfachen) Maschine realisiert werden kann. Obwohl dies extrem erscheinen mag, die Argumente. . Zu ihren Gunsten sind schwer zu widerlegen ".^[37] Gurevich: "… Turings informelles Argument zugunsten seiner These rechtfertigt eine stärkere These: Jeder Algorithmus kann von einer Turing -Maschine simuliert werden. Laut Savage [1987] ist ein Algorithmus ein Rechenprozess, der von einer Turing -Maschine definiert ist."^[38]

Turing -Maschinen können Rechenprozesse definieren, die nicht enden. Die informellen Definitionen von Algorithmen erfordern im Allgemeinen, dass der Algorithmus immer endet. Diese Anforderung macht die Aufgabe, zu entscheiden, ob ein formales Verfahren ein Algorithmus im allgemeinen Fall ist - ausführlich zu einem Hauptsatz von Computerbarkeitstheorie bekannt als Problem stoppen.

Wenn ein Algorithmus mit Verarbeitungsinformationen zugeordnet ist, können Daten aus einer Eingangsquelle gelesen, in ein Ausgabegerät geschrieben und zur weiteren Verarbeitung gespeichert werden. Speichernde Daten werden als Teil des internen Zustands der Entität angesehen, die den Algorithmus ausführt. In der Praxis wird der Staat in einem oder mehreren gespeichert Datenstrukturen.

Für einige dieser Rechenprozesse muss der Algorithmus streng definiert werden: angegeben in der Art und Weise, wie er unter allen möglichen Umständen angewendet wird, die auftreten könnten. Dies bedeutet, dass alle bedingten Schritte systematisch von Fall zu Fall behandelt werden müssen. Die Kriterien für jeden Fall müssen klar (und berechnet) sein.

Da ein Algorithmus eine genaue Liste genauer Schritte ist, ist die Reihenfolge der Berechnung immer entscheidend für die Funktion des Algorithmus. Es wird normalerweise angenommen Kontrollfluss.

Bisher hat die Diskussion über die Formalisierung eines Algorithmus die Räumlichkeiten von angenommen Imperative Programmierung. Dies ist die häufigste Konzeption - eine, die versucht, eine Aufgabe in diskreten, "mechanischen" Mitteln zu beschreiben. Einzigartig für diese Konzeption formalisierter Algorithmen ist die Zuordnungsvorgang, was den Wert einer Variablen festlegt. Es leitet sich aus der Intuition von "ab"Erinnerung"Als Scratchpad. Ein Beispiel für eine solche Aufgabe finden Sie unten.

Für einige alternative Vorstellungen darüber, was einen Algorithmus ausmacht, siehe Funktionelle Programmierung und Logikprogrammierung.

Algorithmen ausdrücken

Algorithmen können in vielen Arten von Notationen ausgedrückt werden, einschließlich natürliche Sprachen, Pseudocode, Flussdiagramme, Drakon-Charts, Programmiersprachen oder Steuertabellen (verarbeitet von Dolmetscher). Algorithmen natürliche Sprachausdrücke sind in der Regel ausführlich und mehrdeutig und werden selten für komplexe oder technische Algorithmen verwendet. Pseudocode, Flussdiagramme, Drakon-Charts und Kontrolltabellen sind strukturierte Möglichkeiten, Algorithmen auszudrücken, die viele der in den Aussagen üblichen Unklarheiten vermeiden, die auf der natürlichen Sprache basieren. Programmiersprachen dienen hauptsächlich zum Ausdrücken von Algorithmen in einem Formular, das von einem Computer ausgeführt werden kann, aber häufig auch als Möglichkeit zum Definieren oder Dokumentieren von Algorithmen verwendet werden.

Es gibt eine Vielzahl von Darstellungen, und man kann eine gegebene Ausdrucke ausdrücken Turing Maschine Programm als Abfolge von Maschinentabellen (siehe Finite-State-Maschine, Zustandsübergangstabelle und Steuerungstabelle für mehr), als Flussdiagramme und Drakon-Charts (sehen Zustandsdiagramm für mehr) oder als Form des rudimentären Maschinensprache oder Montagecode genannt "Sätze von Vierruchen" (siehe Turing Maschine für mehr).

Darstellungen von Algorithmen können wie folgt in drei anerkannte Beschreibung der Turing -Maschine eingeteilt werden:^[39]

1 Beschreibung auf hoher Ebene

"... Prosa, um einen Algorithmus zu beschreiben und die Implementierungsdetails zu ignorieren. Auf dieser Ebene müssen wir nicht erwähnen, wie die Maschine das Band oder den Kopf verwaltet."

2 Implementierungsbeschreibung

"... Prosa wurde verwendet, um die Art und Weise zu definieren, wie die Turing -Maschine ihren Kopf verwendet und wie Daten auf ihrem Band gespeichert sind. Auf dieser Ebene geben wir keine Details der Zustände oder der Übergangsfunktion an."

3 Formale Beschreibung

Die detaillierteste "niedrigste Ebene" gibt den "Zustandstisch" der Turing Machine.

Für ein Beispiel für den einfachen Algorithmus "M+n" beschrieben in allen drei Ebenen siehe Beispiele.

Entwurf

Das Algorithmus-Design bezieht sich auf eine Methode oder einen mathematischen Prozess für Problemlösungen und technische Algorithmen. Das Design von Algorithmen ist Teil vieler Lösungstheorien von Betriebsforschung, wie zum Beispiel Dynamische Programmierung und Divide-and-Conquer. Techniken zum Entwerfen und Implementieren von Algorithmus -Designs werden auch Algorithmus -Designmuster bezeichnet.^[40] mit Beispielen wie dem Vorlagenmethodenmuster und dem Dekorationsmuster.

Einer der wichtigsten Aspekte des Algorithmus-Designs ist die Effizienz der Ressourcen (Laufzeit, Speicherverbrauch). das Big O Notation wird verwendet, um z. Das Laufzeitwachstum eines Algorithmus mit zunehmender Größe seines Eingangs.

Typische Schritte bei der Entwicklung von Algorithmen:

1. Problem Definition
2. Entwicklung eines Modells
3. Spezifikation des Algorithmus
4. Entwerfen eines Algorithmus
5. Überprüfen der Richtigkeit des Algorithmus
6. Analyse des Algorithmus
7. Implementierung des Algorithmus
8. Programmtests
9. Dokumentationsvorbereitung^{[Klarstellung erforderlich]}

Computeralgorithmen

Logischer NAND Algorithmus elektronisch implementiert in 7400 Chip

Beispiele des Flussdiagramms für die Kanonik Böhm-Jakopini-Strukturen: Die Sequenz (Rechtecke, die auf der Seite absteigen), die While-Do und die IF-Then-ELSE. Die drei Strukturen bestehen aus der primitiven bedingten Goto (IF test THEN GOTO step xxx, als Diamant gezeigt), das bedingungslose Goto (Rechteck), verschiedene Zuordnungsoperatoren (Rechteck) und Halt (Rechteck). Das Nisting dieser Strukturen innerhalb von Zuweisungsblocks führt zu komplexen Diagrammen (vgl. Tausworthe 1977: 100, 114).

"Elegante" (kompakte) Programme, "gute" (schnelle) Programme : Der Begriff "Einfachheit und Eleganz" erscheint informell in Knuth und genau in Chaitin:

Knuth: "... wir wollen gut Algorithmen im lose definierten ästhetischen Sinne. Ein Kriterium ... ist die Zeitdauer, um den Algorithmus auszuführen. Andere Kriterien sind die Anpassungsfähigkeit des Algorithmus an Computer, seine Einfachheit und Eleganz usw. "^[41]

Chaitin: "... ein Programm ist 'elegant', womit ich meine, dass es das kleinstmögliche Programm für die Erzeugung der Ausgabe ist, die es tut."^[42]

Chaitin setzt seine Definition vor: "Ich werde zeigen, dass Sie nicht beweisen können, dass ein Programm elegant ist'" - Wie ein Beweis würde das lösen Halting problem (ebenda).

Algorithmus versus Funktion, die von einem Algorithmus berechnet werden kann: Für eine bestimmte Funktion können mehrere Algorithmen existieren. Dies gilt auch ohne den verfügbaren Anweisungssatz, der dem Programmierer zur Verfügung steht. Rogers beobachtet, dass "es ... wichtig ist, zwischen dem Begriff von zu unterscheiden Algorithmus, d.h. Verfahren und der Begriff von Funktion mit Algorithmus berechnet, d.h. Mapping nach Verfahren. Die gleiche Funktion kann mehrere verschiedene Algorithmen haben ".^[43]

Leider kann es einen Kompromiss zwischen Güte (Geschwindigkeit) und Eleganz (Kompaktheit) geben - ein elegantes Programm kann mehr Schritte unternehmen, um eine Berechnung zu vervollständigen als eine weniger elegante. Ein Beispiel, das Euclids Algorithmus verwendet, erscheint unten.

Computer (und Computer), Berechnungsmodelle: Ein Computer (oder ein menschlicher "Computer"^[44]) ist ein eingeschränkter Maschinenart, ein "diskretes deterministisches mechanisches Gerät"^[45] Das folgt blind den Anweisungen.^[46] Melzaks und Lambeks primitive Modelle^[47] reduzierte diesen Begriff auf vier Elemente: (i) diskret, unterscheidbar Standorte(ii) diskret, nicht zu unterscheiden Zähler^[48] (iii) ein Agent und (iv) eine Liste von Anweisungen, die sind Wirksam relativ zur Fähigkeit des Agenten.^[49]

Minsky beschreibt eine kongenialere Variation von Lambeks "Abacus" -Modell in seinen "sehr einfachen Basen für Berechnbarkeit".^[50] Minskys Maschine fährt nacheinander über seine fünf (oder sechs sechs, je nachdem, wie man zählt) Anweisungen, es sei denn, entweder ein bedingter If-then-Goto oder ein bedingungsloses Goto-Programm-Programm, das aus der Sequenz herausfließt. Neben Halt enthält die Maschine von Minsky drei Abtretung (Ersatz, Substitution)^[51] Operationen: Null (z. B. der Ort des Standorts ersetzt durch 0: l ← 0), Nachfolger (z. B. l ← L+1) und Dekrement (z. B. l ← L - 1).^[52] Selten muss ein Programmierer "Code" mit einem so begrenzten Befehlssatz schreiben. Aber Minsky zeigt (wie Melzak und Lambek), dass seine Maschine ist Turing vollständig mit nur vier General Typen von Anweisungen: Bedingte Goto, bedingungslose Goto, Zuordnung/Ersatz/Substitution und Halt. Für eine Minsky-Maschine sind jedoch auch einige verschiedene Zuweisungsanweisungen (z. B. Dekrement, Inkrement und Null/Löschen/leer) erforderlich. Ihre genaue Spezifikation liegt bei dem Designer. Die bedingungslose Goto ist eine Bequemlichkeit; Es kann durch Initialisierung eines dedizierten Ortes auf Null konstruiert werden, z. die Anweisung "z ← 0"; Danach ist die Anweisung, wenn z = 0 dann goto xxx bedingungslos ist.

Simulation eines Algorithmus: Computer (Computer-) Sprache: Knuth rät dem Leser: "Der beste Weg, einen Algorithmus zu lernen, besteht darin, es zu versuchen ... sofort Stift und Papier zu nehmen und ein Beispiel zu durcharbeiten".^[53] Aber was ist mit einer Simulation oder Ausführung der realen Sache? Der Programmierer muss den Algorithmus in eine Sprache umsetzen, die der Simulator/Computer/Computer kann effektiv ausführen. Stein gibt ein Beispiel dafür: Beim Berechnen der Wurzeln einer quadratischen Gleichung muss der Computer wissen, wie man eine quadratische Wurzel einnimmt. Wenn dies nicht der Fall ist, muss der Algorithmus, um wirksam zu sein, eine Reihe von Regeln für das Extrahieren einer quadratischen Wurzel vorlegen.^[54]

Dies bedeutet, dass der Programmierer eine "Sprache" kennen muss, die relativ zum Zielcomputeragenten (Computer/Computor) wirksam ist.

Aber welches Modell sollte für die Simulation verwendet werden? Van emde boas beobachtet "auch wenn wir uns stützen Komplexitätstheorie Bei Abstract anstelle von Betonmaschinen bleibt die willkürliche Auswahl eines Modells bestehen. An diesem Punkt ist der Begriff von Simulation tritt ein ".^[55] Wenn die Geschwindigkeit gemessen wird, ist der Befehlssatz von Bedeutung. Zum Beispiel würde das Subprogramm in Euklids Algorithmus zur Berechnung des Restes viel schneller ausführen, wenn der Programmierer einen "hätte"Modul"Anweisungen verfügbar als nur Subtraktion (oder schlimmer: nur Minskys" Dekrement ").

Strukturierte Programmierung, kanonische Strukturen: Per the These der Kirche und tätige TheseJeder Algorithmus kann von einem Modell berechnet werden, von dem bekannt ist Turing vollständigund pro Demonstrationen von Minsky erfordert die Vollständigkeit nur vier Anweisungen - eine gleiche Goto, bedingungslose Goto, Aufgabe, Halt. Kemeny und Kurtz beobachten, dass zwar bedingungsloser Gotos und bedingte If-then-Then-Ther-Then-Gotos dazu führen können.Spaghetti -Code"Ein Programmierer kann strukturierte Programme nur mit diesen Anweisungen schreiben. Andererseits ist es auch möglich, schlecht strukturierte Programme in einer strukturierten Sprache zu schreiben."^[56] Tausworthe erweitert die drei Kanonische Strukturen von Böhm-Jakopini:^[57] Sequenz, if-then-else und während der Zeit mit zwei weiteren: do-while und case.^[58] Ein zusätzlicher Vorteil eines strukturierten Programms besteht darin, dass es sich selbst eignet Beweise der Korrektheit Verwendung mathematische Induktion.^[59]

Kanonische Flussdiagrammsymbole^[60]: Der grafische Adjutant genannt a Flussdiagrammbietet eine Möglichkeit, einen Algorithmus (und ein Computerprogramm von einem) zu beschreiben und zu dokumentieren. Wie der Programmfluss einer Minsky -Maschine startet ein Flussdiagramm immer oben auf einer Seite und geht nach unten. Seine Hauptsymbole sind nur vier: der gerichtete Pfeil mit dem Programmfluss, dem Rechteck (Sequenz, GOTO), dem Diamanten (if-then-else) und dem Punkt (Or-Tie). Die kanonischen Strukturen von Böhm -Jakopini bestehen aus diesen primitiven Formen. Substrukturen können in Rechtecken "nisten", aber nur, wenn ein einzelner Ausgang aus dem Aufbau auftritt. Die Symbole und ihre Verwendung zum Aufbau der kanonischen Strukturen sind im Diagramm gezeigt.

Beispiele

Beispiel für Algorithmus

Einer der einfachsten Algorithmen besteht darin, die größte Zahl in einer Liste der zufälligen Reihenfolge zu finden. Wenn Sie die Lösung finden, müssen Sie jede Anzahl in der Liste betrachten. Daraus folgt einem einfachen Algorithmus, der in englischer Prosa in einer hochrangigen Beschreibung angegeben werden kann, wie:

Auf hoher Ebene Beschreibung:

1. Wenn es keine Zahlen im Satz gibt, gibt es keine höchste Zahl.
2. Angenommen, die erste Nummer im Set ist die größte Zahl im Set.
3. Für jede verbleibende Zahl im Satz: Wenn diese Zahl größer als die aktuell größte Zahl ist, betrachten Sie diese Zahl als die größte Zahl im Satz.
4. Wenn im Set keine Zahlen vorhanden sind, um sie zu iterieren, betrachten Sie die aktuell größte Anzahl als die größte Anzahl des Satzes.

(Quasi-) Formale Beschreibung: In Prosa geschrieben, aber viel näher an der hochrangigen Sprache eines Computerprogramms, ist Folgendes die formellere Codierung des Algorithmus in Pseudocode oder Pidgin -Code:

Algorithmus Größte Eingabe: Eine Liste von Zahlen L. Ausgabe: Die größte Zahl in der Liste L.

wenn L.SIZE = 0 Rückkehr Nullgrößten ← L[0] für jeden Artikel in L, tun wenn Artikel > größten, dann größten ← Artikel Rückkehr größten 

Euclids Algorithmus

Im Mathematik, das Euklidischer Algorithmus, oder Euclids Algorithmus, ist eine effiziente Methode zum Berechnen der größter gemeinsamer Teiler (GCD) von zwei Ganzzahlen (Zahlen), der größten Zahl, die beide ohne a teilt Rest. Es ist nach dem alten Griechischen benannt Mathematiker Euklid, der es zum ersten Mal beschrieben hat seine Elemente (c.300 v. Chr).^[61] Es ist einer der ältesten Algorithmen bei der gemeinsamen Verwendung. Es kann verwendet werden, um zu reduzieren Brüche zu ihren Einfachste Formund ist Teil vieler anderer zahlentheoretischer und kryptografischer Berechnungen.

Das Beispiel-Diagramm von Euclids Algorithmus von T.L. Heath (1908) mit mehr Details. Euklid geht nicht über eine dritte Messung hinaus und gibt keine numerischen Beispiele. Nicomachus gibt das Beispiel von 49 und 21 an: "Ich subtrahiere das Weniger von der größeren; 28 bleibt übrig; dann subtrahiere ich wieder von dem gleichen 21 (dafür ist möglich); 7 bleibt übrig; ich subtrahiere dies von 21, 14 ist links; von dem ich wieder subtrahiere 7 (dafür ist möglich); 7 bleibt übrig, aber 7 kann nicht von 7 abgezogen werden. " Heath kommentiert, dass "der letzte Satz merkwürdig ist, aber die Bedeutung davon ist offensichtlich genug, ebenso wie die Bedeutung des Ausdrucks über das Ende" mit einer und derselben Zahl "(Heath 1908: 300).

Euklid stellt das Problem so dar: "Angesichts der zwei Zahlen, die nicht zueinander sind, um ihre größte gemeinsame Maßnahme zu finden". Er definiert "eine Zahl [um] eine Menge aus Einheiten": eine Zählzahl, eine positive Ganzzahl ohne Null. Um "zu messen", muss eine kürzere Messlänge platziert werden s nacheinander (q Zeiten) entlang längerer Länge l bis zum verbleibenden Teil r ist weniger als die kürzere Länge s.^[62] In modernen Worten, Rest r = l − q×s, q der Quotient oder Rest sein r ist der "Modul", der nach der Division übrig gebliebene ganzzahlige Teil.^[63]

Damit die Euklid -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 "ordnungsgemäß" sein; d.h. ein Test muss garantieren, dass das kleinere der beiden Zahlen von den größeren Subtrahieren (oder die beiden können gleich sein, so dass ihre Subtraktion Null ergibt).

Der ursprüngliche Beweis von Euclid fügt eine dritte Anforderung hinzu: Die beiden Längen dürfen nicht für einander prim sein. Euklid hat dies festgelegt, damit er a konstruieren konnte Reduktion ad absurdum Beweis, dass die gemeinsame Maßnahme der beiden Zahlen tatsächlich die ist größte.^[64] Während Nicomachus 'Algorithmus der gleiche ist wie der von Euklid, wenn die Zahlen für einander prim sind, gibt es die Zahl "1" für ihre gemeinsame Maßnahme. Um genau zu sein, ist das Folgende wirklich Nicomachus 'Algorithmus.

Ein grafischer Ausdruck von Euklids Algorithmus, um den größten gemeinsamen Divisor 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 Euclids Algorithmus

Nur wenige Anweisungen Typen sind erforderlich, um den Algorithmus von Euclid auszuführen - einige logische Tests (bedingte GOTO), bedingungslose Goto, Zuordnung (Ersatz) und Subtraktion.

• A Lage wird durch obere Fallschreiben (en) symbolisiert, z. S, a usw.
• Die variierende Menge (Nummer) in einem Ort ist in unteren Fallschreiben und (normalerweise) geschrieben, die dem Namen des Ortes zugeordnet sind. Zum Beispiel kann der Ort L am Anfang die Nummer enthalten l = 3009.

Ein unelegantes Programm für den Euklid -Algorithmus

"Inelegant" ist eine Übersetzung von Knuths Version des Algorithmus mit einem subtraktionsbasierten Rest-Loop, der seine Verwendung von Teilung (oder eine "Modulus" ersetzt. Abgeleitet von Knuth 1973: 2–4. Abhängig von den beiden Zahlen "unelegant" kann der G.C.D. in weniger Schritten als "elegant".

Der folgende Algorithmus wird als Knuths vierstufige Version von Euclids und Nicomachus 'umrahmt, aber anstatt Division zu verwenden, um den Rest zu finden s von der verbleibenden Länge r bis um r ist weniger als s. Die in fett geführte hochrangige Beschreibung ist von Knuth 1973: 2–4 angepasst:

EINGANG:

1 [In zwei Orte L und S geben die Zahlen ein l und s das repräsentiert die beiden Längen]: Eingabe l, s2 [Initialisieren R: Machen Sie die verbleibende Länge r Gleich der Start-/Anfangs-/Eingangslänge l]: R ← l

E0: [sicherstellen r ≥ s.]

3 [Stellen Sie sicher, dass der kleinere der beiden Zahlen in S und das größere in R] ist 4, 5 und 6: Goto Schritt 7 Sonst tauschen Sie den Inhalt von R und S. aus4 L ← R (dieser erste Schritt ist überflüssig, ist aber für eine spätere Diskussion nützlich).5 R ← s6 S ← l

E1: [Rest]: Bis die verbleibende Länge r In R ist weniger als die kürzere Länge s in s wiederholt die Messzahl abziehen s in s von der verbleibenden Länge r in R.

7 Wenn s> r dann mit dem Messen so gegangen ist 10 Sonst messen wieder,8 R ← r - s9 [Rest-Loop]: Goto 7.

E2: [Ist der Rest Null?]: Entweder (i) Die letzte Maßnahme war genau, der Rest in R ist Null und das Programm kann anhalten oder (ii) der Algorithmus muss fortgesetzt werden: Die letzte Maßnahme hat einen Rest in R weniger als die Messung der Zahl in S.

10 Wenn r = 0 ist, dann ist es geschafft Schritt 15 Sonst weiter Schritt 11Anwesend

E3: [Austausch s und r]: Die Nuss des Euklid -Algorithmus. Verwenden Sie den Rest r Um zu messen, was bisher kleiner war s; L dient als vorübergehende Lage.

11 L ← r12 R ← s13 S ← l14 [Wiederholen Sie den Messvorgang]: Goto 7 

AUSGANG:

15 [Fertig. S enthält die größter gemeinsamer Teiler]: Druck s

ERLEDIGT:

16 Halten Sie an, beenden Sie, stoppen Sie.

Ein elegantes Programm für den Algorithmus von Euclid

Die folgende Version von Euclids Algorithmus erfordert nur sechs Kernanweisungen, um das zu tun, was dreizehn von "unelegant" tun müssen. Schlimmeres, "unelegant" erfordert mehr Typen von Anweisungen.^[klären] Das Flussdiagramm von "elegant" befindet sich oben in diesem Artikel. In der (unstrukturierten) Grundsprache sind die Schritte nummeriert und der Anweisungen LET [] = [] ist die Zuordnungsanweisung, symbolisiert von ←.

  5 Rem Euclids Algorithmus für den größten gemeinsamen Divisor  6 DRUCKEN "Geben Sie zwei Ganzzahlen mehr als 0 an"  10 EINGANG A,B  20 WENN B=0 DANN GEHE ZU 80  30 WENN A > B DANN GEHE ZU 60  40 LASSEN B=B-A  50 GEHE ZU 20  60 LASSEN A=A-B  70 GEHE ZU 20  80 DRUCKEN A  90 ENDE 

Wie "elegant" funktioniert: Anstelle einer äußeren "euklidischen Schleife", "elegant" wechselt zwischen zwei "Co-Schleifen", einer A> B-Schleife, die A ← A-B und eine B ≤ A-Schleife, die B ← b berechnet, berechnet - A. Dies funktioniert, weil der Minuend schließlich, wenn der Minuend M kleiner oder gleich dem Subtrahend S (Differenz = Minuend - Subtrahend) ist s (die neue Messlänge) und der Subtrahend kann der neue werden r (die zu gemessene Länge); Mit anderen Worten, der "Sinn" der Subtraktion kehrt sich um.

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

// Euclids Algorithmus für den größten gemeinsamen Divisor int Euklidalgorithmus (int A, int B) {  A=Abs(A);  B=Abs(B);  während (B! =0) {  während (A>B) A=A-B;  B=B-A;  }  Rückkehr A; } 

Testen der Euklidalgorithmen

Tut ein Algorithmus, was sein Autor erledigt, was er tun möchte? Einige Testfälle geben normalerweise ein gewisses Vertrauen in die Kernfunktionalität. Aber Tests reichen nicht aus. In Testfällen eine Quelle^[65] Verwendet 3009 und 884. Knuth schlug 40902, 24140 vor. Ein weiterer interessanter Fall sind die beiden relativ primär Zahlen 14157 und 5950.

Aber "außergewöhnliche Fälle"^[66] muss identifiziert und getestet werden. Wird "unelegant" richtig abschneiden, 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? ("Unelegant" in allen Fällen für immer berechnet; "elegant", berechnet für immer, wenn a = 0.) Was passiert, wenn Negativ Nummern werden eingegeben? Bruchzahlen? Wenn die Eingangszahlen, d. H. Die Domäne der Funktion Berechnet vom Algorithmus/Programm soll nur positive Ganzzahlen einschließlich Null einbeziehen, dann zeigen die Fehler bei Null, dass der Algorithmus (und das Programm das Instantiates es ist ein Teilfunktion eher als ein Gesamtfunktion. Ein bemerkenswerter Fehler aufgrund von Ausnahmen ist das Ariane 5 Flug 501 Raketenversagen (4. Juni 1996).

Programmkorrektheit durch die Verwendung der mathematischen Induktion: Knuth zeigt die Anwendung von mathematische Induktion zu einer "erweiterten" Version von Euklids Algorithmus und er schlägt "eine allgemeine Methode vor, die für den Nachweis der Gültigkeit eines Algorithmus anwendbar ist".^[67] Tausworthe schlägt vor, dass ein Maß für die Komplexität eines Programms die Länge seines Korrektheitserzeugnisses ist.^[68]

Messung und Verbesserung der Euklidalgorithmen

Eleganz (Kompaktheit) gegen Güte (Geschwindigkeit): Mit nur sechs Kernanweisungen ist "elegant" der klare Gewinner im Vergleich zu "unelegant" bei dreizehn Anweisungen. "Unelegant" ist jedoch Schneller (Es kommt in weniger Schritten zum Stillstand). Algorithmusanalyse^[69] Gibt an, warum dies der Fall ist: "Elegant" tut es zwei Bedingte Tests in jeder Subtraktionsschleife, während "unelegant" nur eines tut. Wie der Algorithmus (normalerweise) viele Schleifen durchlässt, im Durchschnitt Es wird viel Zeit verschwendet, ein "B = 0" zu machen? Test, der erst nach der Berechnung des Restes benötigt wird.

Können die Algorithmen verbessert werden?: Sobald der Programmierer ein Programm "Anpassung" und "effektiv" beurteilt - das heißt, er berechnet die von seinem Autor beabsichtigte Funktion - kann es sich um die Frage handelt, ob es verbessert werden kann?

Die Kompaktheit von "unelegant" kann durch die Beseitigung von fünf Schritten verbessert werden. Chaitin bewies jedoch, dass die Verfindung eines Algorithmus nicht durch einen verallgemeinerten Algorithmus automatisiert werden kann.^[70] Vielmehr kann es nur getan werden heuristisch; d.h. durch erschöpfende Suche (Beispiele zu finden bei Beschäftigter Biber), Versuch und Irrtum, Klugheit, Einsicht, Anwendung von Induktiver Argumentationusw. Beobachten Sie, dass die Schritte 4, 5 und 6 in den Schritten 11, 12 und 13 wiederholt werden. Der Vergleich mit "elegantem" gibt einen Hinweis darauf, dass diese Schritte zusammen mit den Schritten 2 und 3 beseitigt werden können. Dies reduziert die Anzahl der Kernanweisungen von dreizehn auf acht, was es in neun Schritten "eleganter" als "elegant" macht.

Die Geschwindigkeit von "elegant" kann verbessert werden, indem das "B = 0" bewegt werden? Test außerhalb der beiden Subtraktionsschleifen. Diese Änderung erfordert die Hinzufügung von drei Anweisungen (b = 0?, A = 0?, GOTO). Jetzt berechnet "elegant" die Beispielzahlen schneller; Ob dies für eine bestimmte A, B und R immer der Fall ist, würde eine detaillierte Analyse erfordern.

Algorithmische Analyse

Es ist häufig wichtig zu wissen, wie viel von einer bestimmten Ressource (z. B. Zeit oder Speicher) theoretisch für einen bestimmten Algorithmus erforderlich ist. Methoden wurden für die entwickelt Analyse von Algorithmen solche quantitativen Antworten (Schätzungen) zu erhalten; Zum Beispiel ein Algorithmus, der die Elemente einer Liste von hinzufügt n Zahlen hätten eine Zeitanforderung von An), verwenden Big O Notation. Zu jeder Zeit muss der Algorithmus nur zwei Werte erinnern: die Summe aller bisherigen Elemente und seine aktuelle Position in der Eingabeliste. Daher soll es eine Platzbedarf von haben O (1), wenn der zur Speichern der Eingangsnummern erforderliche Speicherplatz nicht gezählt wird oder An) Wenn es gezählt wird.

Verschiedene Algorithmen können dieselbe Aufgabe mit unterschiedlichen Anweisungen in weniger oder mehr Zeit, Raum oder 'erledigen.Anstrengung' als andere. Zum Beispiel a binäre Suche Algorithmus (mit Kosten O (log n)) übertrifft eine sequentielle Suche (Kosten An) ) wenn für verwendet Tischhowups auf sortierten Listen oder Arrays.

Formal gegen empirisch

Das Analyse und Untersuchung von Algorithmen ist eine Disziplin von Informatikund wird oft abstrakt praktiziert, ohne dass ein bestimmtes Gebrauch verwendet wird Programmiersprache oder Implementierung. In diesem Sinne ähnelt die Algorithmusanalyse anderen mathematischen Disziplinen darin, dass sie sich auf die zugrunde liegenden Eigenschaften des Algorithmus und nicht auf die Besonderheiten einer bestimmten Implementierung konzentriert. Normalerweise Pseudocode wird für die Analyse verwendet, da es die einfachste und allgemeinste Darstellung ist. Letztendlich werden die meisten Algorithmen normalerweise auf bestimmten Hardware-/Softwareplattformen und ihren implementiert Algorithmische Effizienz wird schließlich mit realem Code auf den Test gebracht. Für die Lösung eines "One -Off" -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 schnelle interaktive, kommerzielle oder lange lebensbedingte wissenschaftliche Nutzung entwickelt wurden, kann dies von entscheidender Bedeutung sein. Die Skalierung von kleinem N nach großem N enthält häufig ineffiziente Algorithmen, die ansonsten gutartig sind.

Empirische Tests sind nützlich, da es unerwartete Wechselwirkungen aufdecken kann, die die Leistung beeinflussen. Benchmarks kann verwendet werden, um vor/nach potenziellen Verbesserungen eines Algorithmus nach der Programmoptimierung zu vergleichen. Empirische Tests können jedoch nicht die formale Analyse ersetzen und sind nicht trivial, um fair zu arbeiten.^[71]

Ausführungseffizienz

Um die möglichen Verbesserungen zu veranschaulichen, die auch in gut etablierten Algorithmen möglich sind, ist eine aktuelle bedeutende Innovation in Bezug auf Fft Algorithmen (stark im Bereich der Bildverarbeitung verwendet) können die Verarbeitungszeit für Anwendungen wie die medizinische Bildgebung um das 1.000 -fache verringern.^[72] Im Allgemeinen hängen Geschwindigkeitsverbesserungen von besonderen Eigenschaften des Problems ab, die in praktischen Anwendungen sehr häufig vorkommen.^[73] Beschleunigungen dieser Größenordnung ermöglichen Computergeräte, die die Bildverarbeitung (z.

Einstufung

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

Durch Implementierung

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

int GCD(int A, int B) {   wenn (B == 0)   Rückkehr A;   anders wenn (A > B)   Rückkehr GCD(A-B,B);   anders   Rückkehr GCD(A,B-A); } 

Rekursion

A rekursiger Algorithmus ist eine, die sich wiederholt aufruft (weist auf), bis eine bestimmte Bedingung (auch als Terminierungsbedingung bezeichnet) übereinstimmt, was eine Methode ist, die gemeinsam ist Funktionelle Programmierung. Iterativ Algorithmen verwenden wiederholte Konstrukte wie Schleifen und manchmal zusätzliche Datenstrukturen wie Stapel die gegebenen Probleme zu lösen. Einige Probleme sind natürlich für die eine oder andere Implementierung geeignet. Zum Beispiel, Türme von Hanoi wird durch rekursive Implementierung gut verstanden. Jede rekursive Version hat eine iterative (aber möglicherweise weniger komplexe) iterative (aber möglicherweise weniger komplexe) Version und umgekehrt.

Logisch

Ein Algorithmus kann als kontrolliert angesehen werden logische Folgerung. Dieser Begriff kann ausgedrückt werden als: Algorithmus = Logik + Steuerung.^[74] Die logische Komponente drückt die Axiome aus, die in der Berechnung verwendet werden können, und die Steuerkomponente bestimmt die Art und Weise, wie der Abzug auf die Axiome angewendet wird. Dies ist die Grundlage für die Logikprogrammierung Paradigma. In reinen logischen Programmiersprachen wird die Steuerkomponente festgelegt und Algorithmen werden angegeben, indem nur die Logikkomponente bereitgestellt wird. Die Anziehungskraft dieses Ansatzes ist der elegante Semantik: Eine Änderung der Axiome erzeugt eine gut definierte Änderung des Algorithmus.

Seriell, parallel oder verteilt

Algorithmen werden normalerweise mit der Annahme besprochen, dass Computer gleichzeitig eine Anweisung eines Algorithmus ausführen. Diese Computer werden manchmal als serielle Computer bezeichnet. Ein Algorithmus entworfen Für eine solche Umgebung wird im Gegensatz zu einem Seriennalgorithmus bezeichnet Parallelalgorithmen oder verteilte Algorithmen. Parallelalgorithmen nutzen Computerarchitekturen, bei denen mehrere Prozessoren gleichzeitig an einem Problem arbeiten können, während verteilte Algorithmen mehrere mit a angeschlossene Maschinen verwenden können Computernetzwerk. Parallele oder verteilte Algorithmen teilen das Problem in symmetrischere oder asymmetrische Unterprobleme und sammeln die Ergebnisse wieder zusammen. Der Ressourcenverbrauch in solchen Algorithmen ist nicht nur Prozessorzyklen für jeden Prozessor, sondern auch der 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 parallele Algorithmen und werden inhärent serielle Probleme genannt.

Deterministisch oder nicht deterministisch

Deterministische Algorithmen Lösen Sie das Problem mit der genauen Entscheidung bei jedem Schritt des Algorithmus, während Nichtdeterministische Algorithmen Probleme durch Erraten lösen, obwohl typische Vermutungen durch die Verwendung von genauer gemacht werden Heuristik.

Genau oder ungefähr

Während viele Algorithmen eine genaue Lösung erreichen, Näherungsalgorithmen Suchen Sie eine Näherung, die näher an der wahren Lösung liegt. Die Näherung kann entweder durch eine deterministische oder eine zufällige Strategie erreicht werden. Solche Algorithmen haben für viele harte Probleme einen praktischen Wert. Eines der Beispiele eines ungefähren Algorithmus ist das Rucksackproblem, wo es eine Reihe bestimmter Elemente gibt. Sein Ziel ist es, den Rucksack zu packen, um den maximalen Gesamtwert zu erhalten. Jeder Artikel hat etwas Gewicht und einen gewissen Wert. Das Gesamtgewicht, das getragen werden kann, ist nicht mehr als einige feste Zahl X. Die Lösung muss also sowohl die Gewichte von Elementen als auch deren Wert berücksichtigen.^[75]

Quantenalgorithmus

Sie laufen auf einem realistischen Modell von Quantenberechnung. Der Begriff wird normalerweise für diejenigen Algorithmen verwendet, die von Natur aus quantum erscheinen oder ein wesentliches Merkmal von verwenden Quanten-Computing wie zum Beispiel Quantenüberlagerung oder Quantenverschränkung.

Nach Designparadigma

Eine andere Möglichkeit, Algorithmen zu klassifizieren Paradigma. Es gibt eine bestimmte Anzahl von Paradigmen, die sich jeweils voneinander unterscheiden. Darüber hinaus enthält jede dieser Kategorien viele verschiedene Arten von Algorithmen. Einige gängige Paradigmen sind:

Rohe Gewalt oder erschöpfende Suche

Dies ist das naive Methode Jede mögliche Lösung zu versuchen, um zu sehen, was am besten ist.^[76]

Teilen und erobern

A Divide-and-Conquer-Algorithmus reduziert wiederholt eine Instanz eines Problems auf ein oder mehrere kleinere Instanzen des gleichen Problems (normalerweise rekursiv) bis die Instanzen klein genug sind, um leicht zu lösen. Ein solches Beispiel für Kluft und Eroberung ist Sortierung zusammenführen. Die Sortierung kann in jedem Datensegment durchgeführt werden, nachdem Daten in Segmente geteilt werden und die Sortierung ganzer Daten in der Eroberungsphase durch Zusammenführen der Segmente erhalten werden kann. Eine einfachere Variante von Kluft und Eroberung wird a genannt Abnahmealgorithmus, was ein identisches Teilproblem löst und die Lösung dieses Teilproblems verwendet, um das größere Problem zu lösen. Teilen und erobert das Problem in mehrere Teilprobleme, und so ist die Eroberungstufe komplexer als Abnahme und Erobereralgorithmen. Ein Beispiel für eine Abnahme und ein Erobereralgorithmus ist das binärer Suchalgorithmus.

Suche und Aufzählung

Viele Probleme (z. B. Spielen Schach) kann als Probleme an modelliert werden Grafiken. EIN Graph Exploration Algorithmus Gibt Regeln für das Umzug in ein Diagramm an und ist für solche Probleme nützlich. Diese Kategorie umfasst auch Suchalgorithmen, Zweig und gebunden Aufzählung und Backtracking.

Randomisierter Algorithmus

Solche Algorithmen treffen einige Entscheidungen zufällig (oder pseudo-randomisch). Sie können sehr nützlich sein, um ungefähre Lösungen für Probleme zu finden, bei denen genaue Lösungen unpraktisch finden können (siehe Heuristische Methode unten). Für einige dieser Probleme ist bekannt, dass die schnellsten Annäherungen einige beinhalten müssen Zufälligkeit.^[77] Ob randomisierte Algorithmen mit Polynomzeitkomplexität Kann die schnellsten Algorithmen für einige Probleme sein, ist eine offene Frage, die als die bekannt ist P gegen NP -Problem. Es gibt zwei große Klassen solcher Algorithmen:

1. Monte Carlo -Algorithmen Geben Sie eine korrekte Antwort mit hoher Wahrnehmung zurück. Z.B. RP ist die Unterklasse von diesen, die hereinlaufen Polynomzeit.
2. Las Vegas -Algorithmen Geben Sie immer die richtige Antwort zurück, aber ihre Laufzeit ist nur probabilistisch gebunden, z. Zpp.

Reduzierung der Komplexität

Diese Technik beinhaltet die Lösung eines schwierigen Problems, indem es in ein bekanntes Problem umgewandelt wird, für das wir (hoffentlich) Asymptotisch optimal Algorithmen. Das Ziel ist es, einen reduzierenden Algorithmus zu finden, dessen Komplexität wird nicht von den daraus resultierenden reduzierten Algorithmus dominiert. Zum Beispiel eine Auswahlalgorithmus Für das Finden des Medianes in einer ungeortierten Liste beinhaltet das Sortieren zuerst die Liste (den teuren Teil) und dann das mittlere Element in der sortierten Liste (der billige Teil) heraus. Diese Technik ist auch als bekannt als verwandeln und erobern.

Rü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

Zum Optimierungsprobleme Es gibt 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:

Lineares Programmieren

Bei der Suche nach optimalen Lösungen für eine lineare Funktion, die an lineare Gleichheit und Ungleichheitsbeschränkungen gebunden ist, können die Einschränkungen des Problems direkt bei der Erzeugung der optimalen Lösungen verwendet werden. Es gibt Algorithmen, die jedes Problem in dieser Kategorie lösen können, wie z. B. das Volk Simplex -Algorithmus.^[78] Probleme, die mit linearer Programmierung gelöst werden können Maximales Durchflussproblem für gerichtete Grafiken. Wenn ein Problem zusätzlich erfordert, dass ein oder mehrere der Unbekannten ein sein müssen ganze Zahl dann wird es in klassifiziert in Ganzzahlprogrammierung. Ein linearer Programmieralgorithmus kann ein solches Problem lösen, wenn nachgewiesen werden kann, dass alle Einschränkungen für ganzzahlige Werte oberflächlich sind, d. H. Die Lösungen erfüllen diese Einschränkungen ohnehin. Im allgemeinen Fall wird je nach Schwierigkeit des Problems ein spezialisierter Algorithmus oder ein Algorithmus verwendet, der ungefähre Lösungen findet.

Dynamische Programmierung

Wenn ein Problem zeigt optimale Unterstrukturen- Die optimale Lösung für ein Problem kann aus optimalen Lösungen für Teilprobleme konstruiert werden - und aus überlappende Unterprobleme, was bedeutet, dass dieselben Unterprobleme verwendet werden, um viele verschiedene Probleminstanzen zu lösen, ein schnellerer Ansatz heißt Dynamische Programmierung Vermeiden Sie die bereits berechneten Neuberechnung von Lösungen. Zum Beispiel, Floyd -Warshall -Algorithmus, der kürzeste Weg zu einem Ziel eines Scheitelpunkts in einem gewichteten Graph kann unter Verwendung des kürzesten Weges zum Ziel aller benachbarten Scheitelpunkte gefunden werden. Dynamische Programmierung und Memoisierung Zusammengehen. Der Hauptunterschied zwischen dynamischer Programmierung und Kluft und Eroberung besteht darin, dass Unterprobleme bei Divide und Eroberung mehr oder weniger unabhängig sind, während sich Unterprobleme in der dynamischen Programmierung überlappen. Der Unterschied zwischen dynamischer Programmierung und einfacher Rekursion besteht bei der Ausschnitt oder Memoisierung rekursiver Anrufe. Wenn Unterprobleme unabhängig sind und es keine Wiederholung gibt, hilft die Memoisierung nicht. Daher ist dynamische Programmierung keine Lösung für alle komplexen Probleme. Durch Verwendung von Memoisierung oder Aufrechterhaltung a Tisch Dynamische Programmierung reduziert die exponentielle Natur vieler Probleme auf die polynomische Komplexität.

Die gierige Methode

A Gieriger Algorithmus ähnelt einem dynamischen Programmieralgorithmus darin, dass es durch die Untersuchung von Unterstrukturen funktioniert, in diesem Fall nicht des Problems, sondern einer bestimmten Lösung. Solche Algorithmen beginnen mit einer Lösung, die in irgendeiner Weise gegeben oder konstruiert werden kann, und verbessern sie durch kleine Änderungen. Für einige Probleme können sie die optimale Lösung finden, während sie für andere anhalten Lokale OptimaDas heißt, bei Lösungen, die durch den Algorithmus nicht verbessert werden können, aber nicht optimal sind. Die beliebteste Verwendung von gierigen Algorithmen besteht darin, den minimalen Spannungsbaum zu finden, bei dem mit dieser Methode die optimale Lösung möglich ist. Huffman -Baum, Kruskal, Prim, Sollin sind gierige Algorithmen, die dieses Optimierungsproblem lösen können.

Die heuristische Methode

Im Optimierungsprobleme, Heuristische Algorithmen Kann verwendet werden, um eine Lösung nahe der optimalen Lösung zu finden, wenn die Suche nach der optimalen Lösung unpraktisch ist. Diese Algorithmen arbeiten im Laufe des Fortschritts immer näher an die optimale Lösung. Wenn sie für eine unendliche Zeitspanne ausgeführt werden, finden sie im Prinzip die optimale Lösung. Ihr Verdienst ist, dass sie in relativ kurzer Zeit eine Lösung finden können. Solche Algorithmen umfassen lokale Suche, Tabu -Suche, simuliertes Glühen, und genetische Algorythmen. Einige von ihnen sind, wie simuliertes Tempern, nicht deterministische Algorithmen, während andere, wie die Tabu-Suche, deterministisch sind. Wenn eine Grenze für den Fehler der nicht optimalen Lösung bekannt ist, wird der Algorithmus weiter als ein kategorisiert Näherungsalgorithmus.

Durch Studienfeld

Jedes Wissenschaftsfeld hat seine eigenen Probleme und benötigt effiziente Algorithmen. Verwandte Probleme in einem Bereich werden häufig zusammen untersucht. Einige Beispielklassen sind Suchalgorithmen, Sortieren von Algorithmen, Merge -Algorithmen, Numerische Algorithmen, Graphalgorithmen, String -Algorithmen, Rechengeometrische Algorithmen, Kombinatorische Algorithmen, Medizinische Algorithmen, maschinelles Lernen, Kryptographie, Datenkompression Algorithmen und Parsing -Techniken.

Felder neigen dazu, sich miteinander zu überschneiden, und der Algorithmus -Fortschritt in einem Feld kann diejenigen der anderen, manchmal völlig unabhängig von Feldern, verbessern. Zum Beispiel wurde die dynamische Programmierung für die Optimierung des Ressourcenverbrauchs in der Industrie erfunden, wird jedoch jetzt zur Lösung einer breiten Palette von Problemen in vielen Bereichen verwendet.

Durch Komplexität

Algorithmen können nach der Zeit, die sie benötigen, im Vergleich zu ihrer Eingangsgröße eingestuft werden:

• Konstante Zeit: Wenn die vom Algorithmus benötigte Zeit unabhängig von der Eingangsgröße gleich ist. Z.B. ein Zugang zu einem Array Element.
• Logarithmische Zeit: Wenn die Zeit eine logarithmische Funktion der Eingangsgröße ist. Z.B. binärer Suchalgorithmus.
• Lineare Zeit: Wenn die Zeit proportional zur Eingangsgröße ist. Z.B. Die Traverse einer Liste.
• Polynomzeit: Wenn die Zeit eine Leistung der Eingangsgröße ist. Z.B. das Blasenart Der Algorithmus hat eine quadratische Zeitkomplexität.
• Exponentialzeit: Wenn die Zeit eine exponentielle Funktion der Eingangsgröße ist. Z.B. Brute-Force-Suche.

Einige Probleme können mehrere Algorithmen unterschiedlicher Komplexität aufweisen, während andere Probleme möglicherweise keine Algorithmen oder keine bekannten effizienten Algorithmen aufweisen. Es gibt auch Zuordnungen von einigen Problemen zu anderen Problemen. Auf diese Weise wurde festgestellt, dass es besser geeignet ist, die Probleme selbst anstelle der Algorithmen in Äquivalenzklassen zu klassifizieren, basierend auf der Komplexität der bestmöglichen Algorithmen für sie.

Kontinuierliche Algorithmen

Das Adjektiv "kontinuierlich", wenn er auf das Wort "Algorithmus" angewendet wird, kann bedeuten:

• Ein Algorithmus, der auf Daten arbeitet, die kontinuierliche Größen darstellen, obwohl diese Daten durch diskrete Näherungen dargestellt werden, werden Algorithmen in untersucht numerische Analyse; oder
• Ein Algorithmus in Form von a Differentialgleichung das funktioniert kontinuierlich auf den Daten und läuft auf einem Analoger Computer.^[79]

Rechtsfragen

Algorithmen sind selbst in der Regel nicht patentierbar. In den Vereinigten Staaten ist eine Behauptung, die ausschließlich aus einfachen Manipulationen abstrakter Konzepte, Zahlen oder Signale besteht Gottschalk gegen Benson). Praktische Anwendungen von Algorithmen sind jedoch manchmal patentierbar. Zum Beispiel in Diamond v. Diehr, die Anwendung eines einfachen Rückmeldung Algorithmus zur Härtung von Synthesekautschuk wurde als patentierbar eingestuft. Das Patentierung von Software ist sehr umstritten, und es gibt sehr kritisierte Patente, an denen Algorithmen beteiligt sind, insbesondere mit Algorithmen Datenkompression Algorithmen, wie z. Unisys' LZW Patent.

Darüber hinaus haben einige kryptografische Algorithmen Exportbeschränkungen (siehe Export der Kryptographie).

Geschichte: Entwicklung des Begriffs von "Algorithmus"

Altes Nahen Osten

Der früheste Beweis von Algorithmen findet sich in der Babylonische Mathematik der alten Mesopotamien (Moderner Irak). EIN Sumerianer Tontafel gefunden in Shuruppak nahe Bagdad und datiert auf ca. 2500 v. Chr. beschrieben die früheste Divisionalgorithmus.^[11] Während der Hammurabi -Dynastie ca. 1800-1600 v. Chr., Babylonisch Tontabletten beschrieben Algorithmen zum Computer Formeln.^[80] Algorithmen wurden auch in verwendet Babylonische Astronomie. Babylonische Tontafeln beschreiben und verwenden algorithmische Verfahren, um die Zeit und den Ort erheblicher astronomischer Ereignisse zu berechnen.^[81]

Algorithmen für die Arithmetik sind auch im Alten gefunden Ägyptische Mathematik, stammen aus dem Rhind Mathematical Papyrus ca. 1550 v. Chr.^[11] Algorithmen wurden später in der Antike verwendet Hellenistische Mathematik. Zwei Beispiele sind die Sieb von Eratosthenes, was in der beschrieben wurde Einführung in die Arithmetik durch Nicomachus,^{[82][12]: CH 9.2} und die Euklidischer Algorithmus, was zum ersten Mal in beschrieben wurde Euklids Elemente (c.300 v. Chr).^{[12]: Ch 9.1}

Diskrete und unterscheidbare Symbole

Tally-Marks: Um ihre Herden, ihre Getreidesäcke und ihr Geld zu verfolgen, verwendeten die Alten Tallying: Ansammlung von Steinen oder Markierungen, die auf Stöcken zerkratzt sind oder diskrete Symbole in Ton machen. Durch die babylonische und ägyptische Verwendung von Markierungen und Symbolen schließlich römische Zahlen und die Abakus Evolved (Dilson, S. 16–41). Markierungen erscheinen prominent in Unarmes Ziffernsystem Arithmetik verwendet in Turing Maschine und Post -Turing -Maschine Berechnungen.

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

Muhammad Ibn Mūsā al-Khwārizmī, a Persischer Mathematiker, schrieb die Al-Jabr im 9. Jahrhundert. Die Begriffe "Algorismus"Und" Algorithmus "stammen aus dem Namen al-Khwārizmī, während der Begriff"Algebra"wird aus dem Buch abgeleitet Al-Jabr. In Europa wurde das Wort "Algorithmus" ursprünglich verwendet, um auf die von Al-Khwarizmi verwendeten Regeln und Techniken zur Lösung von algebraischen Gleichungen zu verweisen, bevor später verallgemeinert wurde, um auf eine Reihe von Regeln oder Techniken zu verweisen.^[83] Dies gipfelte schließlich in LeibnizBegriff der Kalkül Ratiocinator (c.1680):

Leibniz schlug ein gutes Jahrhundert vor seiner Zeit vor und schlug eine Algebra der Logik vor, eine Algebra, die die Regeln für die Manipulation logischer Konzepte in der Art und Weise angeben würde, dass gewöhnliche Algebra die Regeln für die Manipulation von Zahlen angibt.^[84]

Kryptografische Algorithmen

Der Erste kryptografisch Der Algorithmus zur Entschlüsselung verschlüsselter Code wurde von entwickelt von Al-kindi, ein 9. Jahrhundert Arabischer Mathematiker, in Ein Manuskript zur Entschlüsselung kryptografischer Botschaften. Er gab die erste Beschreibung von Kryptanalyse durch Frequenzanalyse, der Frühste Code knacken Algorithmus.^[13]

Mechanische Erfindungen mit diskreten Zuständen

Die Uhr: Bolter schreibt die Erfindung der Gewichtsbetrieben zu Uhr als "die Schlüsselerfindung [von Europa im Mittelalter]" insbesondere die Verge -Hemmung^[85] Das bietet uns das Zecken und das Teck einer mechanischen Uhr. "Die genaue automatische Maschine"^[86] sofort zu "mechanisch geführt Automaten"ab dem 13. Jahrhundert und schließlich zu" Computermaschinen " - der Differenzmotor und Analysemotoren von Charles Babbage und Gräfin Ada Lovelace, Mitte des 19. Jahrhunderts.^[87] Lovelace wird die erste Erstellung eines Algorithmus für die Verarbeitung auf einem Computer zugeschrieben - Babbag's Analytical Engine, das erste Gerät als real angesehen Turing-Complete Computer statt a Taschenrechner- und wird manchmal als "erster Programmierer der Geschichte" bezeichnet, obwohl eine vollständige Implementierung des zweiten Geräts von Babbage erst Jahrzehnte nach ihrem Leben realisiert würde.

Logische Maschinen 1870 - Stanley Jevons'"logischer Abakus" und "logische Maschine": Das technische Problem bestand darin, zu reduzieren Boolesche Gleichungen Wenn er in einer Form präsentiert wird, ähnlich dem, was heute bekannt ist Karnaugh Maps. Jevons (1880) beschreibt zunächst einen einfachen "Abakus" von "mit Stiften ausgestatteten Holzschuhen, so dass jeder Teil oder jede Klasse der [logischen] Kombinationen mechanisch ausgewählt werden kann ... in jüngerer Zeit habe ich jedoch reduziert System zu einer völlig mechanischen Form und haben somit den gesamten indirekten Inferenzprozess in sogenannten sogenannten als a Logische Maschine"Seine Maschine war mit" bestimmten beweglichen Holzstangen "und" am Fuß sind 21 Schlüssel wie die eines Klaviers [usw.] ... "mit dieser Maschine konnte er eine analysieren"Syllogismus oder ein anderes einfaches logisches Argument ".^[88]

Diese Maschine zeigte er 1870 vor den Kollegen der Royal Society.^[89] Ein anderer Logiker John Vennjedoch 1881 Symbolische Logik, hat ein gelbsem Auge auf diese Anstrengung gedreht: "Ich habe mich nicht hohe Schätzung des Interesses oder der Bedeutung dessen, was manchmal als logische Maschinen bezeichnet wird ... Es scheint mir nicht, dass derzeit bekannte oder wahrscheinlich entdeckte Erfindungen wirklich verdient werden. der Name logischer Maschinen "; Sehen Sie mehr bei Algorithmus -Charakterisierungen. Aber um nicht übertroffen zu werden, präsentierte auch er "einen etwas analog analog, ich habe der Befürchtung von Prof. Jevon's festgelegt Abakus ... und] [a] Gewinn, entsprechend der logischen Maschine von Prof. Jevons, kann die folgende Erfindung beschrieben werden. Ich nenne es lieber lediglich eine logische Diagrammmaschine ... aber ich nehme an, dass es sehr ganz alles tun könnte, was rational von jeder logischen Maschine erwartet werden kann. "^[90]

Jacquard Loom, Hollerith Punch Cards, Telegraphie und Telefonie - das elektromechanische Relais: Bell und Newell (1971) zeigen, dass die Jacquard Loom (1801), Vorläufer zu Hollerith -Karten (Punch Cards, 1887) und "Telefon -Switching -Technologien" waren die Wurzeln eines Baumes, der zur Entwicklung der ersten Computer führte.^[91] Mitte des 19. Jahrhunderts die TelegraphDer Vorläufer des Telefons wurde weltweit verwendet, seine diskrete und unterscheidbare Codierung von Buchstaben als "Punkte und Striche" als gemeinsamer Klang. Bis zum späten 19. Jahrhundert die Tickerband (c.1870er Jahre) wurde genutzt, ebenso wie die Verwendung von Hollerith -Karten in der US -Volkszählung von 1890. Dann kam der Fernschreiber (c.1910) mit dem Gebrauch von gestanztem Papier von Baudot -Code auf Band.

Telefon-sankte Netzwerke elektromechanischer Relais (erfunden 1835) stand hinter der Arbeit von George Stibitz (1937), der Erfinder des digitalen Additionsgeräts. Als er in Bell Laboratories arbeitete, beobachtete er die "lästige" Verwendung mechanischer Taschenrechner mit Zahnrädern. "Er ging 1937 nach Hause, um seine Idee zu testen ... Als das Basteln vorbei war, hatte Stibitz ein binäres Additionsgerät gebaut." .^[92]

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

Nur mit der Entwicklung, die in den 1930er Jahren von elektromechanischen Taschenrechnern unter Verwendung elektrischer Relais gebaut wurde, wurden Maschinen gebaut, wobei der Geltungsbereich Babbage vorgestellt hatte. "^[93]

Mathematik im 19. Jahrhundert bis zur Mitte des 20. Jahrhunderts

Symbole und Regeln: In schneller Folge die Mathematik von George Boole (1847, 1854), Gottlob Frege (1879) und Giuseppe Peano (1888–1889) reduzierte Arithmetik auf eine Abfolge von Symbolen, die durch Regeln manipuliert wurden. Peano Die Prinzipien der Arithmetik, präsentiert durch eine neue Methode (1888) war "der erste Versuch einer Axiomatisierung der Mathematik in a Symbolische Sprache".^[94]

Aber Heijenoort gibt Frege (1879) dieses Lobs: Frege's ist "vielleicht das wichtigste einzelne Werk, das jemals in Logik geschrieben wurde. ... in dem wir eine" Formelsprache "sehen, das ist ein Lingua Charakterica, Eine Sprache mit speziellen Symbolen, "für reines Denken", dh frei von rhetorischen Verzierungen ... konstruiert aus spezifischen Symbolen, die nach bestimmten Regeln manipuliert werden ".^[95] Die Fregearbeit wurde weiter vereinfacht und verstärkt durch Alfred North Whitehead und Bertrand Russell in ihren Principia Mathematica (1910–1913).

Die Paradoxien: Gleichzeitig erschien insbesondere in der Literatur eine Reihe störender Paradoxien in der Literatur, die Burali-Forti Paradox (1897), die Russell Paradox (1902–03) und die Richard Paradox.^[96] Die resultierenden Überlegungen führten zu Kurt Gödel's Paper (1931) - er zitiert ausdrücklich das Paradox des Lügners -, das Regeln von vollständig reduziert Rekursion zu Zahlen.

Wirksame Berechnbarkeit: Um die zu lösen Entscheidungsproblem Genau von Hilbert im Jahr 1928 definiert und machte sich zunächst darum, das zu definieren, was mit einer "effektiven Methode" oder "effektiven Berechnung" oder "wirksamer Berechnbarkeit" zu verstehen war (d. H. Eine Berechnung, die erfolgreich sein würde). In schneller Folge erschien Folgendes: Alonzo -Kirche, Stephen Kleene und J. B. Rosser's λ-Kalkulus^[97] Eine fein geschliffen Jacques Herbrand (vgl. Gödels Princeton -Vorträge von 1934) und anschließende Vereinfachungen durch Kleene.^[98] Beweis der Kirche^[99] Dass das entscheidungsproblem unlösbar war, Emil Post'S Definition einer effektiven Berechnung als Arbeiter, die gedankenlos einer Liste von Anweisungen befolgt, um sich nach links oder rechts durch eine Folge von Räumen zu bewegen und 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.^[100] Alan Turings Beweis dafür, dass das Inentschen-Problem durch die Verwendung seiner "A- [automatischen] Maschine" nicht löslich war, war nicht löslich^[101]- In Effekt beinahe identisch mit der "Formulierung" von Post, J. Barkley Rosser's Definition der "effektiven Methode" in Bezug auf "eine Maschine".^[102] Kleenes Vorschlag eines Vorläufers zu "Kirchenarbeit"Das nannte er" These ich ",^[103] und ein paar Jahre später umbenannte Kleene seine These "Kirche These" um.^[104] und "Turings These" vorschlagen.^[105]

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

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

"... zwei Konzepte sind beteiligt: ​​das von a Symbolraum in der die Arbeit von Problem zu beantworten wird, die erledigt werden soll, und ein fester unveränderlicher Anweisungen.

Sein Symbolraum wäre sein

"Eine wechselseitige Infinite-Abfolge von Räumen oder Kisten ... Der Problemlöser oder Arbeiter besteht darin, sich in diesem Symbolraum zu bewegen und zu arbeiten, in der Lage zu sein, in der Lage zu sein und gleichzeitig in einer Box zu arbeiten ... eine Box ist nur zwei mögliche Bedingungen zuzugeben, d. H. Leer oder nicht markiert zu sein und eine einzige Marke darin zu haben, sagen Sie einen vertikalen Schlaganfall.

"Eine Box soll herausgegriffen und als Ausgangspunkt bezeichnet werden. ... Ein spezifisches Problem ist in symbolischer Form durch eine endliche Anzahl von Kästchen [d. H. Eingabe] mit einem Schlaganfall markiert. Ebenso die Antwort [d.h. , Ausgabe] ist in symbolischer Form durch eine solche Konfiguration von markierten Kästchen zu verabschieden ...

"Eine Reihe von Anweisungen, die für ein allgemeines Problem anwendbar sind, legt einen deterministischen Prozess fest, wenn er auf jedes spezifische Problem angewendet wird. Dieser Prozess endet nur, wenn es um die Richtung vom Typ (c) [d. H. Stop]".^[106] Sehen Sie mehr bei Post -Turing -Maschine

Alan Turings Statue bei Bletchley Park

Alan TuringArbeit^[107] vorausgegangen der von Stibitz (1937); Es ist nicht bekannt, ob Stibitz die Arbeit der Turing wusste. Turings Biograf war der Ansicht, dass Turings Verwendung eines maschinenwartungsähnlichen Modells aus einem jugendlichen Interesse stammt: "Alan hatte davon geträumt, Schreibmaschinen als Junge zu erfinden; Mrs. Turing hatte eine Schreibmaschine, und er hätte sich gut damit gefragt haben, was mit dem Rufen gedacht war eine Schreibmaschine 'mechanische' ".^[108] Angesichts der Prävalenz zum Zeitpunkt von Morsecode, Telegraphie, Tickerbandmaschinen und Teletypewritern ist es durchaus möglich, dass alle Einflüsse auf Turing während seiner Jugend waren.

Turing - sein Berechnungsmodell wird jetzt als a genannt Turing Maschine- wie Post mit einer Analyse eines menschlichen Computers, den er auf einen einfachen Satz grundlegender Bewegungen und "Geisteszustände" hinunterschleudert. Aber er setzt einen Schritt weiter und erstellt eine Maschine als Modell der Berechnung von Zahlen.^[109]

"Das Computer wird normalerweise durch das Schreiben bestimmter Symbole auf Papier geschrieben. Wir können annehmen, dass dieses Papier in Quadrate unterteilt ist in Quadrate. Ich nehme auch an, dass die Anzahl der Symbole, die gedruckt werden können, endlich ist ...

"Das Verhalten des Computers wird jederzeit durch die Symbole bestimmt, die er beobachtet, und sein" Geisteszustand "in diesem Moment. Wir können annehmen, dass die Anzahl der Symbole oder Quadrate eine Grenze b gibt, die der Computer kann Beobachten Sie in einem Moment. Wenn er mehr beobachten möchte, muss er aufeinanderfolgende Beobachtungen verwenden. Wir werden auch annehmen, dass die Anzahl der Geisteszustände, die berücksichtigt werden müssen, endlich ist ...

"Lasst uns vorstellen, dass die vom Computer ausgeführten Vorgänge in" einfache Operationen "aufgeteilt werden, die so wichtig sind, dass es sich nicht leicht vorstellen kann, sie weiter zu unterteilen."^[110]

Die Reduzierung von Turing ergibt Folgendes:

"Die einfachen Operationen müssen daher enthalten:

"(a) Änderungen des Symbols auf einem der beobachteten Quadrate

"(b) Veränderungen eines der Quadrate, die auf einem anderen Quadrat innerhalb der Quadrate eines der zuvor beobachteten Quadrate beobachtet wurden.

"Es kann sein, dass einige dieser Veränderungen notwendigerweise eine Änderung des Geisteszustands berufen. Die allgemeinste Einzeloperation muss daher als eines der folgenden angesehen werden:

"(A) eine mögliche Änderung (a) des Symbols zusammen mit einer möglichen Änderung des Geisteszustands.

"(B) eine mögliche Veränderung (b) der beobachteten Quadrate sowie eine mögliche Änderung des Geisteszustands"

"Wir können jetzt eine Maschine bauen, um die Arbeit dieses Computers zu erledigen."^[110]

Einige Jahre später erweiterte Turing seine Analyse (These, Definition) mit diesem kraftvollen Ausdruck:

"Eine Funktion soll" effektiv kalkulierbar "sein, wenn ihre Werte durch einen rein mechanischen Prozess gefunden werden können. Obwohl es ziemlich einfach ist, diese Idee intuitiv zu verstehen ... [Er diskutiert die Geschichte der Definition, die oben in Bezug auf Gödel, Herbrand, Kleene, Kirche, Turing und Post vorgestellt wurden. könnte von einer Maschine durchgeführt werden. Es ist möglich, eine mathematische Beschreibung in einer bestimmten normalen Form der Strukturen dieser Maschinen zu erteilen. Die Entwicklung dieser Ideen führt zur Definition des Autors einer berechnbaren Funktion und zur Identifizierung von Berechnbarkeit † mit effektiver Berechnbarkeit ...

"† Wir werden den Ausdruck" berechnungsable Funktion "verwenden, um eine von einer Maschine berechnete Funktion zu bedeuten, und wir lassen" effektiv kalkulierbar "auf die intuitive Idee ohne besondere Identifizierung mit einer dieser Definitionen".^[111]

J. B. Rosser (1939) und S. C. Kleene (1943)

J. Barkley Rosser definierte eine "effektive [mathematische] Methode" auf folgende Weise (Italisierung hinzugefügt):

"'Effektive Methode' wird hier im ziemlich besonderen Sinne einer Methode verwendet, von der jeder Schritt genau bestimmt wird und die die Antwort in einer begrenzten Anzahl von Schritten mit dieser besonderen Bedeutung ergeben wird. Mit dieser besonderen Bedeutung wurden drei verschiedene genaue Definitionen gegeben Bisher. [Seine Fußnote Nr. 5; Siehe Diskussion unmittelbar unten]. Die einfachste von diesen zu sagen (aufgrund von Post und Turing), sagt im Wesentlichen das Es gibt eine wirksame Methode zur Lösung bestimmter Probleme mit Problemen, wenn man eine Maschine erstellen kann. Alle drei Definitionen sind gleichwertig, daher spielt es keine Rolle, welche verwendet wird. Darüber hinaus ist die Tatsache, dass alle drei gleichwertig sind, ein sehr starkes Argument für die Richtigkeit eines beliebten. “(Rosser 1939: 225–226)

Rossers Fußnote Nr. 5 bezieht Ein unlösbares Problem der Elementarzahltheorie (1936); (2) Herbrand und Gödel und deren Verwendung von Rekursion, insbesondere Gödels Verwendung in seinem berühmten Papier Über formell unentscheidbare Aussagen von Principia Mathematica und verwandten Systemen I. (1931); und (3) Post (1936) und Turing (1936–37) in ihren Berechnungsmodellen.

Stephen C. Kleene definiert als seine jetzt berühmte "These i" als die als die These der Kirche und tätige These. Aber er tat dies im folgenden Kontext (fett im Original):

"12. Algorithmische Theorien... Bei der Einrichtung einer vollständigen algorithmischen Theorie beschreiben wir ein Verfahren, das für jeden Satz von Werten der unabhängigen Variablen abgebildet werden kann, die notwendigerweise endet und auf eine solche Weise, dass wir aus dem Ergebnis eine eindeutige Antwort lesen können. "Ja" oder "Nein", zur Frage, ist der Prädikatwert wahr? "" (Kleene 1943: 273)

Geschichte nach 1950

Eine Reihe von Anstrengungen wurde auf eine weitere Verfeinerung der Definition von "Algorithmus" gerichtet, und die Aktivität ist aufgrund von Problemen im Zusammenhang mit insbesondere im Zusammenhang mit der Aktivität weitergeleitet. Grundlagen der Mathematik (insbesondere das These der Kirche und tätige These) und Philosophie des Geistes (insbesondere Argumente zu künstliche Intelligenz). Für mehr siehe Algorithmus -Charakterisierungen.

Siehe auch

Anmerkungen

Literaturverzeichnis

Weitere Lektüre

Externe Links

• "Algorithmus", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Algorithmen bei Curlie
• Weisstein, Eric W. "Algorithmus". Mathord.
• Wörterbuch von Algorithmen und Datenstrukturen – Nationales Institut für Standards und Technologie

Algorithmus -Repositories

• Das Stony Brook -Algorithmus -Repository – State University of New York in Stony Brook
• Gesammelte Algorithmen des ACM – Verband für Rechenmaschinen
• Die Stanford Graphbase – Universität in Stanford