Veri Yapılarında Önemli İsimler

Pascal dilini tasarladı ve Algorithms + Data Structures = Programs (Algoritmalar + Veri Yapıları = Programlar, 1976) kitabını yazdı.

Kitabın adı bu dersin ana fikrini özetler: program, iyi seçilmiş bir veri yapısı üzerinde çalışan bir algoritmadır.

Derste: Bölüm 1 · Giriş

Stephen Zilles ile birlikte soyut veri tipi (abstract data type, ADT) kavramını ortaya koydu (1974) ve bu kavramı CLU dilinin temeline yerleştirdi. 2008 Turing Ödülü'nü aldı.

ADT, işlemlerin ne yaptığını nasıl gerçeklendiklerinden ayırır. Derste yığın, kuyruk, liste, eşleme ve küme tam da bu yolla tanımlanır.

Derste: Bölüm 1 · Giriş

The Art of Computer Programming (Bilgisayar Programlama Sanatı) dizisini yazdı. Algoritmaların matematiksel analizini, O, Ω ve Θ gösterimleriyle birlikte, standart bir uygulama hâline getirdi.

Arama, sıralama, ağaçlar ve hash'leme (hashing) konularını sistemli biçimde ele aldı; gerçekleme teknikleri böylece bir mühendislik disiplinine dönüştü. Doğrusal yoklamada (linear probing) beklenen yoklama sayıları da onun sonuçlarıdır.

Derste: Bölüm 2 · Algoritma Analizi, Bölüm 12 · Eşlemeler ve Hash Tabloları

Birleştirme sıralamasını (merge sort) 1945'te tanımladı. Bu algoritma, programı bellekte saklayan bir bilgisayar için yazılmış ilk algoritmalardan biridir.

Birleştirme sıralaması, böl ve fethet (divide and conquer) yaklaşımının ve kararlı (stable) bir O(n log n) sıralamanın standart örneğidir.

Derste: Bölüm 3 · Sıralama Algoritmaları

Hızlı sıralamayı (quicksort) 1959–1961 yıllarında geliştirdi. Daha sonra program doğruluğunu kanıtlamak için Hoare mantığını kurdu.

Hızlı sıralama; bölümleme (partitioning), özyineleme, yerinde düzenleme ve pivot seçiminin ortalama ve en kötü durum maliyetine etkisini bir arada gösterir.

Derste: Bölüm 3 · Sıralama Algoritmaları

Bağlı listeyi (linked list) 1955–1956'da geliştirdikleri Information Processing Language (IPL) dilinde ilk kez kullandılar.

Referanslarla birbirine bağlanan düğümler, çalışma anında büyüyüp küçülen yapıları mümkün kıldı. Bağlı listeler, bağlı yığınlar, kuyruklar ve ağaçlar bu fikrin üzerine kurulur.

Derste: Bölüm 5 · Bağlı Listeler

Kaplumbağa ve tavşan döngü tespiti algoritması ona atfedilir. 1964 tarihli Treesort 3 algoritması heap'i aşağıdan yukarıya kurar.

Farklı hızlarda ilerleyen iki işaretçi, döngüyü O(n) sürede ve O(1) ek bellekle bulur. Aşağıdan yukarıya heap oluşturma (bottom-up heap construction) O(n log n) yerine O(n) sürer.

Derste: Bölüm 5 · Bağlı Listeler, Bölüm 11 · Öncelikli Kuyruklar ve Heap

Java 1.2 (1998) ile gelen Java Collections Framework'ü (Java koleksiyonlar çerçevesi) tasarladı.

List, Set, Map ve Iterator arayüzleri ile ArrayList, LinkedList ve HashMap gibi sınıflar, tıpkı derste olduğu gibi ADT'yi onu gerçekleyen veri yapısından ayırır.

Derste: Bölüm 6 · Liste

Aritmetik formülleri çevirmek ve hesaplamak için yığın (stack) ilkesini ortaya koydular (Kellerprinzip, 1955–1957).

Son giren ilk çıkar (LIFO) ilkesiyle çalışan yığın; ifade hesaplama, derleyiciler ve metot çağrılarının yönetimi için standart araç oldu.

Derste: Bölüm 7 · Yığınlar

1920'lerde Polonya gösterimini, yani önek (prefix) gösterimini ortaya koydu. Ters Polonya gösterimi, yani sonek (postfix) gösterimi bundan türetildi.

Önek ve sonek ifadeler parantez gerektirmez; tek bir yığınla tek geçişte hesaplanır.

Derste: Bölüm 7 · Yığınlar

Ara ek (infix) ifadeyi sonek ifadeye çeviren shunting-yard (manevra sahası) algoritmasını (1961) ve ağırlıklı çizgelerde en kısa yol algoritmasını (1959) geliştirdi.

Shunting-yard bir işleç yığını ve öncelik kurallarıyla çalışır. En kısa yol algoritması ise gevşetmeyi (relaxation) en küçük öncelikli öğeyi veren bir öncelikli kuyrukla birleştirir.

Derste: Bölüm 7 · Yığınlar, Bölüm 14 · Çizgeler

İlk kendini dengeleyen ikili arama ağacı olan AVL ağacını 1962'de ortaya koydular.

Denge faktörü (balance factor) ile tek ya da çift döndürmeler (rotation) yüksekliği O(log n) tutar. Böylece arama, ekleme ve silme logaritmik kalır.

Derste: Bölüm 10 · Arama Ağaçları

Kırmızı-siyah ağacı 1978'de ortaya koydular. Çalışmaları Rudolf Bayer'in simetrik ikili B-ağaçlarına (1972) dayanır.

Düğüm renkleri ve birkaç döndürme ağacı dengede tutar. Java'daki TreeMap ve TreeSet kırmızı-siyah ağaçla gerçeklenir.

Derste: Bölüm 10 · Arama Ağaçları

Splay ağacını 1985'te ortaya koydular.

Splay ağacı denge bilgisi tutmaz. Erişilen her düğümü köke taşır; bu sayede işlemler amortize O(log n) sürer ve yakın zamanda kullanılan anahtarlara erişim hızlanır.

Derste: Bölüm 10 · Arama Ağaçları

B-ağacını Boeing Scientific Research Labs'ta geliştirdiler (1970; yayımlanışı 1972).

Düğüm başına çok sayıda çocuk (fan-out) ağacı sığ tutar; bu yüzden her aramada az sayıda disk bloğu okunur. B-ağaçları ve B+ ağaçları, veritabanı ve dosya sistemi indekslerinin temelidir.

Derste: Bölüm 10 · Arama Ağaçları

İkili heap'i (binary heap) ve heap sort algoritmasını 1964'te ortaya koydu.

Diziyle tutulan tam ikili ağaç, O(log n) sürede ekleme ve en küçük (ya da en büyük) öğeyi çıkarma sağlar. Aynı yapı, yerinde (in-place) çalışan O(n log n) bir sıralama da verir.

Derste: Bölüm 11 · Öncelikli Kuyruklar ve Heap

Fibonacci heap'i 1984'te ortaya koydular.

Anahtar küçültme (decrease-key) işleminin amortize O(1) maliyeti, özel bir heap'in en kısa yol gibi çizge algoritmalarını nasıl hızlandırabileceğini gösterir.

Derste: Bölüm 11 · Öncelikli Kuyruklar ve Heap

Zincirlemeli hash'leme fikrini 1953'te IBM içinde yazdığı bir notta önerdi.

Anahtarı doğrudan bir kovaya (bucket) eşlemek, aramayı beklenen O(1) süreye indirir. Ayrı zincirleme (separate chaining) bugün de çakışmaları çözmenin standart yollarından biridir.

Derste: Bölüm 12 · Eşlemeler ve Hash Tabloları

Ayrık kümelerin orman gösterimini (disjoint-set forest) 1964'te ortaya koydular.

Her küme bir ağaçtır ve ağacın kökü kümenin temsilcisidir. Bu yüzden birleştirme (union) ve bulma (find) işlemleri için yalnız ebeveyn bağlantıları yeter.

Derste: Bölüm 13 · Kümeler ve Ayrık Kümeler

Rütbeye göre birleştirme ile yol kısaltma birlikte kullanıldığında m işlemin O(m·α(n)) sürede bittiğini 1975'te kanıtladı.

Ters Ackermann fonksiyonu α(n) o kadar yavaş büyür ki her işlem pratikte sabit süre alır.

Derste: Bölüm 13 · Kümeler ve Ayrık Kümeler

Genişlik öncelikli aramayı (breadth-first search, BFS) 1959'da bir labirentteki en kısa yolu bulma yöntemi olarak yayımladı.

BFS, bir kuyruk yardımıyla düğümleri düzey düzey gezer ve ağırlıksız çizgelerde en kısa yolları O(V + E) sürede bulur.

Derste: Bölüm 14 · Çizgeler

Giriş derecesine (in-degree) dayanan topolojik sıralama algoritmasını 1962'de yayımladı.

Giriş derecesi sıfır olan düğümleri art arda çıkarmak, yönlü döngüsüz bir çizgenin (directed acyclic graph, DAG) düğümlerini sıralar ve varsa döngüyü ortaya çıkarır.

Derste: Bölüm 14 · Çizgeler

Minimum kapsayan ağaç (minimum spanning tree, MST) algoritmasını 1956'da yayımladı.

Kruskal algoritması kenarları ağırlığa göre sıralar. Döngü oluşturacak kenarları ayrık kümeler (union-find) yapısıyla eler.

Derste: Bölüm 14 · Çizgeler

Bell Laboratuvarları'nda çalışırken minimum kapsayan ağacı tek bir düğümden başlayıp büyüten algoritmayı “Shortest connection networks and some generalizations” (1957) makalesiyle yayımladı. Aynı yöntemi Vojtěch Jarník 1930'da, Edsger W. Dijkstra da 1959'da bağımsız olarak verdi.

Prim algoritması her adımda ağaçla ağacın dışındaki düğümler arasındaki en hafif kenarı ekler; kesim özelliği bu kenarın bir minimum kapsayan ağaçta bulunduğunu güvenceye alır. Aday kenarlar min-öncelikli kuyrukta tutulduğunda algoritma O(m log n) sürer.

Derste: Bölüm 14 · Prim Algoritması, Bölüm 14 · Kruskal ve Prim