Nombrados por los editores de SIAM (Society for Industrial and Applied Mathematics)
https://www.siam.org/pdf/news/637.pdf
Traducción
Algos es la palabra griega para el dolor. Algor es latín, tener frío. Ninguna es la raíz de algoritmo, que deriva de al-Khwarizmi, el nombre del erudito árabe del siglo IX cuyo libro al-Jabr wa muqabalah ha involucionado hasta llegar a los libros de texto de álgebra de la escuela secundaria de hoy. Al-Khwarizmi hizo hincapié en la importancia de los procedimientos metodológicos para la solución de problemas. Si todavía estuviera por aquí, sin duda alguna estaría impresionado por los avances en la aproximación algorítmica a los problemas.
Algunos de los mejores algoritmos de la era del ordenador se destacan en la edición de enero / febrero de 2000, de Computing in Science & Engineering, una publicación conjunta del Instituto Americano de Física y la IEEE Computer Society. Los editores invitados Jack Dongarra de la Universidad de Tennessee y el Laboratorio Nacional de Oak Ridge y Francis Sullivan, del Centro de Ciencias de la Computación en el Instituto de Análisis de Defensa han hecho una lista de lo que consideran el "Top Ten Algoritmos del siglo".
"Tratamos de reunir los 10 algoritmos con la mayor influencia en el desarrollo y la práctica de la ciencia y la ingeniería en el siglo 20", Dongarra y Sullivan escriben. Al igual que con cualquier top, sus selecciones y no selecciones están destinadas a la controversia, reconocen. Cuando se trata de elegir el mejor algoritmo, no parece haber ningún algoritmo.
Sin más preámbulos, aquí está la lista CISE top-10, en orden cronológico. (Fechas y nombres asociados con los algoritmos deben leerse como aproximaciones de primer orden. La mayoría de los algoritmos toman forma a través del tiempo, con muchos colaboradores.)
Método de Monte Carlo
En 1946 John Von Neumann, Stanislau Ulam, y Nick Metropolis, todos en el laboratorio nacional de Los Álamos (donde se realizó el proyecto Manhattan) diseñan el algoritmo Metropolis, también conocido como método de Monte Carlo.
La idea es obtener soluciones aproximadas a problemas con una cantidad ingente de grados de libertad (aka variables) simulando un proceso aleatorio. Dada la fama del ordenador para cálculos determinísticos, es irónico que uno de los primeros grandes algoritmos fuera aleatorio.
Extendiéndome (yo) sobre el funcionamiento, la manera en que funciona es relativamente simple. Queremos mirar el área que hay dentro de una superficie (una curva por ejemplo). Generamos puntos aleatorios en una superficie mayor y miramos la proporción de puntos que quedan dentro del volumen que queremos medir. Esta proporción tiende en promedio a estar relacionada con el volumen.
Método del Simplex para programación lineal
En 1947 George Dantzig de la RAND corporation creó el algoritmo del Simplex para programación lineal. En términos de propagación, este es uno de los algoritmos más exitosos: Domina el mundo de la industria, donde la supervivencia económica se basa en la habilidad de optimizar beneficios con unos límites al presupuesto y otras restricciones. (Por supuesto se requieren modificaciones a este método pero este fue el que marcó el inicio.) El método del Simplex es una manera elegante de llegar a las respuestas óptimas. En algunos casos extremos puede ser muy lento, pero en la práctica suele ser muy eficiente -- lo cual dice algo sobre la naturaleza de la computación.
Este algoritmo trata de buscar el máximo de una función lineal dado un conjunto de restricciones lineales. En bachillerato social es lo que se hace de mirar la recta paralela qué vértice del polígono toca. Básicamente es lo mismo en n dimensiones, tenemos un polítopo formado por las intersecciones de hiperplanos y hay que mirar de todos los "vértices" en cual la función es mayor o menor.
Métodos de iteración en subespacios de Krylov
Desarrollado en 1950 por Magnus Hestenes, Eduard Stiefel, y Cornelius Lacnzos. Este algoritmo busca resolver la (a priori) simple ecuación Ax = B donde A es una matrix nxn enorme, y b es un vector. La idea es resolver ecuaciones relativamente más simples con matrices "cercanas" a A de manera iterativa:
[; K x{i+1} = K x{i} + b - A x_{i} ;]
Estas matrices K salen del estudio de los subespacios de Krylov (un matemático ruso), generados por las potencias de una matriz aplicada a un vector "inicial" que es el residuo [; r{0}= b - A x{0} ;] . Lacnzos encontró una manera inteligente de generar una base ortogonal para el subespacio cuando la matriz es simétrica. Hestenes y Stiefel mejoraron este método usando el famoso método de los gradientes conjugados, para sistemas simétricos y definidos positivos. Durante las siguientes décadas numerosos investigadores han mejorado y extendido estos algoritmos. Actualmente (2000) hay algoritmos para sistemas no simétricos : GMRES y Bi-CGSTAB.
Descomposición computacional de matrices
En 1951 Alston Householder del laboratorio nacional de Oak Ridge formaliza esta aproximación. La idea es descomponer la matriz A como productos de otras matrices más simples, que permiten mayor eficiencia en los cálculos (sobre todo si hay que repetirlos muchas veces) y mayor control del error que producimos al realizarlos. El ejemplo más típico es el método LU, donde descomponemos A en el producto de L y U donde L es una matriz triangular por debajo con todos los elementos de la diagonal 1, y U es una matriz triangular por arriba.
Compilador de Fortran
En 1957 John Backus lideró un equipo de IBM desarrollando el compilador optimizador de Fortran. La creación de Fortran podría ser considerada una de las grandes piedras de toque de la computación. Por fin los científicos podían tener una manera estándar de programar sin tener que ir a lenguaje máquina, y aunque para los estándares de ahora el compilador no es gran cosa, en aquella época los informáticos se sorprendían de lo fino que hilaba el compilador.
Algoritmo QR
Entre 1959 y 1961 J.G.F. Francis de Ferranti Ltd., Londres, encontró un método estable para computar los valores propios de una matriz nxn. Es relativamente fácil transformar cualquier matriz en una matriz "casi triangular por arriba" (excepto la subdiagonal inferior). Pero hasta que se desarrolló el método QR era casi imposible quitar esos últimos elementos que no son cero sin caer en una avalancha de errores. El método QR descompone una matriz en un producto de Q (matriz ortogonal) y R (matriz triangular por arriba), y lo que se hace a partir de este método es ir pasando de QR a RQ (y volver a descomponer RQ), con unos detallitos para acelerar la convergencia. A mitades de los años 60, lo que una vez fueron problemas gargantuescos se habían convertido en tareas rutinarias.
Quicksort
Presentado en 1962 por Tony Hoare de Elliott Brothers, Ltd., Londres. Poner N números en orden descendente o ascendente parece algo mundano. El problema es encontrar maneras de hacerlo rápidamente. El algoritmo de Hoare usa la clásica técnica de "divide y vencerás". Elige un elemento como pivote, separa el resto en pilas de elementos "grandes" y "pequeños", y repite para cada pila. Aunque es posible tener que hacer todas las N(N-1)/2 comparaciones, en promedio Quicksort corre en O(Nlog(N)) pasos. Su simplicidad ha convertido Quicksort en el ejemplo modélico de la teoría de complejidad computacional.
Nota: Sí, Mergesort es más rápido en el peor caso, pero hay otras cosas a considerar. Si estáis interesados, aquí se discute. Tambien esta heapsort que en la practica es mas rapido, tal y como comenta #9 .
FFT
Desarrollado en 1965 por James Cooley y John Tukey (IBM y Princeton Universtiy) FFT o Fast Fourier Transform (transformada rápida de Fourier) es posiblemente EL algoritmo más importante del último siglo.
La idea es parecida a Quicksort: Dividir el problema recursivamente y pasar de hacer O(N2) pasos a O(NlogN). Pero la manera de hacerlo no es tan evidente como Quicksort. El desarrollo de este algoritmo fue lo que impulsó al estudio más detenido de la complejidad de ciertos programas y algoritmos (i.e. vieron que la manera más obvia no siempre es la mejor). Las aplicaciones de FFT son innumerables, desde las matemáticas teóricas (descomposición en factores) hasta el procesado de señal.
Algoritmo para la detección de relación de enteros
Creado por Helaman Ferguson y Rodney Forcade de Brigham Young University.
El problema es viejo: Dada una lista de números reales [; x_1, x_2, dots, x_n ;] tenemos que encontrar una lista de enteros [; a_1, a_2, \dots, a_n ;] (no todos igual a cero) tales que [; x_1a_1 + \dots x_na_n = 0 ;] o , si no es posible encontrarlos, decirlo. Para n = 2 el algoritmo de Euclides resuelve el problema, simplemente encontrando los términos de la fracción continua si [; x_1/x_2 ;] es racional. La generalización de Ferguson y Forcade es mucho más difícil de implementar (y de entender), pero mucho más poderosa. Su algoritmo de detección se ha usado, por ejemplo, para encontrar los coeficientes de los polinomios que siguen los puntos de bifurcación tercero 3.544090 y cuarto 3.564407 del mapa logístico ) (el último polinomio tiene grado 120, para que os hagáis una idea). También se usa para simplificar cálculos con los diagramas de Feynman en teoría cuántica de campos.
Fast Multipole Algorithm
Desarrollado en 1987 por Leslie Greengard y Vladimir Rokhlin de Yale University.
Este algoritmo resuelve uno de los mayores problemas del problema (valga la redundancia) de N-cuerpos. En el problema de N-cuerpos intentamos encontrar la dinámica que siguen N cuerpos donde todos influyen a todos los otros (por ejemplo galaxias o planetas). Parece que como mínimo para resolverlo necesitamos N2 computaciones (una para cada par de partículas). El algoritmo Fast Multipole lo hace con O(N) computaciones. Lo hace aproximando la influencia de todos los cuerpos lejanos como un cuerpo muy grande y no puntual. Se realiza una descomposición jerárquica del espacio para definir grupos cada vez más grandes conforme nos alejamos del cuerpo (esta descomposición no es trivial y de hecho hacerlo inteligentemente es lo que permite este O(N)). Una de las ventajas de este método es que tenemos estimaciones rigurosas del error cometido, cosa que no pasa en muchos otros métodos.
Y hasta aquí hemos llegado! Si tenéis dudas sobre algún algoritmo, o queréis aportar otro algoritmo que vosotros consideréis más influyente, aquí estaré para discutirlo 
.
