Werbung

7 wesentliche Algorithmen, die die Welt regieren

Algorithmen gibt es schon seit Tausenden von Jahren, aber diese 7 modernen Algorithmen sind für die Funktionsweise der modernen Welt von wesentlicher Bedeutung.

Dies ist der zweite Artikel in einer siebenteiligen Reihe über Algorithmen und Berechnungen, in der untersucht wird, wie wir einfache Binärzahlen verwenden, um unsere Welt mit Energie zu versorgen. Der erste Artikel Wie Algorithmen die Welt steuern, in der wir leben , kann gefunden werden hier .

Die ältesten Algorithmen jemals aufgenommen waren auf alten babylonischen Tafeln von ungefähr 1.800 v. Chr. Erläuterung der spezifischen Verfahren zur Berechnung verschiedener Werte wie Quadratwurzeln und anderer Kennzahlen. Wir verwenden immer noch einen der griechischen Mathematiker Euklids bekannteste Algorithmen - seine Methode zum Auffinden der größter gemeinsamer Teiler zuerst formuliert 300 v. Chr. —In der heutigen Programmierung wegen seiner eleganten Einfachheit.

Erst im Zeitalter der Computer begannen Algorithmen jedoch, scheinbar mathematische Probleme mathematisch anzugehen, und diese modernen Algorithmen sind einige der wichtigsten Lösungen für Probleme, die derzeit die weltweit am häufigsten verwendeten Systeme antreiben.

PageRank

Quelle : 345Kai | Stanner / Wikimedia Commons

nach Diskussion PageRank kurz in der erster Artikel in dieser Serie Google PageRank-Algorithmus ist ein guter Anfang, da es dazu beigetragen hat, Google zum heutigen Internetgiganten zu machen.

VERBINDUNG: TIPPS UND TRICKS FÜR DIE GOOGLE-SUCHE, UM GENAU ZU FINDEN, WAS SIE WOLLEN

PageRank war der erste Algorithmus, den Larry Page und Sergei Brin Ende der 90er Jahre entwickelt haben, um Webseiten im Internet zu indizieren und zu bewerten und damit schließlich ihre neue Google-Suchmaschine zu betreiben.

Das wesentliche Merkmal von PageRank ist, dass es eine Bewertung dafür bestimmt, wie maßgeblich eine Seite ist, basierend auf den Berechtigungsbewertungen der Seiten, die darauf verlinken. Autorisierendere Seiten, die auf eine Seite verlinken, verleihen dieser Seite wiederum ein höheres Maß an Berechtigung als andere, also inAuf diese Weise teilen die Personen, die den Inhalt der Seite schreiben und auf andere Seiten verlinken, Google effektiv mit, welche Seiten mehr Gewicht haben als andere.

Werbung

PageRank war revolutionär, als es eingeführt wurde und andere Suchmaschinen schnell vom Markt verdrängte. PageRank ist so wichtig, dass sich eine ganze Branche um den Algorithmus selbst entwickelt hat : Suchmaschinenoptimierung . The PageRank Algorithmus so gründlich etabliert Googles Dominanz als einzige Suchmaschine, die das Wort ausmachte Google offiziell wurde ein Verb weniger als acht Jahre nach Gründung des Unternehmens. Obwohl PageRank ist jetzt nur einer von ungefähr 200 Maßnahmen Google Wird verwendet, um eine Webseite für eine bestimmte Abfrage zu bewerten. Dieser Algorithmus ist immer noch eine wesentliche treibende Kraft hinter seiner Suchmaschine.

Schlüsselaustauschverschlüsselung

Quelle : Kristen Gilden / Wikimedia Commons

Wie sichern Sie Informationen, die effektiv über einen Lautsprecher an einer Straßenecke ausgelesen werden, die jeder hören kann? Dies ist die Herausforderung beim Versuch, den über öffentliche Kommunikationsleitungen übertragenen Netzwerkkommunikationsverkehr zu schützen. Jeder kann diese Kommunikation unterwegs abfangen und lesendie Daten.

Werbung

Code-Chiffren die jedes Datenbyte basierend auf einer programmatischen Formel in ein anderes Datenbyte konvertieren, sind die offensichtliche Antwort. Diese funktionieren jedoch nicht, wenn eine Partei nicht weiß, welche Verschlüsselung die andere Partei verwendet, und am sicherstenDie Kommunikation findet zwischen Parteien statt, die keinen vorherigen Kontakt hatten, also keine Möglichkeit haben, sich vorher auf einen zu einigen.

Die Schlüsselaustausch-Verschlüsselungsalgorithmus macht das scheinbar Unmögliche möglich, indem es ein einziges gemeinsames mathematisches Geheimnis zwischen zwei Parteien aufbaut, die sich nicht einmal kennen, und wird verwendet, um die Daten zu verschlüsseln und zu entschlüsseln, über ein öffentliches Netzwerk und ohne dass dies jemand anderes tutin der Lage, das Geheimnis herauszufinden. So funktioniert es :

* Ich wähle eine Nummer und Sie wählen eine Nummer, und wir teilen diese Nummern mit niemandem unseren privaten Schlüsseln.
* Einer von uns gibt eine Zufallszahl über einen öffentlichen Kanal bekannt, die jeder lesen kann den öffentlichen Schlüssel.
* Ich wende meine private Nummer als Exponent auf die öffentliche Nummer an und erhalte das Ergebnis, und Sie tun dasselbe.
* Wir tauschen dann unsere verschiedenen Ergebnisse über den öffentlichen Kanal aus, sodass Sie mein Ergebnis und ich Ihr Ergebnis haben.
* Ich wende meine private Nummer als Exponenten auf das Ergebnis an, das Sie gerade über den öffentlichen Kanal gesendet haben, und erhalte einen Wert, und Sie tun dasselbe.
* Dieser Wert ist für uns beide gleich und wir verwenden diesen Wert, um unsere Kommunikation zu verschlüsseln.

Werbung

Da keiner von uns jemals öffentlich seinen eigenen privaten Schlüssel preisgibt, ist es für jeden, der sieht, dass diese Informationen weitergegeben werden, praktisch unmöglich zu bestimmen, welchen Wert wir zum Verschlüsseln unserer Kommunikation verwenden. Der Prozess, der das gemeinsame Geheimnis erzeugt, beruht auf zwei GrundlagenIdeen. Erstens a m n und a n m gibt Ihnen genau die gleiche Antwort. Die privaten Schlüssel sind m und n und der öffentliche Schlüssel ist a. Dies wird immer funktionieren.

Aber was ist, wenn Sie all dies als Dritter beobachten, der versucht, die übergebenen Nachrichten abzufangen? Die einzige unverschlüsselte Information, die übergeben wird, ist der öffentliche Schlüssel a und die beiden Ergebnisse a m und a n außer dass die beiden Ergebnisse für Sie nicht so aussehen; Sie sehen nur zwei sehr große scheinbar zufällige Zahlen, von denen Sie wissen, dass sie mathematisch mit dem öffentlichen Schlüssel a verbunden sind. Ohne m oder n zu kennen, der auf dem nie geteilt wirdöffentlicher Kanal, der einzige Weg, um die zwei privaten Schlüssel herauszufinden, die die Chiffre erzeugen, ist die Umkehrung Prozess zur Potenzierung der das findet diskreter Logarithmus entweder von m oder n.

Werbung

Es gibt derzeit keine bekannte Möglichkeit für einen klassischen Computer, dies zu tun, bevor die Sonne explodiert und uns alle in ein paar Milliarden Jahren aus dem Verkehr zieht.

Warum dies so schwierig ist, ist Gegenstand eines anderen Artikels, aber es ist wirklich so schwierig, was es perfekt für die öffentliche Verschlüsselung macht. Obwohl nicht mehr für sich allein verwendet, ist die öffentlich-private Schlüsselstruktur des Schlüsselaustauschalgorithmus ist ein wesentliches Merkmal fortgeschrittener Verschlüsselungsschemata wie der RSA-Verschlüsselung.

Backpropagation

Quelle : Cecbur / Wikimedia Commons

Backpropagation über ein neuronales Netzwerk ist einer der wichtigsten Algorithmen, die in den letzten 50 Jahren erfunden wurden.

Neuronale Netze arbeiten, indem Eingabedaten in ein Netzwerk von Knoten eingespeist werden, die Verbindungen zur nächsten Schicht von Knoten haben, und unterschiedliche Gewichte, die diesen Verbindungen zugeordnet sind, die bestimmen, ob die Informationen, die sie über diese Verbindung empfangen, an die nächste Schicht von Knoten weitergeleitet werden.Wenn die Informationen durch die verschiedenen sogenannten "versteckten" Schichten des Netzwerks gelangen und in die Ausgabeschicht gelangen, sind dies normalerweise unterschiedliche Entscheidungen darüber, was das neuronale Netzwerk für die Eingabe hält. Wenn es mit einem Bild eines Hundes gefüttert wurde, ist eskönnte die Optionen Hund, Katze, Maus und menschliches Kind haben. Es wird eine Wahrscheinlichkeit für jede dieser haben und die höchste Wahrscheinlichkeit wird als Antwort gewählt.

Werbung

Hier ist Rückausbreitung kommt herein. Backpropagation ist die Ausbreitung des Fehlers zurück durch das neuronale Netzwerk und über die Verbindungen, die die falsche Antwort erzeugt haben. Im Laufe der Zeit werden alle diese Verbindungen angepasst und das Gewicht dieser Verbindung verringert. Im Laufe der Zeitkann ein neuronales Netzwerk lernen, was etwas ist, indem es lernt, was etwas ist ist nicht und auf die richtige Antwort konvergieren.

Auf diese Weise können neuronale Netze trainiert werden, um anhand des zuletzt gesehenen Films zu erkennen, wie ein Gesicht aussieht, wie eine Stimme klingt und welche Filme Ihnen gefallen könnten. Ohne Rückausbreitung tief lernende neuronale Netze würden nicht funktionieren, und ohne diese neuronalen Netze hätten wir keine schnellen Fortschritte in künstliche Intelligenz das haben wir im letzten Jahrzehnt gesehen.

Werbung

Komprimierung

Quelle : stoimen.com / Wikimedia Commons

Wenn Sie eine Datei komprimieren möchten, um sie kleiner und einfacher über ein Netzwerk zu verwalten oder Speicherplatz zu sparen, und Sie sich die Datenbytes vor Ihnen ansehen, wo würden Sie überhaupt anfangen? Wie erstellen Sie Bytes?kleiner, damit sie weniger Platz beanspruchen, aber Sie können sie anschließend dekomprimieren, um das wiederherzustellen, was Sie zu Beginn hatten?

Verschiedene Variationen Komprimierung existieren, aber fast alle basieren auf einem ähnlichen Trick; sie verwenden Referenzen und Offsets anstelle der tatsächlichen Daten selbst, um die Daten mit weniger Platz darzustellen.

Angenommen, Sie hatten eine Zeichenfolge, die Sie komprimieren wollten. ABBCABBCABACABACABACDDDBDB 26 Zeichen lang. Eine andere Möglichkeit, dies zu schreiben, ist ABBC2ABAC3D2DB2 wobei die Zahlen nach einer Zeichenfolge angeben, wie oft diese Zeichenfolge gedruckt werden muss. Die komprimierte Zeichenfolge ist jetzt nur noch 15 Zeichen lang.

Das scheint nicht viel zu sein, aber wir haben gerade den Speicherbedarf dieser Zeichenfolge um etwas mehr reduziert. 40 Prozent . Wenn Sie Dateien mit einer Größe von Gigabyte haben, sind diese 40 Prozent riesig.

Jetzt können nicht alle Daten sein komprimiert so und die Effizienz der Komprimierung variiert, aber das Komprimieren so vieler Daten wie möglich, so oft wir können, verhindert, dass Kommunikationsnetze und Festplatten durch eine massive Menge sich wiederholender Aufblähungen verstopft werden. Diese Grundidee dahinter Dateikomprimierung hat das Streaming von Filmen, das Streamen von Musik, Online-Videospielen und so ziemlich alles andere ermöglicht, ehrlich gesagt. Komprimierung ist überall und für die effiziente Übertragung und Speicherung von Informationen unerlässlich.

Such- und Sortieralgorithmen

Suchen und Sortieren sind eine spezielle Form von Algorithmen, da viele sehr unterschiedliche Techniken verwendet werden zum Sortieren ein Datensatz oder zum Suchen für einen bestimmten Wert innerhalb eines und keiner ist immer besser als der andere. Quicksort Algorithmus ist möglicherweise besser als der Mergesort Algorithmus, wenn Speicher ein Faktor ist, aber wenn Speicher kein Problem ist, Mergesort kann manchmal schneller sein; und alles ist besser als Bubblesort .

Gleiches gilt, wenn Sie haben zum Suchen durch einen Datensatz für einen bestimmten Wert. Auf einer perfekt sortierten Liste, wie einem Wörterbuch, a binäre Suche ist der schnellste Weg, um das zu bekommen, was Sie wollen, aber wenn Sie das längste Wort im Wörterbuch oder einen unsortierten zufälligen Wortstrom aus einer Million aus dem Internet heruntergeladener Artikel finden möchten, dann ist das Heapsort Sortieralgorithmus verdoppelt sich als Ihr Suchalgorithmus da der höchste Wert - oder der niedrigste, wenn Sie danach suchen - in einem Datensatz immer ganz oben auf dem Heap steht.

Die Art der Suche hängt immer von der Datenstruktur ab, die Sie durchsuchen Listen, Bäume, Diagramme usw.. Wenn Sie jedoch ein Programm haben, das mit Daten etwas Nützliches tut, wird garantiert, dass es verwendet wird eine Suche und ein Sortieralgorithmus irgendwo in seinem Code. Sie alle sind wichtig und Programmierer verwenden alle , die ganze Zeit und sie bilden die Grundlage, auf der Datenstrukturen und fortgeschrittenere Algorithmen aufgebaut sind.

Dijkstras kürzester Weg

Quelle : Shiyu Ji / Wikimedia Commons

Dijkstra's Shortest Path-Algorithmus ist ein Suchalgorithmus für Grafiken, aber es ist besonders zu erwähnen, weil es nicht so ist andere Suchalgorithmen .

nach Dijkstra selbst 1959 Informatiker Edsger Dijkstra saß mit seinem Verlobten irgendwo in den Niederlanden und trank Kaffee, als er einen Algorithmus schrieb, der die Leistungsfähigkeit des Computersystems, an dem er arbeitete, einem allgemeinen, nicht rechnergestützten Publikum auf verständliche Weise zeigen konnte.

Er zeichnete 64 Städte in einem Diagramm auf, wobei jede Stadt durch einen Knoten dargestellt wurde, und zeichnete verschiedene Pfade, die technisch als Kanten bezeichnet werden, zwischen ihnen. Er bezeichnete einen Knoten Rotterdam und einen anderen Knoten Groningen und entwarf einen Algorithmus, der den kürzesten fandPfad zwischen den beiden Knoten. Dies erfolgt b Wenn Sie an einem Quellknoten beginnen und den kürzesten Pfad zwischen diesem Knoten und jedem anderen im Diagramm finden und anhalten, sobald er den Zielknoten erreicht hat.

Er glaubte mit ziemlicher Sicherheit nicht, dass er etwas erschaffen würde, das eines der am häufigsten verwendete Algorithmen in der Welt, aber in diesen 20 Minuten im Jahr 1959 Dijkstra aktiviert alles von GPS-Routing auf unseren Handys, um Signalführung über Telekommunikationsnetze und eine beliebige Anzahl zeitkritischer logistischer Herausforderungen wie den Versand eines Pakets im ganzen Land. As ein Suchalgorithmus , Dijkstras kürzester Weg zeichnet sich mehr als die anderen nur durch die enorme Technologie aus, die darauf beruht.

TCP / IP-Routing-Protokollalgorithmen

Quelle : Das Opte-Projekt über PRI.org

Falls Sie es noch nie gesehen haben das Internet . Zumindest sieht es sich sowieso so.

Als das Internet begann, waren die Standards für das Übertragungssteuerungsprotokoll / Internetprotokoll TCP / IP im Grunde genommen brandneu und mathematisch einwandfrei. Algorithmen Das Herzstück des Standard-Internetprotokolls wurde nicht mit dem unergründlichen Verkehrsaufkommen erstellt, das es verwalten muss. Eine ineffiziente Algorithmus hätte das Internet knien können, bevor es wirklich in Gang kam.

Zum Glück für uns, als sich das Internet auf alle Bereiche unseres Lebens ausdehnte, waren die ersten ersten Entscheidungen, aus denen sich TCP / IP zusammensetzt, für den erfolgreichen Betrieb des gesamten Netzwerks von entscheidender Bedeutung, da der Datenverkehr über die wildesten Erwartungen hinaus explodierte.

Eine der kritischsten dieser Entscheidungen war, welcher Algorithmus zum Weiterleiten von Datenpaketen verwendet werden soll. Dabei handelt es sich um die tatsächlichen Informationen, die wir über das Internet senden und empfangen. Die zwei am häufigsten verwendete über das Internet, die Distance-Vector Routing Protocol-Algorithmus DVRPA und die Link-State-Routing-Protokoll-Algorithmus LSRPA sind die zwei wesentliche Algorithmen Wir verwenden jeden Tag, um den Datenverkehr zwischen den Milliarden verbundener Netzwerke, aus denen das Internet besteht, effizient weiterzuleiten.

DVRPA funktioniert durch Ermitteln der kürzesten Entfernung zwischen dem Quell- und dem Zielnetzwerk. Es kann eine beliebige Anzahl von Metriken verwenden, um dies zu berechnen, verwendet jedoch normalerweise etwas sehr Einfaches wie die Anzahl der Router- und Server- "Hops", die auf dem Weg ausgeführt werden müssenAuf die Einfachheit kommt es an DVRPA .

Transport

Neuer Algorithmus könnte Städte vor zu vielen Taxis retten

Router, die diesen Algorithmus verwenden, zeichnen alle bekannten Netzwerke in einer Tabelle zusammen mit der Entfernung zu jedem auf. Wenn dieser Router eine neue Verbindung zu einem anderen Netzwerk herstellt, das normalerweise als Nachbarn oder Peers bezeichnet wird, übergibt er ihnen diese Tabelle, die dieser Peer verwendetUm die Tabelle zu aktualisieren, bevor die aktualisierte Tabelle an ein Netzwerk übergeben wird, mit dem sie bereits verbunden ist usw. Auf diese Weise breiten sich Änderungen schnell über diese Verbindungen aus, sodass jedes Netzwerk weiß, wie weit es von einem anderen Netzwerk im Internet entfernt istIch garantiere nicht die schnellste Verbindung, sie ist sehr schnell und nicht sehr kompliziert zu erarbeiten. Insgesamt hat sie mit Modifikationen zur Verbesserung ihrer Effizienz recht gut funktioniert.

LSRPA arbeitet mittlerweile im Wesentlichen auf die gleiche Weise, aber Router, auf denen der LSRPA-Algorithmus ausgeführt wird, führen eine Karte des gesamten Internets, mit dem eine Verbindung hergestellt werden kann, und testen routinemäßig verschiedene Verbindungen und analysieren sie, um die realistischeren Kosten dieser Verbindung in Bezug auf Berechnung und Zeit zu ermittelnusw. Wie DVRPA leitet es beim Herstellen einer Verbindung seine Karte an das Netzwerk weiter, mit dem es eine Verbindung herstellt, sodass sich Änderungen am Netzwerk im gesamten Netzwerk ausbreiten und Routern, die den Algorithmus verwenden, ein viel realistischeres Bild der verschiedenen Verbindungen erhalten.

Während es wahrscheinlicher ist, dass es häufiger die effizienteste Route findet, ist es rechenintensiver und nicht so gut etabliert wie DVRPA. Da sich die Computerhardware jedoch verbessert und neue Geräte die älteren Netzwerkknoten ersetzen, treten mehr davon aufDas Internet wird in der Lage sein, die Ausführung von LSRPA zu verwalten, wodurch die Effizienz des gesamten Internets verbessert wird.

Das Problem der Effizienz bezieht sich jedoch nicht nur auf die Hardware. Die Effizienz der verschiedenen Algorithmen kann ein System herstellen oder beschädigen. Glücklicherweise wissen wir, wie wir die Effizienz von Algorithmen mit mathematischer Präzision messen können, um das Richtige zu findenAlgorithmus für das richtige Problem.

Der dritte Teil unserer Reihe über Algorithmen und Berechnungen Zeitkomplexität: Warum manche Algorithmen Milliarden von Jahren laufen , kann gefunden werden hier .

Folgen Sie uns auf

Bleiben Sie über die neuesten technischen Neuigkeiten auf dem Laufenden

Geben Sie einfach Ihre E-Mail-Adresse ein und wir kümmern uns um den Rest :

Mit Ihrer Anmeldung stimmen Sie unserer zu Nutzungsbedingungen und Datenschutzerklärung . Sie können sich jederzeit abmelden.