Robert Tarjan: Verimli Algoritmaların Grameri
Herhangi bir bilgisayar bilimi öğrencisinden bir grafı derinlik öncelikli arama ile izlemesini isterseniz, bilseler de bilmeseler de, Robert Tarjan'ın bir meraktan bir disipline dönüştürdüğü bir tekniği uyguluyor olacaklardır. 1972 tarihli "Derinlik öncelikli arama ve doğrusal graf algoritmaları" adlı makalesi bugün temel bir gramer metni gibi okunur; bu çalışma alana o kadar derinlemesine nüfuz etmiştir ki, yazarının adı insanların bu konuda konuşma biçiminden neredeyse silinmiştir, ancak adı her gün kullandıkları yarım düzine yapıya bağlıdır.
Bir Matematikçinin Makinelere Giden Yolu
Robert Endre Tarjan, 30 Nisan 1948'de Pomona, Kaliforniya'da, zihinsel engelliler konusunda uzmanlaşmış çocuk psikiyatristi George Tarjan'ın oğlu olarak dünyaya geldi; küçük kardeşi James satranç büyükustası oldu. Tarjan çocukken astronom olmak istiyordu, ta ki Scientific American'daki Martin Gardner'ın bulmaca köşeleri ve sekizinci sınıftaki ilham verici bir öğretmeni onu matematiğe yönlendirene kadar. 1969'da Caltech'ten matematik lisans derecesini aldı, ardından 1971'de Stanford'da bilgisayar bilimleri yüksek lisansı ve 1972'de Robert Floyd ve Donald Knuth danışmanlığında düzlemsellik algoritmaları üzerine doktora yaptı. Daha sonra alan seçimini basitçe şöyle tanımlayacaktı: bilgisayar bilimi, pratik etkisi olabilecek matematik yapmanın bir yoluydu; bu cümle aynı zamanda tüm çalışmalarının bir tanımı olarak da ikiye katlanır.
Araç Setini Oluşturmak
Cornell, UC Berkeley, Stanford, AT&T Bell Labs, NYU, NEC Araştırma Enstitüsü, Microsoft Research, Compaq, Hewlett Packard ve Intertrust Technologies'i kapsayan ve 1985'te Princeton'da James S. McDonnell Seçkin Üniversite Profesörü olarak yerleşen Tarjan'ın kariyeri, teorik meraklar yerine yük taşıyan altyapı haline gelen çok sayıda algoritma ve veri yapısı üretti. Adı, bir graftaki güçlü bağlantılı bileşenleri bulmak için Tarjan algoritması, en küçük ortak ataları hesaplamak için çevrimdışı bir algoritma ve köprüleri bulmak için doğrusal zamanlı bir algoritma ile bağlantılıdır; bunların tümü, biçimlendirdiği derinlik öncelikli arama çerçevesi üzerine inşa edilmiştir. 1975'te, yol sıkıştırma ile birleştirilmiş union-find veri yapısının ilk kesin analizini verdi ve ters Ackermann fonksiyonunu kullanarak neredeyse sabit amortize edilmiş çalışma süresini kanıtladı; bu sonuç, gerçek dünya performansıyla o kadar sıkı bir şekilde bağlantılıdır ki, artık Kruskal'ın minimum kapsayan ağaç algoritmasından derleyici optimizasyonlarına kadar her şeyin temelini oluşturur. Bell Labs'te Daniel Sleator ile birlikte, açık denge meta verileri taşımak yerine kullanım yoluyla kendini yeniden dengeleyen kendi kendini ayarlayan ikili arama ağaçları olan splay ağaçlarını ortaklaşa icat ettiler ve onlarla birlikte, her şeyi bilen bir rakibe karşı çevrimiçi algoritmaları yargılamak için bir çerçeve olan rekabetçi analizin öncülüğünü yaptılar. 1985'te Michael Fredman ile birlikte, Dijkstra'nın en kısa yol algoritmasını ve ağ optimizasyon algoritmalarını daha önce var olan her şeyden asimptotik olarak daha hızlı hale getiren bir öncelik kuyruğu yapısı olan Fibonacci yığınlarını geliştirdi. Ders kitabı Data Structures and Network Algorithms, Frederick W. Lancaster Ödülü'nü kazandı ve alanda standart okuma haline geldi.
Hopcroft ile Düzlemsellik Atılımı
Turing Ödülü alıntısında en açık şekilde kredilendirilen tek başarı, John Hopcroft ile ortak çalışmadır: 1974'te yayınlanan, bir grafın hiçbir kenar kesişmeden bir düzleme çizilip çizilemeyeceğini test etmek için ilk doğrusal zamanlı algoritma. Düzlemsellik testi, algoritmaları onu dikkatli bir derinlik öncelikli geçiş meselesine indirgeyene kadar yavaş ve hantal bir problemdi; bu teknik çözümleri için o kadar merkeziydi ki, Tarjan'ın derinlik öncelikli aramanın önceki biçimlendirmesi, geriye dönüp bakıldığında, Hopcroft-Tarjan sonucunu mümkün kılan araç haline geldi. İkili, 1986 ACM Turing Ödülü'nü "algoritmaların ve veri yapılarının tasarımı ve analizindeki temel başarılar için" paylaştı; bu alıntı, herhangi bir tek makaleden ziyade ortak ve paralel bir çalışma bütününe kredi verir.
Dört On Yıl Boyunca Tanınma
Tarjan, 1983'te bilgisayar biliminin matematiksel yönlerine sağladığı üstün katkılardan dolayı Bilgi Biliminde Nevanlinna Ödülü'nün ilk sahibi oldu. 1986'da Turing Ödülü'nü kazandı, 1985'te Amerikan Sanat ve Bilim Akademisi'ne, 1987'de Ulusal Bilimler Akademisi'ne ve 1988'de Ulusal Mühendislik Akademisi'ne seçildi. 1999'da Paris Kanellakis Teori ve Uygulama Ödülü'nü ve 2010'da Caltech'in Seçkin Mezun Ödülü'nü aldı. Yayın kaydı, on binlerce atıf içeren 250'den fazla makaleye ulaşmaktadır ve veri yapıları ve güvenlik alanında bir düzineden fazla ABD patentine sahiptir; bu, Princeton'daki akademik teori ile Bell Labs, NEC ve Microsoft gibi endüstriyel laboratuvarlardaki uygulamalı araştırmalar arasında akıcı bir şekilde hareket eden bir kariyeri yansıtır.
Robert Neden Dahi Olarak Adlandırılır
Tarjan'ın bu kelime için durumu belirli bir şeye dayanır: sadece bireysel zor problemleri çözmedi, aynı zamanda daha önce yavaş olan tüm algoritma sınıflarını hızlı hale getiren altta yatan kombinatoryal mekanizmayı (derinlik öncelikli arama, amortize edilmiş analiz, kendi kendini ayarlama) tanımladı ve bunu bir kez değil, dört on yıl boyunca tekrar tekrar yaptı. Union-find analizi ve Hopcroft-Tarjan düzlemsellik algoritması, tam olarak akıllı hileler değil, diğer araştırmacıların yeniden kullanabileceği genel teknikler oldukları için ders kitabı materyali olmaya devam ediyor; bu yeniden kullanılabilirlik, herhangi bir tek sonuçtan daha fazla, Nevanlinna Ödülü ve Turing Ödülü komitelerinin ödüllendirdiği şeydir. Dürüst karmaşıklık, en ünlü sonucu olan doğrusal zamanlı düzlemsellik algoritmasının açıkça John Hopcroft ile ortak bir çalışma olması ve Turing Ödülü alıntısının her iki adamı da ortaklaşa kredilendirmesi, herhangi birini yalnız bir dahi olarak taçlandırmamasıdır; ödülün kendisi, alanın bunu tekil bir icat değil, işbirlikçi bir başarı olarak gördüğünün kanıtıdır. Tarjan'ın diğer dönüm noktası niteliğindeki sonuçları da benzer şekilde isimlendirilmiş ortak yazarlarla inşa edilmiştir: splay ağaçları Daniel Sleator ile, Fibonacci yığınları Michael Fredman ile. Tartışmasız olan, adını taşıyan temel, hala öğretilen sonuçların yoğunluğudur; bu, alanda çok az kişinin eşleştiği bir rekordur.
Miras
Derinlik öncelikli arama, union-find, splay ağaçları veya Fibonacci yığınlarını öğrenen her bilgisayar bilimi öğrencisi, aslında yazılmalarından on yıllar sonra hala Tarjan'ın makaleleri tarafından eğitilmektedir. Çalışması, derleyicilerin, ağ yönlendirmenin ve coğrafi bilgi sistemlerinin altında yatar ve kullanıcılarının çoğu adını bilmez; bu, tamamen başarılı olan altyapı düzeyindeki matematiğin sessiz kaderidir. Yetmişli yaşlarına kadar yeni sonuçlar üretmeye devam etti, Princeton'daki öğretim üyeliği ile Intertrust Technologies'de baş bilim insanı ve Microsoft ve Hewlett Packard'da araştırmacı rolleri arasında gidip geldi; bu kariyer şekli, onu tamamen akademik bir figür olarak görmeye karşı çıkar: En çok atıf alan çalışmalarının çoğu, üniversite boşluğunda değil, endüstriyel araştırma laboratuvarlarında yapıldı, test edildi ve uygulandı. Titiz matematik yayınlarken aynı zamanda pratik sistemlerin patentini alan bu ikili yaşam, onun kaydını fikirleri dergilerle sınırlı kalan teorisyenlerden ayıran şeyin bir parçasıdır.
