¿Hay una enciclopedia de algoritmos? [cerrado]

¿Existe una enciclopedia de algoritmos de estilo similar al Manual de Matemáticas? Parece útil tener un gran número de ellos disponibles en un solo lugar. Sé que el arte de la programación de computadoras se considera una buena fuente, pero no parece enciclopédico sino instructivo.

Nota del moderador

Estamos buscando respuestas largas que brinden alguna explicación y contexto. No solo enumere un libro: explique por qué recomienda un libro o recurso. Las respuestas que no explican nada se eliminarán. Vea Buen subjetivo, Mal subjetivo para más información.

No estoy seguro de si esto es lo que está buscando, pero NIST tiene el Diccionario de Algoritmos y Estructuras de Datos . Es un diccionario bastante completo para estructuras de datos y algoritmos (doh) y, por lo general, es un buen lugar para buscar cuando encuentro algo de lo que nunca antes había oído hablar.

El libro de Skiena es una buena referencia también: http://www.algorist.com/

El libro cubre todo, desde antecedentes hasta diferentes áreas problemáticas (estructuras de datos, búsqueda / clasificación, problemas de gráficos, combinaciones / permutaciones / heurísticas) e incluso los problemas de P vs NP-problemas completos.

La sección particularmente relevante del libro para esta pregunta es un catálogo de ~ 70-75 algoritmos diferentes, los tipos de entradas que generalmente requieren, la descripción general del problema que resuelve un algoritmo particular y ejemplos específicos de aplicaciones (por ejemplo, el La sección sobre árboles de sufijos analiza su uso de los intentos y su aplicabilidad a la subcadena y la búsqueda). Siempre que sea posible, el autor también identifica implementaciones existentes para varios lenguajes comunes (c, c ++, Java y algunos otros).

La estructura e interpretación de los programas de computadora y el arte de la programación de computadoras son lo más cercano que he visto a lo que buscas.

SICP recorre estructuras de datos y algoritmos comunes. Si bien no es enciclopédico, es bastante bueno cubrir una amplia franja de territorio en una cantidad limitada de espacio.

Lo que se puede decir sobre The Art of Computer Programming que aún no se ha dicho. Tenga cuidado cuando lo levante, puede ir a un tema específico y horas después darse cuenta de que ha leído un volumen de principio a fin. Es una excelente manera de llevar realmente su programación al siguiente nivel.

Cormen, Leiserson, Rivest, Stein - "Intucción a los algoritmos"

Introducción a los algoritmos, más comúnmente conocido como CLRS, es el libro de texto de algoritmos estándar en una gran cantidad de universidades. Cubre una variedad de algoritmos para una variedad de aplicaciones, que incluyen clasificación, búsqueda, teoría de grafos y computación numérica básica. También incluye una discusión detallada de la notación Big O, Big Omega y Big Theta. Una crítica común es que realmente no prepara uno para diseñar nuevos algoritmos, pero como una enciclopedia o diccionario de algoritmos, es más que adecuado.

También debo señalar que CLRS también da consejos sobre qué algoritmo usar cuando, y no solo presenta un índice genérico de algoritmos y estructuras de datos. Es útil cuando tiene una tarea que desea realizar y desea asesoramiento sobre la mejor manera de hacerlo. Hay mejores recursos para cuando sabes cómo quieres hacer lo que estás haciendo y solo necesitas un pseudocódigo.

- de los comentarios de @quanticle, a continuación

En la escuela de posgrado en Física, realmente disfruté las Recetas Numéricas en C. No cubre todos los algoritmos, por supuesto, pero ofrece excelentes explicaciones de muchos que son increíblemente útiles en las ciencias:

http://www.nr.com/

El libro cubre cómo resolver:

Ecuaciones lineales

1. Ecuaciones lineales
2. Interpolación y extrapolación
3. Integración de funciones.
4. Evaluación de funciones
5. Funciones especiales que incluyen función gamma, función beta, factoriales
6. Números aleatorios, incluida una buena explicación de lo que esto significa
7. Algoritmos de clasificación
8. Encontrar raíces y ecuaciones no lineales
9. Minimización y maximización de funciones.
10. Eigensystems
11. Transformadas rápidas de Fourier
12. FFT y análisis espectral
13. Descripción estadística de los datos.
14. Modelado de datos
15. Integración de ecuaciones diferenciales ordinarias
16. Problemas de límites de dos puntos
17. Ecuaciones integrales y thory límite inverso
18. Ecuaciones diferenciales parciales
19. Algoritmos "Otros" como verificaciones CRC y compresión de datos

Así que todo es muy matemático, bueno para los científicos y para las personas que diseñan motores de física para juegos. Y no solo proporciona los algoritmos, sino que explica los por qué detrás de ellos para que pueda usarlos correctamente. No es el típico texto de codificación, sino exactamente lo que necesita cuando lo necesita.

Me basé en gran medida cuando utilicé el método de descenso simplex en multidimensiones (una caminata de amebas) para el análisis de datos. Todavía tiene mis marcas de lápiz. Ahh, buenos tiempos!

Si está buscando una "enciclopedia de algoritmos", sería difícil equivocarse con la Enciclopedia de Algoritmos . No puedo decir que lo he leído (a $ 399, es barato para una enciclopedia ), pero la propaganda parece prometedora:

La Enciclopedia de Algoritmos proporciona un conjunto integral de soluciones a problemas algorítmicos importantes para estudiantes e investigadores, incluidas soluciones de alto impacto de la década más reciente.

Alguien ya citó el Manual de Diseño de Algoritmo de Steven Skiena , pero no creo que nadie haya mencionado aún el sitio web asociado de Skiena, El Depósito de Algoritmo de Stony Brook . Desde el sitio web:

Esta página WWW está destinada a servir como una colección completa de implementaciones de algoritmos para más de setenta de los problemas más fundamentales en algoritmos combinatorios.

El libro es más que un simple catálogo de algoritmos conocidos; También es una especie de tutorial (en el mejor sentido de la palabra) sobre cómo decidir qué algoritmo utilizar para adaptarse mejor a su problema y situación. El repositorio, por otro lado, es de naturaleza más enciclopédica. No necesariamente contiene muchos detalles sobre cómo implementar cada algoritmo usted mismo, pero explica qué hace el algoritmo y cómo funciona en general, términos legibles a menudo tomados del libro, y proporciona enlaces a implementaciones reales para cada uno. algoritmo.

El Código de Rosetta Wiki es una gran colección de implementaciones de algoritmos comunes en varios idiomas. No es del todo académico, pero sí bastante informativo y divertido.

En sus propias palabras:

Rosetta Code es un sitio de programación para larestrestomía . La idea es presentar soluciones a la misma tarea en tantos idiomas diferentes como sea posible, demostrar cómo los idiomas son similares y diferentes, y ayudar a una persona con una base en un enfoque de un problema para aprender otro.

Su principal ventaja sobre otros recursos (como el Diccionario de Algoritmos y Estructuras de Datos NIST ) es que le permite ver varias implementaciones para diferentes idiomas. Lo que puede ser útil para diversos fines (comparar expresividad, verificar la viabilidad en un idioma u otro, etc.).

Por ejemplo, la página QuickSort proporciona (a partir del 07/10/2013) al menos 89 implementaciones.

Si bien hay libros instructivos excelentes y atemporales sobre el tema, no creo que encuentre una enciclopedia de este tipo.

• Una enciclopedia sobre matemáticas cubre milenios de investigación. Los algoritmos, por otro lado, apenas se estudian durante un siglo (hablando en una escala mayor). Todo el campo de la informática apenas es entendido por nadie y la mayoría de las cosas todavía se mueven rápidamente. Si hubiera una enciclopedia sobre esto en este momento, supongo que podría arrojar el 90% por la ventana en 10-20 años. Y del 10% que valía la pena conservar, más de la mitad ya se imprimió hace medio siglo. Las vastas partes del manual de matemáticas estarán actualizadas dentro de cien años a partir de ahora.

• La matemática es pura y autónoma. Esto apenas se aplica al "campo de los algoritmos". En realidad, difícilmente se puede considerar como un campo, porque un campo generalmente opera en un espacio problemático bien definido, mientras que los algoritmos en realidad solo operan dentro de un espacio de solución menos definido.
  Entonces, si uno compilara una enciclopedia sobre algoritmos, no está realmente claro qué incluir, si realmente quiere que sea exhaustivo. ¿Teoría de grafos? ¿Álgebra lineal? ¿Análisis numérico?

En mi humilde opinión, en este momento el mejor recurso que cumple el papel de una enciclopedia, es "Internet" (he aquí). El objetivo de una enciclopedia es tener un repositorio de conocimiento indexado, completo y con capacidad de búsqueda (sobre algún tema). Personalmente, encuentro esta lista y esta lista bastante abrumadoras. También en otras respuestas, se han vinculado numerosas bases de datos de algoritmos excelentes.

Entonces, aunque no puede esperar el mismo nivel de calidad que esperaría de una enciclopedia que llena su estantería, sí obtiene el nivel de puntualidad requerido para compensar a los jóvenes del campo que desea conocer.

En cuanto a las fuentes existentes, creo que Wikipedia es lo más parecido a lo que estás buscando. A saber, podría ser útil crear una "plantilla de algoritmo" más definida en Wikipedia para este propósito, pero eso es algo que se debe discutir con los editores de Wikipedia y no aquí.

Una nota rápida sobre El arte de la programación de computadoras : cuando se complete, debe incluir un volumen de "resumen" y aunque eso no lo ayudará ahora, podría ser aproximadamente lo que está buscando. TAOCP es enciclopédico por lo que cubre, pero aún no está completo y la personalidad de Knuth es tal que no incluirá cosas a menos que las haya investigado exhaustivamente.