In der Mathematik und Informatik ist ein Algorithmus (von Algoritmi, der lateinischen Abschrift von al-Khwārizmī) ein schrittweises Verfahren für Berechnungen. Algorithmen werden für die Berechnung, Datenverarbeitung verwendet, und haben das Denken automatisiert.

Genauer ist ein Algorithmus eine wirksame Methode ausgedrückt als eine begrenzte Liste von bestimmten Instruktionen, für eine Funktion zu berechnen. Von einem anfänglichen staatlichen und anfänglichen Eingang (vielleicht leer) anfangend, beschreiben die Instruktionen eine Berechnung, die, wenn durchgeführt, durch eine begrenzte Zahl von bestimmten aufeinander folgenden Staaten weitergehen wird, schließlich "Produktion" erzeugend und an einem endenden Endstaat endend. Der Übergang von einem Staat bis das folgende ist nicht notwendigerweise deterministisch; einige Algorithmen, bekannt als randomized Algorithmen, vereinigen zufälligen Eingang.

Eine teilweise Formalisierung des Konzepts hat mit Versuchen begonnen, Entscheidungsproblem (das "Entscheidungsproblem") aufgestellt von David Hilbert 1928 zu lösen. Nachfolgende Formalisierungen wurden als Versuche eingerahmt, "wirksame Berechenbarkeit" oder "wirksame Methode" zu definieren; jene Formalisierungen haben die Gödel-Herbrand-Kleene rekursiven Funktionen von 1930, 1934 und 1935, Kirchlambda-Rechnung von Alonzo von 1936, die "Formulierung von Emil Post 1" 1936 und der Maschinen von Turing von Alan Turing 1936-7 und 1939 eingeschlossen. Das Geben einer formellen Definition von Algorithmen, entsprechend dem intuitiven Begriff, bleibt ein schwieriges Problem.

Informelle Definition

:For eine ausführliche Präsentation der verschiedenen Gesichtspunkte um die Definition "des Algorithmus" sehen Algorithmus-Charakterisierungen. Für Beispiele von einfachen Hinzufügungsalgorithmen, die auf die ausführliche in Algorithmus-Charakterisierungen beschriebene Weise angegeben sind, sieh Algorithmus-Beispiele.

Während es keine allgemein akzeptierte formelle Definition "des Algorithmus" gibt, konnte eine informelle Definition "eine Reihe von Regeln sein, der genau eine Folge von Operationen definiert." Für einige Menschen ist ein Programm nur ein Algorithmus, wenn es schließlich anhält; für andere ist ein Programm nur ein Algorithmus, wenn es vor einer gegebenen Zahl von Berechnungsschritten anhält.

Ein archetypisches Beispiel eines Algorithmus ist der Algorithmus von Euklid, um den maximalen allgemeinen Teiler von zwei ganzen Zahlen zu bestimmen; ein Beispiel (gibt es andere) wird durch die Fluss-Karte oben und als ein Beispiel in einer späteren Abteilung beschrieben.

bieten Sie eine informelle Bedeutung des Wortes im folgenden Kostenvoranschlag an:

Der Begriff "enumerably Unendliche" bedeutet "zählbare ganze Verwenden-Zahlen, die sich vielleicht bis zu die Unendlichkeit ausstrecken." So sagen Boolos und Jeffrey, dass ein Algorithmus Instruktionen für einen Prozess einbezieht, der ganze Produktionszahlen von einer willkürlichen ganzen "Eingangs"-Zahl oder ganzen Zahlen "schafft", die, in der Theorie, von 0 bis Unendlichkeit gewählt werden können. So kann ein Algorithmus eine algebraische Gleichung wie y = M + n — zwei willkürliche "Eingangsvariablen" M und n sein, die eine Produktion y erzeugen. Aber die Versuche der verschiedenen Autoren, den Begriff zu definieren (sieh mehr bei Algorithmus-Charakterisierungen), zeigen an, dass das Wort viel mehr einbezieht als das, etwas auf der Ordnung (für das Hinzufügungsbeispiel):

:Precise-Instruktionen (auf der Sprache, die durch "den Computer" verstanden ist) für einen schnellen, effizienten, "guten" Prozess, der die "Bewegungen" "des Computers" (Maschine oder Mensch angibt, der mit der notwendigen innerlich enthaltenen Information und den Fähigkeiten ausgestattet ist), um zu finden, decodieren, und bearbeiten dann willkürliche ganze Eingangszahlen/Symbole M und n, Symbole + und =... und erzeugen "effektiv", in einer "angemessenen" Zeit, ganze Zahl der Produktion y an einem angegebenen Platz und in einem angegebenen Format.

Das Konzept des Algorithmus wird auch verwendet, um den Begriff der Entscheidbarkeit zu definieren. Dieser Begriff ist zentral, um zu erklären, wie formelle Systeme entstehen, von einem kleinen Satz von Axiomen und Regeln anfangend. In der Logik kann die Zeit, dass ein Algorithmus verlangt, um zu vollenden, nicht gemessen werden, weil es nicht anscheinend mit unserer üblichen physischen Dimension verbunden ist. Von solchen Unklarheiten, die andauernde Arbeit charakterisieren, entstielt die Nichtverfügbarkeit einer Definition des Algorithmus, der beidem Beton (in einem Sinn) und abstrakter Gebrauch des Begriffes anpasst.

Formalisierung

Algorithmen sind für die Weise notwendig, wie Computer Daten bearbeiten. Viele Computerprogramme enthalten Algorithmen, die über die spezifischen Instruktionen ausführlich berichten, die ein Computer (in einer spezifischen Ordnung) durchführen sollte, um eine angegebene Aufgabe, wie das Rechnen der Gehälter von Angestellten oder der Druck der Zeugnisse von Studenten auszuführen. So, wie man betrachten kann, ist ein Algorithmus jede Folge von Operationen, die durch ein Turing-ganzes System vorgetäuscht werden können. Autoren, die diese These behaupten, schließen Minsky (1967), Wilder (1987) und Gurevich (2000) ein:

Gewöhnlich, wenn ein Algorithmus mit der in einer Prozession gehenden Information vereinigt wird, Daten wird von einer Eingangsquelle gelesen, die einem Produktionsgerät geschrieben ist, und/oder hat für die weitere Verarbeitung versorgt. Versorgte Daten werden als ein Teil des inneren Staates der Entität betrachtet, die den Algorithmus durchführt. In der Praxis wird der Staat in einer oder mehr Datenstrukturen versorgt.

Für etwas solchen rechenbetonten Prozess muss der Algorithmus streng definiert werden: Angegeben im Weg gilt es in allen möglichen Verhältnissen, die entstehen konnten. D. h. irgendwelche bedingten Schritte müssen Fall-für-Fall systematisch befasst werden; die Kriterien für jeden Fall müssen klar (und berechenbar sein).

Weil ein Algorithmus eine genaue Liste von genauen Schritten ist, wird die Ordnung der Berechnung immer zur Wirkung des Algorithmus kritisch sein. Wie man gewöhnlich annimmt, werden Instruktionen ausführlich verzeichnet, und werden als das Starten "von der Spitze" und dem Gehen "unten zum Boden beschrieben,", eine Idee, die mehr formell durch den Fluss der Kontrolle beschrieben wird.

Bis jetzt hat diese Diskussion der Formalisierung eines Algorithmus die Propositionen der befehlenden Programmierung angenommen. Das ist die allgemeinste Vorstellung, und sie versucht, eine Aufgabe im getrennten zu beschreiben, "mechanisches" bedeutet. Einzigartig zu dieser Vorstellung von formalisierten Algorithmen ist die Anweisungsoperation, den Wert einer Variable setzend. Es ist auf die Intuition "des Gedächtnisses" als ein Notizblock zurückzuführen. Es gibt ein Beispiel unten solch einer Anweisung.

Für einige abwechselnde Vorstellungen dessen, was einen Algorithmus einsetzt, sieh funktionelle Programmierung und Logikprogrammierung.

Das Ausdrücken von Algorithmen

Algorithmen können in vielen Arten der Notation, einschließlich natürlicher Sprachen, Pseudocodes, Flussschemen, Programmiersprachen oder Steuertabellen (bearbeitet von Dolmetschern) ausgedrückt werden. Ausdrücke der natürlichen Sprache von Algorithmen neigen dazu, wortreich und zweideutig zu sein, und werden für komplizierte oder technische Algorithmen selten verwendet. Pseudocode, Flussschemen und Steuertabellen sind strukturierte Weisen, Algorithmen auszudrücken, die viele der in Behauptungen der natürlichen Sprache üblichen Zweideutigkeiten vermeiden. Programmiersprachen sind in erster Linie beabsichtigt, um Algorithmen in einer Form auszudrücken, die durch einen Computer durchgeführt werden kann, aber häufig als eine Weise verwendet wird, Algorithmen zu definieren oder zu dokumentieren.

Es gibt ein großes Angebot an möglichen Darstellungen, und man kann ein gegebenes Maschinenprogramm von Turing als eine Folge von Maschinentischen ausdrücken (sieh mehr an der Zustandsmaschine, setzen Sie Übergang-Tisch und Steuertabelle fest), als Flussschemen (sieh mehr am Zustandsdiagramm), oder als eine Form des rudimentären Maschinencodes oder Zusammenbau-Codes genannt "Sätze von Vierfachen" (sieh mehr an der Maschine von Turing).

Darstellungen von Algorithmen können in drei akzeptierte Niveaus der Maschinenbeschreibung von Turing klassifiziert werden:

• 1 Beschreibung Auf höchster Ebene:

:: "... Prosa, um einen Algorithmus zu beschreiben, die Durchführungsdetails ignorierend. An diesem Niveau brauchen wir nicht zu erwähnen, wie die Maschine sein Band oder Kopf führt."

• 2 Durchführungsbeschreibung:

:: "... Prosa hat gepflegt, die Weise zu definieren, wie die Maschine von Turing seinen Kopf und die Weise verwendet, wie es Daten auf seinem Band versorgt. An diesem Niveau geben wir Details von Staaten oder Übergang-Funktion nicht."

• 3 Formelle Beschreibung:

:: Am ausführlichsten, "Tiefststand", gibt die Maschine von Turing "Zustandtisch".

:For ein Beispiel des einfachen Algorithmus "Fügen m+n hinzu, der" in allen drei Niveaus beschrieben ist, sehen Algorithmus-Beispiele.

Durchführung

Die meisten Algorithmen sind beabsichtigt, um als Computerprogramme durchgeführt zu werden. Jedoch werden Algorithmen auch durch andere Mittel, solcher als in einem biologischen Nervennetz (zum Beispiel, die menschliche Gehirneinführen-Arithmetik oder ein Kerbtier durchgeführt, nach Essen suchend), in einem elektrischen Stromkreis, oder in einem mechanischen Gerät.

Computeralgorithmen

In Computersystemen ist ein Algorithmus grundsätzlich ein Beispiel der Logik, die in der Software durch Softwareentwickler geschrieben ist, um für den beabsichtigten "Ziel"-Computer in der Größenordnung von den Zielmaschinen wirksam zu sein, um Produktion vom gegebenen Eingang (vielleicht zu erzeugen, ungültig).

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

:Knuth: "...we wollen gute Algorithmen in einem lose definierten ästhetischen Sinn. Ein Kriterium... ist die Zeitdauer, die genommen ist, um den Algorithmus durchzuführen.... Andere Kriterien sind Anpassungsfähigkeit des Algorithmus zu Computern, seiner Einfachheit und Anmut, usw."

:Chaitin: "... ein Programm ist 'elegant,' durch den ich meine, dass es das kleinstmögliche Programm ist, für die Produktion zu erzeugen, die es" tut

Einleitungen von Chaitin seine Definition mit: "Ich werde zeigen, dass Sie nicht beweisen können, dass ein Programm 'elegant' ist" — würde solch ein Beweis das Stockende Problem (ibd.) beheben.

Algorithmus gegen die durch einen Algorithmus berechenbare Funktion: Für eine gegebene Funktion können vielfache Algorithmen bestehen. Das wird wahr sein, sogar ohne den verfügbaren für den Programmierer verfügbaren Befehlssatz auszubreiten. Rogers bemerkt, dass "Es ist... wichtig, um zwischen dem Begriff des Algorithmus, d. h. Verfahren und dem Begriff der Funktion zu unterscheiden, die durch den Algorithmus berechenbar ist, d. h. nachgegeben durch das Verfahren kartografisch darzustellen. Dieselbe Funktion kann mehrere verschiedene Algorithmen haben".

Leider kann es einen Umtausch zwischen Güte (Geschwindigkeit) und Anmut (Kompaktheit) geben — ein elegantes Programm kann mehr Schritte machen, um eine Berechnung zu vollenden, als ein weniger eleganter. Ein Beispiel, den Algorithmus von Euklid zu verwenden, wird unten gezeigt.

Computer (und computors), Modelle der Berechnung: Ein Computer (oder menschlicher "computor") ist ein eingeschränkter Typ der Maschine, eines "getrennten deterministischen mechanischen Geräts", das blind seinen Instruktionen folgt. Die primitiven Modelle von Melzak und Lambeks haben diesen Begriff auf vier Elemente reduziert: (i) getrennte, unterscheidbare Positionen, (ii) getrennte, nicht zu unterscheidende Schalter (iii) ein Agent, und (iv) eine Liste von Instruktionen, die hinsichtlich der Fähigkeit zum Agenten wirksam sind.

Minsky beschreibt eine kongenialere Schwankung des "Rechenmaschine"-Modells von Lambek in seinen "Sehr Einfachen Basen für die Berechenbarkeit". Die Maschine von Minsky geht folgend durch seine fünf weiter (oder sechs je nachdem, wie man zählt) Instruktionen, wenn entweder ein bedingter, WENN DANN GOTO oder ein vorbehaltloser GOTO Programm-Fluss aus der Folge ändern. Außer dem HALT schließt die Maschine von Minsky drei Anweisung (Ersatz, Ersatz) Operationen ein: NULL (z.B hat der Inhalt der Position durch 0 ersetzt: L  0), NACHFOLGER (z.B. L  L+1), und VERMINDERUNG (z.B. L  L  1). Selten wird ein Programmierer "Code" mit solch einem beschränkten Befehlssatz schreiben müssen. Aber Shows von Minsky (wie Melzak und Lambek tun), dass seine Maschine mit nur vier allgemeinen Typen von Instruktionen abgeschlossener Turing ist: bedingter GOTO, vorbehaltloser GOTO, Anweisung/Ersatz/Ersatz und HALT.

Simulation eines Algorithmus: Computer (computor) Sprache: Knuth empfiehlt dem Leser, dass "die beste Weise, einen Algorithmus zu erfahren, es versuchen soll... nehmen Sie sofort Kugelschreiber und Papier und Arbeit durch ein Beispiel". Aber wie steht's mit einer Simulation oder Ausführung des echten Dings? Der Programmierer muss den Algorithmus in eine Sprache übersetzen, die der simulator/computer/computor effektiv durchführen kann. Stein führt ein Beispiel davon an: Wenn er die Wurzeln einer quadratischen Gleichung schätzt, muss der computor wissen, wie man eine Quadratwurzel nimmt. Wenn sie nicht dann für den Algorithmus tun, um wirksam zu sein, muss er eine Reihe von Regeln zur Verfügung stellen, für eine Quadratwurzel herauszuziehen.

Das bedeutet, dass der Programmierer eine "Sprache" wissen muss, die hinsichtlich des Ziels Rechenreagenz (computer/computor) wirksam ist.

Aber welches Modell sollte für die Simulation verwendet werden? Van Emde Boas beobachtet, "selbst wenn wir Kompliziertheitstheorie über den Auszug statt konkreter Maschinen stützen, bleibt die Eigenmächtigkeit der Wahl eines Modells. Es ist an diesem Punkt, dass der Begriff der Simulation hereingeht". Wenn Geschwindigkeit, die Befehlssatz-Sachen gemessen wird. Zum Beispiel würde das Unterprogramm im Algorithmus von Euklid, um den Rest zu schätzen, viel schneller durchführen, wenn der Programmierer ein "Modul" (Abteilung) Instruktion verfügbar aber nicht gerade Subtraktion hätte (oder schlechter: gerade "die Verminderung" von Minsky).

Strukturierte Programmierung, kanonische Strukturen: Pro Kirch-Turing-These kann jeder Algorithmus durch ein Modell geschätzt werden, das bekannt ist, Turing zu sein, abgeschlossen, und pro die Demonstrationen von Minsky verlangt Vollständigkeit von Turing nur vier Instruktionstypen — bedingter GOTO, vorbehaltloser GOTO, Anweisung, HALT. Kemeny und Kurtz bemerken dass, während "der undisziplinierte" Gebrauch von vorbehaltlosem GOTOs und bedingt, WENN DANN GOTOs "auf Spaghetti-Code" ein Programmierer hinauslaufen kann, strukturierte Programme mit diesen Instruktionen schreiben kann; andererseits "ist es auch, und nicht zu hart möglich, um schlecht strukturierte Programme auf einer strukturierten Sprache zu schreiben". Tausworthe vermehrt die drei Böhm-Jacopini kanonischen Strukturen: FOLGE, "WENN DANN SONST", und WÄHREND - mit noch zwei TUN: TUN SIE - WÄHREND und FALL. Ein zusätzlicher Vorteil eines strukturierten Programms wird derjenige sein, der sich zu Beweisen der Genauigkeit mit der mathematischen Induktion leiht.

Kanonische Flussschema-Symbole: Der grafische Helfer hat gerufen ein Flussschema bietet eine Weise an, einen Algorithmus (und ein Computerprogramm von einem) zu beschreiben und zu dokumentieren. Wie Programm-Fluss einer Maschine von Minsky fängt ein Flussschema immer an der Oberseite von einer Seite und Erlös unten an. Seine primären Symbole sind nur 4: der geleitete sich zeigende Pfeil-Programm-Fluss, das Rechteck (FOLGE, GOTO), der Diamant (WENN DANN SONST), und der Punkt (ODER-BAND). Die Böhm-Jacopini kanonischen Strukturen werden aus diesen primitiven Gestalten gemacht. Unterbauten können in Rechtecken "nisten", aber nur wenn ein einzelner Ausgang vom Oberbau vorkommt. Die Symbole und ihr Gebrauch, um die kanonischen Strukturen zu bauen, werden im Diagramm gezeigt.

Beispiele

Das Sortieren des Beispiels

Einer der einfachsten Algorithmen soll die größte Zahl in einer (unsortierten) Liste von Zahlen finden. Die Lösung verlangt notwendigerweise das Aussehen an jeder Zahl in der Liste, aber nur einmal an jedem. Davon folgt einem einfachen Algorithmus, der in einer englischen Beschreibungsprosa auf höchster Ebene als festgesetzt werden kann:

Beschreibung auf höchster Ebene:

1. Nehmen Sie an, dass der erste Artikel am größten ist.
2. Schauen Sie auf jede der restlichen Sachen in der Liste, und wenn es größer ist als der größte Artikel bis jetzt, merken Sie es vor.
3. Der letzte bekannte Artikel ist in der Liste am größten, wenn der Prozess abgeschlossen ist.

(Quasi-) formelle Beschreibung:

Geschrieben in der Prosa, aber viel näher an der höheren Programmiersprache eines Computerprogramms ist der folgende das mehr formelle Codieren des Algorithmus im Pseudocode oder Angelegenheitscode:

Eingang: Eine nichtleere Liste von Zahlen L.

Produktion: Die größte Zahl in der Liste L.

größter  L

für jeden Artikel in der Liste (Länge (L) 1), tun Sie

wenn der Artikel> am größten, dann

größter  der Artikel

geben Sie größten zurück

Der Algorithmus von Euklid

Der Algorithmus von Euklid erscheint als Vorschlag II im Buch VII ("Elementare Zahlentheorie") von seinen Elementen. Euklid wirft das Problem auf: "In Anbetracht zwei zu einander nicht erster Zahlen, um ihr größtes allgemeines Maß zu finden". Er definiert "Eine Zahl [um] eine aus Einheiten zusammengesetzte Menge zu sein": eine Zählen-Zahl, eine positive ganze Zahl nicht einschließlich 0. Und "zu messen" soll eine kürzere Messlänge s nacheinander (q Zeiten) entlang der längeren Länge l legen, bis der restliche Teil r weniger ist als die kürzere Länge s. In modernen Wörtern ist Rest r = l  q*s, q der Quotient oder Rest r zu sein, das "Modul", der mit der ganzer Zahl unbedeutende Teil verlassen zu Ende nach der Abteilung.

Für die Methode von Euklid, erfolgreich zu sein, müssen die Startlängen zwei Voraussetzungen befriedigen: (i) die Längen muss nicht 0, UND (ii) sein die Subtraktion muss "richtig" sein, ein Test muss versichern, dass die kleinere von den zwei Zahlen vom größeren abgezogen wird (abwechselnd, können die zwei gleich sein, so trägt ihre Subtraktion 0).

Der ursprüngliche Beweis von Euklid fügt ein Drittel hinzu: Die zwei Längen sind zu einander nicht erst. Euklid hat das festgesetzt, so dass er eine reductio Anzeige absurdum Beweis bauen konnte, dass das allgemeine Maß der zwei Zahlen tatsächlich am größten ist. Während der Algorithmus von Nicomachus dasselbe als Euklid ist, wenn die Zahlen zu einander erst sind, gibt es die Nummer "1" für ihr allgemeines Maß nach. So, um genau zu sein, ist der folgende wirklich der Algorithmus von Nicomachus.

Beispiel

Beispiel von 1599 und 650:

Computersprache für den Algorithmus von Euklid

Nur einige Instruktionstypen sind erforderlich, den Algorithmus von Euklid — einige logische Tests (bedingter GOTO), vorbehaltloser GOTO, Anweisung (Ersatz) und Subtraktion durchzuführen.

• Eine Position wird durch den Großbuchstaben-Brief (E) z.B symbolisiert. S, A, usw.
• Die unterschiedliche Menge (Zahl) in einer Position wird im Brief (En) der unteren Umschaltung geschrieben und (gewöhnlich) mit dem Namen der Position vereinigt. Zum Beispiel könnte Position L am Anfang die Nummer l = 3009 enthalten.

Ein unelegantes Programm für den Algorithmus von Euklid

Der folgende Algorithmus wird als die 4-Schritte-Version von Knuth von Euklid und Nichomachus eingerahmt, aber anstatt Abteilung zu verwenden, um den Rest zu finden, verwendet es aufeinander folgende Subtraktionen der kürzeren Länge s von der restlichen Länge r, bis r weniger ist als s. Die Beschreibung auf höchster Ebene, die in der Fettschrift gezeigt ist, wird von Knuth 1973:2-4 angepasst:

EINGANG:

: 1 [In zwei Positionen stellen L und S die Nummern l und s, die die zwei Längen] vertreten: EINGANG L, S

: 2 [Initialisieren R: Machen Sie die restliche Länge r gleich der Länge des Startens/Initiale/Eingangs l] R  L

E0: [Versichern Sie r  s.]

: 3 [Versichern, dass die kleinere von den zwei Zahlen in S und dem größeren in R] ist: WENN R> S DANN der Inhalt von L die größere Zahl so Hopser über die Austauschschritte 4, 5 und 6 ist: GOTO Schritt 6 tauscht SONST den Inhalt von R und S.]

: 4 L  R (ist dieser erste Schritt überflüssig, aber wird für die spätere Diskussion nützlich sein).

: 5 R  S

: 6 S  L

E1: [Finden Sie Rest]: Bis die restliche Länge r in R weniger ist als die kürzere Länge s in S, ziehen Sie wiederholt die Messnummer s in S von der restlichen Länge r in R ab.

: 7 WENN S> R DANN das getane Messen so GOTO 10 SONST Maß wieder,

: 8 R  R  S

: 9 [Rest-Schleife]: GOTO 7.

E2: [Ist der Rest 0?]: ENTWEDER (i) das letzte Maß war genau und der Rest in R, ist 0 Programm, kann ODER (ii) hinken der Algorithmus muss weitergehen: Das letzte Maß hat einen Rest in R weniger verlassen als Messzahl in S.

: 10, WENN R = 0 dann getan so GOTO Schritt 15 SONST zum Schritt 11, weitergeht

E3: [Wechseln Sie s und r] aus: Die Nuss des Algorithmus von Euklid. Verwenden Sie den Rest r, um zu messen, was vorher kleinere Nummer s war:; L dient als eine vorläufige Position.

: 11 L  R

: 12 R  S

: 13 S  L

: 14 [Wiederholen den Messprozess]: GOTO 7

PRODUKTION:

: 15 [Getan. S enthält den größten allgemeinen Teiler]: DRUCKEN SIE S

GETAN:

: 16 HALT, ENDE, HÄLT AN.

Ein elegantes Programm für den Algorithmus von Euklid

Die folgende Version des Algorithmus von Euklid verlangt nur 6 Kerninstruktionen zu tun, was 13 erforderlich sind, durch "den Uneleganten" zu tun; schlechter, "Unelegant" verlangt mehr Typen von Instruktionen. Das Flussschema von "Eleganten" kann an der Oberseite von diesem Artikel gefunden werden. Auf der (unstrukturierten) Grundlegenden Sprache werden die Schritte numeriert, und die Instruktion hat [] = [] GELASSEN ist die durch  symbolisierte Anweisungsinstruktion.

Der Algorithmus von 5 REM Euklid für den größten allgemeinen Teiler

6 DRUCK "Typ zwei ganze Zahlen, die größer sind als 0"

10 GIBT A, B EIN

20 WENN B=0 DANN GOTO 80

30 WENN A> B DANN GOTO 60

40 LASSEN B=B-A

50 GOTO 20

60 LASSEN A=A-B

70 GOTO 20

80 DRUCKEN EINEN

90 ENDE

</pre>

Wie "Elegante" Arbeiten: Im Platz einer "Außenschleife von Euklid", "Elegante" Verschiebungen hin und her zwischen zwei "Co-Schleifen", ein A> B Schleife, die Einen  Ein  B und ein B  Eine Schleife schätzt, die B  B  A schätzt. Das arbeitet, weil, wenn schließlich die minuend M weniger ist als oder gleich dem Subtrahenden S (Unterschied = Minuend  Subtrahend), der minuend s werden kann (die neue Messlänge) und der Subtrahend der neue r (die Länge werden kann, die zu messen ist); mit anderen Worten der "Sinn" der Subtraktionsrückseiten.

Die Prüfung der Algorithmen von Euklid

Tut ein Algorithmus, was sein Autor will, dass er tut? Einige Testfälle genügen gewöhnlich, um Kernfunktionalität zu bestätigen. Eine Quelle verwendet 3009 und 884. Knuth hat 40902, 24140 vorgeschlagen. Ein anderer interessanter Fall ist die zwei Relativ-Primzahlen 14157 und 5950.

Aber Ausnahmefälle müssen identifiziert und geprüft werden. Wird "Unelegant" richtig wenn R> S, S> R, R = S leisten? Dito für "den Eleganten": B> A, A> B, = B? (Ja zu allen). Was geschieht, wenn eine Zahl Null ist, sind beide Zahlen Null? ("Unelegant" rechnet für immer in allen Fällen; "elegant" rechnet für immer wenn = 0.) Was geschieht, wenn in negative Zahlen eingegangen wird? Bruchzahlen? Wenn die Eingangszahlen, d. h. das Gebiet der durch den Algorithmus/Programm geschätzten Funktion, nur positive ganze Zahlen einschließlich der Null einschließen sollen, dann zeigen die Misserfolge an der Null an, dass der Algorithmus (und das Programm, das es realisiert) eine teilweise Funktion aber nicht eine Gesamtfunktion ist. Ein bemerkenswerter Misserfolg wegen Ausnahmen ist der Rakete-Misserfolg von Ariane V.

Beweis der Programm-Genauigkeit durch den Gebrauch der mathematischen Induktion: Knuth demonstriert die Anwendung der mathematischen Induktion zu einer "verlängerten" Version des Algorithmus von Euklid, und er schlägt "eine allgemeine Methode vor, die auf den Beweis der Gültigkeit jedes Algorithmus anwendbar ist". Tausworthe schlägt vor, dass ein Maß der Kompliziertheit eines Programms die Länge seines Genauigkeitsbeweises ist.

Das Messen und die Besserung der Algorithmen von Euklid

Anmut (Kompaktheit) gegen die Güte (Geschwindigkeit): Mit nur 6 Kerninstruktionen, "Elegant" ist der klare Sieger im Vergleich zum "Uneleganten" an 13 Instruktionen. Jedoch, "Unelegant" ist schneller (es erreicht HALT in weniger Schritten). Algorithmus-Analyse zeigt an, warum das der Fall ist: "Elegant" tut zwei bedingte Tests in jeder Subtraktionsschleife, wohingegen "Unelegant" nur denjenigen tut. Da der Algorithmus (gewöhnlich) viele Schleife-throughs verlangt, wird durchschnittlich viel Zeit vergeudet, "B = 0 tuend?" Test, der nur nach dem Rest erforderlich ist, wird geschätzt.

Können die Algorithmen verbessert werden?: Sobald der Programmierer ein Programm "passend" und "wirksam" beurteilt — d. h. schätzt es die Funktion, die von seinem Autor — dann beabsichtigt ist, die Frage wird, kann es verbessert werden?

Die Kompaktheit von "Uneleganten" kann durch die Beseitigung von 5 Schritten verbessert werden. Aber Chaitin hat bewiesen, dass das Verbinden eines Algorithmus durch einen verallgemeinerten Algorithmus nicht automatisiert werden kann; eher kann es nur heuristisch, d. h. durch die erschöpfende Suche (Beispiele getan werden, die am Beschäftigten Biber zu finden sind), Probe und Fehler, Klugheit, Scharfsinnigkeit, Anwendung des induktiven Denkens usw. Bemerken Sie, dass Schritte 4, 5 und 6 in Schritten 11, 12 und 13 wiederholt werden. Der Vergleich mit "dem Eleganten" stellt einen Hinweis zur Verfügung, dass diese Schritte zusammen mit Schritten 2 und 3 beseitigt werden können. Das vermindert die Anzahl von Kerninstruktionen von 13 bis 8, der sie "eleganter" macht als "Elegant" an 9 Schritten.

Die Geschwindigkeit von "Eleganten" kann durch das Bewegen des B=0 verbessert werden? prüfen Sie außerhalb der zwei Subtraktionsschleifen. Diese Änderung verlangt nach der Hinzufügung von 3 Instruktionen (B=0? A=0? GOTO). Jetzt "Elegant" schätzt die Beispiel-Zahlen schneller; ob für irgendwelchen gegeben A, B und R, S das immer der Fall ist, würde eine ausführliche Analyse verlangen.

Algorithmische Analyse

Es ist oft wichtig zu wissen, wie viel einer besonderen Quelle (wie Zeit oder Lagerung) für einen gegebenen Algorithmus theoretisch erforderlich ist. Methoden sind für die Analyse von Algorithmen entwickelt worden, um solche quantitativen Antworten (Schätzungen) zu erhalten; zum Beispiel hat der Sortieren-Algorithmus oben eine Zeitvoraussetzung von O (n) mit der großen O Notation mit n als die Länge der Liste. Zu jeder Zeit muss sich der Algorithmus nur an zwei Werte erinnern: die größte Zahl gefunden bis jetzt, und seine aktuelle Position in der Eingangsliste. Deshalb, wie man sagt, hat es eine Raumvoraussetzung von O (1), wenn der Raum, der erforderlich ist, um die Eingangszahlen zu versorgen, oder O (n) nicht aufgezählt wird, wenn es aufgezählt wird.

Verschiedene Algorithmen können dieselbe Aufgabe mit einem verschiedenen Satz von Instruktionen in weniger oder mehr Zeit, Raum oder 'Anstrengung' vollenden als andere. Zum Beispiel wird ein binärer Suchalgorithmus gewöhnlich eine rohe Gewalt folgende Suche, wenn verwendet, für den Tisch lookups auf sortierten Listen überbieten.

Formell gegen den empirischen

Die Analyse und Studie von Algorithmen sind eine Disziplin der Informatik, und werden häufig abstrakt ohne den Gebrauch einer spezifischen Programmiersprache oder die Durchführung geübt. In diesem Sinn ähnelt Algorithmus-Analyse anderen mathematischen Disziplinen, in denen es sich auf die zu Grunde liegenden Eigenschaften des Algorithmus und nicht auf den Details jeder besonderen Durchführung konzentriert. Gewöhnlich wird Pseudocode für die Analyse verwendet, weil es die einfachste und allgemeinste Darstellung ist. Jedoch, schließlich, werden die meisten Algorithmen gewöhnlich auf der besonderen Hardware / durchgeführt Softwareplattformen und ihre algorithmische Leistungsfähigkeit werden schließlich zum Test mit dem echten Code gestellt. Für die Lösung einer "einer vom" Problem kann die Leistungsfähigkeit eines particulr Algorithmus nicht bedeutende Folgen haben (wenn n groß nicht extremly ist), aber für Algorithmen, die für das schnelle interaktive, kommerzielle oder lange Leben wissenschaftlicher Gebrauch entworfen sind, kann es kritisch sein. Das Schuppen von kleinem n bis großen n stellt oft ineffiziente Algorithmen aus, die sonst gütig sind.

Empirische Prüfung ist nützlich, weil sie unerwartete Wechselwirkungen aufdecken kann, die Leistung betreffen. Abrisspunkte können verwendet werden, um sich vor/nachdem potenziellen Verbesserungen zu einem Algorithmus nach der Programm-Optimierung zu vergleichen.

FFT Beschleunigung

Um die potenziellen Verbesserungen möglich sogar in einem äußerst "gut gegründete" Algorithmen zu illustrieren, kann eine neue bedeutende Neuerung, in Zusammenhang mit FFT Algorithmen (verwendet sehr schwer im Feld der Bildverarbeitung), Verarbeitungszeiten durch einen Faktor nicht weniger als 10,000 vermindert haben. Der Einfluss dieser Beschleunigung, ermöglicht zum Beispiel, tragbaren Rechengeräten (sowie anderen Geräten), weniger Macht zu verbrauchen

Klassifikation

Es gibt verschiedene Weisen, Algorithmen, jeden mit seinen eigenen Verdiensten zu klassifizieren.

Durch die Durchführung

Eine Weise, Algorithmen zu klassifizieren, ist durch Durchführungsmittel.

• Recursion oder Wiederholung: Ein rekursiver Algorithmus ist derjenige, der anruft (spielt auf an) selbst wiederholt, bis eine bestimmte Bedingung zusammenpasst, der eine für die funktionelle Programmierung übliche Methode ist. Wiederholende Algorithmen verwenden wiederholende Konstruktionen wie Schleifen und manchmal zusätzliche Datenstrukturen wie Stapel, um die gegebenen Probleme zu beheben. Einigen Problemen wird für eine Durchführung oder den anderen natürlich angepasst. Zum Beispiel, Türme Hanois ist gut verstanden in der rekursiven Durchführung. Jede rekursive Version hat eine Entsprechung (aber vielleicht mehr oder weniger kompliziert) wiederholende Version, und umgekehrt.
• Logisch: Ein Algorithmus kann als kontrollierter logischer Abzug angesehen werden. Dieser Begriff kann als ausgedrückt werden: Algorithmus = Logik + Kontrolle. Der Logikbestandteil drückt die Axiome aus, die in der Berechnung verwendet werden können und der Kontrollbestandteil den Weg bestimmt, auf den Abzug auf die Axiome angewandt wird. Das ist die Basis für das Logikprogrammierparadigma. Auf reinen Logikprogrammiersprachen wird der Kontrollbestandteil befestigt, und Algorithmen werden durch die Versorgung nur des Logikbestandteils angegeben. Die Bitte dieser Annäherung ist die elegante Semantik: Eine Änderung in den Axiomen hat eine bestimmte Änderung im Algorithmus.
• Serien- oder parallel oder verteilt: Algorithmen werden gewöhnlich besprochen in der Annahme, dass Computer eine Instruktion eines Algorithmus auf einmal durchführen. Jene Computer werden manchmal Seriencomputer genannt. Ein für solch eine Umgebung entworfener Algorithmus wird einen Serienalgorithmus, im Vergleich mit parallelen Algorithmen oder verteilten Algorithmen genannt. Parallele Algorithmen nutzen Computerarchitekturen aus, wo mehrere Verarbeiter an einem Problem zur gleichen Zeit arbeiten können, wohingegen verteilte Algorithmen vielfache mit einem Netz verbundene Maschinen verwerten. Parallele oder verteilte Algorithmen teilen das Problem in mehr symmetrische oder asymmetrische Teilprobleme und sammeln die Ergebnisse zurück zusammen. Der Quellenverbrauch in solchen Algorithmen ist nicht nur Verarbeiter-Zyklen auf jedem Verarbeiter sondern auch die Kommunikation oben zwischen den Verarbeitern. Das Sortieren von Algorithmen kann parallelized effizient sein, aber ihre Kommunikation oben ist teuer. Wiederholende Algorithmen sind allgemein parallelizable. Einige Probleme haben keine parallelen Algorithmen, und werden von Natur aus Serienprobleme genannt.
• Deterministisch oder nichtdeterministisch: Deterministische Algorithmen beheben das Problem mit der genauen Entscheidung an jedem Schritt des Algorithmus, wohingegen nichtdeterministische Algorithmen Probleme über das Schätzen beheben, obwohl typische Annahmen genauer durch den Gebrauch der Heuristik gemacht werden.
• Genau oder ungefähr: Während viele Algorithmen eine genaue Lösung erreichen, suchen Annäherungsalgorithmen eine Annäherung, die der wahren Lösung nah ist. Annäherung kann entweder einen deterministischen oder eine zufällige Strategie verwenden. Solche Algorithmen haben praktischen Wert für viele harte Probleme.
• Quant-Algorithmus: Quant-Algorithmus läuft auf einem realistischen Modell der Quant-Berechnung. Der Begriff wird gewöhnlich für jene Algorithmen gebraucht, die von Natur aus Quant scheinen, oder eine wesentliche Eigenschaft der Quant-Berechnung wie Quant-Überlagerung oder Quant-Verwicklung verwenden.

Durch das Designparadigma

Eine andere Weise, Algorithmen zu klassifizieren, ist durch ihre Designmethodik oder Paradigma. Es gibt eine bestimmte Anzahl von Paradigmen, jeder, der vom anderen verschieden ist. Außerdem wird jede dieser Kategorien viele verschiedene Typen von Algorithmen einschließen. Einige allgemein gefundene Paradigmen schließen ein:

• Rohe Gewalt oder erschöpfende Suche. Das ist die naive Methode, jede mögliche Lösung zu versuchen, zu sehen, der am besten ist.
• Teilen Sie sich und siegen Sie. Ein Teilen und siegt Algorithmus reduziert wiederholt ein Beispiel eines Problems zu einem oder mehr kleineren Beispielen desselben Problems (gewöhnlich rekursiv), bis die Beispiele klein genug sind, um leicht zu lösen. Ein solches Beispiel dessen teilt sich und siegt ist das Verflechtungssortieren. Das Sortieren kann auf jedem Segment von Daten nach sich teilenden Daten in Segmente getan werden, und das Sortieren von kompletten Daten kann in der überwinden Phase durch das Mischen der Segmente erhalten werden. Eine einfachere Variante dessen teilt sich und siegt wird eine Abnahme genannt, und überwinden Sie Algorithmus, der ein identisches Teilproblem löst und die Lösung dieses Teilproblems verwendet, das größere Problem zu beheben. Teilen Sie sich und siegen Sie teilt das Problem in vielfache Teilprobleme, und so wird die überwinden Bühne komplizierter sein als Abnahme und Algorithmen überwinden. Ein Beispiel der Abnahme und siegt Algorithmus ist der binäre Suchalgorithmus.
• Dynamische Programmierung. Wenn ein Problem optimalen Unterbau zeigt, bedeutend, dass die optimale Lösung eines Problems von optimalen Lösungen bis Teilprobleme und überlappende Teilprobleme gebaut werden kann, bedeutend, dass dieselben Teilprobleme verwendet werden, um viele verschiedene Problem-Beispiele zu lösen, hat eine schnellere Annäherung gerufen dynamische Programmierung vermeidet, Lösungen wieder zu rechnen, die bereits geschätzt worden sind. Zum Beispiel, Algorithmus von Floyd-Warshall, kann der kürzeste Pfad zu einer Absicht von einem Scheitelpunkt in einem belasteten Graphen durch das Verwenden des kürzesten Pfads zur Absicht von allen angrenzenden Scheitelpunkten gefunden werden. Dynamische Programmierung und memoization gehen zusammen. Der Hauptunterschied zwischen der dynamischen Programmierung und teilt sich und siegt ist, dass Teilprobleme darin mehr oder weniger unabhängig sind, teilen sich und siegen, wohingegen Teilprobleme in der dynamischen Programmierung überlappen. Der Unterschied zwischen dynamischer Programmierung und aufrichtigem recursion ist im Verstecken oder memoization von rekursiven Anrufen. Wenn Teilprobleme unabhängig sind und es keine Wiederholung gibt, hilft memoization nicht; folglich ist dynamische Programmierung nicht eine Lösung für alle komplizierten Probleme. Durch das Verwenden memoization oder das Aufrechterhalten eines Tisches von Teilproblemen bereits reduziert gelöste, dynamische Programmierung die Exponentialnatur von vielen Problemen zur polynomischen Kompliziertheit.
• Die gierige Methode. Ein gieriger Algorithmus ist einem dynamischen Programmieralgorithmus ähnlich, aber der Unterschied ist, dass Lösungen der Teilprobleme in jeder Bühne nicht bekannt sein müssen; stattdessen kann eine "gierige" Wahl woraus Blicke am besten im Augenblick gemacht werden. Die gierige Methode erweitert die Lösung mit der bestmöglichen Entscheidung (nicht alle ausführbaren Entscheidungen) in einer algorithmischen Bühne, die auf dem aktuellen lokalen Optimum und der besten Entscheidung (nicht alle möglichen Entscheidungen) gestützt ist, gemacht in einer vorherigen Bühne. Es ist nicht erschöpfend, und gibt keine genaue Antwort auf viele Probleme. Aber wenn es arbeitet, wird es die schnellste Methode sein. Der populärste gierige Algorithmus findet den minimalen Überspannen-Baum, wie gegeben, durch den Baum von Huffman, Kruskal, Ordentlich, Sollin.
• Geradlinige Programmierung. Wenn man ein Problem mit der geradlinigen Programmierung behebt, wird spezifische Ungleichheit, die die Eingänge einschließt, gefunden, und dann wird ein Versuch gemacht, zu maximieren (oder zu minimieren), etwas geradlinige Funktion der Eingänge. Viele Probleme (wie der maximale Fluss für geleitete Graphen) können in einer geradlinigen Programmierung Weg festgesetzt werden, und dann durch einen 'allgemeinen' Algorithmus wie der Simplexalgorithmus gelöst werden. Eine kompliziertere Variante der geradlinigen Programmierung wird Programmierung der ganzen Zahl genannt, wo der Lösungsraum auf die ganzen Zahlen eingeschränkt wird.
• Die Verminderung. Diese Technik ist mit dem Beheben eines schwierigen Problems durch das Umwandeln davon in ein besseres bekanntes Problem verbunden, für das wir (hoffentlich) asymptotisch optimale Algorithmen haben. Die Absicht ist, einen abnehmenden Algorithmus zu finden, dessen Kompliziertheit durch den resultierenden reduzierten Algorithmus nicht beherrscht wird. Zum Beispiel schließt ein Auswahl-Algorithmus, für die Mittellinie in einer unsortierten Liste zu finden, zuerst das Sortieren der Liste (der teure Teil) ein und dann das mittlere Element in der sortierten Liste (der preiswerte Teil) herausziehend. Diese Technik ist, auch bekannt als verwandeln Sie sich und siegen Sie.
• Suche und Enumeration. Viele Probleme (wie das Spielen des Schachs) können als Probleme auf Graphen modelliert werden. Ein Graph-Erforschungsalgorithmus gibt Regeln an, für einen Graphen zu bewegen, und ist für solche Probleme nützlich. Diese Kategorie schließt auch Suchalgorithmen, Zweig und gebundene Enumeration und das Zurückverfolgen ein.

1. Algorithmen von Randomized sind diejenigen, die einige Wahlen zufällig (oder pseudozufällig) machen; für einige Probleme kann es tatsächlich bewiesen werden, dass die schnellsten Lösungen eine Zufälligkeit einschließen müssen. Es gibt zwei große Klassen solcher Algorithmen:
2. Algorithmen von Monte Carlo geben eine richtige Antwort mit der hohen Wahrscheinlichkeit zurück. Z.B. RP ist die Unterklasse von diesen, die in der polynomischen Zeit laufen)
3. Las Vegas Algorithmen geben immer die richtige Antwort zurück, aber ihre Laufzeit ist nur probabilistically gebunden z.B. ZPP.
4. In Optimierungsproblemen versuchen heuristische Algorithmen nicht, eine optimale Lösung, aber eine ungefähre Lösung zu finden, wo die Zeit oder Mittel beschränkt werden. Sie sind nicht praktisch, um vollkommene Lösungen zu finden. Ein Beispiel davon würde lokale Suche, tabu Suche, oder vorgetäuschte Ausglühen-Algorithmen, eine Klasse von heuristischen probabilistic Algorithmen sein, die die Lösung eines Problems durch einen zufälligen Betrag ändern. Der Name "hat das Ausglühen vorgetäuscht" spielt auf den metallurgischen Begriff an, der die Heizung und das Abkühlen von Metall bedeutet, Freiheit von Defekten zu erreichen. Der Zweck der zufälligen Abweichung ist, in der Nähe von allgemein optimalen Lösungen aber nicht einfach lokal optimalen, die Idee zu finden, die ist, dass das zufällige Element vermindert wird, weil sich der Algorithmus zu einer Lösung niederlässt. Annäherungsalgorithmen sind jene heuristischen Algorithmen, die zusätzlich einige Grenzen auf dem Fehler zur Verfügung stellen. Genetische Algorithmen versuchen, Lösungen von Problemen durch das Nachahmen biologischer Entwicklungsprozesse mit einem Zyklus von zufälligen Veränderungen zu finden, die aufeinander folgende Generationen von "Lösungen" nachgeben. So eifern sie mit Fortpflanzung und "Überleben des passendsten" wett. In der genetischen Programmierung wird diese Annäherung zu Algorithmen, durch die Bewertung des Algorithmus selbst als eine "Lösung" eines Problems erweitert.

Durch das Studienfach

Jedes Feld der Wissenschaft hat seine eigenen Probleme und braucht effiziente Algorithmen. Zusammenhängende Probleme in einem Feld werden häufig zusammen studiert. Einige Beispiel-Klassen sind Suchalgorithmen, Algorithmen, Verflechtungsalgorithmen, numerische Algorithmen, Graph-Algorithmen sortierend, spannen Algorithmen, rechenbetonte geometrische Algorithmen, kombinatorische Algorithmen, medizinische Algorithmen, das Maschinenlernen, die Geheimschrift, die Datenkompressionsalgorithmen und die Syntaxanalyse von Techniken.

Felder neigen dazu, mit einander zu überlappen, und Algorithmus-Fortschritte in einem Feld können diejenigen von anderem, manchmal völlig ohne Beziehung, Felder verbessern. Zum Beispiel wurde dynamische Programmierung für die Optimierung des Quellenverbrauchs in der Industrie erfunden, aber wird jetzt im Lösen einer breiten Reihe von Problemen in vielen Feldern verwendet.

Durch die Kompliziertheit

Algorithmen können durch die Zeitdauer klassifiziert werden, die sie im Vergleich zu ihrer Eingangsgröße vollenden müssen. Es gibt ein großes Angebot: Einige Algorithmen, die in der geradlinigen Zeit hinsichtlich der Eingangsgröße abgeschlossen sind, einige tun so in einer Exponentialzeitdauer oder noch schlechter, und einige hinken nie. Zusätzlich können einige Probleme vielfache Algorithmen der sich unterscheidenden Kompliziertheit haben, während andere Probleme keine Algorithmen oder keine bekannten effizienten Algorithmen haben könnten. Es gibt auch mappings von einigen Problemen bis andere Probleme. Infolge dessen, wie man fand, war es passender, um die Probleme selbst statt der Algorithmen in Gleichwertigkeitsklassen zu klassifizieren, die auf der Kompliziertheit der bestmöglichen Algorithmen für sie gestützt sind.

Burgin (2005, p. 24) verwendet eine verallgemeinerte Definition von Algorithmen, die die allgemeine Voraussetzung entspannt, dass die Produktion des Algorithmus, der eine Funktion schätzt, nach einer begrenzten Zahl von Schritten bestimmt werden muss. Er definiert eine superrekursive Klasse von Algorithmen als "eine Klasse von Algorithmen, in denen es möglich ist, durch jede Maschine von Turing nicht berechenbare Funktionen zu schätzen" (Burgin 2005, p. 107). Das ist nah mit der Studie von Methoden der Hyperberechnung verbunden.

Dauernde Algorithmen

Das "dauernde" wenn angewandte Adjektiv auf das Wort "Algorithmus" kann bedeuten:

1. Ein Algorithmus, der auf Daten funktioniert, der dauernde Mengen vertritt, wenn auch das Daten durch getrennte Annäherungen — solche Algorithmen vertreten wird, wird in der numerischen Analyse studiert; oder
2. Ein Algorithmus in der Form einer Differenzialgleichung, die unaufhörlich auf den Daten funktioniert, auf einem analogen Computer laufend.

Gesetzliche Probleme

:See auch: Software patentiert für eine allgemeine Übersicht der Patentierfähigkeit der Software einschließlich computerdurchgeführter Algorithmen.

Algorithmen, durch sich, sind nicht gewöhnlich patentfähig. In den Vereinigten Staaten, ein Anspruch, der allein aus einfachen Manipulationen von abstrakten Konzepten besteht, setzen Zahlen oder Signale "Prozesse" (USPTO 2006) nicht ein, und folglich sind Algorithmen nicht patentfähig (als in Gottschalk v. Benson). Jedoch sind praktische Anwendungen von Algorithmen manchmal patentfähig. Zum Beispiel, im Diamanten v. Diehr, die Anwendung eines einfachen Feed-Back-Algorithmus, um im Kurieren von synthetischem Gummi zu helfen, wurde patentfähig gehalten. Das Patentieren der Software ist hoch umstritten, und dort wird Patente hoch kritisiert, die Algorithmen, besonders Datenkompressionsalgorithmen wie das LZW-Patent von Unisys einschließen.

Zusätzlich haben einige kryptografische Algorithmen Exportbeschränkungen (sieh Export der Geheimschrift).

Etymologie

Das Wort "Algorithm" oder "Algorithmus" in einigen anderen Schreiben-Versionen, kommt aus dem Namen al-Khwārizmī, ausgesprochen in klassischem Arabisch als Al-Khwarithmi. Al-Khwārizmī (Persisch , c. 780-850) war ein persischer Mathematiker, Astronom, Geograph und ein Gelehrter im Haus des Verstands in Bagdad, dessen Name "den Eingeborenen von Khwarezm", eine Stadt bedeutet, die ein Teil des Größeren Irans während seines Zeitalters war und jetzt am modernen Tag Usbekistan ist, das Er einer Abhandlung auf der arabischen Sprache während des 9. Jahrhunderts geschrieben hat, das in Latein im 12. Jahrhundert laut des Titels Algoritmi de numero Indorum übersetzt wurde. Dieser Titel bedeutet "Algoritmi auf den Zahlen der Inder", wo "Algoritmi" die Latinisierung des Übersetzers des Namens von Al-Khwarizmi war. Al-Khwarizmi war der am weitesten gelesene Mathematiker in Europa im späten Mittleren Alter, in erster Linie durch sein anderes Buch, die Algebra. In spätmittelalterlichem Latein hat algorismus, der Bestechung seines Namens, einfach das "Dezimalzahl-System" bedeutet, das noch die Bedeutung des modernen englischen Algorithmus ist. In Französisch des 17. Jahrhunderts hat sich die Form des Wortes, aber nicht seine Bedeutung, zu algorithme geändert. Englisch hat die Franzosen sehr bald später angenommen, aber erst als das Ende des 19. Jahrhunderts, dass "Algorithmus" das Meinen übernommen hat, dass es in modernem Englisch hat.

Geschichte: Entwicklung des Begriffs "des Algorithmus"

Getrennte und unterscheidbare Symbole

Aufzeichnungszeichen: Um ihre Herden, ihre Säcke des Kornes und ihres Geldes nachzugehen, haben die Menschen der Antike das Übereinstimmen verwendet: Das Ansammeln von Steinen oder Zeichen hat auf Stöcken oder dem Bilden getrennter Symbole in Ton gekratzt. Durch den babylonischen und ägyptischen Gebrauch von Zeichen und Symbolen schließlich haben sich Römische Ziffern und die Rechenmaschine entwickelt (Dilson, p. 16-41). Aufzeichnungszeichen erscheinen prominent in der unären Ziffer-Systemarithmetik, die in der Maschine von Turing und Post-Turing Maschinenberechnung verwendet ist.

Manipulation von Symbolen als "Platz-Halter" für Zahlen: Algebra

Die Arbeit des alten griechischen geometers (Euklidischer Algorithmus), persischer Mathematiker Al-Khwarizmi (von dessen Namen die Begriffe "Algorithmus" und "Algorithmus" abgeleitet werden), und westeuropäische Mathematiker hat im Begriff von Leibniz der Rechnung ratiocinator (ca 1680) kulminiert:

Mechanische Vorrichtungen mit getrennten Staaten

Die Uhr: Kredite von Bolter die Erfindung der Gewicht-gesteuerten Uhr als "Die Schlüsselerfindung [Europas im Mittleren Alter]", insbesondere die Rand-Hemmung, die uns mit der Zecke und tock einer mechanischen Uhr versorgt. "Der genaue Automat" hat sofort zu "mechanischen Automaten" geführt, im 13. Jahrhundert und schließlich zu "rechenbetonten Maschinen" — der Unterschied analytische und Motormotoren von Charles Babbage und Gräfin Ada Lovelace beginnend.

Logische Maschinen 1870 — die "logische Rechenmaschine von Stanley Jevons" und "logische Maschine": Das technische Problem war, Gleichungen von Boolean, wenn präsentiert, in einer Form zu reduzieren, die dem ähnlich ist, was jetzt als Karten von Karnaugh bekannt ist. Jevons (1880) beschreibt zuerst eine einfache "Rechenmaschine" des "Gleitens von Holz, das mit Nadeln ausgestattet ist, erfunden, so dass jeder Teil oder Klasse der [logischen] Kombinationen mechanisch ausgewählt werden können... Mehr kürzlich jedoch habe ich das System auf eine völlig mechanische Form reduziert, und habe so den ganzen der indirekte Prozess der Schlussfolgerung darin aufgenommen, was genannt werden kann, ist eine Logische Maschine" Seine Maschine ausgestattet mit "bestimmten beweglichen Holzstangen" gekommen, und "am Fuß sind 21 Schlüssel wie diejenigen eines Klaviers [usw.]...". Mit dieser Maschine konnte er einen "Syllogismus oder jedes andere einfache logische Argument" analysieren.

Diese Maschine hat er 1870 vor den Gefährten der Königlichen Gesellschaft gezeigt. Ein anderer Logiker John Venn, jedoch, seinen 1881 Symbolische Logik, hat ein voreingenommenes Auge zu dieser Anstrengung gedreht: "Ich habe keine hohe Schätzung selbst vom Interesse oder der Wichtigkeit davon, was manchmal logische Maschinen genannt wird..., scheint es mir nicht, dass irgendwelche Vorrichtungen zurzeit bekannt oder wahrscheinlich, wirklich entdeckt zu werden, den Namen von logischen Maschinen verdienen"; sieh mehr bei Algorithmus-Charakterisierungen. Aber nicht übertroffen zu werden, hat er auch "einen etwas analogen Plan präsentiert, ich begreife zur Rechenmaschine von Prof. Jevon... [Und] [ein] Gewinn, entsprechend der logischen Maschine von Prof. Jevons, kann die folgende Vorrichtung beschrieben werden. Ich ziehe es vor, es bloß eine Maschine des logischen Diagramms zu nennen..., aber ich nehme an, dass es sehr völlig alles tun konnte, was jeder logischen Maschine vernünftig erwartet werden kann".

Webstuhl von Jacquard, Schlag-Karten von Hollerith, Telegrafie und Telefonie — das elektromechanische Relais: Bell und Newell (1971) zeigen an, dass sich Jacquard (1801), Vorgänger zu Hollerithkarten abzeichnen (Schlag-Karten, 1887), und "rufen an umzuschalten Technologien" waren die Wurzeln eines Baums, der zur Entwicklung der ersten Computer führt. Durch die Mitte des 19. Jahrhunderts war der Telegraf, der Vorgänger des Telefons, im Gebrauch weltweit, seiner getrennten und unterscheidbaren Verschlüsselung von Briefen als "Punkte und Spuren" ein allgemeiner Ton. Bis zum Ende des 19. Jahrhunderts war das Konfetti (ca die 1870er Jahre) im Gebrauch, wie der Gebrauch von Hollerithkarten 1890 Volkszählung der Vereinigten Staaten war. Dann ist der Fernschreiber gekommen (ca. 1910) mit seinem Gebrauch des geschlagenen Papiers von Baudot codieren auf dem Band.

Telefonschaltende Netze von elektromechanischen Relais (erfundener 1835) waren hinter der Arbeit von George Stibitz (1937), der Erfinder des beitragenden Digitalgeräts. Als er in Glockenlaboratorien gearbeitet hat, hat er den "lästigen' Gebrauch von mechanischen Rechenmaschinen mit Getrieben beobachtet. "Er ist eines Abends 1937 nach Hause gegangen vorhabend, seine Idee zu prüfen... Als das Herumbasteln zu Ende war, hatte Stibitz ein binäres beitragendes Gerät gebaut".

Davis (2000) beobachtet die besondere Wichtigkeit vom elektromechanischen Relais (mit seinen zwei "binären Staaten" offen und geschlossen):

: Es war nur mit der Entwicklung, in den 1930er Jahren elektromechanischer Rechenmaschinen mit elektrischen Relais beginnend, dass Maschinen gebaut wurden, das Spielraum habend, das sich Babbage vorgestellt hatte."

Mathematik während des 19. Jahrhunderts bis zur Mitte des 20. Jahrhunderts

Symbole und Regeln: In rascher Folge hat die Mathematik von George Boole (1847, 1854), Gottlob Frege (1879), und Giuseppe Peano (1888-1889) Arithmetik auf eine Folge von durch Regeln manipulierten Symbolen reduziert. Peano Die Grundsätze der Arithmetik, die durch eine neue Methode (1888) präsentiert ist, war "der erste Versuch eines axiomatization der Mathematik auf einer symbolischen Sprache".

Aber Heijenoort gibt Frege (1879) dieses Prestige: Frege ist "vielleicht die wichtigste einzelne in der Logik jemals geschriebene Arbeit...., in dem wir eine "'Formel-Sprache' sehen, die ein lingua characterica ist, eine mit speziellen Symbolen geschriebene Sprache, "für den reinen Gedanken", d. h. frei von rhetorischen Dekorationen, die... von spezifischen Symbolen gebaut sind, die gemäß bestimmten Regeln manipuliert werden". Die Arbeit von Frege wurde weiter vereinfacht und von Alfred North Whitehead und Bertrand Russell in ihrem Principia Mathematica (1910-1913) verstärkt.

Die Paradoxe: Zur gleichen Zeit sind mehrere störende Paradoxe in der Literatur, insbesondere das Burali-Forti Paradox (1897), das Paradox von Russell (1902-03) und das Paradox von Richard erschienen. Die resultierenden Rücksichten haben zum Papier von Kurt Gödel (1931) geführt — er zitiert spezifisch das Paradox des Lügners — der völlig Regeln von recursion zu Zahlen reduziert.

Wirksame Berechenbarkeit: Um Entscheidungsproblem definiert genau von Hilbert 1928, Mathematiker zu lösen, die zuerst in Angriff genommen sind, um zu definieren, was durch eine "wirksame Methode" oder "wirksame Berechnung" oder "wirksame Berechenbarkeit" gemeint geworden ist (d. h., eine Berechnung, die erfolgreich sein würde). In rascher Folge ist das folgende erschienen: Kirche von Alonzo, Stephen Kleene und der λ-calculus von J.B. Rosser eine fein gehonte Definition "allgemeinen recursion" von der Arbeit von Gödel, der Vorschlägen von Jacques Herbrand (vgl die Vorträge von Princeton von Gödel von 1934) und nachfolgende Vereinfachungen durch Kleene folgt. Der Beweis der Kirche, dass Entscheidungsproblem, die Definition von Emil Post der wirksamen Berechenbarkeit als ein Arbeiter unbekümmert im Anschluss an eine Liste von Instruktionen unlösbar war, sich verlassen oder direkt durch eine Folge von Zimmern zu bewegen, und während dort entweder Zeichen oder eine Zeitung löschen oder das Papier beobachten und macht ja - keine Entscheidung über die folgende Instruktion. Dessen Beweis von Alan Turing Entscheidungsproblem durch den Gebrauch sein "a-[automatisch-] Maschine" — tatsächlich fast identisch zur "Formulierung" von Post, der Definition von J. Barkley Rosser der "wirksamen Methode" in Bezug auf "eine Maschine" unlösbar war. Der Vorschlag von S. C. Kleene eines Vorgängers zur "Kirchthese", dass er "These I", und ein paar Jahre später die Umbenennung von Kleene seine These "die These der Kirche" und das Vorschlagen "der These von Turing" genannt hat.

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

Hier ist ein bemerkenswerter Zufall von zwei Männern, die nicht einander kennen, aber einen Prozess von Männern als die Computer beschreiben, die an der Berechnung arbeiten —, und sie geben eigentlich identische Definitionen nach.

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

: "... zwei Konzepte werden beteiligt: Das eines Symbol-Raums, in dem die Arbeit, die vom Problem führt zu antworten, und ein fester unveränderlicher Satz von Richtungen ausgeführt werden soll.

Sein Symbol-Raum würde sein

: "ein zwei Weg unendliche Folge von Räumen oder Kästen... Das Problem solver oder der Arbeiter sollen sich bewegen und in diesem Symbol-Raum arbeiten, dazu fähig seiend, zu sein in, und darin zu funktionieren, aber ein Kasten auf einmal.... ein Kasten soll nur zwei mögliche Bedingungen zulassen, d. h., leer oder nicht markiert seiend, und ein einzelnes Zeichen darin zu haben, einen vertikalen Schlag sagen.

: "Ein Kasten soll ausgesucht und den Startpunkt genannt werden.... ein spezifisches Problem soll in der symbolischen Form durch eine begrenzte Zahl von Kästen [gegeben d. h.,] EINGEGEBEN WERDEN, mit einem Schlag gekennzeichnet werden. Ebenfalls die Antwort [d. h., PRODUKTION] soll in der symbolischen Form durch solch eine Konfiguration von gekennzeichneten Kästen gegeben werden....

: "Eine Reihe von auf ein allgemeines Problem anwendbaren Richtungen stellt einen deterministischen Prozess, wenn angewandt, auf jedes spezifische Problem auf. Dieser Prozess wird nur enden, wenn er zur Richtung des Typs (C) [kommt d. h., HALTEN SIE] AN". Sieh mehr an der Post-Turing Maschine

Die Arbeit von Alan Turing ist der von Stibitz (1937) vorangegangen; es ist unbekannt, ob Stibitz von der Arbeit von Turing gewusst hat. Der Biograf von Turing hat geglaubt, dass der Gebrauch von Turing eines einer Schreibmaschine ähnlichen Modells auf ein junges Interesse zurückzuführen gewesen ist: "Alan hatte davon geträumt, Schreibmaschinen als ein Junge zu erfinden; Frau Turing hatte eine Schreibmaschine; und er könnte gut begonnen haben, indem er sich gefragt hat, was durch das Nennen einer Schreibmaschine 'mechanisch' gemeint geworden ist". In Anbetracht des Vorherrschens von Morsezeichen-Code und Telegrafie, Konfetti-Maschinen und Fernschreibern könnten wir vermuten, dass alle Einflüsse waren.

Turing — sein Modell der Berechnung wird jetzt genannt eine Maschine von Turing — beginnt, weil wirklich mit einer Analyse eines menschlichen Computers Dahingeeilt ist, den er zu einem einfachen Satz von grundlegenden Bewegungen und "Stimmungen" beschneidet. Aber er setzt einen Schritt weiter fort und schafft eine Maschine als ein Modell der Berechnung von Zahlen.

: "Computerwissenschaft wird normalerweise durch das Schreiben bestimmter Symbole auf Papier getan. Wir können annehmen, dass dieses Papier in Quadrate wie ein arithmetisches Buch eines Kindes geteilt wird.... Ich nehme dann an, dass die Berechnung auf eindimensionalem Papier, d. h. auf einem in Quadrate geteilten Band ausgeführt wird. Ich werde auch annehmen, dass die Zahl von Symbolen, die gedruckt werden können, begrenzt ist....

: "Das Verhalten des Computers wird jederzeit durch die Symbole bestimmt, die er, und seine "Stimmung" in diesem Moment beobachtet. Wir können annehmen, dass es einen bestimmten B zur Zahl von Symbolen oder Quadraten gibt, die der Computer in einem Moment beobachten kann. Wenn er mehr beobachten möchte, muss er aufeinander folgende Beobachtungen verwenden. Wir werden auch annehmen, dass die Zahl von Stimmungen, die in Betracht gezogen werden müssen, begrenzt ist...

: "Lassen Sie uns uns vorstellen, dass die in 'einfache Operationen durchgeführten durch den Computer aufzuteilend Operationen', die so elementar sind, dass es nicht leicht ist, sich sie weiter geteilt vorzustellen".

Die Verminderung von Turing gibt den folgenden nach:

: "Die einfachen Operationen müssen deshalb einschließen:

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

:: "(b) Änderungen von einem der Quadrate, die zu einem anderen Quadrat innerhalb von L Quadraten von einem der vorher beobachteten Quadrate beobachtet sind.

"Es kann sein, dass sich einige von diesen ändern, notwendigerweise rufen eine Änderung der Stimmung an. Die allgemeinste einzelne Operation muss deshalb genommen werden, um einer des folgenden zu sein:

:: "(A) Eine mögliche Änderung (a) des Symbols zusammen mit einer möglichen Änderung der Stimmung.

:: "(B) Eine mögliche Änderung (b) beobachteter Quadrate, zusammen mit einer möglichen Änderung der Stimmung"

: "Wir können jetzt eine Maschine bauen, um die Arbeit dieses Computers zu tun".

Ein paar Jahre später hat Turing seine Analyse (These, Definition) mit diesem kräftigen Ausdruck davon ausgebreitet:

: "Wie man sagt, ist eine Funktion "effektiv berechenbar", wenn seine Werte durch etwas rein mechanischen Prozess gefunden werden können. Obwohl es ziemlich leicht ist, einen intuitiven Griff dieser Idee zu bekommen, ist es dennoch wünschenswert, eine bestimmtere, mathematische expressible Definition zu haben... [er bespricht die Geschichte der Definition, ziemlich viel wie präsentiert, oben in Bezug auf Gödel, Herbrand, Kleene, Kirche, Turing und Post]... Wir können diese Behauptung wörtlich nehmen, durch rein mechanische Prozess-diejenige verstehend, die durch eine Maschine ausgeführt werden konnte. Es ist möglich, eine mathematische Beschreibung in einer bestimmten normalen Form der Strukturen dieser Maschinen zu geben. Die Entwicklung dieser Ideen führt zur Definition des Autors einer berechenbaren Funktion, und zu einer Identifizierung der Berechenbarkeit + mit der wirksamen Berechenbarkeit....

:: "+ werden Wir den Ausdruck "berechenbare Funktion" verwenden, um eine Funktion zu bedeuten, die durch eine Maschine berechenbar ist, und wir lassen "effektiv berechenbar" beziehen sich auf die intuitive Idee ohne besondere Identifizierung mit irgendwelchen dieser Definitionen".

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

J. Barkley Rosser hat eine 'wirksame [mathematische] Methode' auf die folgende Weise (Fettschrift hinzugefügt) definiert:

: "'Wirksame Methode' wird hier im ziemlich speziellen Sinn einer Methode verwendet, deren jeder Schritt genau bestimmt wird, und der gewiss die Antwort in einer begrenzten Zahl von Schritten erzeugen wird. Mit dieser speziellen Bedeutung sind drei verschiedene genaue Definitionen bis heute gegeben worden. [sein Kommentar #5; sieh Diskussion sofort unten]. Der einfachste von diesen um (wegen Post und Turing) festzusetzen, sagt im Wesentlichen, dass eine wirksame Methode, bestimmte Sätze von Problemen zu lösen, besteht, wenn man eine Maschine bauen kann, die dann jedes Problem des Satzes ohne menschliches Eingreifen außer dem Einfügen der Frage und (späteren) Lesen der Antwort beheben wird. Alle drei Definitionen sind gleichwertig, so ist es egal, welcher verwendet wird. Außerdem ist die Tatsache, dass alle drei gleichwertig sind, ein sehr starkes Argument für die Genauigkeit von irgend jemandem." (Rosser 1939:225-6)

Der Kommentar von Rosser #5 bringt in der Arbeit (1) Kirche und Kleene und ihre Definition von λ-definability, im Gebrauch der besonderen Kirche davon in seinem Ein Unlösbares Problem der Elementaren Zahlentheorie (1936) Verweise an; (2) Herbrand und Gödel und ihr Gebrauch von recursion im Gebrauch des besonderen Gödels in seiner berühmten Zeitung Auf Formell Unentscheidbaren Vorschlägen von Principia Mathematica und Related Systems I (1931); und (3) Posten (1936) und Turing (1936-7) in ihren Mechanismus-Modellen der Berechnung.

Stephen C. Kleene hat als seine jetzt berühmte "These I" bekannt als die Kirch-Turing-These definiert. Aber er hat das im folgenden Zusammenhang (Fettschrift im Original) getan:

: "12. Algorithmische Theorien... In der Aufstellung einer ganzen algorithmischen Theorie, was wir tun, soll ein Verfahren, performable für jeden Satz von Werten der unabhängigen Variablen beschreiben, die Verfahren notwendigerweise begrenzt und auf solche Weise, dass vom Ergebnis wir eine bestimmte Antwort, "ja" oder "nein", zur Frage lesen können, "ist der Prädikat-Wert wahr?"" (Kleene 1943:273)

Geschichte nach 1950

Mehrere Anstrengungen sind zur weiteren Verbesserung der Definition "des Algorithmus" geleitet worden, und Tätigkeit ist wegen der Problem-Umgebung, insbesondere Fundamente der Mathematik (besonders die Kirch-Turing-These) und Philosophie der Meinung (besonders Argumente um die künstliche Intelligenz) andauernd. Für mehr, sieh Algorithmus-Charakterisierungen.

Siehe auch

• Abstrakte Maschine
• Algebra von Algorithmen
• Algorithmus-Charakterisierungen
• Algorithmus-Design
• Algorithmische Leistungsfähigkeit
• Algorithmus-Technik
• Algorithmus-Beispiele
• Algorithmische Musik
• Algorithmische Synthese
• Algorithmischer Handel
• Datenstruktur
• Müll in, Müll
• Heuristik
• Wichtige Algorithmus-zusammenhängende Veröffentlichungen
• Einführung in Algorithmen
• Liste des Algorithmus allgemeine Themen
• Liste von Algorithmen
• Numerisches Mathematik-Konsortium
• Teilweise Funktion
• (Computerprogrammierung) im Profil darstellend
• Programm-Optimierung
• Algorithmus von Randomized und Quant-Algorithmus
• Das Laufen der Perle
• Theorie der Berechnung
• Berechenbarkeit (ein Teil der Berechenbarkeitstheorie)
• Rechenbetonte Kompliziertheitstheorie

Referenzen

• Axt, P. (1959) Auf einer Subrekursiven Hierarchie und Primitiven Rekursiven Graden, Transaktionen der amerikanischen Mathematischen Gesellschaft 92, Seiten 85-105
• Glocke, C. Gordon und Newell, Allen (1971), Computerstrukturen: Lesungen und Beispiele, McGraw-Hill Book Company, New York. Internationale Standardbuchnummer 0-07-004357-4}.

• Schließt eine ausgezeichnete Bibliografie von 56 Verweisungen ein.
• : vgl Turing Maschinen des Kapitels 3, wo sie "bestimmte Enumerable-Sätze nicht effektiv (mechanisch) enumerable" besprechen.
• Burgin, M. Superrekursive Algorithmen, Monografien in der Informatik, Springer, 2005. Internationale Standardbuchnummer 0-387-95569-0
• Campagnolo, M.L. Moore, C., und Costa, J.F. (2000) Eine analoge Charakterisierung der subrekursiven Funktionen. In Proc. der 4. Konferenz für Reelle Zahlen und Computer, Odense Universität, Seiten 91-109

• Nachgedruckt im Unentscheidbaren, p. 89ff. Der erste Ausdruck der "These der Kirche". Sieh in der besonderen Seite 100 (Das Unentscheidbare), wo er den Begriff der "wirksamen Berechenbarkeit" in Bezug auf "einen Algorithmus" definiert, und er das Wort verwendet, "endet" usw.

• Nachgedruckt im Unentscheidbaren, p. 110ff. Kirche zeigt, dass Entscheidungsproblem in ungefähr 3 Seiten des Textes und 3 Seiten von Kommentaren unlösbar ist.

• Davis gibt Kommentar vor jedem Artikel. Papiere von Gödel, Kirche von Alonzo, Turing, Rosser, Kleene und Emil Post werden eingeschlossen; diejenigen, die im Artikel zitiert sind, werden hier durch den Namen des Autors verzeichnet.

• Davis bietet kurze Lebensbeschreibungen von Leibniz, Boole, Frege, Kantoren, Hilbert, Gödel und Turing mit von Neumann als der Show stehlende Bengel an. Sehr kurzer bios von Joseph-Marie Jacquard, Babbage, Ada Lovelace, Claude Shannon, Howard Aiken, usw.
• Yuri Gurevich, Folgende Abstrakte Staatsmaschinenfestnahme Folgende Algorithmen, ACM Transaktionen auf der Rechenbetonten Logik, Vol 1, Nr. 1 (Juli 2000), Seiten 77-111. Schließt Bibliografie von 33 Quellen ein.

• Präsentiert der amerikanischen Mathematischen Gesellschaft, September 1935. Nachgedruckt im Unentscheidbaren, p. 237ff. Die Definition von Kleene "allgemeinen recursion" (bekannt jetzt als mu-recursion) wurde von der Kirche in seiner 1935-Zeitung Ein Unlösbares Problem der Elementaren Zahlentheorie verwendet, die das "Entscheidungsproblem" bewiesen hat um (d. h., ein negatives Ergebnis) "unentscheidbar" zu sein.

• Nachgedruckt im Unentscheidbaren, p. 255ff. Kleene hat seine Definition "allgemeinen recursion" raffiniert und ist in seinem Kapitel "12 weitergegangen. Algorithmische Theorien", um "These I" (p zu postulieren. 274); er würde später diese These (in Kleene 1952:300) wiederholen und es "die These der Kirche" (Kleene 1952:317) (d. h., die Kirchthese) nennen.

• Ausgezeichnet — zugänglich, lesbar — Bezugsquelle für mathematische "Fundamente".
• Kosovsky, N. K. Elements von Mathematischer Logik und seiner Anwendung auf die Theorie von Subrekursiven Algorithmen, LSU Publ. Leningrad, 1981
• A. A. Markov (1954) Theorie von Algorithmen. [Übersetzt von Jacques J. Schorr-Kon und PST Personal] Abdruck Moskau, Akademie von Wissenschaften der UDSSR, 1954 [d. h., Jerusalem, Programm von Israel für Wissenschaftliche Übersetzungen, 1961; verfügbar vom Büro von Technical Services, der amerikanischen Abteilung des Handels, Washington] Beschreibung 444 p. 28 Cm. Hinzugefügter t.p. in der russischen Übersetzung von Arbeiten des Mathematischen Instituts, Akademie von Wissenschaften der UDSSR, v. 42. Ursprünglicher Titel: Teoriya algerifmov. [QA248. M2943 Dartmouth Universitätsbibliothek. Amerikanische Abteilung des Handels, Büro von Technical Services, Zahl OTS 60-51085.]

• Minsky breitet sich sein "... Idee von einem Algorithmus — ein wirksames Verfahren..." im Kapitel 5.1 Berechenbarkeit, Wirksame Verfahren und Algorithmen aus. Unendliche Maschinen."

• Nachgedruckt im Unentscheidbaren, p. 289ff. Posten definiert einen einfachen algorithmischen Prozess eines Mannes, der Zeichen schreibt oder Zeichen löscht und vom Kasten bis Kasten und schließlich Halt geht, weil er einer Liste von einfachen Instruktionen folgt. Das wird von Kleene als eine Quelle seiner "These I", der so genannten Kirch-Turing-These zitiert.

• Nachgedruckt im Unentscheidbaren, p. 223ff. Hierin ist die berühmte Definition von Rosser der "wirksamen Methode": "... eine Methode, deren jeder Schritt genau vorher bestimmt wird, und der gewiss die Antwort in einer begrenzten Zahl von Schritten... eine Maschine erzeugen wird, die dann jedes Problem des Satzes ohne menschliches Eingreifen außer dem Einfügen der Frage und (späteren) Lesen der Antwort beheben wird" (p. 225-226, Das Unentscheidbare)

• Vgl insbesondere hat das erste Kapitel betitelt: Algorithmen, Turing Maschinen und Programme. Seine kurz gefasste informelle Definition: "... jede Folge von Instruktionen, denen durch einen Roboter gefolgt werden kann, wird einen Algorithmus genannt" (p. 4).
• . Korrekturen, ibd., vol. 43 (1937) Seiten 544-546. Nachgedruckt im Unentscheidbaren, p. 116ff. Das berühmte als eine Doktorarbeit eines Masters vollendete Papier von Turing während in der Universität des Königs Cambridge das Vereinigte Königreich.

• Nachgedruckt im Unentscheidbaren, p. 155ff. Das Papier von Turing, das "das Orakel" definiert hat, war seine Doktorarbeit während an Princeton die USA.
• USA-Patent- und Handelsmarke-Büro (2006), 2106.02 **> Mathematische Algorithmen: 2100-Patentierfähigkeit, Handbuch des Offenen Überprüfen-Verfahrens (MPEP). Letzter Revisionsaugust 2006

Sekundäre Verweisungen

• Internationale Standardbuchnummer 0-8078-4108-0 pbk.

• Internationale Standardbuchnummer 0 312 10409 X (pbk).

• 3. Ausgabe 1976[?], internationale Standardbuchnummer 0-674-32449-8 (pbk).

• Internationale Standardbuchnummer 0-671-49207-1. Vgl Kapitel "Der Geist der Wahrheit" für eine Geschichte führend, und eine Diskussion, sein Beweis.

Weiterführende Literatur

• Jean-Luc Chabert, Évelyne Barbin, Eine Geschichte von Algorithmen: vom Kieselstein bis den Mikrochip, Springer, 1999, internationale Standardbuchnummer 3-540-63369-3
• David Harel, Yishai A. Feldman, Algorithmics: der Geist der Computerwissenschaft, Ausgabe 3, Ausbildung von Pearson, 2004, internationale Standardbuchnummer 0-321-11784-0
• Knuth, Donald E. (2000). Ausgewählte Papiere auf der Analyse von Algorithmen. Stanford, Kalifornien: Zentrum für die Studie der Sprache und Information.
• Knuth, Donald E. (2010). Ausgewählte Papiere auf dem Design von Algorithmen. Stanford, Kalifornien: Zentrum für die Studie der Sprache und Information.
• David Berlinski, Das Advent des Algorithmus: Die 300-jährige Reise von einer Idee bis den Computer, die Seemann-Bücher, 2001, internationale Standardbuchnummer 978-0156013918

Außenverbindungen

• Wörterbuch von Algorithmen und Datenstrukturen — nationales Institut für Standards und Technologie
• Algorithmen und Datenstrukturen durch Dr Nikolai Bezroukov

Algorithmus-Behältnisse

• Das steinige Bach-Algorithmus-Behältnis — staatliche Universität New Yorks am steinigen Bach
• Bibliothek von Efficient Datastructures und Algorimths (LEDA) — vorher von Max-Planck-Institut für Informatik
• Netlib Behältnis — Universität des Tennessees und Eiche-Kamms nationales Laboratorium
• Gesammelte Algorithmen des ACM — Vereinigung, um Maschinerie zu schätzen
• Der Stanford GraphBase — Universität von Stanford
• Combinatorica — Universität Iowas und staatliche Universität New Yorks am steinigen Bach

Vortrag bemerkt

• Algorithmus-Kurs-Materialien. Jeff Erickson. Universität Illinois.