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.
Respuestas:
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 .
fuente
Cordón Knuth-Morris-Pratt a juego. Las ocho líneas de código más ingeniosas que jamás hayas visto.
fuente
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:
fuente
La búsqueda binaria es el algoritmo más simple, hermoso y útil con el que me he encontrado.
fuente
Me sorprende no ver el algoritmo de Floyd-Warshall para los caminos más cortos de todos los pares aquí:
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)
fuente
Algoritmo euclidiano para calcular el máximo común divisor (MCD)
fuente
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.
fuente
Codificación de Huffman para la compresión de datos.
fuente
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!
fuente
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.
fuente
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?
fuente
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).
fuente
El tamiz de Eratóstenes , simple e intuitivo.
También me gusta la belleza del algoritmo de Horner .
fuente
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.
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
fuente
El algoritmo de FFT Cooley-Tukey .
fuente
Algoritmo de Strassen para la multiplicación de matrices.
fuente
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.
fuente
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
fuente
Eliminación gaussiana. Completa la secuencia de generalización del algoritmo Euclidean GCD a Knuth-Bendix.
fuente
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.
fuente
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í.
fuente
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.
fuente
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.
fuente
Ordenar por fusión . Simple, elegante, eficiente.
fuente
fuente
Algoritmos para programación lineal : Simplex, Elipsoide y métodos de punto interior.
http://en.wikipedia.org/wiki/Linear_programming#Algorithms
fuente
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.
fuente
El algoritmo más rápido y más corto de Marcus Hutter para todos los problemas bien definidos .
Esto va en contra del espíritu de las otras ofertas en esta lista, ya que es solo de interés teórico y no práctico, pero nuevamente el título lo dice todo. Tal vez debería incluirse como una historia de advertencia para aquellos que solo mirarían el comportamiento asintótico de un algoritmo.
fuente
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 .
fuente
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:
fuente