Algoritmaların zaman çizelgesi - Timeline of algorithms

Aşağıdaki algoritma zaman çizelgesi, başlangıcından bu yana algoritmaların (esas olarak "matematiksel tarifler") gelişimini özetlemektedir .

Ortaçağ Dönemi

• Öncesi - " yemek tarifleri " hakkında yazmak (yemek pişirme, ritüeller, tarım ve diğer temalar hakkında)
• C. MÖ 1700–2000 – Mısırlılar iki sayıyı çarpmak için bilinen en eski algoritmaları geliştirdiler.
• C. MÖ 1600 – Babilliler , çarpanlara ayırma ve karekök bulma için bilinen en eski algoritmaları geliştirdiler.
• C. MÖ 300 – Öklid'in algoritması
• C. MÖ 200 – Eratosthenes Kalburu
• MS 263 - Liu Hui tarafından açıklanan Gauss eliminasyonu
• 628 - Brahmagupta tarafından açıklanan Chakravala yöntemi
• C. 820 - Al-Khawarizmi çözmek için algoritma açıklanan denklemler lineer ve kuadratik denklemler onun içinde Cebir ; algoritma kelimesi onun adından geliyor
• 825 - Al-Khawarizmi açıklanan rakamları sistemi , kullanmak için algoritmalar Hint-Arap rakam sistemi eserinde, Hindu rakamlarıyla Hesaplama On edildi Latince'ye tercüme olarak Algoritmi'nin de numero Indorum , "Algoritmi'nin" nin çevirmenin yorumuyla Yazarın adı, "hesaplama yöntemi" anlamına gelen algoritma ( Latince algoritma ) kelimesini doğurmuştur.
• C. 850 – Al-Kindi (Alkindus) tarafından şifreleme ve şifre kırma algoritmalarını içeren Kriptografik Mesajların Deşifre Edilmesi Üzerine Bir El Yazması'nda geliştirilen kriptanaliz ve frekans analizi algoritmaları
• C. 1025 - İbnü'l-Heysem (Alhazen), dördüncü kuvvetlerin toplamı için formül türeten ilk matematikçiydi ve sırayla, temel olan herhangi bir integral kuvvetin toplamı için genel formülü belirlemek için bir algoritma geliştirdi. integral hesabın geliştirilmesine
• C. 1400 - Ahmed el-Qalqashandi bir listesini verir şifrelere onun içinde Subh el-a'sha ikisini de içerir ikame ve transpozisyon , ilk kez, her biri için birden ikameler ile bir şifre düz metin harf; ayrıca tek kelimede bir arada bulunamayan harf frekansları ve harf kümelerinin kullanımı da dahil olmak üzere kriptanaliz üzerine bir açıklama ve çalışılmış bir örnek verir .

1940'tan önce

• 1540 - Lodovico Ferrari , bir kuartik polinomun köklerini bulmak için bir yöntem keşfetti
• 1545 - Gerolamo Cardano, Cardano'nun kübik polinomun köklerini bulma yöntemini yayınladı
• 1614 – John Napier , logaritma kullanarak hesaplamalar yapmak için bir yöntem geliştirdi
• 1671 – Isaac Newton tarafından geliştirilen Newton–Raphson yöntemi
• 1690 – Newton–Raphson yöntemi bağımsız olarak Joseph Raphson tarafından geliştirildi
• 1706 – John Machin , π için hızla yakınsak bir ters tanjant serisi geliştirdi ve π ila 100 ondalık basamak hesapladı
• 1789 – Jurij Vega , Machin'in formülünü geliştirir ve π'yi 140 ondalık basamağa kadar hesaplar,
• 1805 – Carl Friedrich Gauss tarafından bilinen FFT benzeri algoritma
• 1842 - Ada Lovelace bir bilgi işlem motoru için ilk algoritmayı yazdı
• 1903 - Carle David Tolmé Runge tarafından sunulan hızlı bir Fourier dönüşüm algoritması
• 1926 – Borůvka'nın algoritması
• 1926 – Grete Hermann tarafından sunulan birincil ayrıştırma algoritması
• 1927 – Hartree-Fock yöntemi , durağan bir durumda kuantum çok cisim sistemini simüle etmek için geliştirildi.
• 1934 - Boris Delaunay tarafından geliştirilen Delaunay üçgenlemesi
• 1936 - makineyi Turing , bir soyut makineyi tarafından geliştirilen Alan Turing ile, diğerlerinin modern kavramını geliştirdi algoritma .

1940'lar

• 1942 – GC Danielson ve Cornelius Lanczos tarafından geliştirilen hızlı bir Fourier dönüşüm algoritması
• 1945 – John von Neumann tarafından geliştirilen birleştirme sıralama
• 1947 – George Dantzig tarafından geliştirilen Simplex algoritması

1950'ler

• 1952 – David A. Huffman tarafından geliştirilen Huffman kodlaması
• 1953 – Nicholas Metropolis tarafından tanıtılan benzetilmiş tavlama
• 1954 – Harold H. Seward tarafından geliştirilen Radix sıralama bilgisayar algoritması
• 1964 - George Edward Pelham Box ve Mervin Edgar Muller tarafından yayınlanan normal dağıtılmış sayıların hızlı üretimi için Box-Muller dönüşümü . 1934 yılında Raymond EAC Paley ve Norbert Wiener tarafından bağımsız olarak önceden keşfedilmiştir .
• 1956 – Joseph Kruskal tarafından geliştirilen Kruskal algoritması
• 1956 – R. Ford Jr. ve DR Fulkerson tarafından geliştirilen ve yayınlanan Ford-Fulkerson algoritması
• 1957 – Robert Prim tarafından geliştirilen Prim'in algoritması
• 1957 – Richard E. Bellman ve LR Ford, Jr. tarafından geliştirilen Bellman–Ford algoritması.
• 1959 – Edsger Dijkstra tarafından geliştirilen Dijkstra algoritması
• 1959 – Donald L. Shell tarafından geliştirilen Shell sort
• 1959 – Paul de Casteljau tarafından geliştirilen De Casteljau'nun algoritması
• 1959 – John GF Francis ve Vera Kublanovskaya tarafından bağımsız olarak geliştirilen QR çarpanlara ayırma algoritması
• 1959 - Rabin-Scott Powerset inşaat dönüştürmek için NFA içine DFA tarafından yayınlanan Michael O. Rabin ve Dana Scott

1960'lar

• 1960 – Karatsuba çarpması
• 1961 – W. Wesley Peterson tarafından icat edilen CRC (döngüsel artıklık kontrolü)
• 1962 – AVL ağaçları
• 1962 – CAR Hoare tarafından geliştirilen Quicksort
• 1962 – Jack E. Bresenham tarafından geliştirilen Bresenham'ın çizgi algoritması
• 1962 - David Gale ve Lloyd Shapley tarafından geliştirilen Gale-Shapley 'kararlı evlilik' algoritması
• 1964 – JWJ Williams tarafından geliştirilen Heapsort
• 1964 – ilk olarak RP Fedorenko tarafından önerilen çoklu şebeke yöntemleri
• 1965 – Cooley–Tukey algoritması James Cooley ve John Tukey tarafından yeniden keşfedildi
• 1965 - Vladimir Levenshtein tarafından geliştirilen Levenshtein mesafesi
• 1965 – Tadao Kasami tarafından bağımsız olarak geliştirilen Cocke–Younger–Kasami (CYK) algoritması
• 1965 - Bruno Buchberger tarafından geliştirilen Gröbner bazlarını hesaplamak için Buchberger'in algoritması
• 1965 – Donald Knuth tarafından icat edilen LR ayrıştırıcıları
• 1966 – Negatif kenarlı bir grafikte en kısa yol için Dantzig algoritması
• 1967 – Andrew Viterbi tarafından önerilen Viterbi algoritması
• 1967 – Daniel H. Younger tarafından bağımsız olarak geliştirilen Cocke–Younger–Kasami (CYK) algoritması
• 1968 – Peter Hart , Nils Nilsson ve Bertram Raphael tarafından tanımlanan A* grafik arama algoritması
• 1968 – Robert Henry Risch tarafından geliştirilen belirsiz entegrasyon için Risch algoritması
• 1969 – Volker Strassen tarafından geliştirilen matris çarpımı için Strassen algoritması

1970'ler

• 1970 – Yefim (Chaim) A. Dinitz tarafından bir akış ağındaki maksimum akışı hesaplamak için Dinic'in algoritması
• 1970 – Donald Knuth ve Peter B. Bendix tarafından geliştirilen Knuth–Bendix tamamlama algoritması
• - 1970 BFGS yöntemi ve yarı-Newton sınıfı
• 1970 - Saul B. Needleman ve Christian D. Wunsch tarafından yayınlanan Needleman-Wunsch algoritması
• 1972 - Jack Edmonds ve Richard Karp tarafından yayınlanan Edmonds-Karp algoritması , esasen 1970'den itibaren Dinic'in algoritmasıyla aynı
• 1972 – Ronald Graham tarafından geliştirilen Graham taraması
• 1972 – Kırmızı-siyah ağaçlar ve B ağaçları keşfedildi
• 1973 – Clifford Cocks tarafından RSA şifreleme algoritması keşfedildi
• 1973 - RA Jarvis tarafından geliştirilen Jarvis yürüyüş algoritması
• 1973 – John Hopcroft ve Richard Karp tarafından geliştirilen Hopcroft–Karp algoritması
• 1974 – John Pollard tarafından geliştirilen Pollard'ın p  − 1 algoritması
• 1974 – Raphael Finkel ve JL Bentley tarafından geliştirilen Quadtree
• 1975 – John Holland tarafından popüler hale getirilen genetik algoritmalar
• 1975 – John Pollard tarafından geliştirilen Pollard'ın rho algoritması
• 1975 – Alfred V. Aho ve Margaret J. Corasick tarafından geliştirilen Aho–Corasick dizi eşleştirme algoritması
• 1975 – George E. Collins tarafından geliştirilen silindirik cebirsel ayrıştırma
• 1976 – Eugene Salamin ve Richard Brent tarafından bağımsız olarak keşfedilen Salamin-Brent algoritması
• 1976 – Donald Knuth ve Vaughan Pratt tarafından ve bağımsız olarak JH Morris tarafından geliştirilen Knuth–Morris–Pratt algoritması
• 1977 - Boyer-Moore dizi arama algoritması , bir dizinin oluşumunu başka bir dizide aramak için.
• 1977 – RSA şifreleme algoritması Ron Rivest , Adi Shamir ve Len Adleman tarafından yeniden keşfedildi.
• 1977 – Abraham Lempel ve Jacob Ziv tarafından geliştirilen LZ77 algoritması
• 1977 - multigrid yöntemler tarafından bağımsız olarak geliştirilen Achi Brandt ve Wolfgang Hackbusch
• 1978 - LZ78 algoritma geliştirilmiş LZ77 tarafından Abraham Lempel ve Jacob Ziv
• 1978 – Georg Bruun tarafından iki kişilik güçler için önerilen Bruun algoritması
• 1979 - Khachiyan'ın elipsoid yöntemi Leonid Khachiyan tarafından geliştirildi
• 1979 – Ross Quinlan tarafından geliştirilen ID3 karar ağacı algoritması

1980'ler

• 1980 – Döngü tespiti için Brent Algoritması Richard P. Brendt
• 1981 – Carl Pomerance tarafından geliştirilen ikinci dereceden elek
• 1981 – Temple F. Smith ve Michael S. Waterman tarafından geliştirilen Smith–Waterman algoritması
• 1983 – Simüle edilmiş tavlama S. Kirkpatrick , CD Gelatt ve MP Vecchi tarafından geliştirildi
• 1983 - Sınıflandırma ve regresyon ağacı tarafından geliştirilen (CART) algoritması Leo Breiman , vd.
• 1984 – Terry Welch tarafından LZ78'den geliştirilen LZW algoritması
• 1984 - Karmarkar'ın Narendra Karmarkar tarafından geliştirilen iç nokta algoritması
• 1984 - ACORN_PRNG , Roy Wikramaratna tarafından keşfedildi ve özel olarak kullanıldı
• 1985 – V. Cerny tarafından bağımsız olarak geliştirilen benzetilmiş tavlama
• 1985 - Roberto Car ve Michele Parrinello tarafından geliştirilen Car–Parrinello moleküler dinamiği
• 1985 - Sleator ve Tarjan tarafından keşfedilen yaylı ağaçlar
• 1986 – Blum Blum Shub , L. Blum , M. Blum ve M. Shub tarafından önerildi
• 1986 – Andrew Goldberg ve Robert Tarjan tarafından yeniden etiketlenen maksimum akış algoritmasını itin
• 1986 - Josh Barnes ve Piet Hut tarafından n-cisim problemlerinin hızlı yaklaşık simülasyonu için geliştirilen Barnes–Hut ağaç yöntemi
• 1987 – Leslie Greengard ve Vladimir Rokhlin tarafından geliştirilen hızlı çok kutuplu yöntem
• 1988 – John Pollard tarafından geliştirilen özel sayı alan eleği
• 1989 - ACORN_PRNG , Roy Wikramaratna tarafından yayınlandı
• 1989 – Leslie Lamport tarafından geliştirilen Paxos protokolü

1990'lar

• 1990 – Carl Pomerance , Joe Buhler , Hendrik Lenstra ve Leonard Adleman tarafından SNFS'den geliştirilen genel sayı alan eleği
• 1990 – Don Coppersmith ve Shmuel Winograd tarafından geliştirilen Coppersmith-Winograd algoritması
• 1990 - BLAST algoritması tarafından geliştirilen Stephen Altschul , Warren Gish , Webb Miller , Eugene Myers ve David J. Lipman gelen Ulusal Sağlık Enstitüleri
• 1991 – Maurice Herlihy tarafından geliştirilen beklemesiz senkronizasyon
• 1992 – D. Deutsch ve Richard Jozsa tarafından önerilen Deutsch–Jozsa algoritması
• 1992 – ID3 karar ağacı algoritmasının soyundan gelen C4.5 algoritması Ross Quinlan tarafından geliştirildi.
• 1993 – Rakesh Agrawal ve Ramakrishnan Srikant tarafından geliştirilen Apriori algoritması
• 1993 - Karger'ın bağlı bir grafiğin minimum kesimini hesaplamak için algoritması David Karger tarafından
• 1994 - Peter Shor tarafından geliştirilen Shor'un algoritması
• 1994 - Michael Burrows ve David Wheeler tarafından geliştirilen Burrows-Wheeler dönüşümü
• 1994 – Leo Breiman tarafından geliştirilen Bootstrap toplama (torbalama)
• 1995 - AdaBoost algoritması, ilk pratik artırma algoritması tarafından tanıtıldı Yoav Freund ve Robert Schapire
• 1995 – Yumuşak marjlı destek vektör makinesi algoritması Vladimir Vapnik ve Corinna Cortes tarafından yayınlandı . Boser, Nguyon, Vapnik'in 1992 algoritmasına yumuşak marjlı bir fikir ekler ve insanların SVM derken genellikle başvurduğu algoritmadır.
• 1995 – Ukkonen'in sonek ağaçlarının inşası için algoritması
• 1996 – Bruun'un algoritması , H. Murakami tarafından rastgele bile kompozit boyutlara genelleştirildi
• 1996 – Lov K. Grover tarafından geliştirilen Grover algoritması
• 1996 – RIPEMD-160 , Hans Dobbertin , Antoon Bosselaers ve Bart Preneel tarafından geliştirildi
• 1997 - Mersenne Twister , Makoto Matsumoto ve Tajuki Nishimura tarafından geliştirilen bir sözde rastgele sayı üreteci
• 1998 – Larry Page tarafından PageRank algoritması yayınlandı
• 1998 – Andrew Tridgell tarafından geliştirilen rsync algoritması
• 1999 – Jerome H. Friedman tarafından geliştirilen gradyan artırma algoritması
• 1999 – Bruce Schneier , John Kelsey ve Niels Ferguson tarafından tasarlanan Civanperçemi algoritması

2000'ler

• 2000 – Köprü kaynaklı konu araması , Jon Kleinberg tarafından geliştirilen bir köprü analiz algoritması
• 2001 – Igor Pavlov tarafından geliştirilen sıkıştırma için Lempel–Ziv–Markov zincir algoritması
• 2001 – Gerçek zamanlı yüz algılama için Viola–Jones algoritması Paul Viola ve Michael Jones tarafından geliştirildi.
• 2001 – DHT (Dağıtılmış hash tablosu) , akademi ve uygulama sistemlerinden birden fazla kişi tarafından icat edildi.
• 2001 – BitTorrent ilk tamamen merkezi olmayan eşler arası dosya dağıtım sistemi yayınlandı
• 2002 – Manindra Agrawal , Neeraj Kayal ve Nitin Saxena tarafından geliştirilen AKS asallık testi
• 2002 – Karmaşık sistemlerdeki toplulukları tespit etmek için Girvan–Newman algoritması
• 2002 – Bryan Ford tarafından geliştirilen doğrusal zaman ayrıştırmada PEG'yi (Ayrıştırma ifadesi dilbilgisi) ayrıştıran bir ayrıştırıcı oluşturmak için geliştirilen Packrat ayrıştırıcı
• 2009 – Bitcoin ilk güvene dayalı olmayan merkezi olmayan kripto para birimi sistemi yayınlandı

2010'lar

• 2013 - Diego Ongaro ve John Ousterhout tarafından yayınlanan Raft konsensüs protokolü
• 2015 – YOLO (“Yalnızca Bir Kez Bakarsınız ”), ilk kez Joseph Redmon ve diğerleri tarafından tanımlanan, etkili bir gerçek zamanlı nesne tanıma algoritmasıdır .

Referanslar