Algoritmalarda Önemli İsimler

OBEB algoritması · Elements

Elements (Elemanlar) adlı yapıtında iki sayının en büyük ortak bölenini art arda çıkarma yoluyla bulmayı anlattı; bugün aynı yöntemi bölme ve kalanla yazıyoruz. gcd(a, b) = gcd(b, a mod b) özdeşliğine dayanan Öklid algoritması (Euclid's algorithm), hâlâ kullanılan en eski algoritmalardan biridir. Büyük sayı her iki adımda en az yarıya indiği için adım sayısı O(log min(a, b)) ile sınırlıdır.

Hint-Arap rakamlarıyla hesap · cebir

Bağdat'taki Beytülhikme'de çalışan bir matematikçiydi. Hint-Arap rakamlarıyla hesap yapmayı anlatan kitabı Latince çevirisiyle (Algoritmi de numero Indorum) Avrupa'ya yayıldı. “Algoritma” sözcüğü adının Latinceleşmiş biçiminden, “cebir” sözcüğü ise al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr wa-l-muqābala adlı yapıtının başlığından gelir. Problemleri açık ve tekrarlanabilir adımlarla çözme fikrinin simgesidir.

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.

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.

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.

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.

Öklid algoritmasının adım sayısı · 1844

1844'te Öklid algoritmasının yaptığı bölme sayısının, küçük sayının onluk basamak sayısının beş katını geçemeyeceğini kanıtladı. Kanıtta Fibonacci sayılarını kullandı: belli sayıda bölme gerektiren en küçük girdi ardışık iki Fibonacci sayısıdır, çünkü bu girdilerde her bölümün sonucu 1 çıkar ve sayılar en yavaş biçimde küçülür. Teorem, bir algoritmanın en kötü durumunu inceleyen en eski çalışmalardan biri sayılır ve O(log min(a, b)) sınırının kesin biçimidir.

Cayley formülü · 1889

1889'da n düğümlü tam çizgenin tam olarak nⁿ⁻² kapsayan ağacı olduğunu gösteren formülü yayımladı; aynı sayıyı Carl Wilhelm Borchardt 1860'ta determinantla bulmuştu. Sayı çok hızlı büyür: 4 düğümde 16, 10 düğümde 100 milyon kapsayan ağaç vardır. Bu yüzden en ucuz kapsayan ağacı bütün ağaçları tek tek deneyerek bulmak pratik değildir; Kruskal ve Prim gibi açgözlü algoritmalar aynı sonuca polinom sürede ulaşır. Cayley matris cebirinin ve soyut grup kavramının da kurucularındandır.

İlk MST algoritması · 1926

1926'da Moravya'nın elektrik şebekesini en düşük maliyetle kurmak için ilk minimum kapsayan ağaç (minimum spanning tree, MST) algoritmasını yayımladı. Her turda her bileşen, kendisinden çıkan en hafif kenarı seçer; bileşen sayısı her turda en az yarıya indiği için O(log V) tur yeter. Bir turdaki seçimler birbirinden bağımsız olduğundan yöntem paralel ve dağıtık ortamlara da uygundur.

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.

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.

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.

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.

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.

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.

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

Hamming uzaklığı · 1950

1950'de Bell System Technical Journal'da yayımladığı “Error Detecting and Error Correcting Codes” makalesinde hata düzelten kodları ve bugün Hamming uzaklığı diye anılan ölçüyü tanıttı. Hamming uzaklığı, eşit uzunluktaki iki dizginin farklı karakter taşıdığı konumların sayısıdır ve tek bir taramayla O(n) sürede hesaplanır; örneğin “karolin” ile “kathrin” arasındaki uzaklık 3'tür. Uzunlukları farklı dizgilerde tanımsızdır; ekleme ve silmeye de izin veren Levenshtein uzaklığı bu durumda kullanılır. 1968'de Turing Ödülü'nü aldı.

Düzenli ifadeler · 1951

1951'de hazırladığı bir RAND raporunda (yayımlanışı 1956) düzenli ifadeleri (regular expressions) tanımladı ve bunların sonlu otomatların tanıdığı dilleri tam olarak betimlediğini gösterdi (Kleene teoremi). “Sıfır ya da daha çok tekrar” anlamına gelen * işlemi onun adıyla Kleene yıldızı diye anılır. Özyinelemeli fonksiyonlar kuramıyla birlikte hesaplanabilirlik kuramının kurucularındandır.

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.

Anahtarları kovalara dağıtma · 1953

1953'te IBM'de, anahtarları bir fonksiyonla “kovalara” dağıtarak aramayı hızlandırmayı önerdi; bu, hash tablolarının (hash table) ve zincirlemenin (chaining) bilinen en eski örneklerinden biridir. Kredi kartı numaralarını doğrulamakta hâlâ kullanılan Luhn denetim basamağı algoritması ve bağlam içinde anahtar sözcük (KWIC) dizinlemesi de onundur.

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.

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.

Maksimum akış · 1956

1956'da RAND Corporation'da, artık ağda (residual network) artış yolu (augmenting path) kalmayana kadar akışı artıran Ford-Fulkerson yöntemini ve maksimum akış minimum kesim teoremini yayımladılar. Ford aynı yıllarda kenarları tekrar tekrar gevşeten en kısa yol yöntemini de verdi; algoritmanın Bellman-Ford diye anılması bundandır. 1962 tarihli Flows in Networks kitapları ağ akışını ayrı bir alan hâline getirdi.

Kruskal algoritması · 1956

1956 tarihli kısa bir makalede kenarları ağırlık sırasıyla inceleyip döngü oluşturmayanları ekleyen MST algoritmasını verdi; aynı makale ters silme (reverse-delete) yöntemini de anlatır. Bugün döngü denetimi union-find yapısıyla yapılır ve algoritma O(E log E) sürede çalışır. Çok boyutlu ölçekleme gibi katkılarıyla istatistikte de önemli bir yeri vardır.

Labirentte en kısa yol (BFS) · 1957

Bell Labs'ta labirentteki en kısa yolu bulmak için genişlik öncelikli aramayı (breadth-first search, BFS) anlattı (“The Shortest Path Through a Maze”, sunuluşu 1957, yayımlanışı 1959). Çalışma, ağırlıksız çizgelerde en kısa yolların katman katman bulunabileceğini gösterir; ağırlıklı durum için verdiği yöntem yüzünden Bellman-Ford kimi zaman “Bellman–Ford–Moore” diye anılır. Sonlu durum makinelerinin Moore makinesi türü de onun adını taşır.

Prim algoritması · 1957

1957'de Bell Labs'ta, bir düğümden başlayıp ağacı her adımda dışarı çıkan en hafif kenarla büyüten minimum kapsayan ağaç algoritmasını yayımladı. Aynı yöntemi Vojtěch Jarník 1930'da bulmuş, Dijkstra da 1959'da yeniden keşfetmişti; bu yüzden Jarník–Prim algoritması diye de anılır. Öncelikli kuyrukla O(E log V) sürede çalışır ve yapısı Dijkstra algoritmasına çok benzer.

Shell sıralaması · 1959

1959'da yayımladığı yöntemde öğeler önce geniş aralıklarla, sonra giderek daralan aralıklarla eklemeli sıralamadan geçirilir. Böylece uzak ters çiftler (inversion) erkenden düzelir ve eklemeli sıralamanın O(n²) davranışı uygulamada büyük ölçüde iyileşir. Karmaşıklık aralık dizisine bağlıdır ve kimi diziler için hâlâ açık bir sorudur.

En kısa yollar · 1959

Kendi anlatımına göre en kısa yol algoritmasını 1956'da Amsterdam'da yirmi dakika kadar içinde tasarladı ve 1959'da yayımladı; aynı makale minimum kapsayan ağaç için Prim yöntemini de bağımsız olarak verir. Geçici uzaklığı en küçük olan düğümü kesinleştirip kenarlarını gevşetmek (relaxation) negatif olmayan ağırlıklarda doğru sonuç verir ve öncelikli kuyrukla (priority queue) O((V + E) log V) sürer. Yapısal programlama ve semaforlarla da tanınır; 1972'de Turing Ödülü'nü aldı.

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.

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

Trie · 1960

1960'ta dizgileri ortak önekleri paylaşan bir ağaçta saklama fikrini yayımladı ve yapıya “retrieval” sözcüğünün ortasından “trie” adını verdi; René de la Briandais aynı yapıyı bir yıl önce (1959) anlatmıştı. Fredkin tersinir hesaplama ve Fredkin kapısıyla da tanınır; MIT'deki Project MAC'i yönetti.

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.

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

Floyd-Warshall · 1962

1962'de tüm çiftler arasındaki en kısa yolları (all-pairs shortest paths) O(V³) sürede bulan algoritmayı yayımladı; ara düğümleri birer birer ekleyen bu dinamik program bugün Floyd-Warshall diye bilinir. 1964'te heap'i O(n) sürede kuran yöntemi verdi; listelerde döngü bulmak için “kaplumbağa ve tavşan” yöntemi de ona atfedilir. Program doğrulama alanındaki öncü çalışmaları için 1978'de Turing Ödülü'nü aldı.

Geçişli kapanış · 1962

1962 tarihli “A Theorem on Boolean Matrices” makalesinde bir bağıntının geçişli kapanışını (transitive closure) Boole matrisi üzerinde O(V³) sürede hesaplayan yöntemi yayımladı: i'den k'ye ve k'den j'ye yol varsa i'den j'ye de yol vardır. Floyd'un aynı yılki en kısa yol algoritması aynı üçlü döngüyü kullandığı için ikisi birlikte anılır. Bernard Roy benzer bir sonucu 1959'da yayımlamıştı.

Topolojik sıralama · 1962

1962 tarihli “Topological Sorting of Large Networks” makalesinde, yönlü ve döngüsüz bir çizgenin topolojik sırasını giriş derecesi sıfır olan düğümleri art arda çıkararak bulan algoritmayı verdi. Giriş derecesi 0 olan düğümler kuyruğa konur; kuyruktan çıkan düğüm sıraya yazılır ve ardıllarının giriş derecesi bir azaltılır, derecesi sıfıra inen düğüm kuyruğa katılır. Algoritma O(V + E) sürede çalışır. Bütün düğümler çıkarılamıyorsa çizgede döngü vardır; böylece aynı yöntem döngü denetimi de yapar.

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

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.

Heap sort · 1964

1964'te heap sort algoritmasını ve onun dayandığı ikili heap yapısını Communications of the ACM'de “Algorithm 232: Heapsort” başlığıyla yayımladı. Diziyi max-heap'e dönüştürüp kökü tekrar tekrar sona taşımak, en kötü durumda O(n log n) süre ve O(1) ek bellek gerektirir. Aynı yıl Robert Floyd heap'i O(n) sürede kuran iyileştirmeyi verdi.

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

Levenshtein uzaklığı · 1965

1965'te bir dizgiyi diğerine dönüştürmek için gereken en az ekleme, silme ve değiştirme sayısını tanımladı; bu ölçü onun adını taşır. Amacı hata düzelten kodlardı; ölçü bugün yazım denetiminde, DNA dizilerini karşılaştırmada ve yaklaşık aramada kullanılır. Uzaklığı dinamik programlamayla O(m·n) sürede hesaplamak (Wagner–Fischer, 1974), derste kullanılan tablo yöntemidir.

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.

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

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.

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.

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.

The Art of Computer Programming · 1968–

Çok ciltli The Art of Computer Programming (Bilgisayar Programlama Sanatı) ile algoritma analizini bir disipline dönüştürdü; işlem sayılarını tam olarak hesaplamayı ve ortalama durum analizini yaygınlaştırdı. 1976'da O, Ω ve Θ gösterimlerinin bugünkü anlamlarını önerdi. Morris ve Pratt ile KMP dizgi eşleştirme algoritmasını yayımladı (1977), TeX dizgi sistemini geliştirdi ve 1974'te Turing Ödülü'nü aldı.

A* algoritması · 1968

SRI'da Shakey robotunun yol planlaması için A* algoritmasını 1968'de yayımladılar. Nilsson'un sezgisel aramasına o ana kadarki maliyeti eklemeyi Raphael önerdi; kabul edilebilir (admissible) ve tutarlı sezgisel kavramlarını Hart getirdi. f = g + h değerine göre ilerleyen A*, kabul edilebilir bir sezgiselle en kısa yolu bulur ve çoğu zaman Dijkstra algoritmasından çok daha az düğüm açar.

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.

Dinic algoritması · 1970

1969'da Moskova'da, düzey çizgesinde (level graph) engelleyici akışlar (blocking flow) bularak ilerleyen maksimum akış algoritmasını tasarladı ve 1970'te yayımladı. Batı'da Shimon Even'ın sunumu aracılığıyla “Dinic algoritması” adıyla tanındı. Algoritma O(V²·E) sürede çalışır; birim kapasiteli ağlarda ve iki parçalı eşleştirmede çok daha hızlıdır.

Knuth-Morris-Pratt · 1970/1977

Morris 1970'te örüntünün kendi öneklerinden yararlanarak metinde hiç geri gitmeyen bir eşleştirme yöntemi buldu ve bunu Pratt ile bir teknik raporda yayımladı; birkaç hafta sonra Knuth aynı algoritmaya otomatlar kuramından bağımsız olarak ulaştı. Üçü “Fast Pattern Matching in Strings” makalesini 1977'de birlikte yayımladı. LPS tablosu sayesinde metin göstergesi hiç geri gitmez ve arama O(n + m) sürer.

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

Güçlü bağlantılı bileşenler · 1972

1972'de yönlü bir çizgenin güçlü bağlantılı bileşenlerini (strongly connected components) tek bir DFS ile doğrusal sürede bulan algoritmayı yayımladı. 1975'te yol kısaltma (path compression) ve rütbeye göre birleştirme (union by rank) kullanan union-find yapısının amortize olarak neredeyse sabit süre aldığını kanıtladı ve amortize analizi (amortized analysis) sistemli hâle getirdi. Sleator ile splay ağaçlarını ve çevrim içi liste güncelleme analizini (1985), Goldberg ile itme–yeniden etiketleme (push–relabel) yöntemini (1988) geliştirdi; 1986 Turing Ödülü'nü Hopcroft ile paylaştı.

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

Hopcroft–Karp eşleştirmesi · 1973

Tarjan ile birlikte derinlik öncelikli aramanın (depth-first search, DFS) çizge algoritmalarında ne kadar güçlü olduğunu gösterdi; düzlemsellik testini birlikte doğrusal sürede çözdüler. Karp ile 1973'te iki parçalı bir çizgede maksimum eşleştirmeyi O(E√V) sürede bulan algoritmayı yayımladı. Ullman ile yazdığı otomatlar ve biçimsel diller kitabı uzun yıllar temel kaynak oldu; 1986 Turing Ödülü'nü Tarjan ile paylaştı.

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.

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.

Aho–Corasick algoritması · 1975

1975'te Communications of the ACM'de yayımladıkları “Efficient String Matching: An Aid to Bibliographic Search” makalesinde birçok örüntüyü metinde tek geçişte arayan algoritmayı verdiler. Örüntüler bir trie'ye yerleştirilir; her düğüme, eşleşme bozulduğunda geçilecek en uzun uygun soneki gösteren hata bağlantısı (failure link) eklenir. Arama süresi metin uzunluğu, örüntülerin toplam uzunluğu ve bulunan eşleşme sayısıyla doğrusaldır. Algoritma Unix'in fgrep komutunun temelidir. Aho, AWK dilinin ve “Dragon Book” diye anılan derleyici kitaplarının da yazarlarındandır; 2020 Turing Ödülü'nü Jeffrey Ullman ile paylaştı.

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

Boyer-Moore · 1977

1977'de örüntüyü sağdan sola karşılaştıran ve kötü karakter (bad character) ile iyi sonek (good suffix) kurallarıyla metinde büyük sıçramalar yapan algoritmayı yayımladılar; uzun örüntülerde metin karakterlerinin çoğuna hiç bakılmaz. Horspool 1980'de yalnız kötü karakter kuralını kullanan daha basit bir sürüm verdi. İkili ayrıca Boyer–Moore teorem kanıtlayıcısını (ACL2'nin atası) ve çoğunluk oyu algoritmasını geliştirdi.

LZ77 · LZ78

Technion'da 1977'de kayan bir pencere içindeki önceki tekrarlara geri başvuran LZ77'yi, 1978'de görülen öbekleri bir sözlükte toplayan LZ78'i yayımladılar. Terry Welch 1984'te LZ78'i sadeleştirerek LZW'yi elde etti; GIF biçimi LZW'yi kullanır, ZIP ve PNG'nin kullandığı DEFLATE ise LZ77'yi Huffman kodlamayla birleştirir. Bu yöntemler, önceden olasılık tablosu gerektirmeyen “evrensel” sıkıştırmanın temelidir.

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.

Kosaraju algoritması · 1978

1978'de yönlü bir çizgenin güçlü bağlantılı bileşenlerini iki DFS ile bulan yöntemi önerdi, ama yayımlamadı; Micha Sharir aynı algoritmayı bağımsız olarak bulup 1981'de yayımladı. Birinci DFS düğümlerin bitiş sırasını çıkarır. İkinci DFS kenarları ters çevrilmiş çizgede, düğümleri bitiş zamanı azalan sırayla başlatır; bu DFS'in her ağacı bir güçlü bağlantılı bileşendir. Komşuluk listesiyle süre O(V + E)'dir. Tarjan'ın tek DFS'li yönteminden daha kolay anlaşılır, ama çizgeyi iki kez gezer.

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.

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

Böl ve fethet bağıntıları · 1980

Haken ve Saxe ile 1980'de T(n) = aT(n/b) + f(n) biçimindeki böl ve fethet bağıntılarını çözmek için genel bir yöntem yayımladı; ana teorem (master theorem) bu çalışmayla yaygınlaştı. Yao ile 1976'da sınırsız arama için neredeyse optimal bir yöntem verdi; bu yöntem üstel aramanın (exponential search) temelidir. 1975'te k-d ağacını tanıttı, Programming Pearls yazılarıyla verimli programlamayı geniş bir kitleye ulaştırdı.

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.

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.

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.

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

Sonek dizisi · 1990

1990'da (dergi sürümü 1993) sonek ağacından çok daha az bellek kullanan sonek dizisini (suffix array) tanıttılar ve önek uzunluğunu her turda ikiye katlayarak sonekleri O(n log n) sürede sıralayan yöntemi verdiler. Myers daha sonra BLAST'ın geliştirilmesine ve insan genomunun dizilenmesine katkıda bulundu; Manber Yahoo!, Amazon ve Google'da arama teknolojileri üzerinde çalıştı.

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.

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

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.

Burrows–Wheeler dönüşümü · 1994

Wheeler'ın 1983'te bulduğu dönüşümü Burrows ve Wheeler 1994'te DEC Systems Research Center'ın 124 numaralı araştırma raporu olarak yayımladı. Bir dizginin sıralanmış dönüşümlerinin son sütunu benzer karakterleri bir araya toplar ve geri çevrilebilir; bzip2 sıkıştırıcısı ve FM-index tabanlı DNA hizalama araçları bu dönüşüme dayanır. Wheeler daha önce Cambridge'de EDSAC için alt program çağrısının ilk biçimlerinden birini geliştirmişti.

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