Algorithmen werden von uns allen ständig mit oder ohne unser direktes Wissen verwendet. Sie haben Anwendungen in vielen verschiedenen Disziplinen, von Mathe und Physik natürlich zu Computer .
Es stellt sich heraus Algorithmen haben eine lange und illustre Geschichte, die bis in das alte Mesopotamien zurückreicht. Aber welcher dieser komplexen Berechnungsprozesse könnte als einer der wichtigsten angesehen werden?
Dies sind 15 der wahrscheinlichsten Kandidaten.
VERBINDUNG: WIE ALGORITHMEN DIE WELT LAUFEN, IN DER WIR LEBEN
Eine kurze Geschichte der Algorithmen
Algorithmen sind vordefinierte, in sich geschlossene Anweisungen, die zur Ausführung verschiedener Funktionen entwickelt wurden und länger existieren als erwartet. Vom alten Babylon bis heute sind Algorithmen seit Jahrtausenden ein wichtiges Merkmal unserer Gesellschaft.
Die allerersten Beispiele waren einfache Algorithmen, mit denen die Alten unter anderem Getreide und Vieh verfolgten. In der Folge und mit dem Aufkommen eines formalisierten numerischen Systems wurden andere technologische und konzeptionelle Sprünge erzielt, einschließlich der Erfindung des Abakus, Algebra und das Konzept der Variablen.
Altgriechische Denker wie Euklid, Archimedes und Eratosthenes verwendeten frühe Algorithmen, um beispielsweise den größten gemeinsamen Teiler verschiedener Zahlen zu bestimmen, Pi zu approximieren und Primzahlen zu berechnen.
Im Laufe der Zeit würden solche Leistungen zu Symbolen und Regeln führen, die bei der Formulierung von Bewertungssystemen eine Rolle spielen.
Es wird angenommen, dass der Begriff „Algorithmus“ selbst seinen Ursprung im persischen Astronomen und Mathematiker Muhammad ibn aus dem 9. Jahrhundert hat. Mūsā al-Khwārizmī . Dieser Mann wird allgemein als die Person angesehen, die zuerst die Dezimalpositionierung im numerischen System der westlichen Welt eingeführt hat.
Sein Nachname, latinisiert als Algorithmi, wird zum Synonym für Anweisungen zum Ausführen von Berechnungen zum Ausführen von Aufgaben.
Ihm wird auch die Entwicklung des ersten Systems zur Lösung linearer und quadratischer Gleichungen zugeschrieben. Die ursprünglichen, wenn auch rudimentären Formen von Algorithmen heißen Algorithmen wurden als Regeln für die Durchführung von arithmetischen Berechnungen mit hindu-arabischen Ziffern angesehen.
Der nächstgrößte Sprung in der Geschichte der Algorithmen erfolgte im 19. Jahrhundert mit der Arbeit des großen George Boole. Viele andere treiben Algorithmen im 19. und 20. Jahrhundert voran, darunter Giuseppe Peano und Ada Lovelace, um nur einige zu nennen.
Aber Algorithmen würden mit der Arbeit von Emil Post und Alan Turing in den 1930er Jahren ein großes Upgrade erhalten, das letztendlich den modernen Computer hervorbringen würde. Nichts würde wieder so sein wie vorher .
Was sind einige der wichtigsten Algorithmen?
Und so, ohne weiteres, hier einige Beispiele der wichtigsten Algorithmen aller Zeiten. Die Liste enthält alte Beispiele sowie einige der bahnbrechendsten Informatik- und Programmieralgorithmen der Geschichte.
Die folgende Liste von Algorithmen ist alles andere als vollständig und in keiner bestimmten Reihenfolge.
1. Babylonische Algorithmen sind die ältesten, die jemals gefunden wurden
Schöpfer : Unbekannt
Als es erstellt wurde : um 1600 v. Chr.
Auswirkungen / Auswirkungen auf die Welt : Der weltweit erste bekannte Algorithmus
Obwohl es in Ägypten einige Hinweise auf frühe Multiplikationsalgorithmen gibt um 2000-1700 v. Chr. , der älteste geschriebene Algorithmus, von dem allgemein angenommen wird, dass er auf einer Reihe von Babyloniern gefunden wurde Tontafeln dieses Datum bis ungefähr 1800-1600 v. Chr.
Ihre wahre Bedeutung kam nur zum Vorschein 1972 als der Informatiker und Mathematiker Donald E. Knuth die ersten englischen Übersetzungen verschiedener keilförmiger mathematischer Tafeln veröffentlichte.
Hier einige Auszüge aus seinem 1972 Manuskript, das diese frühen Algorithmen erklärt :-
"Die in babylonischen Tafeln beschriebenen Berechnungen sind nicht nur Lösungen für bestimmte individuelle Probleme; sie sind eigentlich allgemeine Verfahren zur Lösung einer ganzen Klasse von Problemen." - Seiten 672 bis 673 von " Alte babylonische Algorithmen ".
Die Tablets scheinen auch eine frühe Form der Bedienungsanleitung gewesen zu sein :-
"Beachten Sie auch das stereotype Ende 'Dies ist die Prozedur', das üblicherweise am Ende jedes Abschnitts einer Tabelle zu finden ist. Daher sind die babylonischen Prozeduren echte Algorithmen, und wir können die Babylonier für die Entwicklung eines guten Weges zu lobenErklären Sie einen Algorithmus anhand eines Beispiels, während der Algorithmus selbst definiert wurde .... "- Seiten 672 bis 673 von" Alte babylonische Algorithmen ".
2. Der Euklid-Algorithmus wird heute noch verwendet
Schöpfer : Euklid
Als es erstellt wurde : 300 v. Chr.
Auswirkungen / Auswirkungen auf die Welt : Der Euklid-Algorithmus ist einer der frühesten Algorithmen, die jemals erstellt wurden, und wird mit einigen Änderungen noch heute von Computern verwendet.
Der euklidische Algorithmus ist ein Verfahren, mit dem der größte gemeinsame Teiler GCD zweier positiver Ganzzahlen ermittelt wird. Er wurde erstmals von Euklid in seinem Manuskript beschrieben. Elemente herumgeschrieben 300 v. Chr. .
Es ist eine sehr effiziente Berechnung, die heute noch von Computern in irgendeiner Form verwendet wird.
Der Euklid-Algorithmus erfordert die sukzessive Aufteilung und Berechnung der Reste, bis das Ergebnis erreicht ist. Dies lässt sich am besten anhand eines Beispiels beschreiben :
Was ist die GCD von 56 und 12?
Schritt 1 - Teilen Sie die größere durch die kleinere Zahl :-
56/12 = 4 Rest 8
Schritt 2 - Teilen Sie den Divisor durch den Rest des vorherigen Schritts :-
12/8 = 1 Rest 4
Schritt 3 - Fahren Sie mit Schritt 2 fort, bis keine Reste mehr vorhanden sind in diesem Fall handelt es sich um einen einfachen dreistufigen Vorgang :-
8/4 = 2 kein Rest
In diesem Fall ist der GCD 4.
Dieser Algorithmus wird häufig verwendet, um gemeinsame Brüche auf die niedrigsten Werte und in der fortgeschrittenen Mathematik zu reduzieren. Anwendungen z. B. das Finden ganzzahliger Lösungen für lineare Gleichungen.
3. Das Sieb von Eratosthenes ist ein alter, einfacher Algorithmus
Schöpfer : Eratosthenes
Als es erstellt wurde : 200 v. Chr.
Auswirkungen / Auswirkungen auf die Welt : Die Siebosthenesieb wird allgemein als einer der ältesten Algorithmen aller Zeiten akzeptiert. Sie können alle Primzahlen in einer Tabelle mit bestimmten Zahlen finden so viele, wie Sie einschließen möchten.
Um es auszuführen Sie finden alle Zahlen größer als 2 und streichen dann die durch 2 teilbaren durch. Dann machen Sie dasselbe für nicht durchgestrichene Zahlen größer als 3 usw. ad infinitum bis alle zusammengesetzten Nicht-Prim- Zahlen durchgestrichen sind.
4. Boolesche binäre Algebra war die Grundlage des Informationszeitalters
Schöpfer : George Boole
Als es erstellt wurde : 1847
Auswirkungen / Auswirkungen auf die Welt : Dieser Algorithmus ist weithin als Grundlage der modernen Computercodierung anerkannt. Er wird heute noch verwendet, insbesondere in Computerschaltungen.
Möglicherweise kennen Sie den Begriff Boolesch aus Mathematik, Logik und Computercodierung.
Boolesche Algebra ist ein Zweig der Algebra, in dem eine Variable immer nur wahr oder falsch sein kann - sogenannte Wahrheitswerte normalerweise binär 1 oder 0. Sie wurde zuerst von erfunden. George Boole in seinem 1845 Arbeit Eine Untersuchung der Denkgesetze .
Die Boolesche Algebra wird allgemein als Grundlage für das Informationszeitalter angesehen.
5. Der Algorithmus von Ada Lovelace war das erste Computerprogramm
Schöpfer : Ada Lovelace
Als es erstellt wurde : 1842
Auswirkungen / Auswirkungen auf die Welt : Dieser Algorithmus ist weithin als erstes Computerprogramm anerkannt.
Ada Lovelace verbrachte den größten Teil eines Jahres damit, eine der Vorlesungen von Charles Babbage die von einem italienischen Ingenieur ins Französische transkribiert worden war ins Englische zu übersetzen. Während dieses Prozesses fügte sie pflichtbewusst zusätzliche eigene Erläuterungen hinzu.
Ihre Notizen waren mit A - G gekennzeichnet, wobei letztere einen Algorithmus für eine „analytische Engine“ zur Berechnung von Bernoulli-Zahlen beschreiben. Anmerkung G wird heute allgemein als das erste aufgezeichnete Beispiel für Computercode akzeptiert - was sie zum ersten Computer überhaupt machtProgrammierer.
Der Motor wurde nie gebaut, und so wurde ihr Algorithmus zu Lebzeiten nie getestet. Ihre Arbeit wurde in wiederentdeckt. 1953 als ihre Notizen erneut veröffentlicht wurden.
6. Schnelle Fourier-Transformation zerlegt Signale in Frequenzen
Schöpfer : Carl Gauß, Joseph Fourier, James Cooley und John Tukey
Als es erstellt wurde :1802, 1822, 1965 Auswirkungen / Auswirkungen auf die Welt :
Dieser Algorithmus wird verwendet, um ein Signal in die Frequenzen zu zerlegen, aus denen es besteht - ähnlich wie ein Musikakkord in Frequenzen oder Tonhöhen jeder Note darin ausgedrückt werden kann. Quelle
schnelle Fourier-Transformation FTT Der Algorithmus kann seine Ursprünge auf Carl Gauss zurückführen, der ihn zuerst zur Berechnung der Flugbahnen von Asteroiden erstellt hat. Die Formel wurde später von Joseph Fourier in erweitert. 1822 . Aber die modernere und am weitesten verbreitete Form des Algorithmus wurde von James Cooley und John Tukey in erstellt und veröffentlicht.
1965 . Diese Version ist der weitreichendste Algorithmus in der angewandten Mathematik und hat die Signalverarbeitung revolutioniert. "FFT basiert auf einer Divide-and-Conquer-Strategie, um eine angebliche O N2 -Aufgabe auf einen O N log N -Scherz zu reduzieren. Im Gegensatz zu Quicksort ist die Implementierung jedoch auf den ersten Blick nicht intuitiv und weniger einfach.Dies an sich gab der Informatik den Anstoß, die inhärente Komplexität von Rechenproblemen und Algorithmen zu untersuchen. "-
Barry A. Cipra . 7. Googles Ranking-Algorithmus PageRank könnte der am häufigsten verwendete Algorithmus sein
Schöpfer :
Larry Page hauptsächlich und Sergey Brin Als es erstellt wurde :1996
Auswirkungen / Auswirkungen auf die Welt : PageRank ist heute wohl der am häufigsten verwendete Algorithmus der Welt. Er ist natürlich die Grundlage für das Ranking von Seiten in der Google-Suchmaschine.
Quelle :
Die Hauptvoraussetzung bestand darin, Seiten nach ihrer relativen Bedeutung oder Beliebtheit zu ordnen. Im Allgemeinen haben Seiten, die in der Hierarchie höher erscheinen, mehr Backlinks oder Links zu ihnen.
Die
PageRank-Algorithmus
wird durch die folgende Formel gegeben : PR A = 1-d + d PR T1 / C T1 + ... + PR Tn / C Tn wo :
PR A ist der PageRank von Seite A,
PR Ti ist der PageRank der Seiten Ti, die auf Seite A verlinken.
- C Ti ist die Anzahl der ausgehenden Links auf Seite Ti und;
- d ist ein Dämpfungsfaktor, der zwischen 0 und 1 eingestellt werden kann.
- Wir können sehen, dass dieser Algorithmus Websites nicht als Ganzes bewertet, sondern jede Seite einzeln bewertet. Er kann auch mit einem „ verglichen werden.“
- Pyramidenschema
wobei eine bestimmte Seite rekursiv eingestuft wird, je nachdem, welche anderen Seiten darauf verlinken. PageRank ist in Ungnade gefallen letzte Jahre
wird jedoch weiterhin als Teil einer allgemeinen Reihe anderer Algorithmen bei Google verwendet. 8. Monte-Carlo-Methode Metropolis-Algorithmus wurde in Los Alamos verwendet Schöpfer :
John von Neumann, Stan Ulam und Nick Metropolis
Als es erstellt wurde : 1946
Auswirkungen / Auswirkungen auf die Welt : Es wurde als Los Alamos-Codewort für die stochastischen Simulationen verwendet, mit denen nach dem Zweiten Weltkrieg bessere Atombomben gebaut wurden.
Grundlegende Visualisierung der Monte-Carlo-Methode Quelle
wichtiger Algorithmus
wird verwendet, um Lösungen für numerische Probleme von unüberschaubarer Komplexität durch Nachahmung eines Zufallsprozesses zu approximieren. Es basiert auf wiederholten Zufallsstichproben, um ein Ergebnis zu erhalten. Dabei werden Zufälligkeiten verwendet, um Probleme zu lösen, die im Prinzip deterministisch sein könnten. Der Algorithmus wird häufig bei physikalischen und mathematischen Problemen verwendet und ist am nützlichsten, wenn es schwierig oder unmöglich ist, andere Ansätze zu verwenden. Monte-Carlo-Methoden werden hauptsächlich in drei Problemklassen verwendet: Optimierung, numerische Integration und Generierung von Draws aus einer Wahrscheinlichkeitsverteilung.
9.
Die Simplex-Methode für die lineare Programmierung wurde von der Industrie weitgehend übernommen.
Schöpfer : George Dantzig
Als es erstellt wurde : 1947
Auswirkungen / Auswirkungen auf die Welt : Die s
Implexmethode der linearen Programmierung ist einer der erfolgreichsten Algorithmen aller Zeiten . Es wurde häufig in der Industrie oder in anderen Situationen eingesetzt, in denen das wirtschaftliche Überleben von der Fähigkeit abhängt, die Effizienz innerhalb eines Budgets und / oder anderen Einschränkungen zu maximieren. Quelle : Mark Somerville / YouTube
m
wo m ist die Anzahl der Gleichheitsbeschränkungen bis 3 m zu vervollständigende Iterationen. Es funktioniert mithilfe einer systematischen Strategie, um mögliche Scheitelpunktlösungen innerhalb eines linearen Programms zu generieren und zu validieren. Bei jeder Iteration wählt der Algorithmus die Variable aus, die die größte Änderung in Richtung der Lösung mit minimalen Kosten vornimmt. Diese Variable ersetzt dann eine ihrer Kovariablen, was sie am drastischsten einschränkt, wodurch die Simplex-Methode auf einen anderen Teil des Lösungssatzes und auf die endgültige Lösung verlagert wird.
10.
Krylov-Subraum-Iterationsmethoden werden heute noch verwendet
Schöpfer falls bekannt : Magnus Hestenes, Eduard Stiefel und Cornelius Lanczos
Als es erstellt wurde falls bekannt : 1950
Auswirkungen / Auswirkungen auf die Welt : Die Krylov-Subraum-Iterationsmethode ist eine der zehn wichtigsten numerischen Klassen.
Methoden in der Welt . Die Krylov-Subraum-Iterationsmethoden
sind eine Reihe von Algorithmen, die in den 1950er Jahren am Institut für Numerische Analyse des National Bureau of Standards entwickelt wurden. Sie befassen sich mit der täuschend einfachen Aufgabe, Gleichungen der Form Ax = b zu lösen. Natürlich ist es nicht ganz so einfach, das A ist eine enorme n mal n Matrix. Dies bedeutet daher, dass die algebraische Antwort x = b / A nicht gerade ein Kinderspiel ist. "Iterative Methoden - wie das Lösen von Gleichungen der Form Kx
i
+ 1 = Kx i + b - Axi mit einer einfacheren Matrix K, die idealerweise „nahe“ an A liegt - führt zur Untersuchung von Krylov-Teilräumen. Die nach dem russischen Mathematiker Nikolai Krylov benannten Krylov-Teilräume werden von Potenzen einer Matrix überspannt, die auf einen anfänglichen „Rest“ angewendet wird”Vektor r 0 = b - Axt 0 . "- Barry A. Cipra . "Lanczos hat einen raffinierten Weg gefunden, um eine orthogonale Basis für einen solchen Unterraum zu erzeugen, wenn die Matrix symmetrisch ist. Hestenes und Stiefel schlugen eine noch raffiniertere Methode vor, die als konjugierte Gradientenmethode für Systeme bekannt ist, die sowohl symmetrisch als auch positiv definit sind." Diese Algorithmen wurden in den letzten 50 Jahren kontinuierlich optimiert. Zu ihren aktuellen Iterationen für nicht symmetrische Systeme gehören:
Verallgemeinerte Mindestrestmethode
GMRES und die Bikonjugat-Gradienten-stabilisierte Methode Bi-CGSTAB. 11. Der Kalman-Filter eignet sich hervorragend zur Vorhersage der Zukunft. Schöpfer :
Rudolf E. Kálmán
Als es erstellt wurde falls bekannt : 1958-1961
Auswirkungen / Auswirkungen auf die Welt : Der Kalman-Filter ist ein allgemeines und leistungsstarkes Werkzeug zum Kombinieren von Informationen bei Unsicherheit.
Quelle : Alma News / YouTube
Mit anderen Worten, es hilft Ihnen, eine fundierte Vermutung darüber anzustellen, was ein System wahrscheinlich als nächstes tun wird, natürlich. Kalman-Filter eignen sich hervorragend für Situationen, in denen sich Systeme ständig ändern. Ein weiteres großartiges Merkmal dieses Algorithmus ist, dass er nur wenig Speicher benötigt. Nur das Ergebnis des vorherigen Schritts ist erforderlich, um fortzufahren. Dies macht ihn sehr schnell und ideal für die Problemlösung in Echtzeit.
12.
QR-Algorithmen zur Berechnung von Eigenwerten haben sich als unglaublich nützlich erwiesen
Schöpfer : John GF Francis und von Vera N. Kublanovskaya unabhängig
Als es erstellt wurde : Ende der 1950er Jahre
Auswirkungen / Auswirkungen auf die Welt : Die
QR-Algorithmus vereinfacht die Berechnung von Eigenwerten die wichtigsten Zahlen für Matrizen erheblich. Nach ihrer Entwicklung wurde die Berechnung dieser lästigen Zahlen eher zu einer Routineaufgabe als zu einem gewaltigen und arbeitsintensiven Prozess. Quelle : JoLynne Martinez / Flickr
13. Die Formulierung des Fortran-Optimierungs-Compilers könnte das wichtigste Ereignis in der Programmiergeschichte sein.
Schöpfer :
John Backus und IBM Team
Als es erstellt wurde : 1957
Auswirkungen / Auswirkungen auf die Welt : Möglicherweise der wichtigste Algorithmus / das wichtigste Ereignis in der Computerprogrammierung.
Quelle : GLMEW / Wikimedia Commons
. Backus erkannte seine Bedeutung für die Welt später, 1998, als er sich an die Geschichte von Fortran I, II und III für die erinnerte. IEEE Annals of the History of Computing
. Der Compiler, sagte Backus, "produzierte Code von solcher Effizienz, dass seine Ausgabe die Programmierer erschrecken würde, die ihn studierten." 14 . Quicksort hilft hervorragend beim Sortieren von Dingen
Schöpfer : Tony Hoare von Elliott Brothers, Limited, London
Als es erstellt wurde : 1962
Auswirkungen / Auswirkungen auf die Welt : Es bot eine Möglichkeit, Listen schnell und effizient alphabetisch und numerisch zu sortieren.
An Beispiel für Quicksortierung nach einem zufälligen Satz von Zahlen.
um einen Algorithmus zu erstellen, mit dem diese Aufgabe schnell ausgeführt werden kann. Sein Quicksort
Der Algorithmus verwendete eine rekursive Strategie zum „Teilen und Erobern“, um schnell zu einer Lösung zu gelangen. Es würde sich als zwei- bis dreimal schneller herausstellen, als seine Hauptkonkurrenten Sortierung und Heapsort zusammenführen. Es funktioniert, indem ein Element als "Drehpunkt" ausgewählt wird. Alle anderen werden dann in "größere" und "kleinere" Stapel von Elementen relativ zum Drehpunkt sortiert. Dieser Vorgang wird dann in jedem Stapel wiederholt.
"Obwohl es möglich ist, bei allen N N - 1 / 2-Vergleichen hängen zu bleiben insbesondere, wenn Sie das erste Element in einer bereits sortierten Liste als Drehpunkt verwenden!, Wird Quicksort im Durchschnitt mit O N log N ausgeführt Effizienz. "-
Barry A. Cipra
. Die Einfachheit und Eleganz dieses Algorithmus hat ihn zu seiner Zeit sehr gelobt und ihn Ende der 90er Jahre zum Aushängeschild rechnerischer Komplexität gemacht. 15. JPEG und andere Datenkomprimierungsalgorithmen sind unglaublich nützlich
Schöpfer :
Gemeinsame Fotoexpertengruppe, IBM, Mitsubishi Electric, AT & T, Canon Inc., ITU-T-Studiengruppe 16
Als es erstellt wurde :1992 Auswirkungen / Auswirkungen auf die Welt :
Datenkomprimierungsalgorithmen wie JPEG
, MP3, Zip oder MPEG-2 sind weltweit weit verbreitet. Die meisten sind zu den de facto Standard für ihre jeweilige Anwendung. Sie haben Computersysteme im Laufe der Zeit billiger und effizienter gemacht. Quelle : Basile Morin / Wikimedia Commons
Bleiben Sie über die neuesten technischen Neuigkeiten auf dem Laufenden