Robert Tarjan: Graf Algoritmalarının Ustası ve Turing Ödüllü Bilgisayar Bilimcisi

Doktora yıllarında üç klasik

Bir matematikçi/bilgisayar bilimcisi için en güç başarı: 25 yaşında doktora tezini yazarken ya da hemen sonrasında birkaç klasik algoritma birden üretmek. Robert Endre Tarjan bunu yaptı:

• 1971 (PhD bitiş yılı): Tarjan'ın kuvvetli bağlı bileşenler (SCC) algoritması.
• 1972: Derinlik-öncelikli arama (DFS) analiziyle çift-bağlılık ve köprü algoritmaları.
• 1975: Union-Find karmaşıklık analizi.

Bunlardan ikincisi tek başına Turing Ödülü (1986, John Hopcroft ile birlikte) getirdi. Henüz 38 yaşında. Bilgisayar bilimi tarihinin en parlak başlangıçlarından biri.

Erken yaşam — Pomona, California

• Doğum: 30 Nisan 1948, Pomona, Kaliforniya.
• Aile: Akademisyenler. Babası Macar göçmeni, Pomona Üniversitesi öğretim üyesi.
• Lise: Erken yaşta matematik yeteneği. Berkeley Yaz Programı sayesinde lisede üniversite matematiği gördü.

Caltech (1968) ve Stanford (1971)

• Caltech BS (1968): matematik.
• Stanford PhD (1971): bilgisayar bilimi. Danışman: Robert Floyd (algoritma kuramının kurucularından).

Stanford'da yıllar, bilgisayar biliminin modern algoritma çağının doğuş yeriydi:

• Donald Knuth (TAOCP yazımı).
• John McCarthy (LISP, yapay zeka).
• Robert Floyd (Floyd-Warshall, semantic).
• Edsger Dijkstra (orada misafir).

Tarjan bu altın atmosferin öğrencisiydi.

Tarjan'ın SCC algoritması (1972)

Yönlü grafik (directed graph) $G$ verilsin. Kuvvetli bağlı bileşen (SCC) = her köşeden her köşeye yolu olan maksimum alt graf.

Eski algoritmalar SCC'leri bulmak için iki DFS yapardı. Tarjan tek bir DFS ile, $O(V + E)$ zamanda bütün SCC'leri buldu. Kullandığı araçlar:

• Her köşe için discovery time ve low-link değeri.
• Bir yığın (stack) ile aktif yol takibi.
• DFS geri dönerken low-link'lere göre SCC'leri çıkar.

Bu, modern derleyici teknolojisinde (LLVM, GCC) kontrol akışı analizinin kalbidir. Her gün milyarlarca derleme bu algoritmayı kullanır.

Union-Find karmaşıklık analizi (1975)

Önceki yazılarımızda gördüğümüz Union-Find veri yapısı. Tarjan, path compression (yol sıkıştırma) ve union by rank birlikte kullanıldığında, $n$ işlem dizisi $O(n \alpha(n))$ zaman alır — ters Ackermann.

Bu, amortize analizin (bütün dizi üzerinde ortalama maliyet) klasik örneği. Tarjan amortize teorisinin de babası sayılır.

Fibonacci heap (1984)

Michael Fredman ile birlikte: Fibonacci heap. Bir öncelik kuyruğu yapısı:

• Ekle: $O(1)$ amortize.
• Anahtar azalt: $O(1)$ amortize.
• Minimum sil: $O(\log n)$ amortize.

Dijkstra ve Prim algoritmalarının karmaşıklığını düşürür: $O((V + E) \log V)$'den $O(E + V \log V)$'ye.

Pratikte pek kullanılmaz (sabit faktörler yüksek). Ama teorik sınırı belirler.

Splay tree (1985)

Daniel Sleator ile birlikte: splay tree. Kendini ayarlayan ikili arama ağacı.

• Her erişimde erişilen düğüm köke taşınır (rotation ile).
• Sıkça erişilen elemanlar hızlanır.
• Statik optimallık varsayımı: splay tree, herhangi bir statik BST kadar iyidir.
• Dinamik optimallık varsayımı: splay tree her erişim dizisi için optimaldir. 35 yıllık açık problem.

Linux kernel'in bellek yönetiminde splay tree kullanılır.

Diğer önemli katkıları

Link-cut tree

Ağaçlar üzerinde dinamik bağlama-koparma için veri yapısı. Maximum flow algoritmalarında kullanılır.

Heavy-path decomposition

Ağaç sorgularını hızlandırmak için yapı. Competitive programming'in temel araçlarından.

Persistant data structures

Eski sürümleri kaybetmeden değiştirilebilen veri yapıları. Functional programming'in altyapısı.

Network flow algoritmaları

Tarjan, ve daha sonra Sleator, Kennedy ile birlikte, maximum flow için $O(VE \log V)$ algoritma geliştirdi (1981).

Ödüller

• Turing Ödülü (1986, Hopcroft ile): "fundamental achievements in the design and analysis of algorithms and data structures".
• Nevanlinna Prize (1983): bilgisayar bilimi matematiğinin "Fields madalyası".
• Paris Kanellakis Award (1999): Sleator ile.
• John von Neumann Theory Prize (2022).
• National Academy of Sciences üyesi.
• National Academy of Engineering üyesi.

Akademik kariyer

• Cornell (1972-73): yardımcı profesör.
• UC Berkeley (1973-75): yardımcı profesör.
• Stanford (1975-80): yardımcı profesör → doçent.
• NYU (1980-85): profesör.
• Princeton (1985-): James S. McDonnell Distinguished University Professor of Computer Science.
• AT&T Bell Labs (1985-2014): kıdemli araştırma görevlisi (Princeton ile yarım gün).

Princeton + Bell Labs (sonradan AT&T Labs ve sonra HP Labs) yarı zamanlı kombinasyonu, Tarjan'ın akademik özgürlük + endüstri kaynakları çift fakat ideal ortamı.

Tarjan stilini anlamak

Tarjan algoritmalarının ortak özelliği:

1. Sade veri yapıları + akıllı analiz.
2. Amortize karmaşıklık vurgusu (ortalama maliyet, en kötü maliyet değil).
3. Sezgisel pseudocode, ama titiz matematik kanıt.

Algoritma derslerinde "Tarjan algoritması" denildiğinde, öğrencinin akla gelmesi gereken şey: zarif fikir + dikkatli analiz.

Mirası

Modern bilgisayar bilimi büyük ölçüde Tarjan'ın eseri üzerinde:

• Tarjan SCC: derleyici altyapısı.
• Union-Find karmaşıklık: MST, ağ analizi.
• Splay tree: bellek yönetimi.
• Fibonacci heap: shortest path teorisi.
• Link-cut tree: dinamik graf.
• Persistant structures: functional programming.

Tarjan hâlâ aktif: Princeton'da, 76 yaşında, araştırma ve öğrenci danışmanlığı yapıyor.

Bir matematik öğrencisinin Stanford'da başladığı kariyer — bir doktora tezinden çıkan üç klasik — 55 yıllık akademik üretkenliği. Modern algoritma teorisinin canlı abidesi.

Bilgisayar bilimi tarihinde "graf algoritması = Tarjan" denkliği oluşmuştur. Bu, herhangi bir kişi için en yüksek tanınma şeklidir.