20. yüzyılın en büyük 10 algoritması olan Fourier dönüşümü 8. sırada
İlk on algoritmayı icat eden algoritma ustalarından bazıları
1. 1946 Monte Carlo yöntemi
1946'da, Amerika Birleşik Devletleri'ndeki Las Amos Ulusal Laboratuvarı'ndan üç bilim adamı John von Neumann, StanUlam ve Nick Metropolis, Monte Carlo yöntemi olarak adlandırılan bu yöntemi birlikte icat ettiler.
Spesifik tanımı şudur: kareye kenar uzunluğu bir metre olan bir kare çizin ve karenin içine rastgele tebeşirle düzensiz bir şekil çizin Şimdi bu düzensiz şeklin alanını hesaplamak istiyoruz, sütun nasıl hesaplanır?
Monte Carlo yöntemi bize N (N büyük bir doğal sayıdır) soya fasulyesini kareye eşit şekilde serpiştirdiğimizi ve ardından düzensiz geometrik şeklin içinde kaç soya fasulyesinin olduğunu saydığını söyler, örneğin, M Yani, bu garip şeklin alanı M / N'ye yaklaştırılır. N ne kadar büyükse, hesaplanan değer o kadar doğru olur.
Burada çekirdeklerin hepsinin aynı düzlemde olduğunu ve aralarında hiçbir örtüşme olmadığını varsayacağız. (Sarı fasulyeleri yaymak sadece bir metafordur.) Monte Carlo yöntemi Pi'yi yaklaştırmak için kullanılabilir: İki gerçek sayının birim çember içinde olup olmadığını görmek için bilgisayarın her seferinde 0 ile 1 arasında rastgele iki sayı oluşturmasına izin verin. Bir dizi rastgele nokta oluşturun, birim çemberdeki nokta sayısını ve toplam nokta sayısını sayın, yazılı dairenin alanının karenin alanına oranı PI: 4'tür ve PI pi'dir. Daha fazla rastgele puan alınır (ancak rastgele noktalar 10 üzeri 9. kuvvetine alındığında bile, sonuç sadece ilk 4 basamaktaki pi ile tutarlıdır), sonuç pi'ye daha yakındır.
2. 1947 simpleks yöntemi
1947'de RAND şirketi Groge Dantzig, simpleks yöntemini icat etti.
Simpleks yöntemi o zamandan beri doğrusal programlama disiplininin önemli bir köşe taşı haline geldi.
Sözde doğrusal programlama, basitçe söylemek gerekirse, bir dizi doğrusal (tüm değişkenler ilk güçtür) kısıtlamalar vermektir (örneğin, a1 * x1 + b1 * x2 + c1 * x3 > 0), belirli bir amaç fonksiyonunun uç değerini bulun.
Görünüşe göre eş çok soyut, ancak bir şirketin gerçekte işe yaraması alışılmadık bir durum değil - örneğin, bir şirket için üretime sokulabilecek insan gücü ve malzeme kaynakları sınırlıdır ("doğrusal kısıtlamalar") ve şirketin hedefleri Bu kar maksimizasyonudur ("amaç fonksiyonu maksimum değeri alır") Bakın, doğrusal programlama soyut değildir!
Yöneylem araştırmasının bir parçası olarak doğrusal programlama, yönetim bilimi alanında önemli bir araç haline gelmiştir. Dantzig tarafından önerilen simpleks yöntemi, benzer doğrusal programlama problemlerini çözmek için son derece etkili bir yöntemdir.
3. 1950 Krylov alt uzay yineleme yöntemi
1950: Cornelius'tan Magnus Hestenes, Edward Stiefer ve Lanczos, Ulusal Standartlar Bürosu Sayısal Analiz Enstitüsü Krylov alt uzay yineleme yöntemini icat etti.
Krylov alt uzay yineleme yöntemi, Ax = b formundaki denklemleri çözmek için kullanılır. A, bir n * n matristir. N yeterince büyük olduğunda, doğrudan hesaplama çok zorlaşır. Krylov yöntemi, onu akıllıca Kxi'ye dönüştürür. + 1 = Kxi + b-Axi iteratif form çözülecek.
Burada K (yazar Rus Nikolai Krylov'un soyadının ilk harfinden), A'ya yakın inşa edilmiş bir matristir ve yinelemeli algoritmanın güzelliği, karmaşık problemleri hesaplanması kolay aşamalara indirgemesidir. Alt adımlar.
4. 1951 matris hesaplamasının ayrıştırma yöntemi
1951'de, Alstom Oak Ridge Ulusal Laboratuvarı'ndan Alston Householder, matris hesaplaması için bir ayrıştırma yöntemi önerdi. Bu algoritma, herhangi bir matrisin üçgen, köşegen, ortogonal ve diğer özel matris formlarına ayrıştırılabileceğini kanıtlamaktadır.Bu algoritmanın önemi, esnek bir matris hesaplama yazılım paketi geliştirmeyi mümkün kılmaktadır.
5. 1957 optimize edilmiş Fortran derleyicisi
1957: John Backus liderliğindeki IBM ekibi, Fortran optimizasyon derleyicisini yarattı. Fortran, aynı zamanda evangelizm olarak da çevrilir, "formül çevirisi" anlamına gelen Formül Çevirisi iki kelimenin birleşimidir. Resmi olarak benimsenen ve bugüne kadar kullanılan dünyanın ilk üst düzey programlama dilidir. Bu dil şimdi Fortran 2008'e geliştirildi ve iyi biliniyor.
6. 1959-61 matris özdeğerlerini hesaplamak için QR algoritması
1959-61: J.G.F. Francis of London Ferranti Ltd., ünlü QR algoritması olan kararlı bir özdeğer hesaplama yöntemi buldu. Bu aynı zamanda doğrusal cebir ile ilgili bir algoritmadır.Doğrusal cebirle ilgili çalışmış olanlar "bir matrisin özdeğerlerini" hatırlamalıdır. Özdeğerlerin hesaplanması, matris hesaplamalarının temel içeriğinden biridir.Geleneksel çözüm, yüksek mertebeden denklemlerin köklerini bulmayı içerir. Sorun büyük olduğunda çok zordur.
QR algoritması matrisi ortogonal bir matrise (umarım ortogonal matrisin ne olduğunu bileceksiniz.: D.) ve daha önce bahsedilen Krylov yöntemine benzer bir üst üçgen matrise ayrıştırır, bu başka bir Karmaşık yüksek mertebeden denklemlerin köklerini bulma sorununu aşamalı ve hesaplaması kolay alt adımlara indirgeyen yinelemeli algoritma, büyük ölçekli matris özdeğerlerinin bilgisayarla çözülmesini mümkün kılar. Bu algoritmanın yazarı İngiltere, Londra'dan J.G.F. Francis'dir.
7, 1962 Quicksort algoritması
1962: Londra Tony Elliott Brothers Ltd., Hall hızlı sıralama önerdi. Haha, tebrikler, nihayet ilk tanıdıklarınız olabilecek algoritmayı gördüm ~.
Hızlı sıralama algoritması, algoritmalarda sıralama için klasik bir algoritmadır ve uygulama gölgesi her yerde görülebilir. Hızlı sıralama algoritması ilk olarak Sir Tony Hoare tarafından tasarlandı. Temel fikri, sıralanacak diziyi ikiye bölmektir.Sol yarı her zaman "küçük" ve sağ yarı her zaman "büyük" Bu süreç yinelemeli olarak devam eder. Tüm sıra sırasına gelene kadar devam edin.
Sir Tony Hoare'den bahsetmişken, hızlı sıralama algoritması aslında kazara yaptığı küçük bir keşif. Bilgisayarlara yaptığı katkılar esas olarak biçimsel yöntemler teorisi ve ALGOL60 programlama dilinin icadıdır. Ayrıca bu başarılar için 1980 çizelgesini de aldı. Ruh ödülü. Hızlı sıralamanın ortalama zaman karmaşıklığı yalnızca O (Nlog (N)) olup, sıradan seçici sıralama ve balonlu sıralama ile karşılaştırıldığında tarihi bir yeniliktir.
8.1965 Hızlı Fourier Dönüşümü
1965: IBM Watson Araştırma Enstitüsü'nden James Cooley, Princeton Üniversitesi'nden John Tukey, AT&T Bell Labs ortaklaşa Hızlı Fourier Dönüşümünü başlattı. Hızlı Fourier algoritması, ayrık Fourier algoritmasının hızlı bir algoritmasıdır (bu, dijital sinyal işlemenin temel taşıdır) ve zaman karmaşıklığı yalnızca O (Nlog (N)); zaman verimliliğinden daha önemli, hızlı Fourier algoritması çok kolaydır Donanımla gerçekleştirildiğinden elektronik teknolojisi alanında yaygın olarak kullanılmaktadır. İleride klasik algoritma araştırma serimde bu algoritmaya odaklanacağım.
9.1977 Tamsayı ilişki algılama algoritması
1977: Helaman Ferguson ve Birmingham Üniversitesi'nden Rodney Forcade, Forcade algılama algoritmasının tam sayı ilişkisini önerdi.
Tam sayı ilişkilerinin tespiti eski bir problemdir ve geçmişi Öklid zamanına kadar izlenebilir. Spesifik olarak: X1, X2, ..., Xn gerçek sayıları verildiğinde, hepsi sıfır olmayan a1, a2, ... an tam sayıları olsun, öyle ki: a1 x 1 + a2 x2 + ... + An xn = 0?
Bu yıl Brigham Young Üniversitesi'nden Helaman Ferguson ve Rodney Forcade bu sorunu çözdü. Bu algoritma, "kuantum alan teorisinde Feynman diyagramlarının hesaplanmasını basitleştirmek" için uygulanır. Tamam, anlamanı gerektirmiyor, sadece anla.
10.1987 Hızlı çok kutuplu algoritma
1987: Yale Üniversitesi'nden Greengard ve Rokhlin, hızlı çok kutuplu bir algoritma icat etti. Bu hızlı çok kutuplu algoritma, "Samanyolu galaksisindeki yıldızlar veya proteinlerdeki atomlar arasındaki etkileşimler gibi yerçekimi veya elektrostatik kuvvetlerle etkileşime giren N parçacığın hareketinin tam olarak hesaplanmasını" hesaplamak için kullanılır.
Çevreye katılmaya hoş geldiniz:
(Daire kartı buraya eklendi, lütfen görüntülemek için Toutiao istemcisine gidin)
