Časová osa algoritmů - Timeline of algorithms - Wikipedia
Následující časová osa algoritmů nastiňuje vývoj algoritmy (hlavně „matematické recepty“) od jejich vzniku.
Středověké období
- Před - psaní o "recepty „(o vaření, rituálech, zemědělství a dalších tématech)
- C. 1700–2000 př. Nl - Egypťané vyvíjejí nejdříve známé algoritmy pro násobení dvě čísla
- C. 1600 př. N.l. - Babyloňané vyvinout nejdříve známé algoritmy pro faktorizace a hledání odmocniny
- C. 300 př. N.l. - Euklidův algoritmus
- C. 200 př. Nl - Síto Eratosthenes
- 263 nl - Gaussova eliminace popsal Liu Hui
- 628 – Chakravala metoda popsal Brahmagupta
- C. 820 - Al-Khawarizmi popsané algoritmy pro řešení lineární rovnice a kvadratické rovnice v jeho Algebra; slovo algoritmus pochází z jeho jména
- 825 – Al-Khawarizmi popsal algoritmus, algoritmy pro použití Hindu-arabská číselná soustava, ve svém pojednání Na výpočtu s hinduistickými číslicemi, který byl přeloženo do latiny tak jako Algoritmi de numero Indorum, kde „Algoritmi“, vzniklo překladatelovým překladem jména autora algoritmus (latinský algoritmus) s významem „metoda výpočtu“
- C. 850 - dešifrování a frekvenční analýza algoritmy vyvinuté Al-Kindi (Alkindus) v Rukopis o dešifrování kryptografických zpráv, který obsahuje algoritmy prolomení šifrování a šifry[1]
- C. 1025 - Ibn al-Haytham (Alhazen), byl prvním matematikem, který odvodil vzorec pro součet čtvrtého pravomoci, a na oplátku vyvine algoritmus pro stanovení obecného vzorce pro součet libovolného integrální pravomocí, což bylo zásadní pro rozvoj integrální počet[2]
- C. 1400 - Ahmad al-Qalqashandi poskytuje seznam šifry v jeho Subh al-a'sha které zahrnují obojí substituce a transpozice a poprvé šifra s více substitucemi za každou z nich prostý text dopis; on také dává výklad a pracoval příklad dešifrování, včetně použití tabulek frekvence písmen a sady písmen, které se nemohou vyskytovat společně v jednom slově
Před rokem 1940
- 1540 – Lodovico Ferrari objevil způsob, jak najít kořeny a kvartický polynom
- 1545 – Gerolamo Cardano zveřejnil Cardanovu metodu pro nalezení kořenů a kubický polynom
- 1614 – John Napier vyvíjí metodu pro provádění výpočtů pomocí logaritmy
- 1671 – Newton – Raphsonova metoda vyvinutý uživatelem Isaac Newton
- 1690 – Newton – Raphsonova metoda nezávisle vyvinut Joseph Raphson
- 1706 – John Machin vyvíjí rychle se sbíhající inverzně tečnou řadu pro π a počítá π na 100 desetinných míst
- 1789 – Jurij Vega vylepšuje Machinův vzorec a počítá π na 140 desetinných míst,
- 1805 – Algoritmus podobný FFT známé od Carl Friedrich Gauss
- 1842 – Ada Lovelace zapíše první algoritmus pro výpočetní modul
- 1903 - A. rychlá Fourierova transformace algoritmus předložený Carle David Tolmé Runge
- 1926 – Borůvkův algoritmus
- 1926 – Primární rozklad algoritmus předložený Grete Hermannová[3]
- 1927 – Hartree – Fockova metoda vyvinutý pro simulaci kvantového systému mnoha těl ve stacionárním stavu.
- 1934 – Delaunayova triangulace vyvinutý uživatelem Boris Delaunay
- 1936 – Turingův stroj, an abstraktní stroj vyvinutý uživatelem Alan Turing, s ostatní vytvořil moderní představu o algoritmus.
40. léta
- 1942 - A. rychlá Fourierova transformace algoritmus vyvinutý společností G.C. Danielson a Cornelius Lanczos
- 1945 – Sloučit třídění vyvinutý uživatelem John von Neumann
- 1947 – Simplexní algoritmus vyvinutý uživatelem George Dantzig
1950
- 1952 – Huffmanovo kódování vyvinutý uživatelem David A. Huffman
- 1953 – Simulované žíhání představil Nicholas Metropolis
- 1954 – Radix třídění počítačový algoritmus vyvinutý společností Harold H. Seward
- 1964 – Box – Mullerova transformace pro rychlou generaci normálně distribuovaných čísel publikovaných George Edward Pelham Box a Mervin Edgar Muller. Nezávisle předem objeveno uživatelem Raymond E. A. C. Paley a Norbert Wiener v roce 1934.
- 1956 – Kruskalův algoritmus vyvinutý uživatelem Joseph Kruskal
- 1956 – Algoritmus Ford-Fulkerson vyvinutý a publikovaný R. Ford Jr. a D. R. Fulkerson
- 1957 – Primův algoritmus vyvinutý uživatelem Robert Prim
- 1957 – Algoritmus Bellman-Ford vyvinutý uživatelem Richard E. Bellman a L. R. Ford, Jr.
- 1959 – Dijkstrův algoritmus vyvinutý uživatelem Edsger Dijkstra
- 1959 – Třídění skořápky vyvinutý uživatelem Donald L. Shell
- 1959 – De Casteljauův algoritmus vyvinutý uživatelem Paul de Casteljau
- 1959 – QR faktorizace algoritmus vyvinutý nezávisle uživatelem John G.F. Francis a Věra Kublanovská[4][5]
- 1959 – Konstrukce pohonné jednotky Rabin – Scott pro konverzi NFA do DFA publikováno Michael O. Rabin a Dana Scott
1960
- 1960 – Násobení Karatsuba
- 1961 – CRC (kontrola cyklické redundance) vynalezl W. Wesley Peterson
- 1962 – AVL stromy
- 1962 – Quicksort vyvinutý uživatelem C. A. R. Hoare
- 1962 – Bresenhamův liniový algoritmus vyvinutý uživatelem Jack E. Bresenham
- 1962 – Algoritmus „stabilního manželství“ Gale – Shapleye vyvinutý uživatelem David Gale a Lloyd Shapley
- 1964 – Heapsort vyvinutý uživatelem J. W. J. Williams
- 1964 – multigridové metody poprvé navrhl R. P. Fedorenko
- 1965 – Algoritmus Cooley – Tukey nově objevený uživatelem James Cooley a John Tukey
- 1965 – Levenshteinova vzdálenost vyvinutý uživatelem Vladimir Levenshtein
- 1965 – Algoritmus Cocke – Younger – Kasami (CYK) nezávisle vyvinut Tadao Kasami
- 1965 – Buchbergerův algoritmus pro výpočet Gröbnerovy základny vyvinutý uživatelem Bruno Buchberger
- 1965 – Analyzátory LR vynalezl Donald Knuth
- 1966 – Dantzigův algoritmus pro nejkratší cestu v grafu se zápornými hranami
- 1967 – Viterbiho algoritmus navrhl Andrew Viterbi
- 1967 – Algoritmus Cocke – Younger – Kasami (CYK) nezávisle vyvinut Daniel H. Younger
- 1968 – * Algoritmus pro vyhledávání grafů popsal Peter Hart, Nils Nilsson, a Bertram Raphael
- 1968 – Rischův algoritmus pro neurčitou integraci vyvinutou Robert Henry Risch
- 1969 – Strassenův algoritmus pro multiplikaci matic vyvinutou Volker Strassen
Sedmdesátá léta
- 1970 – Dinicův algoritmus pro výpočet maximálního toku v síti toku od Yefima (Chaima) A. Dinitze
- 1970 – Algoritmus dokončení Knuth – Bendix vyvinutý uživatelem Donald Knuth a Peter B. Bendix
- 1970 – Metoda BFGS z kvazi-Newton třída
- 1970 – Algoritmus Needleman – Wunsch publikováno Saul B. Needleman a Christian D. Wunsch
- 1972 – Algoritmus Edmonds – Karp publikováno Jack Edmonds a Richard Karp, v podstatě totožný s Dinicův algoritmus od roku 1970
- 1972 – Grahamovo skenování vyvinutý uživatelem Ronald Graham
- 1972 – Červeno-černé stromy a B-stromy objevil
- 1973 – RSA šifrovací algoritmus objevený uživatelem Clifford Cocks
- 1973 – Jarvis pochod algoritmus vyvinutý společností R. A. Jarvis
- 1973 – Algoritmus Hopcroft – Karp vyvinutý uživatelem John Hopcroft a Richard Karp
- 1974 – Pollard str - 1 algoritmus vyvinutý uživatelem John Pollard
- 1974 – Čtyřstrom vyvinutý uživatelem Raphael Finkel a J.L.Bentley
- 1975 – Genetické algoritmy popularizoval John Holland
- 1975 – Pollardův rho algoritmus vyvinutý uživatelem John Pollard
- 1975 – Algoritmus shody řetězců Aho – Corasick vyvinutý uživatelem Alfred V. Aho a Margaret J. Corasick
- 1975 – Válcový algebraický rozklad vyvinutý uživatelem George E. Collins
- 1976 – Algoritmus Salamin – Brent nezávisle objeven Eugene Salamin a Richard Brent
- 1976 – Algoritmus Knuth – Morris – Pratt vyvinutý uživatelem Donald Knuth a Vaughan Pratt a nezávisle na J. H. Morris
- 1977 – Algoritmus vyhledávání řetězců Boyer – Moore pro vyhledávání výskytu řetězce do jiného řetězce.
- 1977 – RSA šifrovací algoritmus znovu objeven Ron Rivest, Adi Shamir, a Len Adleman
- 1977 – LZ77 algoritmus vyvinutý společností Abraham Lempel a Jacob Ziv
- 1977 – multigridové metody vyvinutý nezávisle uživatelem Achi Brandt a Wolfgang Hackbusch
- 1978 – LZ78 algoritmus vyvinutý z LZ77 podle Abraham Lempel a Jacob Ziv
- 1978 – Bruunův algoritmus navrhl pro pravomoci dvou do Georg Bruun
- 1979 - Khachiyan elipsoidní metoda vyvinutý uživatelem Leonid Khachiyan
- 1979 – ID3 algoritmus rozhodovacího stromu vyvinutý Ross Quinlan
1980
- 1980 – Brentův algoritmus pro detekci cyklu Richard P. Brendt
- 1981 – Kvadratické síto vyvinutý uživatelem Carl Pomerance
- 1981 – Smith – Watermanův algoritmus vyvinutý uživatelem Temple F. Smith a Michael S. Waterman
- 1983 – Simulované žíhání vyvinutý uživatelem S. Kirkpatrick, C. D. Gelatt a M. P. Vecchi
- 1983 – Klasifikační a regresní strom (CART) algoritmus vyvinutý společností Leo Breiman, et al.
- 1984 – LZW algoritmus vyvinutý z LZ78 podle Terry Welch
- 1984 – Karmarkarův vnitřní bodový algoritmus vyvinutý uživatelem Narendra Karmarkar
- 1984 - ACORN_PRNG objeven Royem Wikramaratnou a použit soukromě
- 1985 – Simulované žíhání nezávisle vyvinut V. Černý
- 1985 - Car-Parrinello molekulární dynamika vyvinutý uživatelem Roberto Car a Michele Parrinello
- 1985 – Roztáhněte stromy objeveno uživatelem Kráječ a Tarjan
- 1986 – Blum Blum Shub navrhl L. Blum, M. Blum, a M. Shub
- 1986 – Algoritmus maximálního toku push relabel Andrew Goldberg a Robert Tarjan
- 1986 - Metoda Barnes – Hut stromu vyvinutý uživatelem Josh Barnes a Piet Hut pro rychlou přibližnou simulaci problémy s tělem n
- 1987 – Rychlá vícepólová metoda vyvinutý uživatelem Leslie Greengard a Vladimir Rokhlin
- 1988 – Speciální sítové pole vyvinutý uživatelem John Pollard
- 1989 - ACORN_PRNG publikoval Roy Wikramaratna
- 1989 – Protokol Paxos vyvinutý uživatelem Leslie Lamport
90. léta
- 1990 – Síto obecného čísla vyvinuto z SNFS podle Carl Pomerance, Joe Buhler, Hendrik Lenstra, a Leonard Adleman
- 1990 – Coppersmith – Winogradův algoritmus vyvinutý uživatelem Don Coppersmith a Shmuel Winograd
- 1990 – Algoritmus BLAST vyvinutý uživatelem Stephen Altschul, Warren Gish, Webb Miller, Eugene Myers, a David J. Lipman z Národní institut zdraví
- 1991 – Synchronizace bez čekání vyvinutý uživatelem Maurice Herlihy
- 1992 – Algoritmus Deutsch – Jozsa navrhl D. Deutsch a Richard Jozsa
- 1992 – Algoritmus C4.5, potomek ID3 algoritmus rozhodovacího stromu, byl vyvinut Ross Quinlan
- 1993 – Apriori algoritmus vyvinuli Rakesh Agrawal a Ramakrishnan Srikant
- 1993 – Kargerův algoritmus vypočítat minimální řez spojeného grafu Davida Kargera
- 1994 – Shorův algoritmus vyvinutý uživatelem Peter Shor
- 1994 – Burrows – Wheelerova transformace vyvinutý uživatelem Michael Burrows a David Wheeler
- 1994 – Agregace bootstrapu (pytlování) vyvinuté Leo Breiman
- 1995 – AdaBoost Algoritmus, první praktický zesilovací algoritmus, představil Yoav Freund a Robert Schapire
- 1995 - měkká marže podporovat vektorový stroj algoritmus zveřejnil Vladimír Vapnik a Corinna Cortes. Přidává do algoritmu z roku 1992 myšlenku soft-margin od Bosera, Nguyona, Vapnika a je to algoritmus, na který lidé obvykle říkají SVM
- 1995 – Ukkonenův algoritmus pro stavbu stromů přípon
- 1996 – Bruunův algoritmus zobecněno na libovolné i kompozitní velikosti o H. Murakami
- 1996 – Groverův algoritmus vyvinutý uživatelem Lov K.Grover
- 1996 – RIPEMD-160 vyvinutý uživatelem Hans Dobbertin, Antoon Bosselaers, a Bart Preneel
- 1997 – Mersenne Twister generátor pseudonáhodných čísel vyvinutý společností Makoto Matsumoto a Tajuki Nishimura
- 1998 – PageRank algoritmus zveřejnil Larry Page
- 1998 – rsync algoritmus vyvinutý uživatelem Andrew Tridgell
- 1999 – zvýšení gradientu algoritmus vyvinutý společností Jerome H. Friedman
- 1999 – Yarrowův algoritmus navrhl Bruce Schneier, John Kelsey, a Niels Ferguson
2000s
- 2000 – Vyhledávání témat vyvolaných hypertextovými odkazy algoritmus analýzy hypertextových odkazů vyvinutý Jonem Kleinbergem
- 2001 – Algoritmus řetězce Lempel – Ziv – Markov pro kompresi vyvinutou Igor Pavlov
- 2001 – Viola – Jones Algoritmus pro detekci obličeje v reálném čase vyvinuli Paul Viola a Michael Jones.
- 2001 – DHT (distribuovaná hash tabulka) je vynalezeno více lidmi z akademické sféry a aplikačních systémů
- 2001 – BitTorrent je zveřejněn první plně decentralizovaný systém distribuce souborů peer-to-peer
- 2002 – Test prvosti AKS vyvinutý uživatelem Manindra Agrawal, Neeraj Kayal a Nitin Saxena
- 2002 – Algoritmus Girvan – Newman detekovat komunity ve složitých systémech
- 2002 – Analyzátor Packrat vyvinutý pro generování analyzátoru, který analyzuje PEG (analýza gramatiky výrazu) v lineárním časovém rozboru vyvinutém Bryan Ford
- 2009 – Bitcoin je zveřejněn první decentralizovaný systém kryptoměny bez důvěryhodnosti
2010s
- 2013 – Protokol Raft Consensu publikováno Diego Ongaro a John Ousterhout
- 2015 – YOLO („Podíváte se pouze jednou“) je efektivní algoritmus rozpoznávání objektů v reálném čase, který poprvé popsal Joseph Redmon et al.
Reference
- ^ Simon Singh, Kniha zákonů, s. 14–20
- ^ Victor J. Katz (1995). "Ideas of Calculus in Islam and India", Matematický časopis 68 (3), s. 163–174.
- ^ Ciliberto, Ciro; Hirzebruch, Friedrich; Miranda, Rick; Teicher, Mina, eds. (2001). Aplikace algebraické geometrie na teorii kódování, fyziku a výpočet. Dordrecht: Springer Nizozemsko. ISBN 978-94-010-1011-5.
- ^ Francis, J.G.F. (1961). „Transformace QR, já“. Počítačový deník. 4 (3): 265–271. doi:10.1093 / comjnl / 4.3.265.
- ^ Kublanovskaya, Vera N. (1961). Msgstr "Na některých algoritmech pro řešení úplného problému vlastních čísel". SSSR výpočetní matematika a matematická fyzika. 1 (3): 637–657. doi:10.1016 / 0041-5553 (63) 90168-X. Publikováno také v: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki [Journal of Computational Mathematics and Mathematical Physics], 1 (4), strany 555–570 (1961).