Algoritmos del libro.

358

Paul Erdos habló sobre el "Libro" donde Dios guarda la prueba más elegante de cada teorema matemático. Esto incluso inspiró un libro (que creo que ahora está en su cuarta edición): Pruebas del libro .

Si Dios tuviera un libro similar para algoritmos, ¿qué algoritmo (s) crees que sería un candidato (s)?

Si es posible, proporcione también una referencia en la que se pueda hacer clic y las ideas clave que lo hacen funcionar.

Solo un algoritmo por respuesta, por favor.

Aryabhata
fuente
11
Gran pregunta! [Editar:} Una pregunta. ¿Dónde trazamos la línea entre algoritmos y estructuras de datos? ¿Qué sucede si la información clave de un algoritmo está íntimamente relacionada con una estructura de datos (por ejemplo, UNION FIND en la función inversa de Ackermann)?
Ross Snider
44
una gran fuente y tal vez un candidato para tal libro es "Enciclopedia de Algoritmos" springer.com/computer/theoretical+computer+science/book/…
Marcos Villagra
21
Me sorprende un poco que los algoritmos que considero bastante complicados (KMP, matrices de sufijos lineales) sean considerados por otros como "del Libro". Para mí, "del Libro" significa simple y obvio, pero solo en retrospectiva. Tengo curiosidad por cómo otros interpretan "elegante".
Radu GRIGore
49
@supercooldave No tienes que creer en Dios, pero debes creer en su libro. ;-)
Ross Snider
10
Durante una conferencia en 1985, Erdős dijo: "No tienes que creer en Dios, pero debes creer en El Libro".
Robert Massaioli

Respuestas:

116

Union-find es un problema hermoso cuyo mejor algoritmo / estructura de datos (Disjoint Set Forest ) se basa en una pila de espagueti. Si bien es lo suficientemente simple e intuitivo como para explicarle a un niño inteligente, tomó varios años obtener un límite estricto en su tiempo de ejecución. Finalmente, se descubrió que su comportamiento estaba relacionado con la función inversa de Ackermann, una función cuyo descubrimiento marcó un cambio de perspectiva sobre la computación (y de hecho se incluyó en Hilbert's On the Infinite ).

Wikipedia ofrece una buena introducción a los bosques disjuntos .

Jukka Suomela
fuente
109

Cordón Knuth-Morris-Pratt a juego. Las ocho líneas de código más ingeniosas que jamás hayas visto.

Jukka Suomela
fuente
44
Es un poco alucinante darse cuenta de que eso era algo que no era obvio en algún momento y ahora solo es obvio porque se les ocurrió y lo aprendimos ... Creo que deberíamos aplicar la teoría de la historia de Carr a las matemáticas y la informática .
Ritwik Bose
1
Por la descripción, diría que esto está relacionado con la búsqueda rápida de subcadenas de Boyer-Moore.
Bart
2
@Mechko El hecho de que este algoritmo fue descubierto simultáneamente e independientemente por personas separadas es una indicación de que es obvio hasta cierto punto. Si algo es "obvio" es una función de las limitaciones del proyecto y del entorno de programación más amplio. Si necesita (1) búsqueda rápida de texto y (2) es consciente de la importancia de los algoritmos verdaderamente O (n), y (3) ha encontrado texto con coincidencias parciales antes y (4) tiene el tiempo para hacer las cosas "bien", entonces este algoritmo es probablemente obvio.
Matt Gallagher
En una entrevista, Knuth dijo que la idea del algoritmo surgió del estudio del autómata finito bidireccional de Stephen Cook para palíndromos.
Kaveh
@Kaveh Lea la Sección 7 (Observaciones históricas) del documento original de KMP. Tiene excelentes comentarios. Sobre Morris escribiendo un editor de texto que "era demasiado complicado para que otros implementadores del sistema lo entendieran". Acerca de Knuth "la primera vez en la experiencia de Knuth que la teoría de los autómatas le había enseñado cómo resolver un problema de programación real mejor de lo que podía resolverlo antes". Y "Knuth se disgustó al saber que Morris ya había descubierto el algoritmo, sin conocer el teorema de Cook". DIVERTIDO.
Hendrik Jan
93

El algoritmo de Blum, Floyd, Pratt, Rivest y Tarjan para encontrar el elemento k de una lista no ordenada en tiempo lineal es un algoritmo hermoso, y solo funciona porque los números son los correctos para el Teorema Maestro. Va de la siguiente manera:

  1. Ordenar cada secuencia de cinco elementos.
  2. Elija la mediana en cada uno.
  3. Vuelva a buscar la mediana de esta lista.
  4. Pivote sobre la mediana de las medianas (como en Quicksort)
  5. Seleccione el lado adecuado de la lista y su posición en esa lista, y repita.
Derrick Stolee
fuente
3
Este es uno de mis algoritmos favoritos. Me gusta la intuición que aprendí del libro de discrepancias de Chazelle: el conjunto de medianas de grupos de elementos es como un -net para intervalos en la lista ordenada de los números de entrada. Entonces, el algoritmo sigue un paradigma general: calcule un -net rápidamente, resuelva el problema en la red, repita en alguna parte de la entrada para refinar la solución, hasta que tenga la solución exacta. es una técnica muy útilϵ ϵ1/ϵϵϵ
Sasho Nikolov
55
Por cierto, una vez que parametriza el tamaño de los grupos, las constantes no son tan mágicas. Por supuesto, están optimizados para dar lo correcto en el teorema del Maestro
Sasho Nikolov
Implementación de Ruby, gist.github.com/chadbrewbaker/7202412 ¿Existe una versión del algoritmo que use espacio (constante, de registro) o tiene que usar un espacio lineal de cero para mantener las medianas?
Chad Brewbaker
2
La afirmación de que "esto solo funciona porque los números son los adecuados para el teorema maestro" no es realmente cierta. Si sustituye el número con un mayor número , es fácil ver que los dos números que tienen que suman menos de convergen a y , así que todo lo suficientemente grande trabajo. es solo el primer número que funciona, no es el único. n 1 3 / 4 0 n 55n13/40n5
Will Sawin
88

La búsqueda binaria es el algoritmo más simple, hermoso y útil con el que me he encontrado.

revs michalmocny
fuente
Reemplazaría elegante por intuitivo. No hay nada tan elegante al respecto; Su simplicidad es su verdadera belleza.
Robert Massaioli
@Robert Massaili: Reemplacé elegante por hermoso. Tenías razón sobre eso.
michalmocny
2
Y es increíblemente difícil de escribir correctamente: vea " ¿Es usted uno del 10% de los programadores que puede escribir una búsqueda binaria? "
jon
En mi primer curso de algoritmos de posgrado tuvimos pruebas de 15 minutos donde tuvimos que resolver 2-3 problemas a mano. La primera prueba incluyó un árbol de búsqueda binario y dos preguntas sobre montones. Estaba avergonzado y consternado al saber que me había equivocado con el problema de búsqueda binaria, antes de que me dijeran que en una clase de aproximadamente 30 personas había dos respuestas correctas. Pero incluso sabiendo eso, el hecho de que la comunidad profesional tardó 15 años en acertar es asombroso.
Stella Biderman
84

Me sorprende no ver el algoritmo de Floyd-Warshall para los caminos más cortos de todos los pares aquí:

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

Uno de los algoritmos no triviales más cortos y claros que existen , y el rendimiento es muy ágil cuando se considera que podría haber bordes . ¡Ese sería mi póster para la programación dinámica!O ( n 2 )O(n3)O(n2)

usuario651
fuente
2
Este algoritmo también se puede generalizar de una manera realmente ordenada. Ver, por ejemplo, r6.ca/blog/20110808T035622Z.html y cl.cam.ac.uk/~sd601/papers/semirings.pdf
Mikhail Glushenkov el
73

Puede parecer algo trivial (especialmente en comparación con las otras respuestas), pero creo que Quicksort es realmente elegante. Recuerdo que cuando lo vi por primera vez pensé que era realmente complicado, pero ahora parece demasiado simple.

Jukka Suomela
fuente
10
Quicksort también plantea preguntas interesantes sobre cuál es exactamente la esencia de un algoritmo. Por ejemplo, la implementación estándar elegante de Haskell se ve exactamente como la definición estándar de pseudocódigo, pero tiene una complejidad asintótica diferente. Entonces, ¿Quicksort se trata solo de dividir y conquistar o el ingenioso puntero in situ es una parte esencial de Quicksort? ¿Se puede implementar Quicksort incluso en un entorno puramente funcional o requiere mutabilidad?
Jörg W Mittag
2
La idea de la "esencia" o la "moral" de un algoritmo proviene, por supuesto, del hermoso artículo The Genuine Sieve of Eratosthenes de Melissa E. O'Neill ( cs.hmc.edu/~oneill/papers/Sieve-JFP. pdf ) y la discusión rápida viene de la discusión de LtU de ese documento ( lambda-the-ultimate.org/node/3127 ), comenzando específicamente en este comentario: lambda-the-ultimate.org/node/3127/#comment-45549
Jörg W Mittag
8
@ Jörg: la implementación de la clasificación rápida en listas vinculadas es completamente sensata y tiene el mismo tiempo de ejecución asintótico que su implementación en el lugar en los arreglos (diablos, incluso la ingenua implementación fuera de lugar en los arreglos tiene el mismo tiempo de ejecución), ambos en promedio y en el peor de los casos. En cuanto al uso del espacio, esto es realmente diferente, pero hay que decir que incluso la versión "in situ" requiere espacio extra no constante (¡pila de llamadas!), Un hecho que se pasa por alto fácilmente.
Konrad Rudolph
También vale la pena mencionar el Quicksort de doble pivote de Vladimir Yaroslavskiy. Eso debería ser al menos un 20% más rápido original quicksort permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/…
SaveTheRbtz
Quicksort en teoría es simple (puede resumirse en 4 pasos) y podría estar altamente optimizado, pero en la práctica es muy difícil codificarlo correctamente. Por eso no recibe mi voto.
Dennis
50

La prueba de primalidad de Miller-Rabin (y pruebas similares) debe estar en The Book. La idea es aprovechar las propiedades de los números primos (es decir, utilizando el pequeño teorema de Fermat) para buscar probabilísticamente un testigo de que el número no es primo. Si no se encuentra ningún testigo después de suficientes pruebas aleatorias, el número se clasifica como primo.

En esa nota, ¡la prueba de primalidad de AKS que mostró que PRIMES está en P ciertamente debería estar en The Book!

Jukka Suomela
fuente
49

Prueba de identidad polinómica con el lema de Schwartz-Zippel :

Si alguien te despertara en medio de la noche y te pidiera que probaras dos expresiones polinómicas univariadas para identificarlas, probablemente las reducirías a la forma normal de la suma de productos y compararías tu identidad estructural. Desafortunadamente, la reducción puede tomar un tiempo exponencial; es análogo a reducir las expresiones booleanas a una forma normal disyuntiva.

Suponiendo que usted es del tipo al que le gustan los algoritmos aleatorios, su próximo intento probablemente sería evaluar los polinomios en puntos elegidos al azar en busca de contraejemplos, declarando que los polinomios son muy probables si pasan suficientes pruebas. El lema de Schwartz-Zippel muestra que a medida que aumenta el número de puntos, la posibilidad de un falso positivo disminuye muy rápidamente.

No se conoce un algoritmo determinista para el problema que se ejecute en tiempo polinómico.

Por Vognsen
fuente
¡Esto debería haber sido sugerido hace mucho tiempo! ¡Gracias!
arnab
1
Hay varios otros algoritmos aleatorios que merecen un lugar destacado en el Libro. Para estos, el contraste entre las alternativas deterministas y probabilísticas es menos sorprendente: generalmente existe un algoritmo determinista pero es mucho más complicado.
Por Vognsen
Inventé el mismo algoritmo de forma independiente mientras trabajaba en un artículo hace un par de años hasta que alguien me preguntó ¿no es el lema de Schwartz-Zippel? Y yo dije, ¿qué es eso? :)
Helium
46

Profundidad primera búsqueda . Es la base de muchos otros algoritmos. También es engañosamente simple: por ejemplo, si reemplaza la cola en una implementación de BFS por una pila, ¿obtiene DFS?

Radu GRIGore
fuente
1
¡También es la base de la ejecución de Prolog!
muad
1
¿Qué sentido tiene BFS con una pila que me falta? Pensé que la respuesta es "sí, obtienes DFS".
Omar Antolín-Camarena
1
Bueno, todo el mundo parece pensar que este problema es trivial. Además, todo el mundo parece pensar que la respuesta es "sí", lo cual es incorrecto. La respuesta es en realidad "depende de con qué implementación BFS comience". Ver cs.stackexchange.com/questions/329/… (Esta es una pregunta que publiqué para ayudar con la fase beta de CS.SE)
Radu GRIGore
También se analiza brevemente aquí: ics.uci.edu//~eppstein/161/960215.html
Radu GRIGore
42

Algoritmo de Dijkstra : el problema de la ruta más corta de una sola fuente para un gráfico con costos de ruta de borde no negativos. Se usa en todas partes y es uno de los algoritmos más bellos que existen. Internet no se podría enrutar sin él: es una parte central de los protocolos de enrutamiento IS-IS y OSPF (Open Shortest Path First).

  1. Asigne a cada nodo un valor de distancia. Póngalo a cero para nuestro nodo inicial y al infinito para todos los demás nodos.
  2. Marque todos los nodos como no visitados. Establecer el nodo inicial como actual.
  3. Para el nodo actual, considere todos sus vecinos no visitados y calcule su distancia tentativa (desde el nodo inicial). Por ejemplo, si el nodo actual (A) tiene una distancia de 6, y un borde que lo conecta con otro nodo (B) es 2, la distancia de B a A será 6 + 2 = 8. Si esta distancia es menor que la distancia registrada anteriormente (infinito al principio, cero para el nodo inicial), sobrescriba la distancia.
  4. Cuando hayamos terminado de considerar a todos los vecinos del nodo actual, márquelo como visitado. Un nodo visitado no se volverá a comprobar nunca más; Su distancia registrada ahora es final y mínima.
  5. Si se han visitado todos los nodos, finalice. De lo contrario, establezca el nodo no visitado con la menor distancia (desde el nodo inicial) como el siguiente "nodo actual" y continúe desde el paso 3.
David Sifry
fuente
40

El esquema de cifrado totalmente homomórfico de Gentry (ya sea sobre redes ideales o sobre enteros) es terriblemente hermoso. Permite a un tercero realizar cálculos arbitrarios en datos cifrados sin acceso a una clave privada.

El esquema de cifrado se debe a varias observaciones entusiastas.

  • Para obtener un esquema de cifrado totalmente homomórfico, solo se necesita tener un esquema que sea homomórfico sobre la suma y la multiplicación. Esto se debe a que la suma y la multiplicación (mod 2) son suficientes para obtener las puertas AND, OR y NOT (y, por lo tanto, la integridad de Turing).
  • Que si se tuviera un esquema de este tipo, pero debido a algunas limitaciones solo podría ejecutarse para circuitos de cierta profundidad finita, entonces uno puede evaluar homomórficamente el procedimiento de descifrado y reencriptación para restablecer la limitación de profundidad del circuito sin sacrificar la privacidad clave.
  • Que al "aplastar" la profundidad de la versión del circuito de la función de descifrado para el esquema, uno podría habilitar un esquema originalmente limitado a circuitos finitos y poco profundos y un número arbitrario de cálculos.

En su tesis, Craig Gentry resolvió un problema abierto de larga data (y magnífico) en criptografía. El hecho de que exista un esquema totalmente homomórfico exige que reconozcamos que hay una estructura inherente a la computabilidad que de otro modo podríamos haber ignorado.

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

Ross Snider
fuente
38

Algoritmo de Strassen para la multiplicación de matrices.

Kaveh
fuente
Probablemente esperaría hasta que sepamos si es óptimo.
Thomas Ahle
No es óptimo, al menos, asintóticamente ... Creo que incluir el algoritmo de Strassen te obliga a incluir primero el algoritmo de Karatsuba.
Timothy Sun
35

El algoritmo de matrimonio estable Gale-Shapley . Este algoritmo es codicioso y muy simple, al principio no es obvio por qué funcionaría, pero luego la prueba de corrección es nuevamente fácil de entender.

Konrad Swanepoel
fuente
+1 porque también hay un capítulo en las pruebas publicadas del libro sobre los matrimonios ...
ixtmixilix
34

El algoritmo de tiempo lineal para construir matrices de sufijos es realmente hermoso, aunque realmente no recibió el reconocimiento que merecía http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

zotachidil
fuente
Yo no pienso que ha recibido el reconocimiento que se merece - lo que le hace pensar lo contrario? Por ejemplo, se implementa en la biblioteca de análisis de secuencia C ++ SeqAn.
Konrad Rudolph
Vale la pena mencionar que ahora hay una serie de otros algoritmos de construcción de matrices de sufijos de tiempo lineales y no lineales que, aunque no son tan bonitos, pueden ser mucho más rápidos en la práctica. "Un enfoque eficiente y versátil para la clasificación de sufijos", Journal of Experimental Algorithmics (JEA), Volumen 12, junio de 2008 tiene algunos resultados experimentales en este sentido.
Raphael
@Raphael: desconfío un poco del hecho de que en la pág. 3 de ese documento de JEA, dan solo lo que "creen" es un límite "suelto" de O (n ^ 2 log n) ... ¿Conocen algún documento con algoritmos de tiempo lineal demostrable que sean más rápidos en la práctica que el ¿Algoritmo sesgado?
user651
32

Eliminación gaussiana. Completa la secuencia de generalización del algoritmo Euclidean GCD a Knuth-Bendix.

Mitch
fuente
Por cierto, ¿cuál es la secuencia de generalización y dónde encaja el algoritmo de Buchberger para la base de Grobner? (Parece análogo a Knuth-Bendix, pero he visto una mención en alguna parte que generaliza la eliminación gaussiana ...)
ShreevatsaR
66
la secuencia es: Euclidean GCD -> Eliminación Gaussiana -> Buchberger -> Knuth-Bendix. También se puede colocar (en lugar de Eliminación Gaussiana) división y módulo polinomial univariante (en el orden de generalización está 'aparte' de Eliminación Gaussiana, GE es multivariante grado 1, el anillo polinomial es univariado ilimitado, Buchberger es multivariado ilimitado. generalización de salto es mayor de EGCD a GE o anillo de polinomios debido a la adición de variables, y luego también de gran Buchberger a KB, debido a la firma ilimitada.
Mitch
+1: el algoritmo euclidiano resuelve la ecuación más famosa ax-by = 1 en matemáticas. Por qué no aparece en CS más a menudo es un misterio.
Tegiri Nenashi
32

Me impresionó la primera vez que vi el algoritmo para el muestreo de yacimientos y su prueba. Es el típico rompecabezas de tipo "desafío para la mente" con una solución extremadamente simple. Creo que definitivamente pertenece al libro, tanto para algoritmos como para teoremas matemáticos.

En cuanto al libro, la historia cuenta que cuando Erdös murió y fue al cielo, solicitó encontrarse con Dios. La solicitud fue concedida y para la reunión, Erdös solo tenía una pregunta. "¿Puedo mirar en el libro?" Dios dijo que sí y llevó a Erdös a eso. Naturalmente muy emocionado, Erdös abre el libro solo para ver lo siguiente.

Teorema 1: ...
Prueba: Obvio.

Teorema 2: ...
Prueba: Obvio.

Teorema 3: ...
Prueba: Obvio.

Arnar
fuente
44
Teorema 4: ... Prueba: ejercicio para el lector.
jon
31

El algoritmo de tortuga y liebre . Me gusta porque estoy seguro de que incluso si desperdiciara toda mi vida tratando de encontrarlo, no hay forma de que se me ocurra una idea así.

Tobias Neukom
fuente
66
¿Conoces el algoritmo tonto que resuelve el problema con las mismas asintóticas y sigue un patrón de diseño algorítmico? Estoy hablando de profundización iterativa. En la enésima iteración, comienza en el 2 ^ n sucesor de la raíz y mira hacia adelante 2 ^ n sucesores en busca de una recurrencia. A pesar de que está volviendo sobre algunos de sus pasos con cada iteración, la tasa de crecimiento geométrico del radio de búsqueda significa que no afecta a los asintóticos.
Por Vognsen
30

Un ejemplo tan fundamental y "trivial" como la prueba de Euclides de infinitos números primos:

Aproximación 2 para MAX-CUT : independientemente de cada vértice, asígnelo a una de las dos particiones con la misma probabilidad.

arnab
fuente
66
Sí, un algoritmo muy bueno. Menos trivialmente, a costa de otro factor de 2, este algoritmo también funciona para maximizar cualquier función submodular, no solo la función de corte de gráfico. Este es el resultado de Feige, Mirrokni y Vondrak de FOCS 07
Aaron Roth
30

Siempre he sido parcial al algoritmo de Christofides que da una aproximación (3/2) para TSP métrico. De hecho, llámame fácil de complacer, pero incluso me gustó el algoritmo de aproximación 2 que vino antes . El truco de Christofides de hacer un euleriano de árbol de extensión de peso mínimo agregando una coincidencia de sus vértices de grados impares (en lugar de duplicar todos los bordes) es simple y elegante, y se necesita poco para convencer a uno de que esta coincidencia no tiene más de la mitad del peso de un recorrido óptimo.

James King
fuente
De hecho, también hay muchos otros algoritmos de aproximación simples y elegantes con garantías de aproximación decentes.
Janne H. Korhonen
27

O(N)

Joe Fitzsimons
fuente
25

Algoritmos para programación lineal : Simplex, Elipsoide y métodos de punto interior.

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Kaveh
fuente
Y, de hecho, se otorgaron varios premios Nobel por avanzar en nuestra comprensión de estos problemas.
Ross Snider
@Ross Kantorovich ganó el premio Nobel de Economía por inventar LP y aplicarlo a la asignación de recursos. ¿En qué otros premios estabas pensando?
Mark Reitblatt el
@Mark Koopermans fue galardonado con el premio Nobel con Kantorovich, pero aún era incorrecto por mi parte decir "varios".
Ross Snider
22

Algoritmo de Robin Moser para resolver una determinada clase de instancias SAT. Tales instancias pueden ser resueltas por Lovasz Local Lemma. El algoritmo de Moser es de hecho una desaleatorización de la declaración del lema.

Creo que hace algunos años su algoritmo (y la técnica para su prueba de corrección) será bien digerido y refinado hasta el punto de ser un candidato viable para un Algoritmo del Libro .

Esta versión es una extensión de su artículo original, escrito con Gábor Tardos.

MassimoLauria
fuente
21

El algoritmo X de Knuth encuentra todas las soluciones para el problema exacto de la cubierta . Lo que es tan mágico es la técnica que propuso para implementarlo eficientemente: Dancing Links .

Diego de Estrada
fuente
20

Creo que debemos incluir el de Schieber-Vishkin , que responde a las consultas de antepasados ​​comunes más bajas en tiempo constante, preprocesando el bosque en tiempo lineal.

Me gusta la exposición de Knuth en el Volumen 4, Fascículo 1, y su reflexión . Dijo que le tomó dos días enteros comprenderlo completamente, y recuerdo sus palabras:

Creo que es bastante hermoso, pero sorprendentemente tiene una mala prensa en la literatura (...) Está basado en las matemáticas que me entusiasman.

Diego de Estrada
fuente
10
Espera, puede ser hermoso, pero si Knuth tardó dos días enteros en comprenderlo completamente, ¿es realmente "del libro"?
ShreevatsaR
@ShreevatsaR El libro tiene letra pequeña en las notas al pie :)
hsmyers