Welches sind die wesentlichen Algorithmen für die Menschheit in den letzten Jahrzehnten? [geschlossen]

Welche weltweit wichtigsten Algorithmen haben in den letzten Jahrzehnten am meisten zur Menschheit beigetragen?

Ich dachte, dies ist ein gutes Allgemeinwissen, über das ein Entwickler Bescheid wissen sollte.

Update:
Behalten Sie die Antwort nach Möglichkeit bei einem bestimmten Programmieralgorithmus .
Ich möchte eine Liste der wichtigsten erhalten, nur einen Algorithmus pro Antwort.
Bitte geben Sie an, warum der Algorithmus wichtig und wichtig ist ...

Die Verschlüsselung mit öffentlichen / privaten Schlüsseln ist verdammt wichtig. Internet-Handel wäre ohne ihn nirgendwo so allgegenwärtig.

Dijkstra's Algorithmus

Der Algorithmus ist in jedem Router der Welt vorhanden, um die beste Route zwischen zwei Knoten in einem Netzwerk zu ermitteln.

Schnelle Fourier-Transformation (FFT)

Die FFT ist eine äußerst wichtige und weit verbreitete Methode zum Extrahieren nützlicher Informationen aus abgetasteten Signalen .

Eine schnelle Fourier-Transformation (FFT) ist ein effizienter Algorithmus zur Berechnung der diskreten Fourier-Transformation (DFT) und ihrer Inversen.

Seitenrang

PageRank ist ein Linkanalysealgorithmus, der nach Larry Page benannt ist und von der Google- Internet-Suchmaschine verwendet wird. Dabei wird jedem Element eines mit Hyperlinks versehenen Satzes von Dokumenten, z Wichtigkeit innerhalb des Satzes.

Datenkomprimierungsalgorithmen

In der Informatik und Informationstheorie ist Datenkomprimierung oder Quellencodierung der Vorgang des Codierens von Informationen unter Verwendung von weniger Bits (oder anderen informationstragenden Einheiten), als dies bei einer nicht codierten Darstellung durch Verwendung spezifischer Codierschemata der Fall wäre.

Smith-Waterman (und Needleman-Wunsch)

Dies kann zu weit hergeholt sein, bitte kommentieren.

Smith-Waterman: Der Sequenzalignment-Algorithmus

Ich denke, eines dieser Beispiele sind die Smith-Waterman- und Needleman-Wunsch-Algorithmen und ihre Annäherungen. Alle tun im Wesentlichen dasselbe: Sie richten zwei oder mehr Zeichenfolgen (Sequenzen) aus . Es gibt eine Bedeutung in der Biologie. Wenn DNA- oder Proteinsequenzen ausgerichtet sind, werden Regionen mit struktureller, funktioneller und evolutionärer Ähnlichkeit sichtbar.

BLAST als Nachkomme von Smith-Waterman

Eine Heuristik, die Smith-Waterman nahe kommt, ist BLAST. Es ermöglicht das Durchsuchen von Sequenzen großer Datenbanken nach biologischer Ähnlichkeit. Die Popularität von BLAST ist wirklich groß - es ist sehr wahrscheinlich der am häufigsten verwendete Algorithmus in der Biologie. Die neueren Bereiche in Bioinformatik und Genomik haben neuere und bessere Annäherungen an Smith-Waterman / Needleman-Wunsch-Algorithmen, die genauer sind als BLAST.

Genomversammlung als Nachkomme von Smith-Waterman

Hochdurchsatz-Approximationen von Smith-Waterman und Needleman-Wunsch, die schneller als BLAST sind, werden verwendet, um Genome aus der Schrotflintensequenzierung zusammenzusetzen - wobei das Produkt der Sequenziermaschine eine riesige Menge DNA ist, die aus beliebigen Teilen des Genoms (Milliarden) gelesen wird sehr kurz (50 bis 100 Nukleotide). Der Ansatz wurde verwendet, um das Humangenomprojekt abzuschließen. Die gesamte moderne Sequenzierung erfolgt auf diese Weise.

Multiple Sequence Alignment eine Erweiterung von Smith-Waterman

Es gibt zahlreiche Algorithmen zur Mehrfachsequenzausrichtung, die sich einer Mehrfachsequenzversion des Smith-Waterman / Needleman-Wunsch annähern. Mehrere Sequenzen werden als Gruppe gleichzeitig aneinander ausgerichtet. Es ist ein viel schwierigeres Problem als das paarweise Entsprechende, aber die Lösungen bieten viel mehr Einblick in die biologische Funktion, Struktur und Evolutionsgeschichte verwandter Sequenzen.

Siam nannte die folgenden als die wichtigsten Algorithmen des 20. Jahrhunderts:

1946: Der Metropolis-Algorithmus für Monte Carlo . Durch die Verwendung zufälliger Prozesse bietet dieser Algorithmus eine effiziente Möglichkeit, Antworten auf Probleme zu finden, die zu kompliziert sind, um sie genau zu lösen.

1947: Simplex-Methode zur linearen Programmierung . Eine elegante Lösung für ein häufig auftretendes Planungs- und Entscheidungsproblem.

1950: Krylov-Subraum-Iterationsmethode . Eine Technik zum schnellen Lösen der linearen Gleichungen, die im wissenschaftlichen Rechnen häufig vorkommen.

1951: Der dekompositionelle Ansatz zur Matrixberechnung . Eine Reihe von Techniken für die numerische lineare Algebra.

1957: Der Fortran Optimizing Compiler . Verwandelt High-Level-Code in effizienten computerlesbaren Code.

1959: QR-Algorithmus zur Berechnung von Eigenwerten . Eine weitere wichtige Matrixoperation wurde schnell und praktisch durchgeführt.

1962: Quicksort-Algorithmen zum Sortieren . Für den effizienten Umgang mit großen Datenbanken.

1965: Schnelle Fourier-Transformation . Der vielleicht allgegenwärtigste Algorithmus, der heute verwendet wird, unterteilt Wellenformen (wie Schall) in periodische Komponenten.

1977: Integer Relation Detection . Eine schnelle Methode zum Erkennen einfacher Gleichungen, die durch Sammlungen scheinbar nicht verwandter Zahlen erfüllt werden.

1987: Schnelle Multipolmethode . Ein Durchbruch im Umgang mit der Komplexität von n-Körper-Berechnungen, die bei Problemen von der Himmelsmechanik bis zur Proteinfaltung angewendet werden.

Persönlich würde ich Integer Relation Detection durch PageRank ersetzen .

PageRank, liebe es oder hasse es, aber es beeinflusst die Entscheidungen und Handlungen von Millionen Menschen weltweit, die täglich googeln.

Wenn ich die drei wichtigsten Algorithmen auflisten müsste, die heute in Computern verwendet werden, würde ich sagen:

1. Binäre Suche
2. Schnelle Sorte
3. Dijkstra's Algorithmus

Der Algorithmus für die binäre Suche wird ständig verwendet, um ein Element in einer sortierten Liste einzugrenzen. Die meisten Index-Lookups verwenden irgendwann etwas in dieser Richtung. Dieser Algorithmus bietet eine Suche in einer geordneten Liste in o (log n) Zeit.

Der Quicksort- Algorithmus hat es endlich geschafft, die Sortierung auf O (n log n) Average Case und O (n ^ 2) Worst Case herabzusetzen. Das Sortieren ist eine der häufigsten Datenaufgaben in einem Computer und eine der teuersten. Die Verbesserung der durchschnittlichen Sortierung von Fällen war ein enormer Effizienzsprung.

Wie gesagt, erzeugt der Dijkstra-Algorithmus einen kürzesten Weg zwischen Punkten innerhalb eines Graphen. Dies wird häufig für alle Arten von Routing-Anwendungen verwendet, insbesondere im Hinblick auf das Internet selbst, um sicherzustellen, dass der schnellste Weg durch das Wirrwarr von miteinander verbundenen Routern verwendet wird.

Satz von Bayes

Es hat wahrscheinlich am meisten dazu beigetragen, die Menge an zeitraubendem Spam in meinem Posteingang auf einem überschaubaren Niveau zu halten.

Natürlich habe ich es schon in zahlreichen anderen sinnvollen Anwendungen verwendet, aber SPAM-Töten ist mein Favorit.

TimSort

Dies ist der Sortieralgorithmus, der jetzt in Python , Java 7 und Android verwendet wird

Grundsätzlich gilt:

• O (N log N) Worst Case (entartet nicht)
• O (N) für fast sortierte Liste (tatsächlich N-1genau auf bereits sortierter Liste)

Und die Schönheit davon? Es ist stabil ! Und damit für die Multipass-Sortierung nach verschiedenen Kriterien geeignet.

Übrigens, wenn jemand eine optimierte C ++ - Implementierung zur Hand hat ...

Alle Algorithmen, die zur Lösung des Sichtbarkeitsproblems in der 3D-Computeranimation verwendet wurden, scheinen mir von entscheidender Bedeutung zu sein.

Algorithmus des Malers

Der Algorithmus des Malers, der auch als Prioritätsfüllung bezeichnet wird, ist eine der einfachsten Lösungen für das Sichtbarkeitsproblem in 3D-Computergrafiken. Wenn Sie eine 3D-Szene auf eine 2D-Ebene projizieren, müssen Sie irgendwann entscheiden, welche Polygone sichtbar und welche ausgeblendet sind.

Z-Pufferung

In der Computergrafik ist Z-Buffering die Verwaltung von Bildtiefenkoordinaten in dreidimensionalen (3-D) Grafiken, die normalerweise in Hardware und manchmal in Software ausgeführt werden. Dies ist eine Lösung für das Sichtbarkeitsproblem. Hierbei handelt es sich um das Problem, zu entscheiden, welche Elemente einer gerenderten Szene sichtbar und welche ausgeblendet sind. Der Algorithmus des Malers ist eine weitere gängige Lösung, die zwar weniger effizient ist, jedoch auch nicht-opake Szenenelemente verarbeiten kann. Z-Pufferung wird auch als Tiefenpufferung bezeichnet.

Versteckte Oberflächenbestimmung

In der 3D-Computergrafik wird mithilfe der Bestimmung der verborgenen Oberfläche (auch als Entfernung verborgener Oberflächen (HSR) bezeichnet), der Okklusionsentfernung (OC) oder der Bestimmung der sichtbaren Oberfläche (VSD) bestimmt, welche Oberflächen und Oberflächenteile unter bestimmten Gesichtspunkten nicht sichtbar sind Ein Bestimmungsalgorithmus für verborgene Oberflächen ist eine Lösung für das Sichtbarkeitsproblem, das eines der ersten Hauptprobleme auf dem Gebiet der 3D-Computergrafik darstellte. Der Vorgang der Bestimmung verborgener Oberflächen wird manchmal als Verstecken bezeichnet, und ein solcher Algorithmus wird manchmal als Verstecken bezeichnet Das Analogon für das Rendern von Linien ist das Entfernen von versteckten Linien. Die Bestimmung der versteckten Oberfläche ist erforderlich, um ein Bild korrekt zu rendern, damit man beispielsweise in der virtuellen Realität nicht durch Wände schauen kann.

Welches Sie benötigen, um Ihr aktuelles Problem zu lösen.

Soundex ist ein phonetischer Algorithmus zum Indizieren von Namen nach Klang.

Viterbi-Algorithmus

Ursprünglich zum Dekodieren von faltungsfehlerkorrigierenden Codes verwendet, wird sie jetzt zur Lösung einer breiten Klasse von Erkennungsproblemen verwendet (von Spracherkennung bis Bioinformatik). Sie finden es in verschiedenen Kommunikations- und Speichergeräten.

MP3

Obwohl es ein allgemeinerer Begriff als ein spezifischer Algorithmus ist, würde ich MP3 als die Zusammenfassung der verschiedenen Algorithmen und Techniken erwähnen, die zusammenarbeiten, um dieses verlustbehaftete Audioformat zu erzeugen.

Es war sicherlich im "digitalen Zeitalter" von großer Bedeutung.

Runge-Kutta numerische Integration. Ohne sie wären viele Simulationen nicht möglich. Kein Weltraumprogramm, keine Atomkraft, keine Ballistik, keine Sportsimulationen, keine kugelsicheren Westen, keine Crashtest-Simulation, keine Simulation von Flüssigkeitsbewegungen, keine Simulationen chemischer Wechselwirkungen, keine erdbebensicheren Gebäude ... die Liste geht weiter.

Sortieralgorithmus.

Schnelle Sorte

Sortieren durch Einfügen

Einfach zu implementieren, sehr schnell auf kleinen Listen und in Merge Sort / Quicksort-Implementierungen verwendet, um sie zu beschleunigen. Es ist stabil und arbeitet in O (n) auf sortierten Listen (wenn in aufsteigender Reihenfolge sortiert).

Gauß-Jordan in der Matrixberechnung

Kalman Filter

Es wird häufig in der Navigation und Zielverfolgung eingesetzt (für fast jeden Sensor: Radar, Sonar, FLIR, Ladar). Ein Lehrbuch zeigt eine Anwendung in einem Festplattencontroller. Robotersteuerungssysteme verwenden häufig Kalman-Filter.

Gesprochene und geschriebene Sprache.

Sie sind derzeit einer der effizientesten Algorithmen, um Wissen von einer Sache zur anderen zu übertragen. Ohne Sprache könnte die Zivilgesellschaft nicht existieren und Informationen könnten nicht vermittelt werden.

Die Heap- Datenstruktur und die zugehörigen Algorithmen für die Erstellung und Wartung von Heaps.

Und respektiere Quicksort. Auch wenn es nicht immer die Art der Wahl ist, ist es einer der grundlegenden Algorithmen in der historischen Entwicklung der Informatik und ein hervorragendes Mittel zum Verständnis von Rekursion und Algorithmusanalyse. Es ist wunderschön und ich liebe es.

Indizierungsalgorithmen wie B-Tree, B + -Baum, Hash-Index, Binärbaum-Index usw. Zur Indizierung großer Datenmengen.

Mit MapReduce können Sie die Verarbeitung großer Datenmengen aufteilen, erobern und parallelisieren.

Brute-Force-Algorithmus!

Viele Leute unterschätzen diesen Brute-Force-Algorithmus. Tatsächlich wird es meistens verwendet, um Probleme ohne Muster zu lösen. Ich liebe es sehr!

Bubble Sort!

Bubble Sort ist nicht so schlimm wie Bogosort . Deshalb stimme ich für die Bubble-Sorte.