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

34

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 .

Weltingenieur
quelle
Ein bisschen googeln würde viel dazu beitragen, diese Frage zu beantworten. Zumindest würde es eine Liste guter Kandidaten liefern, mit denen Sie dann eine genauere Frage stellen könnten.
Caleb

Antworten:

41

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.

Vitor Py
quelle
Ihre Antwort ist so ziemlich genau das, wonach ich suche. Extra Punkte für die Freiheit.
Weltingenieur
Komisch ist, dass die NIST DADS in den letzten Tagen bis auf Weiteres wegen der Schließung der US-Regierung geschlossen sind! Und als dann Tausende von Entwicklern auf einmal schreien hörten ...
Haylem
11

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).

Joe
quelle
Das kommt einer Algorithmusenzyklopädie am nächsten, die ich mir vorstellen kann. Exzellentes Buch!
Charalambos Paschalides
8

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.

Michael Brown
quelle
5
SICP ist ein wunderbares Buch, aber ich denke nicht, dass es ein vernünftiger Vorschlag für jemanden ist, der nach einer "Enzyklopädie der Algorithmen" sucht. SICP versucht nicht, so etwas zu sein. Darüber hinaus schrieb das OP, dass ACP "nicht so sehr enzyklopädisch als lehrreich erscheint", so dass klar sein sollte, dass SICP nicht das ist , wonach er oder sie sucht.
Caleb
Tolles Buch, aber nicht enzyklopädisch.
Haylem
Ich bin mir ziemlich sicher, dass es keine Enzyklopädie ist, sondern einen guten Überblick über Algorithmen gibt. "Obwohl es keine Enzyklopädie ist, ist es ziemlich gut, ein weites Gebiet auf einer begrenzten Fläche abzudecken." Ja, das habe ich gesagt.
Michael Brown
8

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

Dmitry Matveev
quelle
4
Können Sie Ihre Antwort so erweitern, dass sie enthält, was über dieses Buch mit dem Ziel dieser Frage zu tun hat?
2
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.
Quanticle
1
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.
Quanticle
Tipp an Dmitry: Kopieren Sie einfach die Kommentare von @ quanticle in den Text der Antwort, um Ihre Antwort um 1000% zu verbessern.
Nein
5

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!

Daniel Williams PhD
quelle
1
Können Sie Ihre Antwort so erweitern, dass sie auch das enthält, was mit diesem Buch zu tun hat, um das Ziel dieser Frage zu erreichen?
4

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.

Caleb
quelle
2

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.

Haylem
quelle
Würde es Ihnen etwas ausmachen, mehr darüber zu erklären, was es tut, und warum empfehlen Sie es als Antwort auf die gestellte Frage? „Link-only Antworten“ sind nicht ganz willkommen bei Stapelaustausch
gnat
@gnat: Normalerweise würde ich dem zustimmen, aber wie unterscheidet sich das von der Antwort "nur für Bücher"? Ich denke auch, dass "eine Sammlung von Implementierungen allgemeiner Algorithmen in mehreren Sprachen" ziemlich genau das abdeckt, was sie bewirken. Es ist auch so (oder so wenig) detailliert wie die akzeptierte Antwort, wenn Sie genau genug
hinsehen
@gnat: Sowieso, fügte noch etwas hinzu.
Haylem
@AnnaLear: Entschuldigung, ich denke, deine Bearbeitung war vollkommen richtig, um meinen Beitrag kurz und nachvollziehbar zu halten, aber es schien angebracht, den Vergleich in Bezug auf die Änderungen auf Wunsch von gnat wieder aufzunehmen.
Haylem
0

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.

back2dos
quelle
0

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.

sehr dumm
quelle