IEEE Computer Society ve American Institute of Physics kurumlarının ortak ürünü olan “Computer in Science & Engineering” dergisinin 2000 yılındaki bir basımında 20. yüzyılın en iyi algoritmalarına dikkat çekilmiş. Jack Dongarra ve Francis Sullivan adlarında iki bilim adamı, derginin o sayısında konuk editörler olarak “top 10 algorithms of 20th century” başlığı altında 10 adet algoritma belirlemişler. En iyi listesine girebilmek için alınan kıstas ise bilgisayar ve programlama dünyasına olan etkinin büyüklüğü ve uygulanabilirliği olmuş.
Bunun yanında Sullivan ve Dongarra seçtikleri algoritmaların en iyi 10 arasına girilebilirliğinin, tartışılabilir olduğunu kabul etmişler. Zaten konu “en iyi” kavramına geldiğinde tam anlamıyla en iyi algoritmanın olmadığı ve var olamayacağı düşünülürken bu, bence isabetli bir açıklama olmuş.
Tabii ki 2000 yılında yapılmış bir listenin 9 yıl içinde değişmemesi -hele ki teknolojinin ve bilimin hızına yetişemediğimiz şu zamanlarda- pek de akla uymuyor ama her şey bir yana yine de şu an kullanılan bir çok ileri seviyeli matematiksel ve programlamaya yönelik sistemin temelini oluşturan bu algoritmaları bu ay yazımda paylaşmak istedim.
MONTE-CARLO METODU (1946)
Los Alamos Bilimsel Laboratuvar’ından John Von Neumann, Stan Ulam ve Nick Metropolis adlarında üç bilim adamı tarafından ortaya çıkarılmıştır. Metropolis algoritması olarak da bilinir. Algoritma, kesin çözüm yapmanın zor olduğu problemlerde tahmini çözümlere gitmeyi amaçlar. Yani olasılık teorisi üzerine kurulmuştur. Daha somut ifade etmek gerekirse, çözülmesi gereken olayı, durumu ya da problemi rastgele sayılarla simülasyon haline getirip çözer. Çeşitli fizik ve matematik problemlerinde ve nükleer transform hesaplamalarında iyi sonuçlar sağlamaktadır.
 |
| G Dantzig |
SİMPLEKS METODU (1947)
RAND şirketinden George Dantzig’ in yarattığı simpleks metodu, çok yaygın kullanımından dolayı algoritma dünyasının en başarılılarından biri olarak kabul edilir. Algoritmada ilk adım, sorunla ilgili matematiksel bir model kurmaktır. Daha sonra ise iterasyon yoluyla optimum çözüme ulaşılır. Teoride şüphe uyandırsa da, pratikte yüksek bir verimle çalıştığını ispatlayan metod, lineer programlamada önemli bir yer tutmaktadır.
KRYLOV ALTUZAY İTERASYON METODLARI (1950)
Sayısal Analiz Enstitüsü’nden Magnus Hestenes, Eduard Steifel ve Cornelius Lanczos bu metodları geliştirmeye başlamışlardır. Metodlar en genel ifadeyle, matris vektör çarpımlarını ve Ax=b eşitliklerini Krylov alt uzaylarında çözmeyi amaçlar. Son 50 yıl boyunca çeşitli bilim adamları ve araştırmacılar tarafından yapılan eklemelerle ise daha da gelişmişlerdir. Örneğin Lanczos, -matris simetrik iken- bir alt uzay için ortogonal bir basis meydana getiren daha ‘şık’ bir yol keşfetmiştir. Aynı şekilde Steifel ve Hestenes ise pozitif tanımlı ve simetrik sistemler için daha iyi bir yöntem olan “conjugate gradient” (Gradyent bağımlı optimizasyon tekniklerinden biri) metodunu önermişlerdir.
MATRİS HESAPLARI İÇİN ANALİZSEL YAKLAŞIM (1951)
Oak Ridge Ulusal Laboratuvarı’ndan Alston Householder tarafından biçimlendirilmiştir. Analizsel yaklaşımla, ortogonal, diagonal ve diğer özel matrisler arasında çarpım-dönüşüm yapmak inanılmaz derecede kolaylaşmıştır. Yaklaşım aynı zamanda yazılım uzmanlarının esnek ve verimli matris denklikleri geliştirmesine de olanak vermiştir. Ayrıca lineer cebirdeki büyük uğraşlardan biri olan hata analizini de kolaylaştırmıştır.
FORTRAN -OPTİMİZE EDİCİ- DERLEYİCİ (1957)
Bu derleyici IBM grubu ve grubun lideri John Backus tarafından geliştirilmiştir. Fortran’ ın yaradılışı bilgisayar programlama tarihindeki en önemli olay olarak -her ne kadar tartışılsa da- derecelendirilebilir. Çünkü, Fortran diğer programlama dillerinden farklı olarak çevirici yerine derleyici kullanıyordu. Yüksek düzeydeki dille yazılan program daha sonra makine diline çevriliyordu ve böylece hız kaybı engellenmiş oluyordu. Bu sayede Fortran, 50li yıllarda çok geniş kitlelere ulaşabilmiştir.
QR ALGORİTMASI (1959-61)
Öz değerleri hesaplamak için bulunan sabit bir metottur. Öz değerler bir matristeki en önemli nümerik ifadelerden biridir ve öz değer hesabı çoğunlukla karmaşıktır. QR algoritmasında öncelikle çözülecek olan matris üst üçgen duruma getirilir ve bu sayede en aşağıdan itibaren çözümü kolay bir hale gelmiş olur.
1960’ ların ortalarından beri QR algoritması korkunç öz değer problemlerini rutin hesaplamalara dönüştürmektedir.
 |
| T.Hoare |
QUICKSORT SIRALAMA ALGORİTMASI (1962)
Elliott Brothers şirketinden Tony Hoare tarafından geliştirilmiştir. Algoritmada önce bir pivot (eksen) eleman seçilir. Geri kalan elementler pivotla karşılaştırılarak, büyük ve küçük olmak üzere iki gruba ayrılırlar. Oluşan gruplar üzerinde bu işlem, içinde sayı olmayan bir diziye ulaşana kadar tekrarlanır. Algoritmanın sadeliği ise Quicksort algoritmasını, hesaplama karmaşıklığının gözdesi haline getirmektedir.
FOURIER DÖNÜŞÜMÜ (1965)
IBM T.J. Watson araştırma merkezinden James Cooley, Princeton Üniversitesi’ nden John Tukey ve AT&T BELL laboratuarlarının ortak ürünüdür. Temelde fonksiyonları başka fonksiyonlara dönüştürmek vardır. Quicksort gibi bölme stratejisine dayanır. İntegrali alınabilen her türlü fonksiyonu sinüs ve kosinüs fonksiyonlarının toplamı şeklinde yazar. Her türlü verinin işlenmesinde kullanılır.
INTEGER RELATION DETECTION (1977)
Brigham Young Üniversitesi’nden Helaman Ferguson ve Rodney Forcade ürünüdür.
Klasik bir soru verilir: x1,x2…xN şeklinde verilen reel sayılar grubu olsun, ve a1,a2…aN grubu -hepsi sıfır olmayacak şekilde- tamsayı olmak üzere, a1x1 + a2x2 +…aNxN = 0 eşitliği yazılabilir mi?
N=2 için çözüme, öklid algoritması yeterlidir fakat yeterli olmadığı zamanlarda Ferguson ve Forcade’ in genelledikleri yargı, kullanması ve anlaması daha komplike olsa da daha güçlü bir çözüm sunmaktadır.
HIZLI ÇOK-KUTUP ALGORİTMASI (1987)
Yale Üniversitesi’nden Vladimir Rokhlin ve Leslie Greengard tarafından bulunmuştur. Algoritma benzerlerinin aksine cisim-küme etkileşimi değil küme-küme etkileşimi yapar. Bunu yaparken de Taylor serisinin açılımıyla potansiyelleri hesaplayarak işlem zamanını
O(N) adıma indirmiştir. Algoritmanın farklılıklarından biride –birçok algoritmanın eksiği olan- kesin hata tahminleriyle donatılmış olmasıdır.
Kaynaklar :
