Um die Bedeutung von Algorithmen zu demonstrieren (z. B. für Studierende und Professoren, die keine theoretischen Kenntnisse besitzen oder aus ganz anderen Bereichen stammen), ist es manchmal hilfreich, eine Liste von Beispielen zur Hand zu haben, in denen Kernalgorithmen in kommerziellen, staatlichen, oder weit verbreitete Software / Hardware.
Ich suche solche Beispiele, die folgende Kriterien erfüllen:
Die Software / Hardware, die den Algorithmus verwendet, sollte derzeit weit verbreitet sein.
Das Beispiel sollte spezifisch sein. Bitte geben Sie einen Hinweis auf ein bestimmtes System und einen bestimmten Algorithmus.
Beispielsweise ist in "Algorithmus X ist nützlich für die Bildverarbeitung" der Begriff "Bildverarbeitung" nicht spezifisch genug; In "Google-Suche verwendet Grafikalgorithmen" ist der Begriff "Grafikalgorithmen" nicht spezifisch genug.Der Algorithmus sollte in der Regel im Grundstudium oder im Doktorat unterrichtet werden. Klassen in Algorithmen oder Datenstrukturen. Im Idealfall wird der Algorithmus in typischen Lehrbüchern für Algorithmen behandelt. ZB "Das bekannte System X verwendet den wenig bekannten Algorithmus Y" ist nicht gut.
Aktualisieren:
Nochmals vielen Dank für die tollen Antworten und Links! Einige Leute bemerken, dass es schwierig ist, die Kriterien zu erfüllen, da Kernalgorithmen so verbreitet sind, dass es schwierig ist, auf eine bestimmte Verwendung hinzuweisen. Ich sehe die Schwierigkeit. Aber ich denke, es lohnt sich, konkrete Beispiele zu nennen, denn meiner Erfahrung nach sagen die Leute: "Sehen Sie, Algorithmen sind wichtig, weil sie so gut wie überall sind !" funktioniert nicht.
Antworten:
Algorithmen, die der Haupttreiber hinter einem System sind, sind meiner Meinung nach in Kursen ohne Algorithmus leichter zu finden, aus dem gleichen Grund, warum Sätze mit sofortiger Anwendung in Kursen für angewandte Mathematik leichter zu finden sind als in Kursen für reine Mathematik. Es ist selten, dass ein praktisches Problem die genaue Struktur des abstrakten Problems in einer Vorlesung hat. Um argumentativ zu sein, sehe ich keinen Grund, warum modisches Algorithmus-Kursmaterial wie die Strassen-Multiplikation, der AKS-Primalitätstest oder der Moser-Tardos-Algorithmus für praktische Probleme bei der Implementierung einer Videodatenbank, eines optimierenden Compilers oder eines Betriebssystems relevant sind ein Netzüberlastungskontrollsystem oder ein beliebiges anderes System. Der Wert dieser Kurse besteht darin, zu lernen, dass es komplizierte Möglichkeiten gibt, die Struktur eines Problems zu nutzen, um effiziente Lösungen zu finden. Bei fortgeschrittenen Algorithmen trifft man auch auf einfache Algorithmen, deren Analyse nicht trivial ist. Aus diesem Grund würde ich einfache randomisierte Algorithmen oder PageRank nicht verwerfen.
Ich denke, Sie können jedes große Stück Software auswählen und darin implementierte grundlegende und erweiterte Algorithmen finden. Als Fallstudie habe ich dies für den Linux-Kernel getan und einige Beispiele aus Chromium gezeigt.
Grundlegende Datenstrukturen und Algorithmen im Linux-Kernel
Links führen zum Quellcode von Github .
B + Bäume mit Kommentaren, die Ihnen mitteilen, was Sie in den Lehrbüchern nicht finden können.
Prioritätssortierte Listen für Mutexe , Treiber usw.
Radix-Bäume werden für die Speicherverwaltung , NFS-bezogene Suchvorgänge und Netzwerkfunktionen verwendet.
Prioritätsheap , wörtlich übersetzt eine Lehrbuchimplementierung, die im Kontrollgruppensystem verwendet wird .
Hash-Funktionen , mit einem Verweis auf Knuth und auf ein Papier.
Einige Teile des Codes, wie dieser Treiber , implementieren ihre eigene Hash-Funktion.
Bit-Arrays , die für den Umgang mit Flags, Interrupts usw. verwendet werden und in Knuth Vol. 3, No. 4.
Semaphoren und Spin-Locks
Die binäre Suche wird für die Interrupt-Behandlung , die Cache-Suche usw. verwendet.
Binäre Suche mit B-Bäumen
Tiefe erste Suche und Variante in der Verzeichniskonfiguration verwendet .
Mit der Breitensuche wird die Richtigkeit der Sperre zur Laufzeit überprüft.
Die Sortierung nach verknüpften Listen wird für die Speicherbereinigung , die Dateisystemverwaltung usw. verwendet.
Bubble-Sortierung ist auch in einer Treiberbibliothek erstaunlich implementiert.
Knuth-Morris-Pratt-String-Matching ,
Boyer-Moore-Musterabstimmung mit Referenzen und Empfehlungen, wann die Alternative zu bevorzugen ist.
Datenstrukturen und Algorithmen im Chromium-Webbrowser
Links verweisen auf den Quellcode in Google-Code . Ich werde nur einige auflisten. Ich würde vorschlagen, die Suchfunktion zu verwenden, um Ihren bevorzugten Algorithmus oder Ihre bevorzugte Datenstruktur nachzuschlagen.
Programmiersprachenbibliotheken
Ich denke, sie sind eine Überlegung wert. Die Entwickler der Programmiersprachen hielten es für die Zeit und Mühe einiger Ingenieure, diese Datenstrukturen und Algorithmen zu implementieren, damit andere dies nicht tun müssten. Das Vorhandensein von Bibliotheken ist ein Grund dafür, dass wir grundlegende Datenstrukturen in Software wiederfinden, die in C geschrieben ist, jedoch weniger für Java-Anwendungen.
Allokations- und Planungsalgorithmen
Ich finde diese interessant, denn obwohl sie als Heuristik bezeichnet werden, bestimmt die von Ihnen verwendete Richtlinie die Art des Algorithmus und die Datenstruktur, die erforderlich sind. Man muss also über Stapel und Warteschlangen Bescheid wissen.
Kern-Utils in * nix-Systemen
Kryptographische Algorithmen
Dies könnte eine sehr lange Liste sein. Kryptografische Algorithmen sind in jeder Software implementiert, die sichere Kommunikationen oder Transaktionen ausführen kann.
Compiler
Komprimierung und Bildverarbeitung
Konfliktgetriebenes Klausellernen
Seit dem Jahr 2000 ist die Laufzeit von SAT-Lösern auf industriellen Benchmarks (normalerweise aus der Hardwareindustrie, obwohl auch andere Quellen verwendet werden) jedes Jahr fast exponentiell gesunken. Ein sehr wichtiger Teil dieser Entwicklung ist der Conflict Driven Clause Learning- Algorithmus, der den Boolean Constraint Propagation- Algorithmus in der Originalarbeit von Davis Logemann und Loveland mit der aus der Constraint Programming- und Artificial Intelligence-Forschung stammenden Methode des Klausellernens kombiniert. Für die spezifische industrielle Modellierung wird SAT als einfaches Problem angesehen ( siehe diese Diskussion)). Für mich ist dies eine der größten Erfolgsgeschichten der letzten Zeit, da sie über mehrere Jahre verteilte algorithmische Fortschritte, clevere technische Ideen, experimentelle Bewertungen und eine konzertierte gemeinsame Anstrengung zur Lösung des Problems kombiniert. Der CACM-Artikel von Malik und Zhang ist eine gute Lektüre. Dieser Algorithmus wird an vielen Universitäten gelehrt (ich habe dort, wo es der Fall war, vier besucht), normalerweise jedoch in einer Klasse für Logik oder formale Methoden.
Es gibt zahlreiche Anwendungen von SAT-Lösern. IBM, Intel und viele andere Unternehmen haben ihre eigenen SAT-Löser-Implementierungen. Der Paketmanager in OpenSUSE verwendet auch einen SAT-Löser.
quelle
PageRank ist einer der bekanntesten derartigen Algorithmen. Es wurde von Google-Mitbegründer Larry Page und Mitautoren entwickelt und bildete die Grundlage der ursprünglichen Suchmaschine von Google. Es wird weithin als hilfreich für die Erzielung besserer Suchergebnisse als die damaligen Wettbewerber anerkannt.
Wir stellen uns einen "zufälligen Surfer" vor, der auf einer Webseite beginnt und wiederholt auf einen zufälligen Link klickt, um zu einer neuen Seite zu gelangen. Die Frage ist: "Welchen Teil der Zeit verbringt der Surfer auf jeder Seite?" Je mehr Zeit der Surfer auf einer Seite verbringt, desto wichtiger wird die Seite.
Wir betrachten das Internet eher als eine Grafik, in der Seiten Knoten und Links gerichtete Kanten sind. Wir können dann die Aktion des Surfers als zufällige Bewegung auf einem Graphen oder äquivalent als Markov-Kette mit Übergangsmatrix modellieren . Nachdem wir uns mit einigen Problemen befasst haben, um sicherzustellen, dass die Markov-Kette ergodisch ist (wohin geht der Surfer, wenn eine Seite keine ausgehenden Links hat?), Berechnen wir die Zeit, die der Surfer auf jeder Seite als Steady-State-Verteilung der Markov-Kette verbringt .M
Der Algorithmus selbst ist in gewisser Weise trivial - wir berechnen einfach für großes und willkürliche Anfangsverteilung . Dies kommt nur einer wiederholten Matrix-Matrix- oder Matrix-Vektor-Multiplikation gleich. Der Inhalt der Algorithmen liegt hauptsächlich im Aufbau (Gewährleistung der Ergodizität, Nachweis der einzigartigen Gleichgewichtsverteilung einer ergodischen Markov-Kette) und in der Konvergenzanalyse (Abhängigkeit von der spektralen Lücke von ). k π 0 MMkπ0 k π0 M
quelle
Ich möchte die weit verbreitete Software CPLEX (oder eine ähnliche) Implementierung der Simplex-Methode / des Simplex-Algorithmus zur Lösung linearer Programmierprobleme erwähnen. Es ist der (?) Am häufigsten verwendete Algorithmus in der Wirtschafts- und Operationsforschung.
"Wenn man Statistiken darüber anfertigen würde, welches mathematische Problem den größten Teil der Computerzeit der Welt beansprucht, dann wäre die Antwort wahrscheinlich lineare Programmierung (ohne Datenbankprobleme wie Sortieren und Suchen). " (L. Lovász, A new.) linearer Programmieralgorithmus - besser oder schlechter als die Simplex-Methode - Math. Intelligencer 2 (3) (1979/80) 141-146.)
Der Simplex-Algorithmus hat auch theoretisch großen Einfluss; siehe zum Beispiel die (Polynom-) Hirsch-Vermutung .
Ich vermute, ein typischer Student oder Doktorand. Algorithmusklasse befasst sich mit dem Simplex-Algorithmus (einschließlich grundlegender Algorithmen aus der linearen Algebra wie der Gauß-Eliminierungsmethode).
(Andere erfolgreiche Algorithmen, einschließlich Quicksort zum Sortieren, sind in Algorithmen aus dem Buch aufgeführt .)
quelle
Soweit ich weiß, war das National Resident Matching Program lange Zeit nur eine einfache Anwendung des Gale-Shapley-Algorithmus für das Problem der stabilen Ehe. Es wurde seitdem leicht überarbeitet, um einige zusätzliche Details wie Ehepartnerzuweisungen (auch bekannt als das "Zwei-Körper-Problem") usw. zu behandeln.
quelle
Wenn Sie auch Promovieren mit einbeziehen, bieten viele (die meisten?) CS-Programme Kurse in Codierungstheorie an. Wenn Sie einen Kurs in Codierungstheorie haben, werden Sie auf jeden Fall den Reed-Solomon-Code behandeln, der ein wesentlicher Bestandteil der Funktionsweise von CDs ist, und die Huffman-Codierung, die in den Dateiformaten JPEG, MP3 und ZIP verwendet wird. Je nach Ausrichtung des Kurses können Sie auch Lempel-Ziv behandeln, das im GIF-Format verwendet wird. Persönlich habe ich Lempel-Ziv in einem Bachelor-Algorithmus-Kurs bekommen, aber ich denke, das könnte untypisch sein.
quelle
GNU grep ist ein Befehlszeilentool zum Durchsuchen einer oder mehrerer Eingabedateien nach Zeilen, die eine Übereinstimmung mit einem bestimmten Muster enthalten. Es ist bekannt, dass grep sehr schnell ist! Hier ist ein Zitat von seinem Autor Mike Haertel (von hier genommen ):
quelle
Generell wird der Kanellakis-Preis von der ACM für genau solche theoretischen Entdeckungen vergeben, die einen großen Einfluss auf die Praxis hatten.
Die Auszeichnung 2012 ist für ortsabhängiges Hashing vorgesehen , das zu einer gängigen Methode zur Reduzierung der Dimensionalität beim Data Mining für Probleme in der Nähe von Nachbarn geworden ist (und relativ einfach zu vermitteln ist - zumindest der Algorithmus selbst).
quelle
Einige Beispiele für industrielle Verwendungen dieser Datenstrukturen sind:
Auf dieser Website werden auch Informationen zu CountMin-Anwendungen gesammelt.
Soweit ich unterrichte, weiß ich, dass in Princeton grundlegende Skizzentechniken in diskreten Mathematikkursen unterrichtet werden. In meinem ersten Algorithmenkurs wurde mir die CountMin-Skizze beigebracht. In jedem Fall ist die Analyse von CountMin einfacher als die Analyse für fast jeden anderen randomisierten Algorithmus: Es ist eine einfache Anwendung von paarweiser Unabhängigkeit und Markovs Ungleichung. Wenn dies in den meisten Algorithmenkursen kein Standardmaterial ist, denke ich, hat dies historische Gründe.
quelle
In den letzten zehn Jahren wurden Algorithmen verwendet, um die Anzahl (und Qualität, glaube ich?) Von Nierentransplantationen durch verschiedene Nierenspender-Matching-Programme zu erhöhen. Ich habe Probleme damit, die neuesten Nachrichten zu finden, aber hier sind mindestens ein paar Hinweise:
Noch im Jahr 2007 verwendete die Alliance for Paired Donation einen Algorithmus von Abraham, Blum und Sandholm . Sie benutzen es vielleicht noch, aber ich konnte es nicht herausfinden, indem ich online suchte. Obwohl dieser Algorithmus in "Standard" -Kursen mit ziemlicher Sicherheit nicht behandelt wird, kombiniert er einige grundlegende Ideen, die in solchen Kursen sicherlich vermittelt werden, um einen Algorithmus zu liefern, der für ein Problem gut genug ist, das im Allgemeinen NP-vollständig ist (eine Variante von Cycle Cover) ).
Das Nationale Nierenregister verwendet auch einige Standardalgorithmen, einschließlich (an einer Stelle) CPLEX. Dies führte zu einer tatsächlich durchgeführten Transplantationskette, an der 60 Personen teilnahmen .
Dies ist eines meiner Lieblingsbeispiele nicht nur für den Erfolg von Algorithmen, sondern auch für die Wichtigkeit, Algorithmen für NP-vollständige Probleme zu untersuchen. Sie können buchstäblich Leben retten und haben es bereits getan!
quelle
Viterbis Algorithmus, der in der Spracherkennung und vielen anderen Anwendungen immer noch weit verbreitet ist: http://en.wikipedia.org/wiki/Viterbi_algorithm Der Algorithmus selbst ist eine grundlegende dynamische Programmierung.
Aus Wikipedia: "Der Viterbi-Algorithmus wurde 1967 von Andrew Viterbi als Decodierungsalgorithmus für Faltungscodes über verrauschte digitale Kommunikationsverbindungen vorgeschlagen. [1] Der Algorithmus hat universelle Anwendung bei der Decodierung der Faltungscodes gefunden, die sowohl in digitalen CDMA- als auch GSM-Mobilfunkzellen verwendet werden." DFÜ-Modems, Satelliten-, Deep-Space-Kommunikations- und 802.11-Wireless-LANs werden heute auch häufig für Spracherkennung, Sprachsynthese, Keyword-Spotting, Computerlinguistik und Bioinformatik verwendet Erkennung) wird das akustische Signal als beobachtete Ereignissequenz behandelt, und eine Textfolge wird als "verborgene Ursache" des akustischen Signals angesehen. Der Viterbi-Algorithmus findet die wahrscheinlichste Textfolge, die dem akustischen Signal gegeben ist. "
quelle
quelle
Schauen Sie sich Jens Vygens Projekt BonnTools for Chip Design an. http://www.or.uni-bonn.de/~vygen/projects.html Ich habe einige Vorträge darüber gehört und auch einige ihrer Papiere angeschaut. Sie verwenden randomisierte Rundungen nach Raghavan-Thompson-Art sowie eine Methode zur multiplikativen Gewichtsaktualisierung zum Lösen von LPs mit großem Multicommodity-Flow. Wie bei jedem großen Projekt muss auch hier ein Engineering durchgeführt werden, die Methodik basiert jedoch weitgehend auf bekannten Algorithmen.
quelle
Komisch, dass ich diese Frage heute gesehen habe und dann zufällig auf diesen Link über die vielen Verwendungen der Fouriertransformation geklickt habe .
quelle
Ich bin ziemlich überrascht, dass bei all den oben genannten ausgefallenen Algorithmen niemand die ehrwürdige Lempel-Ziv-Familie von Kompressionsalgorithmen erwähnt hat (erfunden 1977/78).
Aktualisieren
Anscheinend wurde es schon kurz erwähnt.
quelle
Die Singular Value Decomposition (SVD) steht in engem Zusammenhang mit der statistischen Faktorenanalyse oder der Analyse der Hauptkomponenten. Sie ist innerhalb einer linearen Algebra oder Statistikklasse für Anfänger nachvollziehbar und hat viele wichtige theoretische Eigenschaften. es spielt auch eine Rolle bei Bildkomprimierungsalgorithmen. Es spielte eine Schlüsselrolle bei den Gewinnerbeiträgen des Netflix- Preiswettbewerbs im Wert von 1 Mio. US-Dollar (eines der weltweit größten Datenerfassungswettbewerbe in der Geschichte) und wird jetzt auf seiner Website implementiert, um Nutzerbewertungen vorherzusagen. Es ist auch bekannt, dass es in hohem Maße mit hebräischen selbstorganisierenden neuronalen Netzen verwandt ist, die ihren Ursprung in der biologischen Theorie haben.
Es gibt auch eine gewisse Verbindung zum Gradientenabstieg, der im maschinellen Lernen und in künstlichen neuronalen Netzen weit verbreitet ist und eine sehr universell angewandte Optimierungstechnik darstellt. In diesem Fall ist Newtons Methode eine grundlegende 2d-Form. Es gibt einen Gradientenabstiegsalgorithmus zum Erhalten der SVD.
quelle
Die Suche nach einem Eulerschen Pfad bildet die Grundlage der Genomassemblierung - eine Aufgabe, die häufig bei der Arbeit mit vollständigen Genomen (in den Bereichen Bioinformatik, Medizin, Forensik und Ökologie) ausgeführt wird.
UPDATE Vergaß dieses offensichtliche: UPS, FedEx, USPS müssen jede Nacht große Instanzen des Travelling Salesman-Problems lösen. Spart viel Zeit und Geld, um die Fahrer auf eine optimale Route zu schicken.
UPDATE2 In vielen Betriebssystemen wird das Problem der minimalen Rückkopplungsscheitelpunkteinstellung für die Deadlock-Auflösung verwendet.
quelle
Ich mag dieses System, um mit Nierentransplantationen die maximale Anzahl von Leben in Großbritannien zu retten, basierend auf maximalen Matching-Algorithmen: Paired and Altruistic Kidney Donation . Sie bringen Menschen zusammen, die Nieren brauchen und einen nicht passenden Freund / Verwandten haben, der bereit ist, mit anderen Menschen in der gleichen Situation auf maximale Weise zu spenden. Am Spendentag spenden dann alle Spender gleichzeitig, gefolgt von einem zügigen Nierentransport im ganzen Land zu den Empfängern.
quelle
Dieses relativ neue Buch ist es wert, als vollständige / detaillierte Antwort auf die Frage in praktischer, erweiterter / gesammelter Form betrachtet zu werden, die als ergänzendes Material für eine Algorithmusklasse verwendet werden könnte. [einige davon wurden bereits erwähnt; die starke Überlappung selbst ist bemerkenswert.]
Neun Algorithmen, die die Zukunft veränderten: Die genialen Ideen, die die heutigen Computer von MacCormick antreiben
Eine andere, etwas ähnliche, aber theoretischere Referenz ist The Best of the 20th Century: Herausgeber nennen die 10 besten Algorithmen Cipra / SIAM.
quelle
Die Suche nach Knuth-Morris-Pratt- Zeichenfolgen ist weit verbreitet, spezifisch und wird in CS für Studenten und Absolventen unterrichtet.
quelle
Denken Sie an sehr grundlegende Algorithmen
Schön zu zeigen, dass sie im wirklichen Leben auftauchen:
A. Viele Gruppen verwenden eine Art Überdeckungsbaum-Algorithmus, um zu kommunizieren, indem sie Telefonlisten hierarchisch auf Personen aufteilen. B. Autos an einer Kreuzung verwenden normalerweise einen Round-Robin-Algorithmus (auf freiwillige Weise). C. Die meisten Orte, wie Banken und Krankenhaus, organisieren ihre Kunden in einem FIFO-Algorithmus
quelle
Ein faszinierendes algorithmisches Problem ergibt sich bei der medizinischen Anwendung des CT-Scans. Bei der Computertomographie (CT) wird der Körper Röntgenstrahlen aus verschiedenen Winkeln ausgesetzt. Am einen Ende des Scanners befinden sich die Röntgensender und am anderen Ende die Sensoren. Aus einer solchen Reihe von Scans wird ein Bild rekonstruiert, das der Arzt untersuchen kann!
Der gefilterte Rückprojektionsalgorithmus ist die Grundlage für die Rekonstruktion eines Bildes aus einer Reihe von Scans. Dieser Algorithmus ist tatsächlich eine Form eines Approximationsproblems, bei dem das "Signal" unterhalb der Nyquist-Rate abgetastet wird. Dieser Algorithmus wird in allen Krankenhäusern "hinter den Kulissen" verwendet, und die grundlegende gefilterte Rückprojektion verwendet Grundmathematik wie Fourier-Transformationen, um das Fourier-Schnitt-Theorem zu erreichen .
quelle
Ein Beispiel für FFT
Ich habe einmal geholfen, einen FFT-Algorithmus auf eine andere Systemsprache zu portieren.
Der Algorithmus wurde verwendet, um Leitungsbrüche bei der koaxialen Übertragung von Kabelfernsehen / Internet / Telefon zu bestimmen. Grundsätzlich würde ein Techniker verlangen, dass ein Signal an die Box des Kunden gesendet wird, und gleichzeitig würden sie eine Echtzeitanzeige der Statistiken für den bestimmten Kunden aufrufen, wie z. B. QoS, dB, ..., die der Techniker verwenden könnte die Daten und ein Diagramm, um innerhalb weniger Meter zwischen Haus und Mast zu bestimmen, wo ein Teilbruch bestand (oder mehrere Brüche, wie mir gesagt wurde).
Wie oben erwähnt, ist FFT weit verbreitet, aber dies war einer der offensichtlichen und offensichtlichen Gründe (warum und wie), die ich in der Praxis gesehen habe.
Tut mir leid, dass ich es auf einem hohen Niveau halten musste.
quelle
Bresenhams Linienalgorithmus ist der nützlichste Algorithmus, auf den ich gestoßen bin. Leicht zu verstehen Ich habe es für viele Anwendungen verwendet, vom Strichzeichnen über einen komplexen Spliner für eine 3D-Casting-Engine bis hin zu einem komplexen Polygon-Renderer sowie für komplexe Animations- und Skalierungsanwendungen.
quelle
Anpassbare Routenplanung (Daniel Delling, Andrew V. Goldberg, Thomas Pajor und Renato F. Werneck) http://research.microsoft.com/apps/pubs/default.aspx?id=145688
Befähigt Bing Maps: http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx
quelle
Wikipedia hat eine anständige Sammlung von Algorithmen / Anwendungen, die mehr oder weniger in einer Liste aufgeführt sind . Microsoft stellt die am häufigsten zitierten Artikel zur Verfügung, jedoch ohne explizite Erklärung des Gebiets der Informatik oder der Anwendung. Es gibt auch eine chronologische Liste von verschiedenen CS-Konferenzen, _http: //jeffhuang.com/best_paper_awards.html_ zusammengestellt von Prof. Huang.
Spectral Clustering ist ein eleganter Clustering-Algorithmus, bekannt als der von Jianbo Shi und Jitendra Malik für die Bildsegmentierung eingeführte Algorithmus für normalisierte Schnitte . Es wurde auch in Datenclusteranwendungen entwickelt, da es eine gute Schnittstelle zwischen den beiden Communities darstellt.
quelle
zwei weitere persönliche Lieblingsbeispiele, die fest in der Informatik verwurzelt sind, aber von abstraktionistischen Theoretikern leicht übersehen werden können, die enorme / transformative Fortschritte gemacht haben und in den letzten Jahrzehnten erhebliche bis massive praktische / angewandte Auswirkungen auf das tägliche Leben hatten. bereits ist eine ganze generation aufgewachsen, die die welt ohne sie nicht kennt. im Grunde die Kategorie der Modellierung und Simulation .
Physiksimulationsalgorithmen . Hauptsächlich unter Verwendung von Newtonschen Gesetzen, aber unter Verwendung anderer Gesetze (wie z. B. Fluiddynamik). wird in einer Vielzahl von Anwendungen verwendet, von technischen Anwendungen über Videospiele bis hin zu Filmen. Dies ist auch dafür verantwortlich, die Sicherheit, Effizienz oder Zuverlässigkeit von z. B. Autos und Flugzeugen erheblich zu verbessern, indem virtuelle / Test-Designs simulierten Beanspruchungen ausgesetzt werden. Ein wichtiger verwandter Forschungsbereich aus der Bioinformatik mit massiven Auswirkungen auf die Biologie, z. B. Arzneimitteldesign, Krankheitsvorbeugung usw.: Proteinfaltung / Strukturvorhersage . Beachten Sie auch, dass der diesjährige Nobelpreis für Chemie für Chemie-Simulation an Karplus, Levitt, Warshel verliehen wurde. Physiksimulationsalgorithmen sind in hohem Maße in die Sicherheit / Prüfung von Atomwaffen involviert zB bei Los Alamos Labors.
Raytracing / CGI-Algorithmen . Dies begann vor einigen Jahrzehnten als Forschungsthema [ein Freund hat seinen Masterabschluss in CS-Schreiben von Raytracing-Algorithmen gemacht], wurde jedoch z. B. in Spielen und im Filmgeschäft sehr angewendet und erreichte ein außergewöhnliches Maß an Wahrhaftigkeit, das für große Mengen verantwortlich ist Spezialeffekte in Filmen. Diese Branchen haben buchstäblich Milliarden von Dollar investiert und stützen sich auf diese Algorithmen, und ganze große Unternehmen basieren darauf, sie zu nutzen, z . B. Pixar . Die Technik, die ursprünglich hauptsächlich in Scifi-Filmen verwendet wurde, ist mittlerweile so weit verbreitet, dass sie routinemäßig auch in "typischen" Filmen eingesetzt wird. zum Beispiel kürzlich The Great Gatsby stützte sich stark auf CGI-Effekte, um überzeugende oder stilisierte Umgebungen zu zeichnen, Filme / Charaktere zu retuschieren usw.
quelle
Rosetta Code listet angewandte Algorithmen nach Programmiertask (692) und nach Programmiersprache (518) mit Semantic MediaWiki auf.
quelle
Vielleicht wurden an dieser Stelle alle wichtigen / bevorzugten Algorithmen erwähnt, die für dieses Publikum von Interesse sind. Der Vollständigkeit halber verdienen jedoch noch einige weitere Erwähnungen. & Eine Analyse dessen, was als signifikanter Algorithmus angesehen wird, ist hier relevant.
in CS & IT-Bereichen scheint es ein Phänomen zu geben, das vor langer Zeit in der KI bemerkt wurde und das "Bewegen der Torpfosten" heißt . Dies ist ein psychologisches Phänomen, bei dem das Feld relativ schnell voranschreitet, die Menschen sich jedoch mental schnell an das "neue Normal" anpassen und reale oder sogar bahnbrechende Fortschritte im Nachhinein als banal oder unauffällig betrachten, nachdem sie erreicht, dh heruntergespielt oder minimiert wurden. Dies wird in dieser Frage in hohem Maße in der Art und Weise erfasst, wie Algorithmen von F & E in "Bereitstellung" übergehen. Zitiert den Autor der Frage in späteren Kommentaren:
Dies ist jedoch problematisch und im Grunde genommen eine TCS-zentrierte Neudefinition des Wortes "Algorithmus". vermutlich sind die interessanten Algorithmen weiterentwickelt. Bedeutet das, dass ein Problem, wenn es auf einen fortgeschrittenen Algorithmus reduziert wird, nicht mehr "interessant" ist? und "fortgeschritten" ist eindeutig ein sich bewegendes Ziel. Es gibt also eine Möglichkeit, "Algorithmen" eng oder breit zu definieren . es scheint, dass sich die TCS-Definition im Kontext ändert, aber auch in TCS gibt es einen Trend zur breiten Definition, z. B. in der sogenannten "algorithmischen Linse" .
manchmal werden die allgegenwärtigsten Algorithmen auch am meisten übersehen! Das Internet und das WWW sind eine große Umgebung / Nahe-Ökologie für Algorithmen. noch relativ jung, erst etwa zwei Jahrzehnte alt (erfunden ~ 1991), ist es in kurzer Zeit massiv und exponentiell gewachsen. Das Wachstum der WWW-Site hat wahrscheinlich sogar das berühmte exponentielle Moores-Gesetz übertroffen.
Das Internet / WWW wird von vielen ausgefeilten Algorithmen unterstützt. Das Internet verfügt über komplexe Routing-Algorithmen, die in Router integriert sind (die wiederum Unternehmen im Wert von mehreren Milliarden US-Dollar wie Cisco mit Strom versorgen). Einige fortgeschrittene Theorien sind dort anwendbar, z . B. in Routing-Algorithmen . Diese Algorithmen waren vor Jahrzehnten Gegenstand aufkommender, fortschrittlicher und innovativer Forschungen. Sie sind jedoch inzwischen so fein abgestimmt und gut verstanden, dass sie etwas unsichtbar sind.
Wir sollten nicht so schnell vergessen, dass führende Forscher vor Jahrzehnten nicht einmal sicher waren, ob die Internetwelt funktioniert oder möglich war (wie in der frühen Paketvermittlungsforschung zu sehen, ein radikal neues Entwurfsmuster zu der Zeit, das von der vorherigen Schaltung abweicht) Noch vor ein paar Jahren gab es Befürchtungen, dass es irgendwann nicht mehr skalieren und aufgrund der überwältigenden Volumenspitzen versagen könnte.
Es verwendet auch eine ausgeklügelte Fehlererkennung / -korrektur . Das Internet ist wahrscheinlich das größte, fehlertoleranteste System, das jemals von Menschen gebaut wurde und wächst weiter.
Als nächstes gibt es einen guten Grund dafür, die Algorithmen, die das WWW antreiben, weiterzuentwickeln. HTTP- und Webserver sind stark optimiert und verwenden erweiterte Sicherheits- / Verschlüsselungsprotokolle (HTTPS). Die Rendering-Logik einer Webseite wurde in HTML5 und CSS3 zusammen mit der Programmiersprache Javascript extrem erweitert .
Das relativ neue CSS hat verschiedene Prinzipien, die der OOP-Programmierung ähneln, wie Wiederverwendbarkeit und Vererbung. Apropos Schriftsatz: TeX ist ein wichtiges, intern komplexes wissenschaftliches Schriftsatzsystem (nicht anders als eine Programmiersprache), das von Knuth erfunden wurde und jetzt auf Webseiten gerendert werden kann (und möglicherweise in Hunderttausenden von wissenschaftlichen Artikeln oder mehr verwendet wird).
Ein weiterer relativ neuer Bereich von Algorithmen, die auf dem Internet aufbauen und noch auf kollektiver Intelligenz basieren . Die Stackexchange-Software selbst ist ein Beispiel für ein ausgeklügeltes kollektives Nachrichtensystem. Das soziale Netzwerk zeigt auch die Schlüsselmerkmale der kollektiven Intelligenz und es werden kontinuierlich Funktionen hinzugefügt, um diese Intelligenz zu erhöhen (zum Beispiel sind Facebook "Likes" nur ein paar Jahre alt). Das Gebiet der Bewertungssysteme basiert auf kollaborativen Filteralgorithmen und entwickelt sich immer noch basierend auf neuen Forschungen und Anwendungen.
Kurz gesagt, alle revolutionären Erfolge, die die tägliche menschliche Erfahrung verwandeln, gehen weit über bloße "Feldziele" hinaus. Wie der Titel der Frage besagt, sind alle Kernalgorithmen implementiert . Jetzt so allgegenwärtig und unsichtbar, dass es so etwas wie der IT-Ausdruck "Teil des Sanitärs" ist.
quelle
Ein erstaunlich erfolgreicher (Hardware-) Algorithmus ist der Power-On-Reset.
Ohne ein System, bei dem sich ein Computer beim Einschalten in einem bekannten Zustand befindet, passiert nichts anderes .
Power-On-Reset ist der Grund, warum alles funktioniert, was eine CPU enthält, unabhängig davon, ob dies als eingebettet oder auf andere Weise betrachtet wird.
Wenn Sie das nächste Mal an der Wasserstelle für Programmierer und Informatiker sind, heben Sie Ihr Glas Kirschsoda auf den Einschalt-Reset.
quelle