İleri Algoritmalarda Önemli İsimler
Dersin dokuz bölümündeki algoritmaların ve fikirlerin arkasındaki 43 isim: Karatsuba çarpımından ve Huffman kodlamadan Bellman'ın dinamik programlamasına, Cook'un NP-tamlık teoremine, dal sınır yöntemine, rekabetçi analize ve paralel hesaplamaya kadar.
Her kartta kişinin yaşadığı yıllar, ülkesi ve kurumu, en bilinen katkısı ve kısa bir özet yer alır; bağlantılar bu katkının işlendiği slaytlara gider. Kartlar bölüme göre süzülebilir, aranabilir, katkı yılına ya da soyadına göre sıralanabilir.
Leonardo Fibonacci
Liber Abaci · 1202
Liber Abaci (1202) ile Hint-Arap rakamlarını Avrupa'ya tanıttı; kitaptaki tavşan problemi 1, 1, 2, 3, 5, 8, … dizisini üretir. F(n) = F(n − 1) + F(n − 2) bağıntısını düz özyinelemeyle çözmek üstel zaman alır, çünkü aynı alt problemler yeniden ve yeniden hesaplanır. Bu örnek, dinamik programlamanın ve bellekleme (memoization) tekniğinin en bilinen başlangıç noktasıdır.
Pierre de Fermat
Fermat'nın küçük teoremi · 1640
1640'ta Frénicle de Bessy'ye yazdığı bir mektupta, bugün küçük teoremi diye bilinen sonucu bildirdi: n asal ve 1 < a < n ise aⁿ⁻¹ ≡ 1 (mod n) olur. Teoremin yayımlanan ilk kanıtını 1736'da Euler verdi. Fermat asallık testi bu eşitliği rastgele seçilen tabanlarla dener; eşitlik bozulursa sayı kesinlikle bileşiktir. Tersi ise her zaman doğru değildir: 561 = 3 · 11 · 17 gibi Carmichael sayıları, kendileriyle aralarında asal her tabanda eşitliği sağlar. Robert Carmichael 561'i 1910'da yayımladı. Miller–Rabin testi bu açığı karekök özelliğiyle kapatır.
Leonhard Euler
Königsberg köprüleri · 1736
1736'da Königsberg'in yedi köprüsünün her birinden tam bir kez geçen bir yürüyüş olmadığını kanıtladı; kara parçalarını düğüm, köprüleri kenar olarak ele alması çizge kuramının başlangıcı sayılır. Böyle bir yürüyüş için tek dereceli düğüm sayısının 0 ya da 2 olması gerektiğini gösterdi. Her kenarı bir kez kullanan Euler turu, Christofides algoritmasının da bir adımıdır.
Carl Friedrich Gauss
Aritmetik seri · 1 + 2 + … + n
Okul yıllarına ait bilinen bir öyküye göre 1'den 100'e kadar olan sayıları, iki uçtan terimleri eşleyerek bir anda topladı ve n(n + 1)/2 sonucuna ulaştı. Bu toplam, iç içe döngüler O(n²) olarak sayıldığında her seferinde karşımıza çıkar. İki karmaşık sayıyı dört yerine üç gerçel çarpmayla çarpma hilesi de ona atfedilir; Karatsuba yöntemi benzer bir fikri büyük sayılara uygular.
Alan Turing
Turing makinesi · 1936
1936 tarihli “On Computable Numbers” makalesinde algoritma kavramını Turing makinesiyle biçimselleştirdi ve durma problemini (halting problem) hiçbir algoritmanın çözemeyeceğini gösterdi. Alonzo Church'ün aynı yıl lambda hesabıyla elde ettiği sonuçla birlikte bu tanım, “etkin biçimde hesaplanabilir” kavramının anlamı olarak kabul edilir (Church–Turing tezi). P ve NP sınıfları da aynı modelin zamanla sınırlanmış bir biçimiyle tanımlanır.
Ronald A. Fisher ve Frank Yates
Fisher–Yates karıştırma · 1938
1938'de Statistical Tables for Biological, Agricultural and Medical Research adlı kitapta, bir listenin rastgele permütasyonunu rastgele sayı tablosu yardımıyla kâğıt kalemle üretmenin yolunu anlattılar. Richard Durstenfeld 1964'te yöntemi bilgisayara uyarlayarak O(n) süreli takas sürümünü verdi; bu sürümü Knuth yaygınlaştırdı. Fisher, deney tasarımının ve modern istatistiğin kurucularındandır.
John von Neumann
Birleştirme sıralaması · 1945
1945'te EDVAC için yazdığı programlarda birleştirme sıralamasını (merge sort) anlattı; Knuth bu programı bilgisayar için yazılmış ilk sıralama programları arasında sayar. Böl ve fethet (divide and conquer) yaklaşımının klasik örneği olan yöntem en kötü durumda bile O(n log n) sürede çalışır ve kararlıdır. Stanisław Ulam ile Monte Carlo yönteminin geliştirilmesine katkıda bulundu; bugünkü bilgisayar mimarisi de onun adını taşır.
Stanisław Ulam
Monte Carlo yöntemi · 1946–1949
1946'da Los Alamos'ta, bir solitaire oyununu kazanma olasılığını rastgele denemelerle kestirme fikrinden yola çıkarak Monte Carlo yöntemini önerdi; von Neumann ile birlikte yöntemi ENIAC üzerinde nötron yayınımı hesaplarına uyguladı. Yöntemin adını taşıyan ilk makale 1949'da Nicholas Metropolis ile yayımlandı. Rastgele noktalarla π sayısını kestirmek, derste kullanılan en yalın örnektir.
George B. Dantzig
Simpleks yöntemi · 1947
1947'de doğrusal programları çözmek için simpleks yöntemini geliştirdi; dal sınır algoritmalarında her düğümdeki sınır çoğunlukla böyle bir LP gevşetmesiyle (LP relaxation) hesaplanır. 1954'te Fulkerson ve Johnson ile birlikte 49 şehirlik bir gezgin satıcı problemini (travelling salesman problem, TSP) kesme düzlemleriyle en iyi biçimde çözdü. Öğrenciyken çözülmemiş iki istatistik problemini ödev sanıp çözdüğü öykü de ünlüdür.
Claude Shannon
Bilgi kuramı · 1948
1948 tarihli “A Mathematical Theory of Communication” makalesiyle bilgi kuramını kurdu ve entropiyi, kayıpsız sıkıştırmada simge başına ortalama bit sayısının alt sınırı olarak tanımladı. Bir Huffman kodunun ortalama uzunluğu entropiyi en çok 1 bit aşar. Boole cebirini anahtarlama devrelerine uyguladığı 1937 tarihli yüksek lisans tezi de sayısal devre tasarımının temellerindendir.
Derrick H. Lehmer
Lehmer üreteci (1949) · “backtrack” terimi
1949'da bugün Lehmer üreteci olarak anılan sözde rastgele sayı (pseudo-random number) yöntemini, yani çarpımsal doğrusal eşlik üretecini x(k+1) = a · x(k) mod m tanıttı. 1950'lerde kısmi bir çözümü genişleten ve çıkmaza girince geri adım atan arama için “backtrack” terimini kullandı; bu yaklaşım bugün geri izleme (backtracking) adıyla bilinir. Sayılar kuramında asallık testleri ve hesap makineleri üzerine de öncü çalışmalar yaptı.
David A. Huffman
Huffman kodlama · 1952
MIT'de lisansüstü öğrenciyken, Robert Fano'nun dersinde final sınavının yerine geçen dönem ödevi olarak en kısa önek kodunu bulma problemini çözdü ve sonucu 1952'de yayımladı. En az sıklıktaki iki düğümü tekrar tekrar birleştiren açgözlü yöntem, karakter başına beklenen bit sayısını en aza indirir ve hocasının Shannon–Fano yöntemini geride bırakır. Huffman kodlama (Huffman coding) bugün DEFLATE ve JPEG gibi biçimlerin bir aşamasıdır.
Richard Bellman
Dinamik programlama · 1950'ler
1950'lerde RAND Corporation'da çok aşamalı karar problemleri için “dinamik programlama” (dynamic programming) adını ve optimallik ilkesini ortaya koydu: optimal bir çözümün her parçası, kendi alt problemi için de optimaldir. 1958'de negatif kenar ağırlıklarına izin veren tek kaynaklı en kısa yol yöntemini yayımladı (Bellman-Ford). “Boyutluluk laneti” (curse of dimensionality) deyimi de ona aittir.
Gene Amdahl
Doğrusal yoklama (1954) · Amdahl yasası (1967)
1954'te Elaine McGraw ve Arthur Samuel ile birlikte IBM 701 için yazılan bir çeviricide, çakışma olunca bir sonraki boş hücreye geçen doğrusal yoklamayı (linear probing) kullandı. IBM System/360'ın baş mimarlarından biriydi. 1967'deki bir konferans konuşmasında, programın sıralı kısmının paralel hızlanmayı sınırladığını savundu; bu gözlem Amdahl yasası (Amdahl's law) olarak bilinir.
Michael O. Rabin
Miller–Rabin (1980) · Rabin-Karp (1987)
1959'da Dana Scott ile deterministik olmayan sonlu otomatları tanımladı; bu çalışma 1976 Turing Ödülü'nü getirdi. 1980'de Gary Miller'ın asallık testini (1976) koşulsuz bir olasılıksal teste dönüştürdü: Miller–Rabin testinde bileşik bir sayı bir turu en çok 1/4 olasılıkla geçer. Karp ile kayan hash (rolling hash) kullanan Rabin-Karp dizgi eşleştirme algoritmasını 1987'de yayımladı; rastgeleliği algoritma tasarımında bilinçli olarak kullanmanın öncülerindendir.
C. A. R. (Tony) Hoare
Hızlı sıralama · 1959–1961
Hızlı sıralamayı (quicksort) 1959–1960'ta Moskova Devlet Üniversitesi'nde konuk öğrenciyken tasarladı; algoritma 1961'de yayımlandı. Bir pivot çevresinde bölümleyip iki yanı özyinelemeyle sıralamak ortalamada O(n log n), kötü pivotlarla O(n²) sürer. Aynı yıl k. en küçük öğe için Find yöntemini (bugünkü QuickSelect) yayımladı; program doğruluğu için Hoare mantığını kurdu ve 1980'de Turing Ödülü'nü aldı.
Anatoly Karatsuba
Karatsuba çarpımı · 1960/1962
1960'ta Kolmogorov'un seminerinde iki n basamaklı sayıyı çarpmanın Ω(n²) işlem gerektirdiği sanısı tartışılırken, bir hafta içinde üç alt çarpımla O(n^1,585) sürede çalışan yöntemi buldu; o sırada 23 yaşındaydı. Kolmogorov sonucu 1962'de Karatsuba ve Ofman adlarıyla yayımlattı. Böl ve fethet yaklaşımının varsayılan bir alt sınırı aşabildiğini gösteren ilk örneklerden biridir.
Ailsa Land ve Alison Doig
Dal sınır · 1960
London School of Economics'te yazdıkları 1960 tarihli Econometrica makalesinde tam sayılı doğrusal programları çözmek için dal sınır (branch and bound) yöntemini önerdiler: çözüm uzayı dallara ayrılır ve her dal için LP gevşetmesiyle bir sınır hesaplanır. Sınırı bilinen en iyi çözümden kötü olan dallar budanır. Bu fikir bugünkü tam sayılı programlama çözücülerinin hâlâ çekirdeğindedir; Doig daha sonra Alison Harcourt adıyla University of Melbourne'de çalıştı.
Michael Held ve Richard M. Karp
Gezgin satıcı için dinamik programlama · 1962
1962 tarihli “A Dynamic Programming Approach to Sequencing Problems” makalesinde gezgin satıcı problemini dinamik programlamayla çözdüler. Durum bir küme ile bir düğümden oluşur: dp[S][i], başlangıçtan çıkıp S kümesindeki şehirlerin hepsine uğrayan ve i'de biten en kısa yoldur. Algoritma O(n² · 2ⁿ) sürede ve O(n · 2ⁿ) bellekle çalışır; n! turu tek tek denemekten çok hızlıdır ama yine üsteldir. Richard Bellman aynı yöntemi aynı yıl bağımsız olarak yayımladı.
John D. C. Little, Katta G. Murty, Dura W. Sweeney ve Caroline Karel
Gezgin satıcı için dal sınır · 1963
1963'te Operations Research dergisinde yayımladıkları “An Algorithm for the Traveling Salesman Problem” makalesinde gezgin satıcı problemi için bir dal sınır algoritması verdiler; “dal sınır” (branch and bound) adı ilk kez bu makalede geçer. Alt sınır indirgenmiş maliyet matrisiyle bulunur: her satırdan ve her sütundan en küçük öğe çıkarılır, çıkarılan değerlerin toplamı her turun maliyetine bir alt sınırdır. Yöntem simetri gerektirmez, d[i][j] ≠ d[j][i] olan asimetrik problemlerde de çalışır. Little, kuyruk kuramındaki Little yasasıyla (1961) da tanınır.
Jack Edmonds
Çiçek algoritması (1965) · Edmonds-Karp (1972)
1965 tarihli “Paths, Trees, and Flowers” makalesinde genel çizgelerde maksimum eşleştirmeyi polinom zamanda bulan çiçek (blossom) algoritmasını verdi ve “verimli algoritma” ifadesinin polinom zamanlı algoritma anlamına gelmesi gerektiğini savundu. 1972'de Karp ile, artış yolları BFS ile seçildiğinde Ford-Fulkerson yönteminin O(V·E²) sürede çalıştığını gösterdi. 1971'de açgözlü algoritmanın tam olarak matroidler üzerinde optimal olduğunu gösterdi.
Solomon W. Golomb
Backtrack Programming · 1965
Leonard Baumert ile yazdığı 1965 tarihli Journal of the ACM makalesi “Backtrack Programming”, geri izlemeyi genel bir arama yöntemi olarak sistemli biçimde anlatan ilk çalışmalardandır; budamanın (pruning) arama ağacını nasıl küçülttüğünü örneklerle gösterir. 1953'te poliominoları tanımlaması, bulmaca ve döşeme problemlerinin bilgisayarla aranmasına esin kaynağı oldu. Golomb kodlaması da onun katkısıdır.
Ronald Graham
Liste çizelgeleme (1966) · Graham taraması (1972)
1966'da her işi ilk boşalan makineye veren liste çizelgelemenin (list scheduling) en büyük yükünün (makespan) en iyi değerin en çok (2 − 1/m) katı olduğunu kanıtladı; bu, yaklaşım oranının (approximation ratio) ilk örneklerindendir. 1969'da işleri uzundan kısaya sıralayan LPT kuralının oranının 4/3 − 1/(3m) olduğunu gösterdi. 1972'de düzlemdeki noktaların dışbükey örtüsünü (convex hull) O(n log n) sürede bulan Graham taramasını yayımladı.
László Bélády
OPT (MIN) · Belady anomalisi
1966'da IBM'de, gelecekte en geç kullanılacak sayfayı çıkaran ve en az sayfa hatası veren çevrim dışı algoritmayı (MIN, bugün OPT) tanımladı; çevrim içi politikalar bu ideal ile karşılaştırılır. Nelson ve Shedler ile, FIFO kullanıldığında çerçeve sayısı artınca sayfa hatası sayısının da artabileceğini gösterdi (Belady anomalisi). 1961'de ABD'ye göç etmişti.
Michael J. Flynn
Flynn sınıflandırması · 1966
1966'da Proceedings of the IEEE'de yayımlanan “Very High-Speed Computing Systems” makalesinde bilgisayarları aynı anda işledikleri komut ve veri akışlarının sayısına göre dört sınıfa ayırdı: SISD (tek komut, tek veri), SIMD (tek komut, çok veri), MISD (çok komut, tek veri) ve MIMD (çok komut, çok veri). Klasik tek çekirdekli işlemci SISD, vektör birimleri SIMD, çok çekirdekli işlemciler ve kümeler MIMD sınıfındadır. Sınıflandırma paralel makineleri anlatmanın ortak dili oldu.
Andrew Viterbi
Viterbi algoritması · 1967
1967'de evrişimli kodları çözmek için her adımda her duruma ulaşan en iyi yolu saklayan bir dinamik programlama algoritması önerdi. Gizli Markov modellerinde en olası durum dizisini bulan bu yöntem mobil ve uydu iletişiminde, konuşma tanımada ve biyoinformatikte kullanılır. 1985'te Irwin Jacobs ile Qualcomm'u kurdu.
Volker Strassen
Strassen algoritması · 1969
1969 tarihli “Gaussian Elimination is not Optimal” makalesinde matrisleri dört bloğa ayırıp sekiz yerine yedi blok çarpımıyla çarptı ve O(n^2,81) süreli matris çarpımını elde etti; matrislerin n³'ten hızlı çarpılabildiğini gösteren ilk sonuç buydu. 1971'de Schönhage ile çok büyük tam sayıların hızlı çarpımını, 1977'de Solovay ile olasılıksal bir asallık testini geliştirdi.
Stephen Cook
Cook teoremi · 1971
1971 tarihli “The Complexity of Theorem-Proving Procedures” makalesinde NP'deki her problemin polinom zamanda SAT'a indirgendiğini, yani SAT'ın NP-tam (NP-complete) olduğunu gösterdi. Bu sonuç P = NP sorusunu biçimsel olarak ortaya koydu ve NP-tamlık kuramını başlattı. 1982'de Turing Ödülü'nü aldı.
Richard M. Karp
21 NP-tam problem · 1972
1972'de SAT'tan başlayarak klik, düğüm kapsama (vertex cover), Hamilton döngüsü ve sırt çantası gibi 21 problemin NP-tam olduğunu polinom zamanlı indirgemelerle (reduction) gösterdi ve NP-tamlığın ne kadar yaygın olduğunu ortaya koydu. Edmonds ile Edmonds-Karp algoritmasını (1972), Hopcroft ile iki parçalı eşleştirme algoritmasını (1973), Rabin ile Rabin-Karp dizgi eşleştirme algoritmasını (1987) geliştirdi. 1985'te Turing Ödülü'nü aldı.
Leonid Levin
Cook–Levin teoremi · 1973
SSCB'de, Cook'tan bağımsız olarak arama problemleri için “evrensel problemler” kavramını geliştirdi ve 1973'te yayımladı; teoremin Cook–Levin teoremi diye anılması bundandır. Bu problemler için neredeyse optimal bir “evrensel arama” algoritması da verdi. Daha sonra ABD'ye göç etti ve 1980'den beri Boston University'de çalışıyor.
Richard P. Brent
Brent teoremi · 1974
1974'te Journal of the ACM'de yayımladığı “The Parallel Evaluation of General Arithmetic Expressions” makalesinde, çok işlemci için yazılmış bir hesabın daha az işlemciyle ne kadar sürede yapılabileceğini sınırladı. İş–derinlik diliyle sonuç Tₚ ≤ W/p + D biçimindedir: W toplam iş, D derinlik, p işlemci sayısıdır. Tₚ ≥ W/p ve Tₚ ≥ D alt sınırlarıyla birlikte okunduğunda, p işlemcili süre en iyinin iki katını geçmez. Brent sayısal kök bulmadaki Brent yöntemiyle (1973) de tanınır.
Nicos Christofides
Christofides algoritması · 1976
1976'da üçgen eşitsizliğini sağlayan TSP (metrik TSP) için en iyi turun en çok 3/2 katı uzunlukta bir tur bulan algoritmayı verdi: bir MST kurulur, tek dereceli düğümler üzerine minimum mükemmel eşleştirme eklenir ve Euler turunda kısayollarla gezinilir. Bu oran 2020'ye kadar metrik TSP için bilinen en iyi garantiydi. Anatoliy Serdyukov aynı sonuca SSCB'de hemen hemen aynı zamanda ulaştı.
Joseph B. (Jay) Kadane
En büyük toplamlı alt dizi · 1977
Ulf Grenander'ın 1977'de görüntü analizi için ortaya koyduğu en büyük toplamlı alt dizi problemini Michael Shamos, Carnegie Mellon'daki bir seminerde anlattı. Seminerdeki istatistikçi Kadane, problemi tek taramada çözen O(n) süreli algoritmayı buldu: V(i) = max(a[i], V(i−1) + a[i]) değeri i'de biten en iyi alt dizinin toplamıdır, cevap bu değerlerin en büyüğüdür. Öykü ve algoritma Jon Bentley'in 1984'teki Programming Pearls yazısıyla yaygınlaştı. Kadane Bayesçi istatistik alanındaki çalışmalarıyla tanınır.
Michael Garey ve David S. Johnson
Computers and Intractability · 1979
Bell Labs'ta yazdıkları Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), yüzlerce NP-tam problemi listeleyen ve indirgeme tekniklerini öğreten temel başvuru kitabı oldu. Johnson 1974'te kutulama ve küme örtüsü gibi problemler için yaklaşım algoritmalarının ilk sistemli analizlerinden birini yaptı. Bir problemin NP-tam olduğunu kanıtlamanın yaklaşım algoritmalarına (approximation algorithm) ya da sezgisel aramaya yönelmeyi haklı çıkardığı görüşü bu çalışmalarla yerleşti.
Leslie Valiant
#P · PAC · BSP · 2010 Turing Ödülü
1979'da sayma problemleri için #P sınıfını tanımladı ve permanent hesabının #P-tam olduğunu gösterdi. Makine öğrenmesinin kuramsal temellerinden PAC öğrenme modelini 1984'te, paralel hesaplama için toplu eş zamanlı paralel (bulk synchronous parallel, BSP) köprü modelini 1990'da önerdi. Vazirani ile rastgele indirgemeler üzerinde çalıştı ve 2010'da Turing Ödülü'nü aldı.
Daniel Sleator
Rekabetçi analiz · 1985
Tarjan ile yazdığı 1985 tarihli “Amortized Efficiency of List Update and Paging Rules” makalesinde bir çevrim içi algoritmayı (online algorithm) geleceği bilen en iyi çevrim dışı algoritmayla karşılaştırmayı önerdi; öne taşı (move-to-front, MTF) kuralının 2-rekabetçi, LRU'nun k-rekabetçi olduğunu gösterdiler. “Rekabetçi analiz” (competitive analysis) adı Karlin, Manasse, Rudolph ve Sleator'ın 1988 tarihli makalesinde kondu. Tarjan ile splay ağaçlarını ve link-cut ağaçlarını da geliştirdi.
Jeffrey S. Vitter
Rezervuar örnekleme · 1985
1985 tarihli “Random Sampling with a Reservoir” makalesinde, uzunluğu bilinmeyen bir veri akışından (data stream) tek geçişte k öğelik düzgün rastgele örnek tutan yöntemleri analiz etti; temel yönteme Algorithm R adını verdi ve daha hızlı Algorithm Z'yi geliştirdi. Doktorasını Knuth'un yanında yaptı; dış bellek algoritmalarının ve veri sıkıştırmanın da öncülerindendir.
W. Daniel Hillis ve Guy L. Steele Jr.
Paralel önek toplamı · 1986
1986'da Communications of the ACM'de yayımladıkları “Data Parallel Algorithms” makalesinde, binlerce işlemcili Connection Machine için veri paralel algoritmalar anlattılar. Önek toplamında d = 1, 2, 4, … için her i ≥ d konumu aynı anda x[i] ← x[i − d] + x[i] işlemini yapar ve hesap ⌈log n⌉ turda biter. Toplam iş O(n log n) olduğu için yöntem iş-verimli değildir; Blelloch'un yöntemi O(log n) derinlikte O(n) iş yapar. Hillis Connection Machine'i tasarladı; Steele, Scheme dilinin tasarımcılarından ve Java dil belirtiminin yazarlarındandır.
John L. Gustafson
Gustafson yasası · 1988
1988'de Edwin Barsis ile yazdığı “Reevaluating Amdahl's Law” yazısında Amdahl yasasının varsayımını sorguladı. Amdahl problem boyutunu sabit tutar, bu yüzden sıralı kısım hızlanmayı 1/(1 − f) ile sınırlar. Gerçekte işlemci sayısı arttıkça çoğu zaman daha büyük problemler çözülür; problem p ile büyürse ölçeklenmiş hızlanma S = (1 − f) + f · p olur ve işlemci sayısıyla neredeyse doğrusal artar. Aynı yıl ilk Gordon Bell Ödülü'nü aldı.
Charles E. Leiserson
Cilk · iş çalma · CLRS
Cormen, Rivest ve Stein ile yazdığı Introduction to Algorithms (ilk baskı 1990), dünyada en çok kullanılan algoritma ders kitaplarından biri ve bu dersin ana kaynaklarındandır. MIT'de geliştirdiği Cilk dili, boşta kalan işlemcinin başka bir işlemcinin kuyruğundan iş aldığı, verimliliği kanıtlanmış bir iş çalma (work stealing) zamanlayıcısı kullanır; Java'nın fork/join çatısı da aynı fikre dayanır. İş/derinlik (work/span) analizinin yaygınlaşmasında da büyük payı vardır.
Guy Blelloch
Önek toplamı (scan) · NESL
1990 tarihli “Prefix Sums and Their Applications” çalışmasında önek toplamını (prefix sum, scan) paralel algoritmaların temel yapı taşı olarak ele aldı; O(n) iş ve O(log n) derinlikle çalışan yukarı tarama/aşağı tarama yöntemi onun adıyla anılır. İş–derinlik maliyet modeline dayanan paralel programlama dili NESL'i geliştirdi. Carnegie Mellon'da paralel çizge işleme kütüphaneleri üzerinde çalışıyor.
David Karger
Rastgele minimum kesim · 1993
Stanford'da doktora öğrencisiyken, rastgele seçilen kenarları iki düğüm kalana kadar büzen minimum kesim algoritmasını 1993'te yayımladı. Tek bir çalıştırma minimum kesimi en az 2/(n(n − 1)) olasılıkla bulur; yeterince tekrarla hata olasılığı istenildiği kadar küçülür. Stein ile geliştirdiği Karger–Stein sürümü yöntemi çok daha hızlı hâle getirdi.
Vijay V. Vazirani
Approximation Algorithms · 2001
Approximation Algorithms (2001) kitabı, yaklaşım algoritmalarını LP gevşetmesi ve primal–dual şeması gibi ortak tekniklerle anlatan temel ders kitabıdır. Micali ile genel çizgelerde maksimum eşleştirme için bilinen en hızlı algoritmalardan birini verdi (1980). Valiant ile 1986'da tek çözümlü SAT'ın da rastgele indirgemeler altında zor olduğunu gösterdi (Valiant–Vazirani teoremi).
Arama ve süzgece uyan isim yok.
Yıllar ve katkılar özgün yayınlara ve ansiklopedik kaynaklara dayanır. “Günümüz” ibaresi, doğum yılı yayımlanmış kaynaklarda verilmeyen yaşayan kişileri gösterir. Fermat'nın doğum yılı kaynaklarda tartışmalı olduğu için yalnız ölüm yılı verilmiştir; yaşam yılları güvenilir kaynaklarda bulunamayan kişilerde ise yalnız katkının yılı ve yayımlandığı dergi verilmiştir.