Cronología de algoritmos

La siguiente línea de tiempo de algoritmos describe el desarrollo de algoritmos (principalmente "recetas matemáticas") desde sus inicios.

Período medieval

• Antes: escribiendo sobre " recetas " (sobre cocina, rituales, agricultura y otros temas)
• C. 1700-2000 a. C. - Los egipcios desarrollan los primeros algoritmos conocidos para multiplicar dos números.
• C. 1600 aC - Los babilonios desarrollan los primeros algoritmos conocidos para la factorización y la búsqueda de raíces cuadradas.
• C. 300 aC - algoritmo de Euclides
• C. 200 aC - el tamiz de Eratóstenes
• 263 d.C. - Eliminación gaussiana descrita por Liu Hui.
• 628 - Método Chakravala descrito por Brahmagupta
• C. 820 - Al-Khawarizmi describió algoritmos para resolver ecuaciones lineales y ecuaciones cuadráticas en su Álgebra ; la palabra algoritmo proviene de su nombre
• 825 - Al-Khawarizmi describe el algoritmo , algoritmos para usar el sistema de numeración Hindú-Árabe , en su tratado sobre el cálculo con el hindú números , que fue traducido al latín como Algoritmi de numero Indorum , donde "Algoritmi", versión del traductor de la el nombre del autor dio lugar a la palabra algoritmo (en latín algorítmo ) con un significado "método de cálculo"
• C. 850 - Algoritmos de criptoanálisis y análisis de frecuencia desarrollados por Al-Kindi (Alkindus) en A Manuscript on Deciphering Cryptographic Messages , que contiene algoritmos para romper cifrados y cifrados ^[1]
• C. 1025 - Ibn al-Haytham (Alhazen), fue el primer matemático en derivar la fórmula para la suma de las cuartas potencias y, a su vez, desarrolla un algoritmo para determinar la fórmula general para la suma de las potencias integrales , que fue fundamental. al desarrollo del cálculo integral ^[2]
• C. 1400 - Ahmad al-Qalqashandi da una lista de cifrados en su Subh al-a'sha que incluyen tanto sustitución como transposición , y por primera vez, un cifrado con múltiples sustituciones para cada letra de texto llano ; También ofrece una exposición y un ejemplo elaborado de criptoanálisis , incluido el uso de tablas de frecuencias de letras y conjuntos de letras que no pueden aparecer juntas en una palabra.

Antes de 1940

• 1540 - Lodovico Ferrari descubrió un método para encontrar las raíces de un polinomio cuártico.
• 1545 - Gerolamo Cardano publicó el método de Cardano para encontrar las raíces de un polinomio cúbico
• 1614 - John Napier desarrolla un método para realizar cálculos usando logaritmos
• 1671 - Método de Newton-Raphson desarrollado por Isaac Newton
• 1690 - Método de Newton-Raphson desarrollado independientemente por Joseph Raphson
• 1706 - John Machin desarrolla una serie de tangente inversa rápidamente convergente para π y calcula π con 100 lugares decimales
• 1789 - Jurij Vega mejora la fórmula de Machin y calcula π a 140 lugares decimales,
• 1805 - Algoritmo similar a FFT conocido por Carl Friedrich Gauss
• 1842: Ada Lovelace escribe el primer algoritmo para un motor informático.
• 1903 - Un algoritmo de transformada rápida de Fourier presentado por Carle David Tolmé Runge
• 1926 - algoritmo de Borůvka
• 1926 - Algoritmo de descomposición primario presentado por Grete Hermann ^[3]
• 1927 - Se desarrolla el método Hartree-Fock para simular un sistema cuántico de muchos cuerpos en un estado estacionario.
• 1934 - Triangulación de Delaunay desarrollada por Boris Delaunay
• 1936 - La máquina de Turing , una máquina abstracta desarrollada por Alan Turing , junto con otros desarrollaron la noción moderna de algoritmo .

Década de 1940

• 1942 - Un algoritmo de transformada rápida de Fourier desarrollado por GC Danielson y Cornelius Lanczos
• 1945 - Tipo de fusión desarrollado por John von Neumann
• 1947 - Algoritmo simplex desarrollado por George Dantzig

Década de 1950

• 1952 - Codificación de Huffman desarrollada por David A. Huffman
• 1953 - Recocido simulado introducido por Nicholas Metropolis
• 1954 - Algoritmo informático de ordenación Radix desarrollado por Harold H. Seward
• 1964 - Transformada de Box-Muller para la generación rápida de números distribuidos normalmente publicado por George Edward Pelham Box y Mervin Edgar Muller . Independientemente pre-descubierto por Raymond EAC Paley y Norbert Wiener en 1934.
• 1956 - Algoritmo de Kruskal desarrollado por Joseph Kruskal
• 1956: algoritmo Ford-Fulkerson desarrollado y publicado por R. Ford Jr. y DR Fulkerson
• 1957 - El algoritmo de Prim desarrollado por Robert Prim
• 1957: algoritmo Bellman-Ford desarrollado por Richard E. Bellman y LR Ford, Jr.
• 1959 - Algoritmo de Dijkstra desarrollado por Edsger Dijkstra
• 1959 - Tipo de concha desarrollado por Donald L. Shell
• 1959 - El algoritmo de De Casteljau desarrollado por Paul de Casteljau
• 1959 - Algoritmo de factorización QR desarrollado independientemente por John GF Francis y Vera Kublanovskaya ^{[4] [5]}
• 1959 - Construcción powerset Rabin-Scott para la conversión de la NFA en DFA publicado por Michael O. Rabin y Dana Scott

1960

• 1960 - Multiplicación de Karatsuba
• 1961 - CRC (verificación de redundancia cíclica) inventado por W. Wesley Peterson
• 1962 - árboles AVL
• 1962 - Quicksort desarrollado por CAR Hoare
• 1962 - Algoritmo de línea de Bresenham desarrollado por Jack E. Bresenham
• 1962 - Algoritmo de 'matrimonio estable' de Gale-Shapley desarrollado por David Gale y Lloyd Shapley
• 1964 - Heapsort desarrollado por JWJ Williams
• 1964 - métodos de redes múltiples propuestos por primera vez por RP Fedorenko
• 1965 - El algoritmo Cooley-Tukey redescubierto por James Cooley y John Tukey
• 1965 - Distancia de Levenshtein desarrollada por Vladimir Levenshtein
• 1965 - Algoritmo Cocke – Younger – Kasami (CYK) desarrollado de forma independiente por Tadao Kasami
• 1965 - El algoritmo de Buchberger para calcular las bases de Gröbner desarrollado por Bruno Buchberger
• 1965 - Analizadores sintácticos LR inventados por Donald Knuth
• 1966 - Algoritmo de Dantzig para la ruta más corta en un gráfico con bordes negativos
• 1967 - Algoritmo de Viterbi propuesto por Andrew Viterbi
• 1967 - Algoritmo Cocke – Younger – Kasami (CYK) desarrollado de forma independiente por Daniel H. Younger
• 1968 - Algoritmo de búsqueda de gráficos A * descrito por Peter Hart , Nils Nilsson y Bertram Raphael
• 1968: algoritmo de Risch para la integración indefinida desarrollado por Robert Henry Risch
• 1969 - Algoritmo de Strassen para la multiplicación de matrices desarrollado por Volker Strassen

1970

• 1970 - Algoritmo de Dinic para calcular el flujo máximo en una red de flujo por Yefim (Chaim) A. Dinitz
• 1970 - Algoritmo de finalización Knuth-Bendix desarrollado por Donald Knuth y Peter B. Bendix
• 1970 - Método BFGS de la clase cuasi-Newton
• 1970 - Algoritmo de Needleman-Wunsch publicado por Saul B. Needleman y Christian D. Wunsch
• 1972 - Algoritmo de Edmonds-Karp publicado por Jack Edmonds y Richard Karp , esencialmente idéntico al algoritmo de Dinic de 1970
• 1972 - Escaneo de Graham desarrollado por Ronald Graham
• 1972 - Se descubren árboles rojo-negros y árboles B
• 1973 - Algoritmo de cifrado RSA descubierto por Clifford Cocks
• 1973 - Algoritmo de marcha de Jarvis desarrollado por RA Jarvis
• 1973 - Algoritmo Hopcroft – Karp desarrollado por John Hopcroft y Richard Karp
• 1974 - de Pollard p  - 1 algoritmo desarrollado por John Pollard
• 1974 - Quadtree desarrollado por Raphael Finkel y JL Bentley
• 1975 - Algoritmos genéticos popularizados por John Holland
• 1975 - Algoritmo rho de Pollard desarrollado por John Pollard
• 1975 - Algoritmo de coincidencia de cadenas Aho-Corasick desarrollado por Alfred V. Aho y Margaret J. Corasick
• 1975 - Descomposición algebraica cilíndrica desarrollada por George E. Collins
• 1976 - El algoritmo Salamin-Brent es descubierto de forma independiente por Eugene Salamin y Richard Brent.
• 1976 - Algoritmo Knuth-Morris-Pratt desarrollado por Donald Knuth y Vaughan Pratt e independientemente por JH Morris
• 1977 - Algoritmo de búsqueda de cadenas de Boyer-Moore para buscar la aparición de una cadena en otra cadena.
• 1977 - El algoritmo de cifrado RSA redescubierto por Ron Rivest , Adi Shamir y Len Adleman
• 1977 - Algoritmo LZ77 desarrollado por Abraham Lempel y Jacob Ziv
• 1977: métodos de redes múltiples desarrollados de forma independiente por Achi Brandt y Wolfgang Hackbusch
• 1978 - Algoritmo LZ78 desarrollado a partir de LZ77 por Abraham Lempel y Jacob Ziv
• 1978 - El algoritmo de Bruun propuesto para potencias de dos por Georg Bruun.
• 1979 - Método elipsoide de Khachiyan desarrollado por Leonid Khachiyan
• 1979 - Algoritmo de árbol de decisión ID3 desarrollado por Ross Quinlan

Década de 1980

• 1980 - Algoritmo de Brent para la detección de ciclos Richard P. Brendt
• 1981 - Tamiz cuadrático desarrollado por Carl Pomerance
• 1981 - Algoritmo de Smith-Waterman desarrollado por Temple F. Smith y Michael S. Waterman
• 1983 - Recocido simulado desarrollado por S. Kirkpatrick , CD Gelatt y MP Vecchi
• 1983 - Algoritmo de árbol de clasificación y regresión (CART) desarrollado por Leo Breiman , et al.
• 1984 - Algoritmo LZW desarrollado a partir de LZ78 por Terry Welch
• 1984: algoritmo de punto interior de Karmarkar desarrollado por Narendra Karmarkar
• 1984 - ACORN_PRNG descubierto por Roy Wikramaratna y utilizado de forma privada
• 1985 - Recocido simulado desarrollado independientemente por V. Cerny
• 1985 - Dinámica molecular Car-Parrinello desarrollada por Roberto Car y Michele Parrinello
• 1985 - Splay trees descubiertos por Sleator y Tarjan
• 1986 - Blum Blum Shub propuesto por L. Blum , M. Blum y M. Shub
• 1986 - Algoritmo de flujo máximo Push Rebelde por Andrew Goldberg y Robert Tarjan
• 1986 - Método de árbol de Barnes-Hut desarrollado por Josh Barnes y Piet Hut para la simulación aproximada rápida de problemas de n-cuerpos
• 1987 - Método rápido multipolar desarrollado por Leslie Greengard y Vladimir Rokhlin
• 1988 - Tamiz de campo de número especial desarrollado por John Pollard
• 1989 - ACORN_PRNG publicado por Roy Wikramaratna
• 1989 - Protocolo de Paxos desarrollado por Leslie Lamport

Década de 1990

• 1990 - Tamiz de campo numérico general desarrollado a partir de SNFS por Carl Pomerance , Joe Buhler , Hendrik Lenstra y Leonard Adleman
• 1990 - Algoritmo Coppersmith – Winograd desarrollado por Don Coppersmith y Shmuel Winograd
• 1990: algoritmo BLAST desarrollado por Stephen Altschul , Warren Gish , Webb Miller , Eugene Myers y David J. Lipman de los Institutos Nacionales de Salud
• 1991 - Sincronización sin espera desarrollada por Maurice Herlihy
• 1992 - Algoritmo Deutsch – Jozsa propuesto por D. Deutsch y Richard Jozsa
• 1992 - El algoritmo C4.5 , un descendiente del algoritmo de árbol de decisión ID3 , fue desarrollado por Ross Quinlan
• 1993 - Algoritmo Apriori desarrollado por Rakesh Agrawal y Ramakrishnan Srikant
• 1993 - Algoritmo de Karger para calcular el corte mínimo de un gráfico conectado por David Karger
• 1994 - Algoritmo de Shor desarrollado por Peter Shor
• 1994 - Transformada de Burrows – Wheeler desarrollada por Michael Burrows y David Wheeler
• 1994 - Bootstrap aggregating (ensacado) desarrollado por Leo Breiman
• 1995 - El algoritmo AdaBoost , el primer algoritmo de impulso práctico, fue introducido por Yoav Freund y Robert Schapire.
• 1995: Vladimir Vapnik y Corinna Cortes publicaron el algoritmo de máquina vectorial de soporte de margen blando . Agrega una idea de margen suave al algoritmo de 1992 de Boser, Nguyon, Vapnik, y es el algoritmo al que la gente suele referirse cuando dice SVM
• 1995: algoritmo de Ukkonen para la construcción de árboles de sufijos
• 1996 - El algoritmo de Bruun se generalizó a tamaños compuestos incluso arbitrarios por H. Murakami
• 1996 - Algoritmo de Grover desarrollado por Lov K. Grover
• 1996 - RIPEMD-160 desarrollado por Hans Dobbertin , Antoon Bosselaers y Bart Preneel
• 1997 - Mersenne Twister, un generador de números pseudoaleatorios desarrollado por Makoto Matsumoto y Tajuki Nishimura
• 1998 - Larry Page publicó el algoritmo PageRank
• 1998 - algoritmo rsync desarrollado por Andrew Tridgell
• 1999 - algoritmo de aumento de gradiente desarrollado por Jerome H. Friedman
• 1999 - Algoritmo de milenrama diseñado por Bruce Schneier , John Kelsey y Niels Ferguson

2000

• 2000 - Búsqueda de temas inducida por hipervínculos, un algoritmo de análisis de hipervínculos desarrollado por Jon Kleinberg
• 2001 - Algoritmo de cadena Lempel – Ziv – Markov para compresión desarrollado por Igor Pavlov
• 2001 - Paul Viola y Michael Jones desarrollaron el algoritmo Viola-Jones para la detección de rostros en tiempo real.
• 2001 - DHT (tabla hash distribuida) es inventada por varias personas de la academia y los sistemas de aplicación.
• 2001 - Se publica BitTorrent, el primer sistema de distribución de archivos peer-to-peer completamente descentralizado
• 2002 - Prueba de primalidad AKS desarrollada por Manindra Agrawal , Neeraj Kayal y Nitin Saxena
• 2002 - Algoritmo Girvan-Newman para detectar comunidades en sistemas complejos
• 2002 - Analizador de Packrat desarrollado para generar un analizador que analiza PEG (análisis de gramática de expresión) en análisis de tiempo lineal desarrollado por Bryan Ford
• 2009 - Bitcoin , se publica el primer sistema de criptomonedas descentralizado sin confianza

Década de 2010

• 2013 - Protocolo de consenso de balsa publicado por Diego Ongaro y John Ousterhout
• 2015 - YOLO ("Solo mira una vez") es un algoritmo de reconocimiento de objetos en tiempo real efectivo, descrito por primera vez por Joseph Redmon et al.

Referencias

1. Simon Singh , El libro de códigos , págs. 14-20
2. Víctor J. Katz (1995). "Ideas de cálculo en el Islam y la India", Revista de matemáticas 68 (3), págs. 163-174.
3. Ciliberto, Ciro; Hirzebruch, Friedrich; Miranda, Rick; Teicher, Mina , eds. (2001). Aplicaciones de la geometría algebraica a la teoría de la codificación, la física y la computación . Dordrecht: Springer Holanda. ISBN 978-94-010-1011-5.
4. Francis, JGF (1961). "La Transformación QR, yo" . The Computer Journal . 4 (3): 265-271. doi : 10.1093 / comjnl / 4.3.265 .
5. Kublanovskaya, Vera N. (1961). "Sobre algunos algoritmos para la solución del problema de autovalores completo". URSS Matemáticas Computacionales y Física Matemática . 1 (3): 637–657. doi : 10.1016 / 0041-5553 (63) 90168-X . También publicado en: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki [Revista de matemática computacional y física matemática], 1 (4), páginas 555–570 (1961).