Algorithmus - Algorithm


Aus Wikipedia, der freien Enzyklopädie

Flussdiagramm eines Algorithmus ( Euklidischen Algorithmus ) zum Berechnen des größten gemeinsamen Teiler (ggT) von zwei Zahlen a und b in Orten benannt A und B geht der Algorithmus durch sukzessive Subtraktionen in zwei Schleifen: Wenn der Test B ≥ A liefert „Ja“ (oder wahr) (genauer gesagt die Anzahl b in Position B größer oder gleich der Zahl a in Position A) THEN gibt der Algorithmus B ← B - A (dh die Zahl b - a ersetzt die alte b ). In ähnlicher Weise , wenn A> B, dann ein ← A - B. Der Prozess endet , wenn (der Inhalt) B 0, (abgeleitet Algorithmus aus Scott 2009: 13; Symbolen und Zeichenstil von Tausworthe 1977) , die in GCD A. Nachgeben .

In Mathematik und Informatik , ein Algorithmus ( / æ l ɡ ə r ɪ ð əm /  ( hören )Über diesen Sound ) ist eine eindeutige Angabe , wie eine Klasse von Problemen zu lösen. Algorithms durchführen kann Kalkulation , Datenverarbeitung und automatisierte Argumentation Aufgaben.

Als ein wirksames Verfahren kann ein Algorithmus innerhalb einer endlichen Menge von Raum und Zeit und in einer wohldefinierten formalen Sprache zur Berechnung eine exprimiert wird Funktion . Ausgehend von einem anfänglichen Zustand und Anfangs-Eingang (möglicherweise leeren ) beschreiben die Anweisungen , um eine Berechnung , die, wenn ausgeführt , was schließlich die Herstellung von „output“ und endet bei einem End - Endzustand durch eine endliche Anzahl von gut definierten aufeinanderfolgenden Zuständen fort. Der Übergang von einem Zustand in den nächsten ist nicht notwendigerweise deter ; einige Algorithmen, wie bekannt randomisierte Algorithmen , integrieren Zufallseingabe.

Der Begriff des Algorithmus hat seit Jahrhunderten. Griechischen Mathematiker verwendeten Algorithmen in zum Beispiel das Sieb des Eratosthenes für Primzahlen zu finden und den euklidischen Algorithmus für die Suche nach größten gemeinsamen Teiler von zwei Zahlen.

Das Wort Algorithmus selbst stammt aus dem 9. Jahrhundert Mathematiker Al-Chwarizmi , latinisiert Algoritmi . Eine partielle Formalisierung von dem, was das modernen Konzept des Algorithmus werden würde begann mit Versuchen , die zu lösen Entscheidungsproblem (Entscheidungsproblem) durch stellte Hilbert 1928. Später Formalisierung wurden als Versuche eingerahmt „zu definieren wirksame Berechenbarkeit “ oder „effektive Methode“. Diese Formalisierung gehörte die Gödel - Herbrand - Kleene rekursiven Funktionen von 1930, 1934 und 1935, Alonzo Church 's Lambda - Kalkül von 1936, Emil hochladen s Formulierung 1 von 1936 und Alan Turing ‚s Turingmaschinen von 1936 bis 1937 und 1939.

Etymologie

Das Wort ‚Algorithmus‘ hat seinen Ursprung in latinizing den Namen des Al-Chwarizmi in einem ersten Schritt Algorismus . Al-Khwarizmi ( persisch : خوارزمی ., C 780-850) war ein persischer Mathematiker, Astronom , Geograph und Wissenschaftler im Haus der Weisheit in Bagdad , dessen Name bedeutet ‚die gebürtige Khwarezm ‘, eine Region , die Teil war von größer Iran und ist jetzt in Usbekistan .

Über 825, schrieb al-Khwarizmi eine arabische Sprache Abhandlung über das indisch-arabische Zahlensystem , das in übersetzt wurde Latein während des 12. Jahrhunderts unter dem Titel Algoritmi de numero Indorum . Dieser Titel bedeutet „Algoritmi auf die Zahlen der Indianer“, wobei „Algoritmi“ , war die des Übersetzers Latinisierung von Al-Khwarizmi Namen. Al-Khwarizmi war das am meisten gelesene Mathematiker in Europa im späten Mittelalter, vor allem durch eine anderen seine Bücher, die Algebra . In spätmittelalterlichen Latein, Algorismus , Englisch ‚ Algorithmus ‘, der Korruption seines Namens gemeint einfach die „Dezimalzahl - System“. Im 15. Jahrhundert, unter dem Einfluss der griechischen Wort ἀριθμός ‚Zahl‘ ( vgl ‚Arithmetik‘) wurde das lateinische Wort verändert Algorithmus und der entsprechenden englischen Begriff ‚Algorithmus‘ wird erstmals im 17. Jahrhundert bezeugt; der moderne Sinn wurde im 19. Jahrhundert eingeführt.

Im Englischen wurde es zuerst in etwa 1.230 und dann benutzt Chaucer in 1391 Englisch nahm die Französisch Begriff, aber es war nicht bis zum Ende des 19. Jahrhunderts , die „Algorithmus“ übernahm die Bedeutung , dass es in der modernen englischen aufweist.

Eine weitere frühe Verwendung des Begriffs ist aus dem Jahr 1240, in einem manuellen betitelten Carmen de Algorismo komponiert von Alexandre de Villedieu . Es beginnt so:

HAEC Algorismus ars Praesenz dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

das heißt übersetzt:

Algorithmus ist die Kunst, mit denen wir gegenwärtig jene indischen Zahlen verwenden, die Nummer zwei mal fünf.

Das Gedicht ist ein paar hundert Zeilen lang und fasst die Kunst mit dem neuen Stil der Inder Würfel berechnet wird, oder Talibus Indorum oder Hindu Zeichen.

informelle Definition

Eine informelle Definition könnte „eine Reihe von Regeln, die genau eine Folge von Operationen definiert“ sein. das würde alle Computerprogramme, einschließlich der Programme, die keine numerischen Berechnungen durchführen. Im Allgemeinen ist ein Programm nur ein Algorithmus, wenn es schließlich stoppt.

Ein prototypisches Beispiel für einen Algorithmus ist der euklidische Algorithmus den maximalen gemeinsamen Teiler zweier ganzer Zahlen zu bestimmen; ein Beispiel (es gibt auch andere) von dem beschriebenen Flussdiagramm oberhalb und als Beispiel in einem späteren Abschnitt.

Boolos, Jeffrey & 1974 1999 bietet eine informelle Bedeutung des Wortes im folgende Zitat:

Kein Mensch kann schnell genug schreiben, oder lange genug oder klein genug † († „kleine grenzenlos ... Sie würden versuchen , auf Moleküle zu schreiben, an den Atomen, an Elektronen“) alle Mitglieder einer zur Liste abzählbar unendliche gesetzt durch ihre Namen auszuschreiben, einer nach der anderen, in gewisser Notation. Aber die Menschen können etwas gleichermaßen nützlich, im Falle bestimmter abzählbar unendlichen Mengen tun: Sie können geben explizite Anweisungen zur Bestimmung des n - ten Element des Satzes für beliebige endliche n . Solche Befehle sind sehr explizit angegeben werden, bei dem in einer Form , sie von einer Rechenmaschine folgen könnte , oder von einem Menschen, der nur von der Durchführung der Lage ist , sehr elementare Operationen auf Zeichen.

Ein „abzählbar unendliche Menge“ ist derjenige , dessen Elemente mit den ganzen Zahlen stellen in einer Eins-zu-Eins - Beziehung werden kann. So Boolos und Jeffrey sagen , dass ein Algorithmus Anweisungen für ein Verfahren impliziert , dass Ausgang ganze Zahlen von einem „schafft“ willkürlich „input“ integer oder ganze Zahlen, die in der Theorie, kann beliebig groß sein. Auf diese Weise kann ein Algorithmus eine algebraische Gleichung, wie Be y = m + n zwei willkürlich „input variables“ - m und n , die einen Ausgang erzeugen , y . Aber verschiedene Autoren versuchen , den Begriff zu definieren , zeigen an, dass das Wort impliziert , viel mehr als das, was in der Größenordnung von (für die Zugabe Beispiel):

Ein genaue Anleitung (in der Sprache von „Computern“ zu verstehen) für einen schnellen, effizienten, „gut“ Prozess, der die „bewegt“ von „Computer“ spezifiziert (Maschine oder Menschen, ausgestattet mit dem notwendigen enthielt interne Information und Fähigkeiten) zu finden , zu dekodieren und dann Vorgang willkürlich Eingang Ganzzahlen / Symbole m und n , Symbole + und = ... und „wirkungsvoll “ produzieren, in einem „vernünftigen“ -Zeit, ausgang ganzer Zahl y an einem bestimmten Ort und in einem angegebenen Format.

Das Konzept des Algorithmus wird auch benutzt , um die Idee zu bestimmen decidability . Dieser Begriff ist zentral zur Erläuterung , wie formalen Systeme erben von einer kleinen Gruppe von Ausgang seine Axiomen und Regeln. In Logik , dass die Zeit ein Algorithmus nicht mess abgeschlossen erfordert, da es anscheinend nicht zu unserer gewohnten physischen Dimension verwendet ist. Ab solche Unsicherheiten, die laufenden Arbeiten prägen, dämmt die Nichtverfügbarkeit einer Definition des Algorithmus , der sowohl konkret (in gewissem Sinne) und abstrakte Verwendung des Begriffs entspricht.

Formalisierung

Algorithmen sind auf dem Weg Computer Prozessdaten von wesentlicher Bedeutung. Viele Computer - Programme enthalten Algorithmen , die die konkreten Anweisungen ein Computer (in einer bestimmten Reihenfolge) durchführen soll eine bestimmte Aufgabe zu übernehmen, wie Mitarbeiter paychecks oder Druck Schüler Zeugnisse berechnet wird . Somit kann ein Algorithmus eine beliebige Abfolge von Vorgängen betrachtet werden , die von einem simuliert werden kann Turing-complete Systems. Autoren , die diese These behaupten umfassen Minsky (1967), Savage (1987) und Gurevich (2000):

Minsky: „Wir werden aber auch pflegen, mit Turing, dass jedes Verfahren, das könnte...‚‘Natürlich wirksame genannt werden kann, kann in der Tat durch eine (einfache) Maschine realisiert wird zwar extreme klingen mag, die Argumente... . zu ihren Gunsten sind schwer zu widerlegen“.

Gurevich: „... Turings informelles Argument für seine These begründet eine stärkere These: Jeder Algorithmus kann durch eine Turing-Maschine simuliert wird ... nach Savage [1987], ein Algorithmus ist ein Rechenvorgang durch eine Turing-Maschine definiert“ .

Typischerweise wird , wenn ein Algorithmus mit Verarbeitungsinformationen zugeordnet ist, Daten von einer Eingabequelle, geschrieben an ein Ausgabegerät und gespeichert zur weiteren Verarbeitung ausgelesen werden. Die gespeicherten Daten werden als Teil des internen Zustands der Einheit betrachtet , den Algorithmus durchführt. In der Praxis wird der Zustand in einem oder mehreren gespeicherten Datenstrukturen .

Für einige solcher Rechenprozess muss der Algorithmus rigoros definiert werden: in der Art und Weise festgelegt es in allen möglichen Umständen gilt, die entstehen könnten. Das heißt, jede bedingte Schritte müssen systematisch behandelt werden, von Fall zu Fall; die Kriterien für jeden Fall muss klar (und berechenbar) sein.

Da ein Algorithmus eine exakte Liste der genauen Schritte ist, ist die Reihenfolge der Berechnung für das Funktionieren des Algorithmus stets von entscheidender Bedeutung. Anweisungen werden angenommen , dass in der Regel explizit aufgeführt werden, und als Ausgang „von oben“ und gehen „bis auf den Boden“, eine Idee beschrieben , die von mehr formal beschrieben Ablauf der Steuerung .

Bis jetzt diese Diskussion über die Formalisierung eines Algorithmus hat die Geschäftsräume des angenommenen imperative . Dies ist die allgemeinste Konzeption, und es versucht , eine Aufgabe in diskreten „mechanischen“ Mitteln zu beschreiben. Einzigartig in dieser Auffassung von formalisierten Algorithmen ist die Zuweisungsoperation , um den Wert einer Variablen zu setzen. Es leitet sich aus der Anschauung des „ Speicher “ als Notizblock. Es ist ein Beispiel unter einer solchen Zuordnung.

Für einige alternative Vorstellungen von dem, was stellt einen Algorithmus sehen funktionale Programmierung und Programmlogik .

exprimierenden Algorithmen

Algorithmen kann in vielen Arten von Notation, darunter zum Ausdruck gebracht werden , die natürlichen Sprachen , Pseudo - Code , Flußdiagramme , drakon-Tabellen , Programmieren Sprachen oder Steuertabellen (bearbeitet von Dolmetschern ). Natürlichsprachlicher Ausdrücke von Algorithmen sind in der Regel ausführliche und zweideutig zu sein, und sind für komplexe oder technische Algorithmen selten verwendet. Pseudo - Code, Flussdiagramme, drakon-Grafiken und Steuertabellen sind strukturierte Wege Algorithmen zum Ausdruck bringen , dass viele der Mehrdeutigkeiten häufig in natürlicher Sprache Aussagen zu vermeiden. Programmieren Sprachen sind für die Expression von Algorithmen in einer Form , in erster Linie , die von einem Computer ausgeführt werden kann , werden jedoch oft als eine Möglichkeit zur Definition oder Dokumente - Algorithmen.

Es gibt eine Vielzahl von Darstellungen möglich , und man kann ein gegebene auszudrücken Turing Maschine Programm als eine Folge von Maschinen-Tabellen (siehe mehr bei endlichen Automaten , Zustandsübergangstabelle und die Steuertabelle ), wie Flußdiagramme und drakon-Tabellen (siehe mehr unter Zustandsdiagramm ) oder als eine Form von rudimentären Maschinencode oder Assembler - Code „Sets von Quadrupel“ genannt (siehe mehr bei Turing Maschine ).

Darstellungen von Algorithmen lassen sich in drei akzeptiert Ebene Turing-Maschine Beschreibung eingestuft werden:

1 High-Level-Beschreibung
„... Prosa, einen Algorithmus zu beschreiben, die Details der Implementierung zu ignorieren. Auf dieser Ebene wir brauchen nicht zu erwähnen, wie die Maschine ihre Band oder Kopf schafft.“
2 Umsetzung Beschreibung
„... Prosa verwendet, um die Art und Weise die Turing-Maschine verwendet, um seinen Leiter und die Art und Weise zu bilden, dass sie Daten auf dem Band gespeichert werden. Auf dieser Ebene geben wir keine Einzelheiten über Zustände oder Übergangsfunktion.“
3 Formale Beschreibung
Detaillierteste „untersten Ebene“, gibt die „Zustandstabelle“ der Turing-Maschine.

„In m + n“ für ein Beispiel des einfachen Algorithmus in allen drei Ebenen beschrieben, siehe Algorithmus # Beispiele .

Design

Algorithm Design bezieht sich auf ein Verfahren oder mathematisches Verfahren zur Problemlösung und Ingenieur Algorithmen. Das Design von Algorithmen ist Bestandteil vieler Lösung Theorien der Bedienung Forschung , wie dynamischer Programmierung und Teile-und-herrsche . Techniken für die Gestaltung und Umsetzung Algorithmus Designs sind außerdem Algorithmus Entwurfsmuster, wie die Template - Methode Muster und Dekorateur Muster genannt.

Eines der wichtigsten Aspekte des Algorithmus Design schafft einen Algorithmus, der eine effiziente Laufzeit hat, auch seine bekannten Big O .

Typische Schritte in der Entwicklung von Algorithmen:

  1. Problem Definition
  2. Entwicklung eines Modells
  3. Die Angabe des Algorithmus
  4. Gestaltung eines Algorithmus
  5. Überprüfung der Richtigkeit des Algorithmus
  6. Analyse-Algorithmus
  7. Implementierung des Algorithmus
  8. Programmtest
  9. Dokumentationsvorbereitung

Implementierung

Logical NAND - Algorithmus elektronisch implementiert in 7400 - Chip

Die meisten Algorithmen sollen als umgesetzt werden Computerprogramme . Jedoch sind Algorithmen auch mit anderen Mitteln realisiert, beispielsweise in einem Neuronales Netz (beispielsweise das menschliche Gehirn Umsetzung arithmetische oder ein Insektes der Suche nach Nahrung), in einer elektrischen Schaltung oder in einer mechanischen Vorrichtung.

Computer-Algorithmen

Flussdiagramm Beispiele für die kanonischen Böhm-Jacopini Strukturen : die Folge (Rechtecke absteigende Seite), der WHILE-DO und der IF-THEN-ELSE. Die drei Strukturen des primitiven bedingten GOTO (hergestellt IF Test = true THEN GOTO Schritt xxx ) (ein Diamant), die unbedingte GOTO (Rechteck), verschiedener Zuweisungsoperator (Rechteck) und HALT (Rechteck). Verschachtelung dieser Strukturen innerhalb Zuweisungsblöcke resultiert in komplexen Schaltbildern (CF Tausworthe 1977 100.114).

In Computersystemen ist ein Algorithmus im Grunde genommen eine Instanz von Logik in der Software durch die Software - Entwickler geschrieben, für die vorgesehenen „target“ Computer wirksam zu sein (e) zu erzeugen Ausgang von bestimmtem (möglicherweise null) Eingang . Ein optimaler Algorithmus, auch in alter Hardware läuft, erzeugen würde schnellere Ergebnisse als ein nicht-optimale (höhere Zeitkomplexität ) Algorithmus für den gleichen Zweck, in effizienter Hardware läuft; das ist , warum Algorithmen, wie Computer - Hardware, berücksichtigt Technologie.

„Elegant“ (kompakt) Programme, „gut“ (fast) Programme : Der Begriff der „Einfachheit und Eleganz“ erscheinen formlos in Knuth und genau in Chaitin :

Knuth:..“.Wir wollen gut ...... Algorithmen in einigem losen ästhetischen Sinne definierte Ein Kriterium ist die Länge der Zeit, um den Algorithmus auszuführen .. Weitere Kriterien sind die Anpassungsfähigkeit des Algorithmus zu Computern, seine Einfachheit und Eleganz , usw"
Chaitin: „.. Ein Programm‚elegant‘, womit ich meine, dass es das kleinstmögliche Programm ist für die Herstellung des Ausgangs, dass es funktioniert“

Chaitin Vorworte seine Definition mit: „Ich zeige Ihnen nicht beweisen kann , dass ein Programm‚elegant “ -such ein Beweis der lösen würde Halting Problem (ebenda).

Algorithmus im Vergleich Funktion berechenbar durch einen Algorithmus : Für eine gegebene Funktion können mehrere Algorithmen existieren. Dies gilt auch ohne den verfügbaren Befehlssatz zur Verfügung, die Programmierer zu erweitern. Rogers stellt fest , dass „Es ist... Wichtiges zwischen den Begriffen zu unterscheiden Algorithmus , dh Verfahren und den Begriff der Funktion berechenbar durch Algorithmus , dh Kartierung ergab durch Verfahren. Die gleiche Funktion mehrere verschiedene Algorithmen können“.

Leider kann ein Kompromiss zwischen der Güte (Geschwindigkeit) und Eleganz (Kompaktheit) seinem -an elegantes Programm mehr Schritte unternehmen kann eine Berechnung als ein weniger eleganten zu. Ein Beispiel, das euklidische Algorithmus verwendet erscheint unten.

Rechner (und computors), Berechnungsmodelle : ein Computer (oder human „computor“) ist eine eingeschränkte Art von Gerät, eine „diskrete deterministische mechanische Vorrichtung“, der seine Anweisungen blind folgt. Melzak ist und Lambek primitive Modelle dieser Idee zu vier Elementen reduziert: (i) diskrete, unterscheidbare Ziele , (ii) diskreter, ununterscheidbar Zähler (iii) ein Agens, und (iv) eine Liste von Anweisungen, die wirkungsvoll in Bezug auf die Fähigkeit der Agent.

Minsky beschreibt eine sympathische Variation von Lambek des „Abakus“ -Modell in seinem „Very Simple Bases für Berechenbarkeit “. Minsky der Maschine geht sequentiell durch seine fünf (oder sechs, je nachdem wie man counts) Anweisungen, soweit nicht entweder ein bedingtes IF-THEN GOTO oder ein bedingungsloses GOTO änderten Programm fließt außerhalb der Reihenfolge. Neben HALT beinhaltet Minsky der Maschine drei Zuweisungs (Ersatz, Substitution) -Operationen: ZERO (zB der Inhalt des Speicherplatzes ersetzt durch 0: L ← 0), SUCCESSOR (zB L ← L + 1), und Dekrementieren (zB L ← L - 1 ). In seltenen Fällen muss ein Programmierer schreiben „Code“ mit einer solchen beschränkten Befehlssatz. Aber Minsky zeigt (ebenso wie Melzak und Lambek) , dass seine Maschine Turing komplett mit nur vier allgemeinen Arten von Anweisungen: bedingten GOTO, unbedingtem GOTO, Zuordnung / Ersatz / Substitution und HALT.

Simulation eines Algorithmus: Computer (computor) Sprache : Knuth rät den Leser , dass „.. Der beste Weg , einen Algorithmus zu lernen , ist es zu versuchen , sofort nimmt Stift und Papier und arbeitet durch ein Beispiel“. Aber was ist mit einer Simulation oder Ausführung von der Realität? Der Programmierer muss den Algorithmus in eine Sprache übersetzen , die der Simulator / Computer / computor kann effektiv auszuführen. Stein gibt ein Beispiel dafür: Wenn die Wurzeln einer quadratischen Gleichung Berechnung der computor muss wissen , wie eine Wurzel zu nehmen. Tun sie dies nicht, so wird der Algorithmus, um wirksam zu sein, muss eine Reihe von Regeln sorgen für eine radizierend.

Das bedeutet, daß der Programmierer muß eine „Sprache“ kennen, die auf das Zielcomputermittel (Computer / computor) wirksame relatives ist.

Aber welches Modell sollte für die Simulation verwendet werden? Van Emde Boas stellt fest , „auch wenn wir uns stützen Komplexitätstheorie auf abstrakte statt Beton Maschinen, Beliebigkeit der Wahl eines Modells verbleibt. Es ist an dieser Stelle , dass der Begriff der Simulation gelangt“. Wenn die Geschwindigkeit gemessen wird, gesetzt die Anweisung Sachen. Zum Beispiel würde ausführt der Programmteil in Euklids Algorithmus den Rests zu berechnen wesentlich schneller , wenn der Programmierer eine „mußte Modulus “ Anweisung eher verfügbar als nur Subtraktion (oder noch schlimmer: nur Minsky „Abnahme“).

Strukturierte Programmierung, kanonische Strukturen : Pro die Church-Turing - These kann jeder Algorithmus durch ein Modell berechnet wird bekannt sein Turing vollständig und pro Minsky Vorführungen, erfordert Turing Vollständigkeit nur vier Befehlstypen-bedingten GOTO, bedingungslose GOTO, aufgabe, HALT. Kemeny und Kurtz bemerken , dass zwar „undiszipliniert“ Einsatz von unbedingten GOTOs und bedingten IF-THEN GOTOs in „ zur Folge haben kann Spaghetti - Code “, ein Programmierer strukturierte Programme nur diese Anweisungen mit schreiben kann; auf der anderen Seite „ist es auch möglich, und nicht zu hart, zu schlecht strukturierten Programme in einer strukturierten Sprache zu schreiben“. Tausworthe erweitert die drei Böhm-Jacopini kanonische Strukturen : FOLGE, IF-THEN-ELSE und while-do, zwei weitere: DO-WHILE und CASE. Ein weiterer Vorteil eines strukturierten Programms ist , dass es sich verleiht Beweise Korrektheits mit vollständiger Induktion .

Canonical Flussdiagramm Symbole : Die grafischen aide genannt Flussdiagramm , bieten eine Art und Weise zu beschreiben und zu dokumentieren , einen Algorithmus (und ein Computer - Programm von einem). Wie der Programmablauf einer Minsky Maschine beginnt ein Ablaufdiagramm , immer am Anfang einer Seite und fährt nach unten. Seine Primär Symbole sind nur vier: das gerichtete Pfeil zeigt , das Strömungs, das Rechteck (Reihenfolge, GOTO), der Diamant (IF-THEN-ELSE), und der Punkt (OR-Bindung). Die Böhm-Jacopini kanonische Strukturen dieser primitiven Formen. Sub-Strukturen können „Nest“ in Rechtecke, aber nur dann , wenn ein einzelner Ausstieg aus dem Überbau auftritt. Die Symbole, und ihre Verwendung , die kanonischen Strukturen aufzubauen sind in dem Diagramm gezeigt.

Beispiele

Algorithm Beispiel

Eine Animation des quicksort Algorithmus eine Reihe von randomisierten Werte zu sortieren. Die roten Balken markieren das Drehelement; zu Beginn der Animation wird das Element am weitesten nach rechts als Drehpunkt gewählt.

Eine der einfachsten Algorithmen ist die größte Zahl in einer Liste von Nummern von willkürlicher Reihenfolge zu finden. die Lösung zu finden, erfordert bei jeder Nummer in der Liste suchen. Daraus folgt einen einfachen Algorithmus, der in einer High-Level-Beschreibung in englischer Prosa angegeben werden kann, wie:

High-Level-Beschreibung:

  1. Gibt es keine Zahlen in der Menge sind dann gibt es keine höchste Zahl.
  2. Angenommen, die erste Zahl in der Reihe die größte Zahl in der Reihe ist.
  3. Für jede verbleibende Zahl im Set: Wenn diese Zahl größer ist als die derzeit größte Zahl ist, sollten Sie diese Zahl die größte Zahl in der Menge sein.
  4. Gibt es keine Zahlen übrig in dem Satz über die Iteration, sollten Sie die aktuelle Nummer größten die größte Anzahl des Satzes sein.

(Quasi-) formale Beschreibung: Written in Prosa , aber viel näher an die High-Level - Sprache von einem Computer - Programm, das im Anschluss an der formellere Codierung des Algorithmus in Pseudo - Code oder Pidgin Code :

Algorithm LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest
  • „←“ bezeichnet Zuordnung . Zum Beispiel : „ größteArtikel bedeutet“ , dass der Wert der größten Veränderungen den Wert von Artikel .
  • Return “ beendet den Algorithmus , und gibt den folgenden Wert.

Euklids Algorithmus

Das Beispiel-Diagramm von Euklids Algorithmus von TL Heath (1908), mit mehr Details hinzugefügt. Euclid geht nicht über eine dritte Messung und gibt keine numerischen Beispiele. Nicomachus gibt das Beispiel von 49 und 21: „Ich habe die weniger von der größeren subtrahieren; 28 übrig ist, dann erneut I davon subtrahieren, um die 21 gleich (für diese möglich ist), 7 übrig; I dies aus 21 subtrahieren, 14 linken, von dem ich wieder 7 subtrahieren (hierzu ist möglich), 7 verbleibt, aber kann nicht von 7 7 abgezogen werden“ Heath kommentiert, dass „Der letzte Satz ist merkwürdig, aber die Bedeutung der es liegt auf der Hand, wie auch die Bedeutung des Ausdrucks über Endung‚auf ein und derselben Zahl‘.“ (Heath 1908: 300).

Euclid ‚s Algorithmus die berechnen größten gemeinsamen Teiler (GCD) auf zwei Zahlen erscheint als Proposition II in Buch VII (‚Elementare Zahlentheorie‘) seine Elemente . Euclid wirft das Problem auf diese Weise: „zwei Zahlen Anbetracht nicht prim zueinander, zu ihrem größten gemeinsamen Maße zu finden“. Er definiert „A number [um] eine Vielzahl aus Einheiten“: a Zählnummer, eine positive ganze Zahl einschließlich Null. Zu „messen“ , ist eine kürzere Meßlänge zu platzieren s sukzessive ( Q - mal) längs längere Länge L , bis der verbleibende Teil r kleiner ist als die kürzere Länge s . In modernen Worten Rests r = l - F x s , q ist , um die Quotienten oder Rest r ist der „modulus“, der Ganzzahl-Bruchteil nach dem Teilungs übrig.

Für Euklidischen Verfahren erfolgreich zu sein, müssen die Anfangslängen zwei Anforderungen erfüllen: (i) die Längen nicht gleich Null sein muss, und (ii) die Subtraktion muß „richtige“ sein; dh, muss ein Test garantieren, dass der kleinere der beiden Zahlen von den größeren subtrahiert wird (alternativ können die beide gleich sein, damit ihre Subtraktions Ausbeuten Null).

Euklids original Beweis fügt eine dritte Forderung: die beiden Längen nicht zueinander Primzahl sein muss. Euclid vereinbarten dies so , dass er ein Konstrukt kann ad absurdum Beweis dafür , dass die gemeinsame Maßnahme ist die in der Tat zwei Zahlen grössten . Zwar Nicomachus Algorithmus der gleiche wie Euklid ist, wenn die Zahlen zueinander prim sind, liefert es die Zahl ‚1‘ für ihre gemeinsame Maßnahme. Also, um genau zu sein, ist die folgende wirklich Nikomachos Algorithmus.

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

Computersprache für Euklids Algorithmus

Nur ein paar Anweisung Typen erforderlich Euklids Algorithmus-einige logischen Tests (bedingter GOTO), unbedingter GOTO, Zuweisung (Ersatz) und Subtraktion auszuführen.

  • Ein Standort wird durch Großbuchstaben (n), beispielsweise S, A symbolisiert etc.
  • Die variierende Menge (Anzahl) in einer Position ist , in Kleinbuchstaben (e) und ( in der Regel) schriftlich mit der Lage des Namen zugeordnet. Zum Beispiel, Standort L am Anfang könnte die Zahl enthält l = 3009.

Ein unelegantes Programm für Euklidalgorithmus

„Unelegant“ ist eine Übersetzung von Knuth-Version des Algorithmus mit einem Subtraktions-basierten Rest-Loop seine Verwendung von Teilungs ersetzt (oder einem „Modul“ Befehl). Abgeleitet von Knuth 1973: 2-4. In Abhängigkeit von den beiden Zahlen „unelegant“ kann die GCD in weniger Schritten als „eleganten“ berechnen.

Der folgende Algorithmus als Knuth Vier-Stufen - Version von Euklids und Nikomachos eingerahmt ist, sondern vielmehr als Division mit dem Rest zu finden, verwendet er sukzessive Subtraktionen der kürzeren Länge s von der verbleibenden Länge r bis r kleiner als ist s . Die High-Level - Beschreibung, in Fettdruck gezeigt, wird von Knuth 1973 adaptiert: 2-4:

INPUT :

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

E0: [Stellen Sie sicher , rs .]

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

E1: [Finden restlichen] : Bis die verbleibende Länge r in R kleiner als die kürzere Länge ist n in S, wiederholt die Maßzahl subtrahieren n in S von der restlichen Länge r in R.

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

E2: [Ist der Rest Null?] : Entweder (i) die letzte Maßnahme war genau, der Rest in R Null ist , und das Programm kann halt, oder (ii) der Algorithmus muss weiterhin: die letzte Maßnahme einen Rest in R links weniger als Zahl in S. Mess

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

E3: [Tausch s und r ] : Die Mutter von Euklids Algorithmus. Verwenden restlich r zu messen , was zuvor kleinere Anzahl s ; L dient als temporären Speicherort.

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

OUTPUT :

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

DONE :

16 HALT, END, STOP.

Ein elegantes Programm für Euklids Algorithmus

Die folgende Version von Euklids Algorithmus benötigt nur sechs Kerne Anweisungen zu tun , was Dreizehn durch „unelegant“ tun erforderlich; schlimmer noch, „unelegant“ erfordert mehr Arten von Anweisungen. Das Flussdiagramm von „Elegante“ kann am Anfang dieses Artikels zu finden. In der (unstrukturierte) Basic - Sprache werden die Schritte gezählt, und die Anweisung ist die Zuordnungsanweisung durch ← symbolisiert. LET [] = []

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

Die folgende Version kann mit Object Oriented Sprachen verwendet werden:

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

Wie "elegante" arbeitet : Anstelle eines äußeren "Euclid Loop", "elegante" verschiebt sich hin und her zwischen zwei "co-loops", einen A> B - Schleife , die A berechnet ← A - B, und ein B ≤ A Schlaufe berechnet , daß B ← B - A. Dies funktioniert , weil, wenn schließlich der Minuend M kleiner als oder gleich den Subtrahend - S (= Difference Minuend - Subtrahend) kann der Minuend worden s (die neuen Meßlänge) und der Subtrahend kann wird die neue R (die Länge gemessen werden); mit anderen Worten die „Sense“ der Subtraktion umkehrt.

Test der Euclid-Algorithmen

Hat ein Algorithmus tut , was sein Autor will , es zu tun? Ein paar Testfällen in der Regel ausreichen Kernfunktionalität zu bestätigen. Eine Quelle verwendet 3009 und 884. Knuth vorgeschlagen 40902, 24140. Ein weiterer interessanter Fall ist die zwei relativ prim Nummern 14157 und 5950.

Aber Ausnahmefälle müssen identifiziert und getestet werden. Werden "unelegant" perform korrekt , wenn R> S, S> R, R = S? Das Gleiche gilt für "Elegante": B> A, A> B, A = B? (Ja zu allem). Was passiert , wenn eine Zahl Null ist, beide Zahlen sind Null? ( „Unelegant“ berechnet für immer in allen Fällen, „elegant“ berechnet für immer , wenn A = 0) Was passiert , wenn negative Zahlen eingegeben werden? Gebrochene Zahlen? Wenn die Eingabe von Zahlen, das heißt die Domäne der Funktion durch den Algorithmus / Programm berechnet wird , ist es , nur positive ganze Zahlen einschließlich null umfassen, dann sind die Ausfälle bei Null zeigen an, dass der Algorithmus (und das Programm , das instanziert it) a partielle Funktion anstatt eine Gesamtfunktion . Ein bemerkenswertes Versagen aufgrund von Ausnahmen ist der Trägerrakete Ariane 5 Flight 501 Raketenausfall (4. Juni 1996).

Der Nachweis der Richtigkeit Programm durch Verwendung mathematischer Induktion : Knuth demonstriert die Anwendung von mathematischer Induktion auf eine „erweiterte“ Version von Euklids Algorithmus, und er schlägt vor , „eine allgemeine Methode für die Gültigkeit eines Algorithmus zu beweisen“. Tausworthe schlägt vor , dass ein Maß für die Komplexität eines Programms die Länge ihrer Richtigkeit fest sein.

Messung und Verbesserung der Euclid-Algorithmen

Elegance (Kompaktheit) gegen die Güte (Geschwindigkeit) : Mit nur sechs Kernen Anweisungen, „Elegant“ ist der klare Sieger, im Vergleich zu „unelegant“ mit dreizehn Anweisungen. Doch „unelegant“ ist schneller (es kommt zu HALT in weniger Schritten). Algorithmus Analyse zeigt , warum dies der Fall ist: „Elegante“ macht zwei bedingte Tests in jedem Abzug Schlaufe, während „unelegant“ nur tut. Da der Algorithmus ( in der Regel) viele Schleifendurch, erfordert im Schnitt viel Zeit ein „B = 0?“ Wasted tun Tests , die erst nach dem Rest berechnet wird , benötigt wird.

Kann die Algorithmen verbessert werden? : Ein Programm , „passen“ und „wirkungsvoll “ , dh Sobald die Programmierer beurteilt wird, berechnet es die Funktion von seinen beabsichtigten autoren dann stellt sich die Frage, kann sie verbessert werden?

Die Kompaktheit der „unelegant“ kann durch die Eliminierung von fünf Stufen verbessert werden. Aber Chaitin bewies , dass ein Algorithmus Verdichten nicht durch eine verallgemeinerte Algorithmus automatisiert werden; vielmehr kann es nur geschehen, heuristisch ; dh durch erschöpfende Suche (Beispiele bei gefunden werden Busy Beaver ), Versuch und Irrtum, Schlau, Einsicht Anwendung induktives Denken usw. Man beachte , dass die Schritte 4, 5 und 6 werden wiederholt in den Schritten 11, 12 und 13. Ein Vergleich mit „eleganter“ liefert einen Hinweis , dass diese Schritte in Verbindung mit Schritt 2 und 3, beseitigt werden können. Dadurch verringert sich die Anzahl der Kern - Anweisungen 13-8, die es „elegantere“ als „elegant“, um neun Uhr Schritte macht.

Die Geschwindigkeit der „Elegante“ kann durch Bewegen des verbessert werden „B = 0?“ Test außerhalb der beiden Subtraktions-Loops. Diese Änderung sieht die Addition von drei Anweisungen (B = 0 ?, A = 0 ?, GOTO). Jetzt „Elegante“ berechnet die Beispiel-Nummern schneller; ob dies immer der Fall für jeden gegebenen A, B und R, würde S eine detaillierte Analyse erfordern.

algorithmische Analyse

Häufig ist es wichtig , wie viel von einer bestimmten Ressource zu kennen (wie zum Beispiel Zeit oder Lagerung) theoretisch für einen bestimmten Algorithmus benötigt wird. Es wurden Verfahren entwickelt für die Analyse von Algorithmen zu erhalten , solche quantitativen Antworten (Schätzungen); zum Beispiel hat der Sortieralgorithmus oben einen Zeitbedarf von O ( n ), die unter Verwendung von O - Notation mit n als die Länge der Liste. Zu allen Zeiten muss der Algorithmus nur zwei Werte erinnern: die höchste Zahl bisher gefunden, und seine aktuelle Position in der Eingabeliste. Deshalb wird gesagt , einen Platzbedarf haben , O (1) , wenn der Platz erforderlich , um die eingegebenen Zahlen zu speichern , nicht gezählt wird , oder O ( n ) , wenn es gezählt wird.

Verschiedene Algorithmen können die gleiche Aufgabe mit einem anderen Satz von Anweisungen in weniger oder mehr Zeit, Raum vervollständigen oder ‚ Anstrengung ‘ als andere. Zum Beispiel kann ein binärer Suchalgorithmus (mit Kosten O (lügt n)) übertrifft eine sequentielle Suche (cost O (n)) , wenn für die verwendete Tabelle Lookups auf sortierten Listen oder Arrays.

Formale Vergleich empirischen

Die Analyse und Untersuchung von Algorithmen ist eine Disziplin der Informatik und wird oft abstrakt , ohne die Verwendung eines bestimmten geübt Programmiersprache oder Umsetzung. In diesem Sinne ähnelt Algorithmus Analyse andere mathematische Disziplinen, dass sie auf den darunter liegenden Eigenschaften des Algorithmus konzentriert und nicht auf den Besonderheiten einer bestimmten Implementierung. Gewöhnlich Pseudo - Code wird für die Analyse verwendet , da es die einfachste und allgemeine Darstellung ist. Doch schließlich sind die meisten Algorithmen in der Regel auf bestimmte Hardware- / Software - Plattformen implementiert und ihre Effizienz wird schließlich auf die Probe gestellt echten Code. Für die Lösung eines „one off“ -Problem, die Effizienz eines speziellen Algorithmus kann nicht erhebliche Folgen haben (es sei denn , n sehr groß ist) , aber für Algorithmen zur schnellen interaktiven, Gewerbe oder lange Lebensdauer wissenschaftlichen Sprachgebrauch konzipiert kann es entscheidend sein. Skalieren von kleinen bis hin zu großen n n aussetzt häufig ineffiziente Algorithmen , die sonst gutartig sind.

Empirische Tests sind nützlich , weil es unerwartete Wechselwirkungen aufdecken kann die Leistung beeinflussen. Benchmarks können vor / nach potenziellen Verbesserungen zu einem Algorithmus nach Programmoptimierung zum Vergleich verwendet werden. Empirische Tests können formale Analyse nicht ersetzen, aber, und sind nicht trivial in fairer Weise durchzuführen.

Ausführung Effizienz

Um die potenziellen Verbesserungen möglich , auch in etablierten Algorithmen, eine anderen bedeutende Innovation in Zusammenhang mit zu illustrieren FFT - Algorithmen (verwendet schwer auf dem Gebiet der Bildverarbeitung), kann die Verarbeitungszeit verringert bis zu 1.000 Mal für Anwendungen wie medizinische Bildverarbeitung. Im Allgemeinen hängen Verbesserungen in der Geschwindigkeit auf spezielle Eigenschaften des Problems, die in der Praxis sehr häufig sind. Speedups dieser Größenordnung ermöglichen EDV - Geräte , die umfangreiche Verwendung von Bildverarbeitung (wie digitale Kameras und medizinische Geräte) machen weniger Energie zu verbrauchen.

Einstufung

Es gibt verschiedene Möglichkeiten Algorithmen, die jeweils mit ihren eigenen Leistungen einzuordnen.

durch die Implementierung

Eine Möglichkeit, Algorithmen zu klassifizieren ist durch Einführung Mitteln.

Rekursion
Ein rekursiver Algorithmus ist einer, der (bezieht dich auf) selbst so oft , bis einen bestimmten Zustand (als Abbruchbedingung auch bekannt) ruft entspricht, das Verfahren ist gemeinsam funktionale Programmierung . Iterative Algorithmen verwenden repetitive Konstrukte wie Schleifen und manchmal zusätzliche Daten Strukturen wie Stapel die gegebenen Probleme zu lösen. Einige Probleme sind natürlich für eine Implementierung oder andere geeignet. ZB Türme von Hanoi ist gut mit rekursive Implementierung verstanden. Jede rekursive Version hat eine äquivalente (aber möglicherweise mehr oder weniger komplex) iterative Ausführung, und vice versa.
Logisch
Ein Algorithmus kann als gesteuerte sieht logische Ableitung . : Dieser Begriff kann ausgedrückt werden Algorithm = logic + Steuerung . Die Logik - Komponente exprimiert die Axiome , die in der Berechnung und die Steuerung Komponente verwendet werden können , bestimmt die Art und Weise , in dem Abzug auf die Axiome angelegt wird. Dies ist die Grundlage für die Logik - Programmierung Paradigma. In der reinen Logik Programmiersprache wird die Steuerkomponente befestigt und Algorithmen spezifiziert , indem nur die Logik - Komponente liefert. Die Attraktivität dieses Ansatzes ist die elegante Semantik : ein Wechsel in den Axiomen produziert eine klar definierte Änderung des Algorithmus.
Seriell, parallel oder verbreitet
Algorithmen werden in der Regel unter der Annahme erörtert , dass Computer eine Anweisung eines Algorithmus zu einem Zeitpunkt ausgeführt werden . Diese Computer werden manchmal seriellen Computer genannt. Ein Algorithmus ausgelegt für eine solche Umgebung ist ein serieller Algorithmus genannt, im Gegensatz zu Algorithmen parallel oder verteilte Algorithmen . Parallele Algorithmen nutzen Computer - Architekturen , wo mehrere Prozessoren auf einem Problem gleichzeitig arbeiten können, während verteilen Algorithmen mehrere Rechner mit einem angeschlossenen nutzen Computer - Netzwerk . Parallel oder verteilen Algorithmen dividieren das Problem in symmetrischen oder asymmetrische Subprobleme und sammelt die Ergebnisse wieder zusammen. Der Ressourcenverbrauch in solchen Algorithmen ist nicht nur Prozessorzyklen für jeden Prozessor , sondern auch der Kommunikations - Overhead zwischen den Prozessoren. Einige Sortieralgorithmen effizient parallelisiert werden, aber ihr Kommunikations - Overhead ist teuer. Iterative Algorithmen sind in der Regel parallelizable. Einige Probleme haben keine parallelen Algorithmen und sind von Natur aus Serien Probleme genannt.
Deterministisch oder nicht-deterministisch
Deterministischen Algorithmen Lösung des Problems mit genau Entscheidung bei jedem Schritt des Algorithmus der Erwägung , dass nicht-deterministischen Algorithmen Probleme lösen über raten obwohl typische Vermutungen gemacht werden genauer durch die Verwendung von Heuristiken .
Exact oder annähernde
Während viele Algorithmen eine exakte Lösung zu erreichen, Approximationsalgorithmen suchen eine Annäherung , die näher an der wahren Lösung. Die Approximation kann erreicht werden durch entweder eine deterministische oder eine zufällige Strategie. Solche Algorithmen haben praktischen Nutzen für viele schwere Probleme. Eines der Beispiele für einen annähernden Algorithmus ist die Knapsackproblem . Die Knapsackproblem ist ein Problem , bei dem es eine Reihe von vorhandenen Gegenständen ist. Das Ziel des Problems ist , den Ranzen zu packen den maximalen Gesamtwert zu erhalten. Jeder Artikel hat etwas Gewicht und einen gewissen Wert. Gesamtgewicht , die wir nicht mehr als eine gewisse feste Zahl X. So tragen können, müssen wir Gewichte der Elemente ebenso wie ihre Werts erwägen.
Quantum-Algorithmus
Sie laufen auf ein realistisches Modell der Quantenberechnung . Der Begriff wird in der Regel für solche Algorithmen verwendet , die von Natur aus Quanten scheint, oder etwas Wesentliches Merkmal verwenden Quantum computing wie quantenmechanische Überlagerung oder Quantenverschränkung .

Mit dem Design-Paradigma

Eine weitere Möglichkeit, Algorithmen zur Klassifizierung ist mit ihrem Design-Methodik oder Paradigma. Es gibt eine gewisse Anzahl von Paradigmen, die jeweils von den anderen. Ferner enthält jede dieser Kategorien viele verschiedene Arten von Algorithmen. Einige gängige Paradigmen sind:

Brute-Force oder erschöpfende Suche
Dies ist die naive Methode, jede mögliche Lösung zu finden versuchen, die beste ist.
Teile und herrsche
Eine Teile und Herrsche - Algorithmus verringert wiederholt eine Instanz eines Problems zu einem oder mehreren kleineren Instanzen des gleichen Problems ( in der Regel rekursiv ) , bis die Instanzen klein genug sind , leicht zu lösen. Ein solches Beispiel für Teile und Herrsche ist Sortieranlage fusionieren . Die Sortierung kann auf jedem Segment der Daten durchgeführt werden , nachdem die Daten in Segmente unterteilt und die gesamten Datensortier kann durch Zusammenführen der Segmente in der Conquer Phase erzielt werden. Eine einfachere Variante von Teile und Herrsche ist ein sogenannter Rückgang und Algorithmus erobern , dass löst ein identisches Subproblem und verwendet die Lösung dieses Teilproblems , das größere Problem zu lösen. Teile und Herrsche dividiert die problemlos in mehrere Teilprobleme und so die Conquer Stufe ist komplexer als verringern und herrsche - Algorithmen. Ein Beispiel für einen Rückgang und herrscht - Algorithmus ist der binäre Suchalgorithmus .
Suchen und Aufzählung
Viele Probleme (wie zB Spiel Schach ) können als Probleme modelliert werden Graphen . Ein Graph Explorations Algorithmus legt Regeln für um einen Graphen zu bewegen und ist nützlich für solche Probleme. Zu dieser Kategorie gehören auch Suchalgorithmen , Branch and Bound Enumeration und Backtracking .
randomisierte Algorithmus
Solche Algorithmen machen zufällig einige Entscheidungen (oder pseudo-zufällig). Sie können bei der Suche nach annähernden Lösungen für Probleme sehr nützlich sein , wenn exakte Lösungen zu finden , kann unpraktisch sein (siehe heuristisches Verfahren unten). Für einige dieser Probleme ist es bekannt , dass die am schnellsten Annäherungen etwas beteiligen müssen Zufälligkeit . Ob randomisierte Algorithmen mit Komplexität Polynomzeit die schnellsten Algorithmen für einige Probleme sein können , ist eine offene Frage , wie das bekannte P - versus - NP - Problem . Es gibt zwei große Klassen derartiger Algorithmen:
  1. Monte Carlo - Algorithmen liefern eine korrekte Antwort mit hohen Wahrscheinlichkeit. ZB RP ist die Unterklasse von diesen , die in laufen Polynomzeit .
  2. Las-Vegas-Algorithmus stets die richtige Antwort zurück, aber ihre Laufzeit nur probabilistically gebunden, zB ZPP .
Reduzierung der Komplexität
Diese Technik beinhaltet ein schwieriges Problem zu lösen , indem es in ein besseren bekannten Problem verwandeln , für die wir (hoffentlich) haben asymptotisch optimal Algorithmen. Das Ziel ist , einen Reduktionsalgorithmus , das zu finden Komplexität wird von der daraus resultierenden reduzierten Algorithmus dominiert. Zum Beispiel, eine Auswahl - Algorithmus umfasst zunächst den Median in einer unsortierten Liste zum Auffinden der Liste (der teure Teil) Sortierung und dann das mittlere Element in der sortierten Liste Abziehen (die billig Teil). Diese Technik ist auch bekannt als transformieren und erobern .
Zurück Tracking
Bei diesem Ansatz werden mehrere Lösungen schrittweise aufgebaut und verließen, wenn bestimmt wird, dass sie nicht zu einer vollständigen Lösung führen können.

Optimierungsprobleme

Für Optimierungsprobleme dort ist eine spezifischere Einstufung von Algorithmen; ein Algorithmus für solche Probleme können in eine oder mehrere der allgemeinen Kategorien oberhalb sowie in eine der folgenden Möglichkeiten beschrieben fällt:

Lineares Programmieren
Wenn für eine optimale Lösung auf eine lineare Funktion gebunden linear Gleichheit und Ungleichheit Zwänge suchen, kann die Zwänge des Problems direkt die optimale Lösung bei der Herstellung verwendet werden. Es gibt Algorithmen , die ein Problem in dieser Kategorie, wie die beliebten lösen können Simplex - Algorithmus . Probleme , die mit der linearen Optimierung gelöst werden können , umfassen das kann maximal Strömungsproblem für gerichtete Graphen. Wenn ein Problem erfordert zusätzlich , dass eine oder mehrere der Unbekannten muss eine sein integer dann in eingestuft integer Programmieren . Ein linearer Programmlogarithmus kann ein solches Problem lösen , wenn es , dass alle Beschränkungen für ganzzahlige Werte nachgewiesen werden kann , sind oberflächlich, dh erfüllen die Lösungen , die diese Beschränkungen sowieso. Im allgemeinen Fall, ein spezialisierter Algorithmus oder ein Algorithmus, die Näherungslösung findet verwendet wird , je nach Schwierigkeit des Problems.
dynamische Programmierung
Wenn ein Problem zeigt optimale Unterbauten - die optimale Lösung für ein Problem was bedeutet , kann von optimalen Lösungen für Teilprobleme konstruiert werden - und überlappende Teilprobleme sind die gleichen Teilprobleme Sinn verwendet , um viele verschiedene Problemfälle zu lösen, ist ein schneller Konzept namens dynamischer Programmierung vermeidet recomputing Lösungen, bereits berechnet worden. ZB Floyd-Warshall - Algorithmus , der kürzeste Weg zu einem Ziel von einem Knoten in einem gewichteten Graphen kann mit dem kürzesten Weg zum Ziel von allen benachbarten Eckpunkt ermittelt werden. Die dynamische Programmierung und memoization gehören zusammen. Der Hauptunterschied zwischen dynamischer Programmierungs- und Teile und Herrsche ist , dass Subprobleme sind mehr oder weniger unabhängig in Teile und Herrsche, wogegen Subprobleme in dynamischer Programmierung überlappen. Der Unterschied zwischen der dynamischen Programmierung und unkompliziert Rekursion ist in Caching oder memoization der rekursiven Aufrufe. Als Teilprobleme unabhängig sind und es keine Wiederholung, hilft memoization nicht; daher die dynamische Programmierung ist keine Lösung für alle komplexen Probleme. Durch die Verwendung von memoization oder warten eine Tabelle von Subprobleme bereits gelöst, dynamischer Programmierung verringert die exponentielle Natur vieler Probleme Polynom Komplexität.
Das Verfahren gierigen
Ein Greedy - Algorithmus ist ähnlich wie bei einem dynamischen Programmieralgorithmus, dass sie durch die Prüfung Unterbauten, in diesem Fall nicht das Problem , sondern einer bestimmten Lösung funktioniert. Solche Algorithmen beginnen mit einiger Lösung, die gegeben werden kann , oder auf irgendeine Weise konstruiert worden, und verbessern sie durch kleine Änderungen vornehmen. Für manche Probleme können sie die optimale Lösung , während für die anderen finden sie stoppen lokalen optima , das heißt, bei Lösungen , die durch den Algorithmus nicht verbessert werden kann , sind aber nicht optimal. Die beliebteste Anwendung von Greedy-Algorithmus ist für den minimalen Spanning - Tree zu finden , wo die optimale Lösung zu finden , mit dieser Methode möglich ist. Huffman Baum , Kruskal , Prim , Sollin sind Greedy-Algorithmus, der dieses Optimierungsproblem lösen kann.
Das heuristische Verfahren
In Optimierung Problemen , heuristische Algorithmen können verwendet werden , um eine Lösung in der Nähe der optimalen Lösung in Fällen zu finden , wo die optimale Lösung unpraktisch ist , zu finden. Diese Algorithmen arbeiten , indem sie näher und näher an der optimalen Lösung bekommen , wie sie Fortschritte. Grundsätzlich läuft , wenn für eine unendliche Menge an Zeit, werden sie die optimale Lösung finden. Ihr Verdienst ist , dass sie eine Lösung sehr nahe an der optimalen Lösung in relativ kurzer Zeit finden können. Solche Algorithmen gehören die lokale Suche , Tabu Search , Simulated Annealing und genetische Algorithmen . Einige von ihnen, wie Simulated Annealing, sind nicht-deterministischen Algorithmen während andere, wie Tabu Search, deterministisch sind. Wenn eine Schranke für die Fehler der nicht-optimalen Lösung bekannt ist, wird der Algorithmus weiter als kategorisierten Approximationsalgorithmus .

Nach Studienbereichen

Jedes Feld der Wissenschaft hat seine eigenen Probleme und Bedürfnisse effiziente Algorithmen. Ähnliche Probleme in einem Bereich werden häufig gemeinsam untersucht. Einige beispielhaften Klassen Suchalgorithmen , Sortieralgorithmen , fusioniert Algorithmen , numerische Algorithmen , Graphenalgorithmen , String - Algorithmen , Computational geometrisches Algorithmen , kombinatorische Algorithmen , medizinische Algorithmen , maschinelles Lernen , Kryptographie , Datenkomprimierungsalgorithmen und Parsing - Techniken .

Die Felder sind in der Regel mit sich, und Algorithmus in einem Feld zu überlappen können die anderes, manchmal völlig unabhängig, Felder verbessern. Zum Beispiel wurde dynamische Programmierung zur Optimierung des Ressourcenverbrauches in der Industrie erfunden, aber jetzt bei der Lösung eine breite Palette von Problemen in vielen Bereichen verwendet wird.

durch die Komplexität

Algorithms kann durch die Menge der Zeit, die sie brauchen, im Vergleich zu ihrem Eingang Größe abzuschließen eingeteilt werden:

  • Konstante Zeit: Wenn die Zeit vom Algorithmus benötigt wird , ist die gleiche, unabhängig von der Eingangsgröße. Zum Beispiel ein Zugang zu einem Array - Element.
  • Lineare Zeit: wenn die Zeit ist proportional zu der Eingangsgröße. ZB die Traverse einer Partei.
  • Logarithmische Zeit: Wenn die Zeit eine logarithmische Funktion der Eingangsgröße ist. ZB binären Suchalgorithmus .
  • Polynomzeit: wenn die Zeit eine Potenz der Eingang Größe ist. ZB die Blasensortierung Algorithmus hat quadratische Zeitkomplexität.
  • Exponential Zeit: wenn die Zeit , ist eine exponentielle Funktion der Eingangsgröße. Eg Brute-Force-Methode .

Einige Probleme haben können mehrere Algorithmen unterschiedlicher Komplexität, während andere Probleme keine Algorithmen haben könnten oder keine bekannten effiziente Algorithmen. Es gibt auch Abbildungen von einigen Problemen auf andere Probleme. Aufgrund dieser Tatsache wurde gefunden, mehr als geeignet erwiesen, die Probleme zu klassifizieren sich statt der Algorithmen in Äquivalenzklassen basierend auf der Komplexität der optimalen Algorithmen für sie.

kontinuierliche Algorithmen

Das Adjektiv „kontinuierlich“, wenn das Wort angewandt „Algorithmus“ kann bedeuten:

  • Ein Algorithmus auf Daten arbeiten , die kontinuierliche Größen darstellt, obwohl diese Daten durch diskrete Annäherungen-solch dargestellt wird Algorithmen untersucht numerische Analyse ; oder
  • Ein Algorithmus in Form einer Differentialgleichung , die kontinuierlich auf den Daten, läuft auf einen betreibt Analogrechner .

Rechtsfragen

Algorithmen, von sich selbst, ist nicht in der Regel patentfähig . In den Vereinigten Staaten, die aus einem Anspruch nur aus einfachen Manipulationen von abstrakten Begriffen, Zahlen oder Signalen stellt keine „Prozesse“ (USPTO 2006) und daher Algorithmen sind nicht patentierbar (wie in Gottschalk v. Benson ). Allerdings praktische Anwendungen von Algorithmen sind manchmal patentierbar. Zum Beispiel, in Diamanten V. Diehr , die Anwendung eines einfachen Rückkopplungsalgorithmus bei der Härtung von unterstützen synthetischer Kautschuk wurde patentierbar angesehen. Die Patentierung von Software ist sehr umstritten, und es gibt sehr kritisierte Patente Einbeziehung Algorithmen, insbesondere Daten Komprimierungsalgorithmen, wie Unisys ' LZW - Patent .

Darüber hinaus haben einige Kryptografiealgorithmen Exportbeschränkungen (siehe Export von Kryptographie ).

Geschichte: Entwicklung des Begriffs des „Algorithmus“

Altorientalischen

Algorithms wurden im antiken Griechenland verwendet. Zwei Beispiele sind das Sieb des Eratosthenes , die beschrieben wurde , Introduction to Arithmetic von Nicomachus und den euklidischen Algorithmus , der zuerst in beschrieben wurde Euklidischen Element (c. 300 BC). Babylonischen Tontafeln beschreiben und verwenden algorithmische Verfahren , um die Zeit und den Ort bedeutende astronomische Ereignisse zu berechnen.

Diskrete und unterscheidbare Symbole

Tally-Marken : Für eine Übersicht über ihre Schafe, ihre Getreidesäcke und ihre Kosten die Alten benutzt Auszählung: gekratzt Steine oder -marken Sticks Akkumulieren oder machen einzelne Symbole in Ton. Durch die babylonische und ägyptische Verwendung von Zeichen und Symbolen, schließlich römischen Ziffern und dem Abakus entwickelt (Dilson, Seite 16-41). Zählstriche erscheinen prominent in Unärsystem Arithmetik verwendet in Turing - Maschine und Post-Turing - Maschine Berechnungen.

Manipulation von Symbolen als „Platzhalter“ für Nummern: Algebra

Die Arbeit der antiken griechischen Geometer ( euklidische Algorithmus ), der indischen Mathematiker Brahmagupta und der persischen Mathematiker Al-Khwarizmi (aus deren Namen die Begriffe „ Algorithmus “ und „Algorithmus“ abgeleitet) und westeuropäischer Mathematiker gipfelte in Leibniz ‚n Begriff des Kalküls ratiocinator (ca 1680):

Ein gutes Jahrhundert und eine Hälfte seiner Zeit voraus, vorgeschlagen Leibniz eine Algebra der Logik, eine Algebra, die die Regeln für die Manipulation logische Konzepte in der Art und Weise, die gewöhnlichen Algebra geben die Regeln für die Manipulation von Zahlen festlegen würde.

Mechanische Vorrichtungen mit einzelnen Staaten

Die Uhr : Bolter schreibt die Erfindung der Gewicht getriebene Uhr als „The Taste Erfindung [Europas im Mittelalter]“, insbesondere die Spindelhemmung , die uns mit dem Tick und Tack einer mechanischen Uhr liefert. „Die genauen Automaten“ führten sofort zu „mechanischen Automaten “ im 13. Jahrhundert begonnen und dann auf „Rechenmaschinen“ -das Difference Engine und Analytical Engine von Charles Babbage und Gräfin Ada Lovelace , Mitte des 19. Jahrhundert. Babbage Analytical Engine, das erste Gerät eines echter betrachtet - Lovelace mit der ersten Schöpfung eines Algorithmus zur Verarbeitung auf einem Computer bestimmt Gutschrift Turing-complete Computer statt nur einen Rechner - und manchmal auch als „Geschichte der ersten Programmierer“ als Folge genannt wird, obwohl eine vollständige Umsetzung des zweiten Geräts Babbage würde erst Jahrzehnte nach ihrem Leben verwirklicht werden.

Logische Maschinen 1870- Stanley Jevons ' ‚logische Rechenmaschine‘ und ‚logische Maschine‘ : Das technische Problem war zu reduzieren Boolesche Gleichungen , wenn sie in einer ähnlichen Form dargestellt , was jetzt als bekannt Karnaugh Karten . Jevons (1880) beschreibt zuerst eine einfache „Rechenmaschine“ von „Schlicker des Holzes mit Stiften ausgestattet, ersonnen , so dass ein Teil oder die Klasse der [logischen] Kombinationen mechanischen ausgesucht werden kann... In neuerer Zeit jedoch I die reduzierte habe System zu einem völlig mechanischen bilden, und haben somit die Gesamtheit der indirekten Vorgang des Schließens verkörpert in dem, was genannt werden kann eine logische Maschine an bestimmten beweglichen hölzernen Stäbe „kam mit seiner Maschine ausgestattet‚‘und“ Fuß sind 21 Tasten wie jene von ein Klavier [etc]... ". Mit dieser Maschine konnte er eine „Analyse Syllogismus oder anderes einfaches logisches Arguments“.

Diese Maschine zeigte er im Jahr 1870 vor dem Fellows der Royal Society. Ein anderer Logiker John Venn , aber in seinem 1.881 Symbolic Logic , eine Gelbsucht Auge zu diesen Bemühungen wandte: „Ich habe hohe keine Schätzung mich von Interesse oder Bedeutung von dem, was manchmal logischen Maschinen genannt ... es ist mir scheinen , dass alle contrivances derzeit bekannt oder wahrscheinlich wirklich den Namen der logischen Maschine "verdienen , entdeckt zu werden; Sehen Sie mehr unter Algorithm Charakterisierungen . Aber nicht , dass er auch präsentiert „ein Plan etwas analog übertroffen werden, ich erfassen, Herr Prof. Jevon des Abakus ... [und] [a] Gewinn, entsprechend Prof. Jevons 'logisches Gerät, wird die folgende Einrichtung kann beschrieben werden. Ich bevorzuge zu nennen es nur logisch-Diagramm Maschine ... aber ich nehme an, dass es alle tun könnte sehr völlig rational jede logischen Maschine gerechnet werden kann“.

Jacquard Webstuhl, Hollerith Lochkarten, Telegraphie und Telephonie-den elektromechanischen Relais : Bell and Newell (1971) zeigen , dass die Jacquard - Webstuhl (1801), Vorstufe für Hollerith Karte (Lochkarten, 1887), und "Telefonvermittlungs technologies" waren die Wurzeln von einem Baum auf die Entwicklung des ersten Computers führt. Durch die Mitte des 19. Jahrhunderts wurde die Telegraphen , der Vorläufer des Telefons, war im Einsatz in der ganzen Welt, seine diskrete und unterscheidbare Codierung von Buchstaben wie „Punkte und Striche“ ein gemeinsam Sound. Gegen Ende des 19. Jahrhunderts das Tickerband (ca 1870) war im Einsatz, wie die Verwendung von Hollerith - Karten in der 1890 US Volkszählung war. Dann kam die Fernschreibmaschine (ca. 1910) mit seiner Ausstanzungen Papier Verwendung von Baudot - Code auf dem Band.

Telefon-Vermittlungsnetze von elektromechanischen Relais (erfunden 1835) wurden hinter der Arbeit von George Stibitz (1937), der Erfinder der digitalen Addiereinrichtung. Wie er in dem Bell Laboratories arbeitete, beobachtete er die „lästige‘ Verwendung von mechanischen Rechenmaschinen mit Gängen. ‚Er ging einem Abend nach Hause im Jahr 1937 die Absicht , seine Idee zu testen ... Wenn die Bastelei vorbei war, Stibitz ein binäres Addiervorrichtung aufgebaut hatte‘ .

Davis (2000) beobachtet die besondere Bedeutung des elektromechanischen Relais (mit seinen zwei „binären Zuständen“ offen und geschlossen ):

Erst mit der Entwicklung, der in den 1930er Jahren begannen, von elektromechanischen Rechenmaschinen elektrische Relais verwendet wird, dass Maschinen gebaut wurden, den Umfang mit Babbage vorgestellt hatte.“

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

Symbole und Regelungen : In rascher Folge, die Mathematik von George Boole (1847, 1854), Gottlob Frege (1879) und Giuseppe Peano (1888-1889) durch Regeln manipulierten Arithmetik zu einer Folge von Symbolen reduziert. Peanos Die Prinzipien der Arithmetik, durch ein neues Verfahren vorgestellt (1888) waren „der erste Versuch einer Axiomatisierung der Mathematik in einer symbolischen Sprache“.

Aber Heijenoort gibt Frege (1879) diese ein dickes Lob: Freges ist „vielleicht das wichtigste einzelne Werk , das je in der Logik geschrieben ... , in denen wir sehen.“ ‚Formelsprache‘, das eines ist lingua characterica , eine Sprache , geschrieben mit Sonderzeichen „für die reine Denken“, das heißt, von rhetorischen Verzierungen frei ... von spezifischen Symbolen aufgebaut , die nach bestimmten Regeln manipuliert werden“. Die Arbeit von Frege wurde weiter vereinfacht und verstärkt von Alfred North Whitehead und Bertrand Russell in ihrem Principia Mathematica (1910-1913).

Die Paradoxien : Zur gleichen Zeit eine Reihe von störenden Paradoxien in der Literatur erschienen, insbesondere die Burali-Forti Paradox (1897), die Russell Paradoxon (1902-1903) und die Richard Paradox . Die resultierenden Überlegungen führten zu Kurt Gödel ‚s Papier (1931) -Er speziell zitiert das Paradoxon des Lügners-die Regeln vollkommen reduziert Rekursion zu Zahlen.

Effektiver Berechenbarkeit : In dem Bemühen , die zu lösen Entscheidungsproblem genau durch Hilbert Mathematiker zunächst im Jahr 1928 definierte daran , zu definieren , was unter einer „wirksamen Methode“ oder „wirksame Berechnung“ oder „wirksame Berechenbarkeit“ (dh gelingen würde eine Berechnung gemeint war , die ). In rascher Folge erschienen: Alonzo Church , Stephen Kleene und JB Rosser ‚s λ-Kalkül eine fein geschliffene Definition des Begriffs‚allgemeine Rekursion‘aus der Arbeit von Gödel Vorschläge von wirkenden Jacques Herbrand (vgl Gödels Princeton Vorlesungen aus dem Jahr 1934) und nachfolgende Vereinfachungen durch Kleene. Kirche der Beweis , dass das Entscheidungsproblem war unlösbar, Emil Geben Sie ‚s Definition der effektiven Berechenbarkeit als ein Arbeiter gedankenlos eine Liste von Anweisungen folgen nach links oder rechts durch eine Abfolge von Räumen und solange dort entweder Note oder ein Papier löschen oder das Papier einhalten und machen ein ja-nein - Entscheidung über die nächste Anweisung. Alan Turings Beweis , dass das Entscheidungsproblem war unlösbar durch Verwendung seiner „a- [Automatik-] machine“ -in Wirkung fast identisch mit Post „Formulierung“, J. Barkley Rosser ‚s Definition des Begriffs‚effektiver Methode‘im Sinne von„einem Maschine". SC Kleene ‚Vorschlag einer Vorstufe zur‚ Kirche These ‘ , dass er‚These I‘, und ein paar Jahre später Kleenes Umbenennung seiner Dissertation‚Kirche Arbeit‘und schlägt‚Turing Arbeit‘genannt.

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

Hier ist eine bemerkenswerte Koinzidenz von zwei Männern, nicht einander zu kennen, sondern beschreibt einen Prozess der Mann-as-Computern arbeiten Berechnungen-und liefern sie praktisch identisch Definitionen.

Emil hochladen (1936) beschrieb die Aktionen eines „Computer“ (Mensch) wie folgt:

“... zwei Konzepte sind beteiligt: das einen Bedeutungsraum , in dem die Arbeit von Problem führt zu beantworten ist , ausgeführt werden, und eine feste unveränderliche Reihe von Richtungen .

Sein Bedeutungsraum wäre

„Eine bidirektionale unendliche Folge von Leerzeichen oder Boxen ... Der Problemlöser oder Arbeiter ist in diesem Zeichen Platz zu bewegen und arbeiten, in der Lage ist, zu sein, und arbeitet gleichzeitig in nur eine Box .... eine Box ist von nur zwei möglichen Bedingungen zugeben, nämlich leer oder unmarkiert zu sein, und in ihm eine einzige Marke, das, sagen sie einen senkrechten Strich.
„Eine Box ist zu ausgesondert und rief den Ausgangspunkt. ... ein spezifisches Problem ist durch eine endliche Anzahl von Boxen [dh INPUT] in symbolischer Form geben mit einem Hub markiert werden. In ähnlicher Weise ist die Antwort [dh , AUSGANG] ist durch eine solche Konfiguration markierte Boxen in symbolischer Form geben ...
„Eine Reihe von Richtungen anwendbar auf ein generelles Problem stellt einen deterministischen Prozess, wenn auf jedes spezielles Problem angewandt. Dieser Vorgang nur beendet , wenn es auf die Richtung der Art (C) kommt [dh STOP]“. Sehen Sie mehr bei Post-Turing - Maschine
Alan Turings Statue am Bletchley Park

Alan Turing ‚s Arbeiten voraus, die von Stibitz (1937); es ist unbekannt , ob Stibitz der Arbeit von Turing wußte. Turing-Biograf glaubt , dass Turings Verwendung eines schreibmaschinenähnliche Modell von einem jugendlichen Interesse abgeleitet: „Alan erfinden Schreibmaschinen als Junge geträumt hatte, Mrs. Turing eine Schreibmaschine hatte, und er auch von ihm selbst zu fragen begonnen haben könnte , was durch den Aufruf gemeint eine Schreibmaschine ‚mechanischer‘“. Angesichts der Häufigkeit von Morse - Code und Telegraphie, Lochstreifen Maschinen und Fernschreibmaschinen könnten wir vermuten , dass alle Einflüsse waren.

Turing-sein Rechenmodell ist nun einen genannter Turingmaschine -begins, als Beitrag tat, mit einer Analyse eines menschlichen Computers, den er zu einem einfachen Satz von grundlegenden Bewegungen und „Zuständen des Geistes“ schnitzt nieder. Aber er setzt noch einen Schritt weiter und schafft eine Maschine als Modell der Berechnung von Zahlen.

„Computing wird in der Regel durch das Schreiben bestimmte Symbole auf Papier. Wir können dieses Papier vermuten ist in Quadrate wie ein Rechenbuch des Kindes ... Ich nehme dann, dass die Berechnung auf eindimensionalem Papier ausgeführt, dh, auf einem Band geteilt in Quadrate. werde ich nehme an, dass die Anzahl von Symbolen, die endlich gedruckt werden können, ist ...
„Das Verhalten des Computers jederzeit durch die Symbole ermittelt, die er beobachtet, und seine‚State of mind‘in diesem Moment. Wir können annehmen, dass es eine Schranke B ist auf die Anzahl von Symbolen oder Quadraten, die der Computer kann in einem Moment bemerken. Wenn er mehr einzuhalten, muss er aufeinanderfolgende Beobachtungen nutzen. Wir vermuten auch, dass die Anzahl der Zustände des Geistes, die in Betracht gezogen werden muss, ist endlich ...
„Stellen wir uns vor, dass die vom Computer durchgeführten Operationen in‚einfaches‘aufgeteilt werden, die so elementar sind, dass es nicht leicht ist, sie weiter unterteilt vorstellbar.“

Turings Reduktion ergibt die folgende:

„Die einfachen Vorgänge müssen daher umfassen:
„(A) Änderung des Symbols auf einem der beobachteten Quadrate
„(B) Veränderung eines der Quadrate auf ein anderes Feld innerhalb L Quadrate von einem der zuvor beobachteten Quadraten beobachtet.

„Es kann sein, dass einige diese Veränderung notwendigerweise eine Veränderung der Gemütsverfassung berufen Der allgemeinste einzelne Vorgang muss daher sein, eine der folgenden Möglichkeiten genommen werden.:

„(A) Ein mögliche Änderung (a) des Symbols zusammen mit einer möglichen Änderung des Zustandes des Geistes.
„(B) eine mögliche Veränderung (b) beobachteter Quadrate, zusammen mit einer möglichen Veränderung des Zustandes des Geistes“
„Wir können jetzt ein Gerät konstruieren, die Arbeit des Computers zu tun.“

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

„Eine Funktion soll als‚wirkungsvoll berechenbar‘, wenn seine Werte können durch eine rein mechanische Verfahren gefunden werden. Obwohl es ziemlich einfach ist, ein intuitives Verständnis dieser Idee zu bekommen, ist es doch wünschenswert, eine gewisse festere, mathematisch ausdrückbar Definition zu haben ... [bespricht er die Geschichte der Definition ziemlich wie oben mit Bezug auf Gödel, Herbrand, Kleene, Kirche, Turing präsentiert und Post]... Wir wörtlich diese Aussage in Anspruch nehmen, Verständnis durch ein rein mechanischen Verfahren ein die konnte von einer Maschine ausgeführt. Es ist möglich, eine mathematische Beschreibung, in einer bestimmten Normalform, den Strukturen dieser Maschinen. Die Entwicklung dieser Ideen führt zu dem Autor Definition einer berechenbaren Funktion und zu einer Identifikation geben Berechenbarkeit † mit wirksamer Berechenbarkeit....
berechenbare Funktion „† Wir werden den Ausdruck‚‘eine Funktion berechenbar durch eine Maschine zu verstehen, und wir lassen‚wirkungsvoll berechenbar‘verweisen auf die intuitive Idee ohne besondere Identifikation mit jedem dieser Definitionen“.

JB Rosser (1939) und SC Kleene (1943)

J. Barkley Rosser definierte eine ‚wirksame [mathematische] Methode‘ in der folgenden Weise (Kursiv hinzugefügt):

„‚Effektive Methode‘wird hier im ganz besonderen Sinne eines Verfahrens jeder Schritt von denen genau festgelegt verwendet wird und das ist sicher , die Antwort in einer endlichen Anzahl von Schritten zu erzeugen. Mit dieser besonderen Bedeutung, drei verschiedene exakte Definitionen erhalten haben to date [seine Fußnoten # 5, siehe Diskussion unverzüglich unten]. Die einfachste davon zu Staat (durch Post und Turing) sagt im wesentlichen , dass. eine wirksame Methode , bestimmte Arten von Problemen zu lösen , liegt vor , wenn man eine Maschine bauen kann die dann irgendwelche Probleme des Satzes ohne menschliche Eingriffe über das Einfügen der Frage und (später) das Lesen der Antwort zu lösen . Alle drei Definitionen äquivalent sind, so ist es egal , welche verwendet wird. die Tatsache, dass alle drei gleichwertige sind , ist ein sehr starkes Argument für die Richtigkeit der eine.“ (Rosser 1939: 225-6)

Rossers Fußnote No. 5 verweist auf die Arbeit von (1) Kirche und Kleene und ihre Definition von λ-Definierbarkeit, insbesondere Kirche Gebrauch davon in seinem unlösbaren Problem der elementaren Zahlentheorie (1936); (2) Herbrand und Gödel und deren Verwendung von Rekursion insbesondere Gödels Verwendung in seinem berühmten Aufsatz Auf formal unentscheidbare Propositions von Principia Mathematica und verwandter Systeme I (1931); und (3) Post (1936) und Turing (1936-1937) in ihren mechanismusBerechnungsModellen.

Stephen C. Kleene definiert als seine mittlerweile berühmten „These I“ bekannt als die Church-Turing - These . Aber er tat dies in folgendem Zusammenhang (fett gedruckt im Original):

„12. Algorithmische Theorien ... Bei der Gestaltung eines kompletten algorithmischen Theorie nach oben, was wir tun , ist ein Verfahren, aufführbar für jeden Satz von Werten der unabhängigen Variablen zu beschreiben, die notwendigerweise Prozedur beendet und in einer solchen Art und Weise , dass von den Ergebnissen können wir lesen Sie eine definitive Antwort „ja“ oder „nein“ auf die Frage, „ist das Prädikat Wert wahr?““(Kleene 1943: 273)

Geschichte nach 1950

Eine Reihe von Bemühungen wurden zur weiteren Verfeinerung der Definition des Begriffs „Algorithmus“ gerichtet und Tätigkeit ist im Gang , weil von Fragen rund um vor allem Grundlagen der Mathematik (besonders die Church-Turing - These ) und Philosophie des Geistes (vor allem Argumenten über künstliche Intelligenz ). Weitere Informationen finden sich Charakterisierungen Algorithmus .

Siehe auch

Anmerkungen

Literaturverzeichnis

  • Axt, P (1959). „Auf einer Subrecursive Hierarchie und primitiv - rekursive Degrees“. Transaktionen der American Mathematical Society . 92 : 85-105. doi : 10,2307 / 1993169 . JSTOR  1.993.169 .
  • Bell, C. Gordon und Newell, Allen (1971), Computer - Bauwerke: Lesungen und Beispiele , McGraw-Hill Book Company, New York. ISBN  0-07-004357-4 .
  • Blass, Andreas ; Gurevich, Yuri (2003). "Algorithms: A Quest for Absolute Definitions" (PDF) . Bulletins der European Association for Theoretical Computer Science . 81 . Enthält eine ausgezeichnete Bibliographie von 56 Referenzen.
  • Bolter, David J. (1984). Turings Man: westliche Kultur im Computerzeitalter (1984 Hg.). Die University of North Carolina Press, Chapel Hill NC. ISBN  0-8078-1564-0 ., ISBN  0-8078-4108-0 pbk.
  • Boolos, George ; Jeffrey, Richard (1999) [1974]. Berechenbarkeit und Logik (4. Aufl.). Cambridge University Press, London. ISBN  0-521-20402-X .: Vgl Kapitel 3 Turingmaschine , wo sie „gewisse aufzählbaren nicht wirkungsvoll (mechanisch) zählbare“ diskutieren.
  • Burgin, Markus (2004). Super-rekursive Algorithms . Springer. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Moore, C. , und Costa, JF (2000) Eine analoge Charakterisierung der subrecursive Funktionen. In Proc. der 4. Konferenz über Reelle Zahlen und Computer , Odense University, pp. 91-109
  • Kirche, Alonzo (1936a). „Ein unlösbares Problem der elementaren Zahlentheorie“. Das American Journal of Mathematics . 58 (2): 345-363. doi : 10,2307 / 2371045 . JSTOR  2.371.045 .Abgedruckt in The Unentscheidbare , p. 89ff. Der erste Ausdruck von „Kirche Arbeit“. Siehe insbesondere Seite 100 ( Die Unentscheidbare ) , wo er den Begriff der „effektiven Berechenbarkeit“ definiert im Sinne von „Algorithmus“, und er verwendet das Wort „endet“, usw.
  • Kirche, Alonzo (1936b). „Eine Notiz auf dem Entscheidungsproblem “. The Journal of Symbolic Logic . 1 (1): 40-41. doi : 10,2307 / 2269326 . JSTOR  2.269.326 .Kirche, Alonzo (1936). „Korrektur zu einem Hinweis auf dem Entscheidungsproblem “. The Journal of Symbolic Logic . 1 (3): 101-102. doi : 10,2307 / 2269030 . JSTOR  2.269.030 .Abgedruckt in The Unentscheidbare , S.. 110ff. Kirche zeigt , dass das Entscheidungsproblem in ca. 3 Seiten Text und 3 Seiten von Fußnoten unlösbar ist.
  • Daffa‘, Al- Ali Abdullah (1977). Die muslimischen Beiträge zur Mathematik . London: Croom Helm. ISBN  0-85664-464-1 .
  • Davis, Martin (1965). Die Unentscheidbare Basic Papers On Unentscheidbare Propositions, unlösbare Probleme und berechenbaren Funktionen . New York: Raven Press. ISBN  0-486-43228-9 .Davis gibt Kommentar bevor jeden Artikel. Papiere von Gödel , Alonzo Church , Turing , Rosser , Kleene , und Emil Geben Sie sind im Lieferumfang enthalten; diejenigen , die in dem Artikel zitiert sind hier aufgeführt von den Namen des Autors.
  • Davis, Martin (2000). Motoren von Logic: Mathematiker und der Ursprung des Computers . New York: WW Nortion. ISBN  0-393-32229-7 .Davis bietet kurze Biographien von Leibniz , Boole , Frege , Cantor , Hilbert , Gödel und Turing mit von Neumann als die Show stiehlt Bösewicht. Sehr kurze Biographien Joseph-Marie Jacquard , Babbage , Ada Lovelace , Claude Shannon , Howard Aiken etc.
  •  Dieser Artikel enthält geschütztes Material  von der  NIST document:  Schwarz, Paul E. „Algorithmus“ . Wörterbuch von Algorithmen und Datenstrukturen .
  • Dekan, Tim (2012). „Evolution und moralische Vielfalt“. Baltic Internationale Yearbook of Cognition, Logik und Kommunikation . 7 .
  • Dennett, Daniel (1995). Darwins gefährliche Idee . New York: Prüfstein / Simon & Schuster. ISBN  0-684-80290-2 .
  • Dilson, Jesse (2007). Die Abacus ((1968,1994) , Hg.). St. Martins Press, NY. ISBN  0-312-10409-X ., ISBN  0-312-10409-X (PBK) .
  • Yuri Gurevich , Sequential Abstract State Machines Erfassung Sequential Algorithms , ACM Transactions on Computational Logic, Band 1, Nr 1 (Juli 2000), Seiten 77-111. Enthält Bibliografie von 33 Quellen.
  • van Heijenoort, Jean (2001). Von Frege zu Gödel, A Source Book in Mathematische Logik, 1879-1931 ((1967) Hrsg.). Harvard University Press, Cambridge, MA. ISBN  0-674-32449-8 ., 3. Auflage 1976 [?], ISBN  0-674-32449-8 (PBK) .
  • Hodges, Andrew (1983). Alan Turing: Das Rätsel . New York: Simon and Schuster . ISBN  0-671-49207-1 ., ISBN  0-671-49207-1 . Vgl Kapitel „Der Geist der Wahrheit“ für eine Geschichte , die zu, und eine Diskussion, sein Beweis.
  • Kleene, Stephen C. (1936). „Allgemein rekursiven Funktionen der natürlichen Zahlen“ . Mathematischen Annalen . 112 (5): 727-742. doi : 10.1007 / BF01565439 .Präsentiert auf der American Mathematical Society, September 1935. Neu gedruckt in der Unentscheidbare , S.. 237ff. Kleenes Definition des Begriffs „allgemeine Rekursion“ (jetzt bekannt als Mu-Rekursion) wurde von Church in seinem 1.935 Papier ein unlösbares Problem der elementaren Zahlentheorie , die die „Entscheidungsproblem“ erwiesen „unentscheidbar“ (dh ein negatives Ergebnis).
  • Kleene, Stephen C. (1943). „Rekursive Prädikate und Quantifizierer“. American Mathematical Society Transactions . 54 (1): 41-73. doi : 10,2307 / 1990131 . JSTOR  1.990.131 .Abgedruckt in The Unentscheidbare , p. 255ff. Kleene verfeinerte seine Definition des Begriffs „allgemeine Rekursion“ und in seinem Kapitel „12. Algorithmische Theorien“ postulieren „These I“ vorgegangen (S. 274.); er würde später diese These wiederholen (in Kleene 1952: 300) und den Namen "Church Arbeit" (Kleene 1952: 317) (dh die Kirche These ).
  • Kleene, Stephen C. (1991) [1952]. Einführung in Metamathematics (Zehnte Hrsg.). Nord-Holland Publishing Company. ISBN  0-7204-2103-9 . Ausgezeichnete zugängliche, gut lesbare-Referenzquelle für mathematisch „Grundlagen“.
  • Knuth, Donald (1997). Fundamental Algorithms, Third Edition . Reading, Massachusetts: Addison-Wesley. ISBN  0-201-89683-4 .
  • Knuth, Donald (1969). Volume 2 / Seminumerical Algorithms, The Art of Computer Programming First Edition . Reading, Massachusetts: Addison-Wesley.
  • Kosovsky, NK Elemente der mathematischen Logik und ihre Anwendung auf die Theorie der Subrecursive Algorithms , LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). "Algorithm = Logic + Control". Communications of the ACM . 22 (7): 424-436. doi : 10,1145 / 359.131,359136 .
  • AA Markov (1954) Theorie der Algorithmen . [Übersetzt von Jacques J. Schorr-Kon und PST Mitarbeitern] Impressum Moskau, Akademie der Wissenschaften der UdSSR, 1954 [ie, Jerusalem, Israel Programm für wissenschaftliche Übersetzungen, 1961; erhältlich beim Amt der Technischen Dienste, US Dept. of Commerce, Washington] Beschreibung 444 p. 28 cm. Hinzugefügt tp in der russischen Übersetzung von Werken des Mathematischen Instituts der Akademie der Wissenschaften der UdSSR, v 42. Ursprünglicher Titel:. Teoriya algerifmov. [QA248.M2943 Dartmouth College - Bibliothek. US Dept. of Commerce, Office of Technical Services, OTS - Nummer 60-51085.]
  • Minsky, Marvin (1967). Berechnung: Endlichen und Unendlichen Maschinen (Erste Hg.). Prentice-Hall, Englewood Cliffs, NJ. ISBN  0-13-165449-7 .Minsky erweitert seine „... Idee eines Algorithmus-ein effektives Verfahren ...“ in Kapitel 5.1 Berechenbarkeit, wirksame Verfahren und Algorithmen. Unendliche Maschinen.
  • Post, Emil (1936). "Finite kombinatorische Prozesse, Formula I". The Journal of Symbolic Logic . 1 (3): 103-105. doi : 10,2307 / 2269031 . JSTOR  2.269.031 .Abgedruckt in The Unentscheidbare , p. 289ff. Geben Sie bildet ein einfaches algorithmisches artiges Verfahren von einem Mann Noten schreiben oder Markierungen zu löschen und von Box gehen zu boxen und schließlich anzuhalten, als er eine Liste mit einfachen Anweisungen folgt. Dies wird durch Kleene als Quelle seiner „These I“ genannt, der sogenannten Church-Turing - These .
  • Rogers, Jr., Hartley (1987). Theorie der rekursiven Funktionen und effektive Berechenbarkeit . The MIT Press. ISBN  0-262-68052-1 .
  • Rosser, JB (1939). „Eine informelle Exposition von Proofs von Gödels Satz und Kirche Theorem“. Journal of Symbolic Logic . 4 (2): 53-60. doi : 10,2307 / 2269059 . JSTOR  2.269.059 .Abgedruckt in The Unentscheidbare , p. 223ff. Hierin ist Rossers bekannte Definition des Begriff „wirksamer Methode“:“... ein Verfahren , wobei jeder Schritt von denen genau vorgegeben ist und welches bestimmen die Antwort in einer endlichen Anzahl von Schritten zu erzeugen , ... eine Maschine , die dann irgendein Problem lösen der Satz ohne menschliche Eingriffe über die Frage eingefügt und (später) Lesen Sie die Antwort . “(S. 225-226, The Unentscheidbare )
  • Santos-Lang, Christopher (2014). „Moralische Ökologie Ansätze zur Maschinenethik“. In van Rysewyk, Simon; Pontier, Matthijs. Maschine Medical Ethics (PDF) . Schweiz: Springer. pp. 111-127. doi : 10.1007 / 978-3-319-08108-3_8 .
  • Scott, Michael L. (2009). Programming Language Pragmatik (3. Aufl.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Michael (2006). Einführung in die Theorie der Berechnung . PWS Publishing Company. ISBN  0-534-94728-X .
  • Sober, Elliott; Wilson, David Sloan (1998). Unto Others: The Evolution und Psychologie der Selbstlose Verhalten . Cambridge: Harvard University Press.
  • Stein-, Harold S. (1972). Einführung in die Computer - Organisation und Datenstrukturen (1972 Hrsg.). McGraw-Hill, New York. ISBN  0-07-061726-0 .Vgl insbesondere das erste Kapitel mit der Überschrift: Algorithms, Turingmaschinen und Programmen . Seine prägnante informelle Definition: „... eine beliebige Folge von Anweisungen , die von einem Roboter eingehalten werden kann, wird ein aufgerufen Algorithmus (S. 4) . “.
  • Tausworthe, Robert C (1977). Standardisierte Entwicklung von Computersoftware Teil 1 Verfahren . Englewood Cliffs NJ: Prentice-Hall, Inc. ISBN  0-13-842195-1 .
  • Turing, Alan M. (1936-1937). „On Computable Zahlen, mit einer Applikation auf das Entscheidungsproblem “. Proceedings of the London Mathematical Society . Serie 2 42 : 230-265. doi : 10,1112 / PLMS / s2-42.1.230 .. Korrigiert, ibid, Bd. 43 (1937) pp. 544-546. Abgedruckt in The Unentscheidbare , S.. 116ff. Turings berühmte Papier als Masterarbeit abgeschlossen , während im Kings College Cambridge UK.
  • Turing, Alan M. (1939). „ Die Systeme der Logik Basierend auf Ordinals“. Proceedings of the London Mathematical Society . 45 : 161-228. doi : 10,1112 / PLMS / s2-45.1.161 .Abgedruckt in The Unentscheidbare , S.. 155ff. Turings Papier , das „das Orakel“ definiert war seine Doktorarbeit in Princeton USA.
  • US - Patent- und Markenamt (2006), 2.106,02 **> Mathematische Algorithmen: 2100 Patentierbarkeit , Handbuch der Patentprüfungsverfahren (MPEP). Zuletzt überarbeitet August 2006

Weiterführende Literatur

Externe Links

Algorithm Repositorys
Vorlesungsnotizen