Gibt es eine Enzyklopädie von Algorithmen? [geschlossen]

Gibt es eine Enzyklopädie von Algorithmen, deren Stil dem Handbuch der Mathematik ähnelt ? Es scheint nützlich, eine große Anzahl von ihnen an einem Ort verfügbar zu haben. Ich weiß, dass die Kunst der Computerprogrammierung eine gute Quelle ist, aber sie scheint nicht so sehr enzyklopädisch als lehrreich.

Moderator Hinweis

Wir suchen lange Antworten, die einige Erklärungen und Zusammenhänge liefern. Listen Sie nicht nur ein Buch auf, sondern erläutern Sie, warum Sie ein Buch oder eine Ressource empfehlen. Antworten, die nichts erklären, werden gelöscht. Weitere Informationen finden Sie unter Gutes Subjektiv, Schlechtes Subjektiv .

Ich bin nicht sicher, ob Sie danach suchen, aber NIST hat das Dictionary of Algorithms and Data Structures . Es ist ein ziemlich umfassendes Wörterbuch für Datenstrukturen und Algorithmen (doh) und normalerweise ein guter Ort, um nachzuschauen, wenn ich etwas finde, von dem ich noch nie gehört habe.

Das Skiena-Buch ist auch eine gute Referenz: http://www.algorist.com/

Das Buch deckt alles vom Hintergrund über verschiedene Problembereiche (Datenstrukturen, Suchen / Sortieren, Graphprobleme, Kombinationen / Permutationen / Heuristiken) bis hin zu den Problemen von P vs. NP-vollständigen Problemen ab.

Der besonders relevante Teil des Buches zu dieser Frage ist ein Katalog mit ~ 70-75 verschiedenen Algorithmen, den Arten der Eingaben, die sie im Allgemeinen benötigen, der allgemeinen Beschreibung des Problems, das ein bestimmter Algorithmus löst, und spezifischen Anwendungsbeispielen (z Abschnitt über Suffixbäume beschreibt die Verwendung von Versuchen und deren Anwendbarkeit auf Teilzeichenfolgen und Suchen. Soweit möglich, identifiziert der Autor auch vorhandene Implementierungen für verschiedene gängige Sprachen (c, c ++, Java und einige andere).

Struktur und Interpretation von Computerprogrammen und die Kunst der Computerprogrammierung kommen dem, was Sie suchen, am nächsten.

SICP durchläuft gängige Datenstrukturen und Algorithmen. Obwohl es keine Enzyklopädie ist, ist es ziemlich gut, einen weiten Bereich des Territoriums auf einer begrenzten Fläche abzudecken.

Was kann man über die Kunst der Computerprogrammierung sagen, die es noch nicht gegeben hat? Seien Sie vorsichtig, wenn Sie es aufgreifen, da Sie möglicherweise zu einem bestimmten Thema gehen und erst Stunden später feststellen, dass Sie einen Band von Anfang bis Ende gelesen haben. Es ist eine großartige Möglichkeit, Ihre Programmierung auf die nächste Stufe zu heben.

Cormen, Leiserson, Rivest, Stein - "Einführung in Algorithmen"

Die Einführung in Algorithmen, besser bekannt als CLRS, ist das Standardlehrbuch für Algorithmen an einer großen Anzahl von Universitäten. Es deckt eine Reihe von Algorithmen für eine Vielzahl von Anwendungen ab, darunter Sortieren, Suchen, Graphentheorie und grundlegende numerische Berechnungen. Es enthält auch eine detaillierte Diskussion der Big O-, Big Omega- und Big Theta-Notation. Eine verbreitete Kritik ist, dass es nicht wirklich darauf vorbereitet ist, neue Algorithmen zu entwerfen, aber als Enzyklopädie oder Wörterbuch von Algorithmen ist es mehr als ausreichend.

Ich sollte auch beachten, dass CLRS auch Hinweise gibt, welcher Algorithmus wann verwendet werden soll, und nicht nur einen allgemeinen Index von Algorithmen und Datenstrukturen darstellt. Dies ist nützlich, wenn Sie eine Aufgabe erledigen möchten und Ratschläge dazu wünschen, wie Sie am besten vorgehen können. Es gibt bessere Ressourcen, wenn Sie wissen, wie Sie das tun möchten, was Sie tun, und nur Pseudocode benötigen.

- Aus den Kommentaren von @quanticle weiter unten

In der Graduiertenschule für Physik hat mir Numerical Recipes in C sehr gut gefallen. Es werden natürlich nicht alle Algorithmen behandelt, aber es werden hervorragende Erklärungen für viele, die in den Naturwissenschaften unglaublich nützlich sind, gegeben:

http://www.nr.com/

Das Buch behandelt, wie zu lösen:

Lineare Gleichungen

1. Lineare Gleichungen
2. Interpolation und Extrapolation
3. Integration von Funktionen
4. Funktionsbewertung
5. Sonderfunktionen wie Gammafunktion, Betafunktion, Fakultäten
6. Zufallszahlen - einschließlich einer guten Erklärung, was dies bedeutet
7. Sortieralgorithmen
8. Finden von Wurzeln und nichtlinearen Gleichungen
9. Minimierung und Maximierung von Funktionen
10. Eigensysteme
11. Schnelle Fourier-Transformationen
12. FFT und Spektralanalyse
13. Statistische Beschreibung der Daten
14. Modellierung von Daten
15. Integration gewöhnlicher Differentialgleichungen
16. Zwei-Punkt-Randprobleme
17. Integralgleichungen und inverse Grenztheorie
18. Partielle Differentialgleichungen
19. "Andere" Algorithmen wie CRC-Prüfungen und Datenkomprimierung

Es ist also alles sehr mathematisch, sowohl für Wissenschaftler als auch für Leute, die Physik-Engines für Spiele entwickeln. Und es werden nicht nur die Algorithmen angegeben, sondern auch die Gründe dafür erläutert, damit Sie sie richtig verwenden können. Kein typischer Codierungstext, aber genau das, was Sie brauchen, wenn Sie es brauchen.

Ich habe mich bei der Verwendung der Downhill-Simplex-Methode in Mehrdimensionen (einer Amöbenwanderung) für die Datenanalyse stark darauf verlassen. Hat noch meine Bleistiftstriche drin. Ahh, gute Zeiten!

Wenn Sie nach einer "Enzyklopädie der Algorithmen" suchen, ist es schwierig, mit der Enzyklopädie der Algorithmen einen Fehler zu machen . Ich kann nicht sagen, dass ich es gelesen habe (bei 399 US-Dollar ist es günstig für eine Enzyklopädie ), aber der Klappentext sieht vielversprechend aus:

Die Encyclopedia of Algorithms bietet eine umfassende Sammlung von Lösungen für wichtige algorithmische Probleme von Studenten und Forschern, einschließlich wirkungsvoller Lösungen aus dem letzten Jahrzehnt.

Jemand hat bereits Steven Skienas The Algorithm Design Manual zitiert , aber ich glaube, dass noch niemand Skienas zugehörige Website, The Stony Brook Algorithm Repository, erwähnt hat . Von der Website:

Diese WWW-Seite soll als umfassende Sammlung von Algorithmusimplementierungen für über siebzig der grundlegendsten Probleme in kombinatorischen Algorithmen dienen.

Das Buch ist mehr als nur ein Katalog bekannter Algorithmen. Es ist auch eine Art Tutorial (im besten Sinne des Wortes), wie Sie entscheiden, welcher Algorithmus am besten zu Ihrem Problem und Ihrer Situation passt. Das Endlager ist dagegen enzyklopädischer Natur. Es enthält nicht unbedingt viele Details zur Implementierung jedes Algorithmus selbst, erklärt jedoch, was der Algorithmus tut und wie er im Allgemeinen funktioniert, lesbare Begriffe, die häufig aus dem Buch entnommen werden, und enthält Links zu den tatsächlichen Implementierungen für jeden Algorithmus Algorithmus.

Das Rosetta Code Wiki ist eine großartige Sammlung von Implementierungen gängiger Algorithmen in mehreren Sprachen. Es ist nicht ganz akademisch, aber sehr informativ und macht Spaß, es durchzublättern.

In ihren eigenen Worten:

Rosetta Code ist eine Programmierseite für Chrestomathie . Die Idee ist, Lösungen für dieselbe Aufgabe in möglichst vielen verschiedenen Sprachen vorzustellen, um zu demonstrieren, wie ähnlich und unterschiedlich Sprachen sind, und eine Person zu unterstützen, die mit einer bestimmten Herangehensweise an ein Problem beim Erlernen einer anderen vertraut ist.

Der Hauptvorteil gegenüber anderen Ressourcen (wie dem NIST- Wörterbuch für Algorithmen und Datenstrukturen ) besteht darin, dass Sie mehrere Implementierungen für verschiedene Sprachen betrachten können. Was für verschiedene Zwecke hilfreich sein kann (Vergleich der Ausdruckskraft, Überprüfung der Machbarkeit in einer oder einer anderen Sprache usw.).

Zum Beispiel enthält die QuickSort-Seite (Stand 2013-10-07) mindestens 89 Implementierungen.

Es gibt zwar hervorragende und zeitlos lehrreiche Bücher zu diesem Thema, aber ich glaube kaum, dass Sie eine solche Enzyklopädie finden werden.

• Eine Enzyklopädie zur Mathematik befasst sich mit Jahrtausenden der Forschung. Algorithmen hingegen werden seit einem Jahrhundert kaum erforscht (in größerem Maßstab). Das gesamte Gebiet der Informatik ist für niemanden verständlich und die meisten Dinge bewegen sich immer noch schnell. Wenn es momentan eine Enzyklopädie dazu gäbe, könnten Sie in 10-20 Jahren wahrscheinlich 90% aus dem Fenster werfen. Und von den 10%, die es wert sind, behalten zu werden, wurde mehr als die Hälfte bereits vor einem halben Jahrhundert gedruckt. Die weiten Teile des Handbuchs der Mathematik werden in hundert Jahren auf dem neuesten Stand sein.

• Mathematik ist rein und in sich geschlossen. Dies gilt kaum für "das Gebiet der Algorithmen". Es kann eigentlich kaum als ein Feld betrachtet werden, da ein Feld normalerweise in einem genau definierten Problemraum arbeitet, während Algorithmen tatsächlich nur in einem weniger genau definierten Lösungsraum arbeiten.
  Wenn man also eine Enzyklopädie über Algorithmen kompiliert, ist es nicht wirklich klar, was man einbeziehen soll, wenn man wirklich möchte, dass es umfassend ist. Graphentheorie? Lineare Algebra? Numerische Analyse?

IMHO, im Moment die beste Ressource, die die Rolle einer Enzyklopädie erfüllt, ist "das Internet" (siehe). In einer Enzyklopädie geht es darum, ein indexiertes, umfassendes und durchsuchbares Repository für Wissen (zu einem bestimmten Thema) zu haben. Persönlich finde ich sowohl diese Liste als auch diese Liste ziemlich überwältigend. Auch in anderen Antworten wurden zahlreiche exzellente Algorithmen-Datenbanken verlinkt.

Während Sie also nicht die Qualität erwarten können, die Sie von einer Enzyklopädie erwarten, die Ihr Bücherregal füllt, erhalten Sie die erforderliche Aktualität, um die Jugend des Fachs zu kompensieren, über das Sie wissen möchten.

Soweit es Quellen gibt, halte ich Wikipedia für das, wonach Sie suchen. Es kann sinnvoll sein, für diesen Zweck eine definierte "Algorithmus-Vorlage" auf Wikipedia zu erstellen. Dies sollte jedoch mit den Wikipedia-Redakteuren besprochen werden und nicht hier.

Ein kurzer Hinweis zu The Art of Computer Programming : Wenn es fertig ist, soll es einen "Zusammenfassungs" -Volumen enthalten, und obwohl das Ihnen jetzt nicht weiterhilft, könnte es ungefähr das sein, wonach Sie suchen. TAOCP ist eine Enzyklopädie für das, was es abdeckt, aber es ist noch nicht vollständig und Knuths Persönlichkeit ist so, dass er Dinge nicht einbeziehen wird, es sei denn, er hat sie gründlich recherchiert.