C ile Veri Yapılarında Önemli İsimler

Königsberg köprüleri · 1736

Königsberg'in yedi köprüsünün her birinden yalnız bir kez geçen bir yürüyüş olup olmadığını sordu. Kara parçalarını düğüm, köprüleri kenar sayarak sorunun şekle değil yalnız bağlantılara bağlı olduğunu gösterdi ve böyle bir yürüyüşün olmadığını kanıtladı. 1736 tarihli bu çalışma çizge kuramının başlangıcı kabul edilir; her düğümün derecesi çift olmadıkça kapalı bir Euler yürüyüşü kurulamaz.

Horner yöntemi · 1819

Polinom köklerini yaklaşık hesaplayan bir yöntemle tanındı; yöntem ondan önce Ruffini'de de görülür. Bugün adı daha çok polinomu iç içe çarpımlarla hesaplama biçimine verilir: a₀ + x(a₁ + x(a₂ + …)) yazımıyla n dereceli bir polinom n çarpmayla hesaplanır. Derste aynı düzen iki yerde kullanılır: n boyutlu bir dizide öğenin ofsetini bulurken ve bir dizgiyi h = h * 31 + c döngüsüyle hash'lerken.

Etiketli ağaç sayısı · 1889

1889'da yayımladığı kısa bir notta n etiketli düğüm üzerinde nⁿ⁻² farklı ağaç kurulabileceğini ileri sürdü. Sonuç ilk kez Borchardt'ın 1860 tarihli çalışmasında görülür, ama bugün Cayley formülü adıyla bilinir. Aynı sayı, n düğümlü tam çizgenin kapsayan ağaç (spanning tree) sayısıdır: K₄ için 4² = 16.

Ackermann fonksiyonu · 1928

Hilbert'in öğrencisi olan bu mantıkçı, hesaplanabilir olduğu hâlde ilkel özyinelemeli (primitive recursive) olmayan bir fonksiyon tanımladı. Bugün ders kitaplarında kullanılan iki değişkenli biçimi Rózsa Péter ile Raphael Robinson'un sadeleştirmesidir. Fonksiyon şaşırtıcı hızla büyür; tersi α(n) ise o kadar yavaş büyür ki ağırlıklı kural ve azaltma kuralıyla çalışan ayrık küme işlemlerinin maliyeti pratikte sabit sayılır.

Minimum kapsayan ağaç için tek öbekli büyütme · 1930

Asıl alanı sayılar kuramı olan Çek matematikçi, Borůvka'nın sonucunu sadeleştiren bir algoritmayı 1930'da Çekçe yayımladı: ağaç tek bir düğümden başlar ve her adımda ağaçla ağaç dışını birleştiren en ucuz kenar eklenir. Algoritma Prim (1957) ve Dijkstra (1959) tarafından yeniden bulundu; bu yüzden DJP ya da Prim–Jarník algoritması adıyla da anılır.

İlk minimum kapsayan ağaç algoritması · 1926

Batı Moravya'da bir elektrik şirketinin şebeke sorusu üzerine, bilinen ilk minimum kapsayan ağaç algoritmasını 1926'da yayımladı. Her turda her bileşen kendinden çıkan en ucuz kenarı seçer; bileşen sayısı her turda en az yarıya indiği için en çok log n tur yeter. Çekçe yazılan çalışma uzun süre fark edilmedi; Sollin 1965'te yöntemi yeniden bulunca algoritma Sollin adıyla da yaygınlaştı. Turlar birbirinden bağımsız olduğu için paralel hesaplamaya uygundur.

Birleştirme sıralaması · 1945

1945'te EDVAC bilgisayarı için iki sıralı diziyi tek sıralı dizide birleştiren bir yordam yazdı; bu yordam bugün birleştirme sıralaması (merge sort) denen algoritmanın parçasıydı. El yazması, von Neumann'ın kodlarından günümüze ulaşan en eski örnektir. Algoritma parçala ve yönet yaklaşımının ve en kötü durumda da O(n lg n) süren kararlı sıralamanın standart örneğidir.

Sihirli kare kuralı · Coxeter grupları

Çok boyutlu çokyüzlüler ve yansıma grupları üzerine çalışan, yüzyılın önde gelen geometricilerinden biridir. W. W. Rouse Ball'un Mathematical Recreations and Essays kitabının 1939'dan sonraki baskılarını o hazırladı; ders kitabı tek n için sihirli kare kuralını ona dayandırır. Kural n² adımda biter; kaba kuvvetle 25! dizilişi denemek ise milyonlarca yüzyıl sürer. Derste bu fark, iyi bir algoritmanın daha hızlı bir makineden önemli olduğunu göstermek için kullanılır.

Bellman–Ford algoritması · 1956, 1958

Ford 1956'da, Bellman 1958'de negatif ağırlıklı kenarlara izin veren tek kaynaklı en kısa yol yöntemini yayımladı; aynı fikir Shimbel'de (1955) ve Moore'da da görülür. Bütün kenarlar n − 1 tur gevşetilir; n. turda hâlâ gevşeyen bir kenar varsa çizgede negatif döngü vardır. Bellman dinamik programlamanın, Ford ise Fulkerson'la birlikte en büyük akış kuramının kurucularındandır.

Prim algoritması · 1957

Bell Laboratuvarları'nda Kruskal'la aynı dönemde çalışırken minimum kapsayan ağaç için tek öbeği büyüten algoritmayı 1957'de yayımladı; Jarník'in 1930 tarihli yöntemini bağımsız olarak yeniden buldu. Ağaçtaki ve ağaç dışındaki düğümleri birleştiren en ucuz kenar seçildiği için döngü denetimi gerekmez. Dizi ile O(n²) süren algoritma, heap ile O(e log n)'ye iner ve seyrek çizgelerde daha hızlıdır.

AVL ağacı · 1962

“Bilginin düzenlenmesi için bir algoritma” başlıklı 1962 makalelerinde, her düğümde iki alt ağacın yükseklik farkını en çok 1 tutan ilk kendini dengeleyen ikili arama ağacını tanımladılar; yapı adını ikisinin soyadlarının baş harflerinden alır. Denge bozulduğunda tek ya da çift döndürme yapılır ve yükseklik ≈ 1,44 lg n'yi aşmaz. Adelson-Velsky ayrıca Kaissa satranç programının yazarlarındandır; Landis'in asıl alanı kısmi türevli denklemlerdir.

Kılavuzlu ağaçlar · 1960

ALGOL'ün tasarımcılarından biridir ve 1966'da ilk Turing Ödülü'nü aldı. C. Thornton'la birlikte 1960'ta, bir ikili ağaçtaki boş işaretçilerin kök ortada sıradaki önceli ve ardılı göstermek için kullanılabileceğini önerdi; bu işaretçilere kılavuz (thread) denir. Kılavuzlu ağaçta kök ortada gezinme yığın ya da özyineleme olmadan yapılır. Derste sık alıntılanan kısa vecizeleri de 1982'de yayımlanan “Epigrams on Programming” yazısından gelir.

Shell sıralaması · 1959

“A High-Speed Sorting Procedure” başlıklı makalesini 1959'da Communications of the ACM'de yayımladı. Eklemeli sıralama birbirinden h uzaklıktaki öğelere uygulanır ve h küçültülerek 1'e indirilir; uzak takaslar evrikleri hızla azalttığı için komşu takaslı algoritmaların Ω(n²) sınırı aşılır. Süre aralık dizisine bağlıdır ve uzak takaslar yüzünden sıralama kararlı değildir.

Kruskal algoritması · 1956

Minimum kapsayan ağacı bulmak için kenarları maliyete göre sıralayıp döngü oluşturmayan her kenarı ağaca ekleyen yöntemi 1956'da yayımladı. Seçilen kenarlar önce bir orman oluşturur, sonunda tek ağaçta birleşir. Döngü denetimi ayrık kümelerle yapılır: kenarın iki ucu farklı kümelerdeyse kenar alınır ve kümeler birleştirilir; toplam süre O(e log e) olur. İstatistikte çok boyutlu ölçekleme çalışmalarıyla da tanınır.

En kısa yol algoritması · 1959

1959'da yayımladığı iki sayfalık notta hem tek kaynaklı en kısa yol algoritmasını hem de minimum kapsayan ağaç için Jarník–Prim yöntemini verdi. En kısa yol algoritması açgözlüdür: uzaklığı en küçük olan düğüm kesinleşir ve komşularının uzaklıkları onun üzerinden güncellenir. Bu seçim yalnız negatif olmayan kenar ağırlıklarında doğrudur. Yapısal programlamanın öncülerinden olan Dijkstra 1972'de Turing Ödülü'nü aldı.

Hızlı sıralama · 1961–1962

Hızlı sıralamayı (quicksort) 1959'da Moskova'da bir sözlük çevirisi üzerinde çalışırken tasarladı; algoritmayı 1961'de Communications of the ACM'de, ayrıntılı çözümlemesiyle 1962'de The Computer Journal'da yayımladı. Dayanak öğeye göre bölümleme ve iki parçanın özyinelemeli sıralanması, ortalamada O(n lg n) süren yerinde bir sıralama verir. Program doğruluğu için Hoare mantığını da geliştirdi ve 1980'de Turing Ödülü'nü aldı. 5 Mart 2026'da Cambridge'de öldü.

Geçişli kapanış · 1962

1962'de bir Boole matrisinin geçişli kapanışını O(n³) sürede bulan algoritmayı yayımladı: her k için “i'den k'ye ve k'den j'ye yol varsa i'den j'ye de yol vardır” kuralı bütün çiftlere uygulanır. Floyd aynı yıl bu düzeni yol uzunluklarına taşıdı; tüm çiftler arasındaki en kısa yolları bulan algoritma bu yüzden Floyd–Warshall adıyla anılır.

Floyd–Warshall · döngü tespiti

1962'de tüm düğüm çiftleri arasındaki en kısa yolları bulan Floyd–Warshall algoritmasını yayımladı. Bağlı listede iki işaretçiyle (biri bir, öteki iki adım ilerleyen) döngü bulan “tavşan ve kaplumbağa” yöntemi de Knuth'un aktarımıyla ona atfedilir; yöntem O(1) ek bellekle çalışır. 1964'te heap'i aşağıdan yukarı O(n) sürede kuran yöntemi verdi. Program doğrulamasına katkılarıyla 1978'de Turing Ödülü'nü aldı.

The Art of Computer Programming · 1968'den bu yana

İlk cildi 1968'de çıkan The Art of Computer Programming dizisiyle algoritmaların matematiksel çözümlemesini bir disiplin hâline getirdi; 1974'te Turing Ödülü'nü aldı. Derste birçok sonuç ona dayanır: doğrusal yoklamada beklenen yoklama sayıları, çarpma yönteminde önerilen A ≈ (√5 − 1)/2 sabiti, Shell sıralaması için 1, 4, 13, 40, … aralık dizisi ve Floyd'un döngü tespitinin aktarımı. Knuth–Morris–Pratt dizgi arama algoritmasının da ortak yazarıdır. Sedgewick onun doktora öğrencisidir.

B-ağacı · 1970–1972

Boeing'de birlikte çalışırken büyük sıralı dizinleri diskte tutmak için B-ağacını tasarladılar; makale 1970'te rapor olarak dağıtıldı, 1972'de Acta Informatica'da yayımlandı. m yollu bu dengeli ağaçta her düğüm birçok anahtar tutar ve bütün yapraklar aynı düzeydedir; dolan düğüm ortadaki anahtarı ebeveynine göndererek ikiye bölünür. Bayer'in 1972'de tanımladığı simetrik ikili B-ağaçları, kırmızı-siyah ağaçların öncüsüdür.

Ayrık kümelerin çözümlemesi · 1975, 1984

1975'te birleştirme kuralıyla yol sıkıştırmanın birlikte kullanıldığı ayrık küme işlemlerinin ters Ackermann fonksiyonu α ile sınırlandığını kanıtladı. Jan van Leeuwen'le (d. 1946, Utrecht Üniversitesi) 1984'te yayımladığı çalışma, bu türden birleştirme ve bulma yöntemlerinin en kötü durum çözümlemesini bir arada verdi. Sleator'la birlikte splay ağaçlarını, Fredman'la birlikte Fibonacci heap'lerini tanımladı; 1986'da Turing Ödülü'nü aldı.

C dili · Unix

C dilini 1972 dolayında Bell Laboratuvarları'nda Unix işletim sistemini yazmak için geliştirdi; Unix'i Ken Thompson'la birlikte tasarladı ve 1983'te onunla Turing Ödülü'nü paylaştı. Dersteki her yapı C'nin sunduğu araçlarla kurulur: struct ile kayıt, işaretçiyle bağ, malloc ve free ile çalışma anında bellek. Kernighan'la yazdığı The C Programming Language (1978) dersin başucu kitabıdır.

The C Programming Language · 1978

Ritchie'yle yazdığı The C Programming Language (1978; ANSI C'ye göre ikinci baskı 1988), yazarlarının baş harfleriyle “K&R” diye anılır ve C'nin fiilî tanımı oldu. Kitap kısa, okunaklı örnekleriyle bir programlama dili kitabının nasıl yazılacağına da örnek oldu. AWK dilinin ortak yazarıdır (adındaki K onundur); 2000'den bu yana Princeton'da ders vermektedir.

Fundamentals of Data Structures · 1976

Sahni'yle birlikte yazdığı Fundamentals of Data Structures (1976) ve Fundamentals of Computer Algorithms (1978) uzun yıllar dünyada en çok okutulan ders kitapları arasında yer aldı. Kitabın C sürümü Fundamentals of Data Structures in C, Anderson-Freed'in katılımıyla 1993'te çıktı ve bu dersin ana kitabıdır; slaytlardaki “Horowitz 2.2” gibi göndermeler bu kitabın bölümlerini gösterir. USC'de bilgisayar bilimleri bölüm başkanlığını 1990–1999 arasında yürüttü.

Horowitz–Sahni kitapları

Horowitz'le birlikte veri yapıları ve algoritmalar kitaplarını yazdı; ders kitabının sistem yaşam döngüsü, algoritmanın tanımı ve ADT anlatımı bu ortak çalışmadan gelir. Florida Üniversitesi'nde ayırt edici profesör (distinguished professor) olarak paralel hesaplama, NP-tamlık ve yaklaşım algoritmaları üzerine çalıştı. 1997'de IEEE Taylor L. Booth Eğitim Ödülü'nü aldı.

Fundamentals of Data Structures in C · 1993

Horowitz ve Sahni'nin kitabını C diline uyarlayan üçüncü yazardır; 1993'te çıkan Fundamentals of Data Structures in C beş dile çevrildi. Illinois Wesleyan University'de sosyoloji öğretim üyesi olarak başlayıp programlama dersleri verdi ve 1986'da üniversitenin bilgisayar bilimleri bölümünü kurarak ilk başkanı oldu. 4 Kasım 2012'de öldü.

Hızlı sıralamanın çözümlemesi · Algorithms in C

Knuth'un danışmanlığında 1975'te hızlı sıralama üzerine doktora tezini yazdı; medyan-3 ve küçük parçaları eklemeli sıralamayla bitirme gibi iyileştirmelerin çözümlemesi bu çalışmalardan gelir. Algorithms in C dersin ek kaynaklarındandır; hızlı sıralama bölümündeki kod bu kitaptan alınmıştır. Guibas'la birlikte kırmızı-siyah ağaçları tanımladı ve Princeton'da bilgisayar bilimleri bölümünün kurucu başkanı oldu.