İleri Algoritmalar · İsimler

İ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

y. 1170 – y. 1250 · İtalyan · Pisa

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.

yineleme bağıntısıörtüşen alt problemler

Pierre de Fermat

ö. 1665 · Fransız · Toulouse

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.

Fermat testiCarmichael sayılarımodüler aritmetik

Leonhard Euler

1707–1783 · İsviçreli · St. Petersburg, Berlin

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.

çizge kuramıEuler turu

Carl Friedrich Gauss

1777–1855 · Alman · Göttingen

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.

aritmetik seridöngü sayma

Alan Turing

1912–1954 · İngiliz · Cambridge, Manchester

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.

hesaplanabilirlikdurma problemiChurch–Turing tezi

Ronald A. Fisher ve Frank Yates

1890–1962 · 1902–1994 · İngiliz · Rothamsted

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.

Fisher–Yates karıştırma (Fisher–Yates shuffle)düzgün dağılımlı permütasyon

John von Neumann

1903–1957 · Macar asıllı Amerikalı · Princeton IAS

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.

böl ve fethetkararlı sıralamaMonte Carlo

Stanisław Ulam

1909–1984 · Polonya doğumlu · ABD, Los Alamos

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.

Monte Carlorastgele örnekleme

George B. Dantzig

1914–2005 · Amerikalı · RAND, Stanford

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.

doğrusal programlamasimpleksTSP

Claude Shannon

1916–2001 · Amerikalı · Bell Labs, MIT

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.

entropisıkıştırma sınırı

Derrick H. Lehmer

1905–1991 · Amerikalı · UC Berkeley

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ı.

sözde rastgele sayılargeri izleme

David A. Huffman

1925–1999 · Amerikalı · MIT, UC Santa Cruz

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.

Huffman kodlamaönek koduaçgözlü seçim

Richard Bellman

1920–1984 · Amerikalı · RAND Corporation

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.

dinamik programlamaoptimal alt yapıBellman-Ford

Gene Amdahl

1922–2015 · Amerikalı · IBM

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.

doğrusal yoklamahızlanmaAmdahl yasası

Michael O. Rabin

d. 1931 · İsrailli · Kudüs İbrani Üniversitesi; Harvard

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.

asallık testikayan hashsonlu otomat

C. A. R. (Tony) Hoare

1934–2026 · İngiliz · Oxford

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ı.

hızlı sıralamabölümlemeQuickSelect

Anatoly Karatsuba

1937–2008 · Sovyet · Moskova

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.

Karatsuba çarpımıböl ve fethet

Ailsa Land ve Alison Doig

1927–2021 · d. 1929 · İngiliz · London School of Economics

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ı.

dal sınırLP gevşetmesi

Michael Held ve Richard M. Karp

Karp: d. 1935 · Journal of the SIAM, 1962

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ı.

Held–Karpgezgin satıcıalt küme DP

John D. C. Little, Katta G. Murty, Dura W. Sweeney ve Caroline Karel

Little: 1928–2024 · Amerikalı · MIT

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.

dal sınırindirgenmiş maliyet matrisigezgin satıcı

Jack Edmonds

d. 1934 · Amerika doğumlu · Kanada, Waterloo

Ç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.

Edmonds-Karppolinom zamanmatroid

Solomon W. Golomb

1932–2016 · Amerikalı · University of Southern California

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.

geri izlemebudama

Ronald Graham

1935–2020 · Amerikalı · Bell Labs, UC San Diego

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ı.

liste çizelgelemeyaklaşım oranıdışbükey örtü

László Bélády

1928–2021 · Macaristan doğumlu · ABD, IBM

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.

sayfalamaçıkarma politikası

Michael J. Flynn

1934–2025 · Amerikalı · Stanford

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.

SIMDMIMDparalel mimari

Andrew Viterbi

d. 1935 · İtalya doğumlu · ABD, UCLA, Qualcomm

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.

dinamik programlamaen olası yol

Volker Strassen

d. 1936 · Alman · Zürih, Konstanz

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.

Strassen algoritmasımatris çarpımı

Stephen Cook

d. 1939 · Amerikalı-Kanadalı · University of Toronto

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ı.

NP-tamSATP = NP?

Richard M. Karp

d. 1935 · Amerikalı · Berkeley

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ı.

NP-tamindirgemeRabin-Karp

Leonid Levin

d. 1948 · Sovyet-Amerikalı · Boston University

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.

NP-tamindirgeme

Richard P. Brent

d. 1946 · Avustralyalı · Avustralya Ulusal Üniversitesi

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.

Brent teoremiişderinlik

Nicos Christofides

1942–2019 · Kıbrıslı-İngiliz · Imperial College London

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ı.

gezgin satıcı problemiyaklaşım oranı

Joseph B. (Jay) Kadane

d. 1941 · Amerikalı · Carnegie Mellon

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.

Kadane algoritmasıen büyük toplamlı alt diziO(n)

Michael Garey ve David S. Johnson

d. 1945 · 1945–2016 · Amerikalı · Bell Labs

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.

NP-tamlıkyaklaşım algoritması

Leslie Valiant

d. 1949 · Macaristan doğumlu · Birleşik Krallık; ABD, Harvard

#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ı.

#Pparalel modelrastgele indirgeme

Daniel Sleator

d. 1953 · Amerikalı · Carnegie Mellon

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.

rekabetçi analizöne taşısayfalama

Jeffrey S. Vitter

d. 1955 · Amerikalı · Brown University

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.

rezervuar örnekleme (reservoir sampling)veri akışı

W. Daniel Hillis ve Guy L. Steele Jr.

d. 1956 · d. 1954 · Amerikalı · Thinking Machines

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.

önek toplamıveri paralelliğiiş-verimlilik

John L. Gustafson

d. 1955 · Amerikalı · Communications of the ACM 31(5), 1988

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ı.

Gustafson yasasıölçeklenmiş hızlanmaAmdahl yasası

Charles E. Leiserson

d. 1953 · Amerikalı · MIT

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.

iş çalmaiş / derinlik

Guy Blelloch

günümüz · Amerikalı · Carnegie Mellon

Ö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.

önek toplamıiş / derinlik

David Karger

d. 1967 · Amerikalı · Stanford, MIT

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.

minimum kesimMonte Carlo algoritması

Vijay V. Vazirani

günümüz · Hindistan doğumlu · ABD, Georgia Tech, UC Irvine

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).

yaklaşım algoritmasıLP gevşetmesi

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.