ロバート・タージャン：効率的なアルゴリズムの文法

計算機科学の学生に深さ優先探索でグラフをたどるよう頼めば、彼らは意識しているかどうかにかかわらず、ロバート・タージャンが好奇心の対象から学問へと変えた手法を実行していることになります。彼の1972年の論文「Depth-first search and linear graph algorithms（深さ優先探索と線形グラフアルゴリズム）」は、今日では基礎的な文法のテキストのように読まれています。この分野に深く浸透しているため、著者の名前が人々の会話からほとんど消えてしまっているほどですが、それでも彼の名前は彼らが毎日使用する半ダースもの構造に関連付けられています。

数学者の機械への道

ロバート・エンドレ・タージャン（Robert Endre Tarjan）は1948年4月30日、カリフォルニア州ポモナで生まれました。父のジョージ・タージャンは知的障害を専門とする児童精神科医で、弟のジェームズはチェスのグランドマスターになりました。タージャンは少年時代、天文学者になりたいと思っていましたが、サイエンティフィック・アメリカン誌のマーティン・ガードナーのパズルコラムと、中学2年生の時の刺激的な教師の影響で、数学の道に進むことになりました。1969年にカリフォルニア工科大学（Caltech）で数学の学士号を取得し、1971年にスタンフォード大学で計算機科学の修士号、1972年に博士号を取得しました。博士論文はロバート・フロイドとドナルド・クヌースの指導の下、平面性アルゴリズムに関するものでした。彼は後に、自分の分野の選択を簡潔にこう説明しました。「計算機科学は、実用的な影響を与えることができる数学を行う方法である」。この一文は、彼の全業績の説明としても通用するものです。

ツールキットの構築

タージャンのキャリアは、コーネル大学、カリフォルニア大学バークレー校、スタンフォード大学、AT&Tベル研究所、ニューヨーク大学、NEC研究所、マイクロソフトリサーチ、コンパック、ヒューレット・パッカード、インタートラスト・テクノロジーズを経て、1985年にプリンストン大学のジェームズ・S・マクドネル特別大学教授に就任するまで続きました。彼が生み出したアルゴリズムとデータ構造の多くは、理論的な好奇心の対象ではなく、負荷を支えるインフラストラクチャとなりました。彼の名前は、グラフ内の強連結成分を見つけるためのタージャンのアルゴリズム、最小共通祖先を計算するためのオフラインアルゴリズム、ブリッジを見つけるための線形時間アルゴリズムに関連付けられており、これらはすべて彼が形式化した深さ優先探索のフレームワークに基づいています。1975年には、パス圧縮と組み合わせたUnion-Findデータ構造の最初の正確な分析を行い、逆アッカーマン関数を使用して、ほぼ一定の償却実行時間を証明しました。この結果は現実世界のパフォーマンスと密接に関連しており、クラスカルの最小全域木アルゴリズムからコンパイラの最適化に至るまで、あらゆるものの基礎となっています。ベル研究所ではダニエル・スレーターと共に、明示的なバランスメタデータを持たずに使用を通じて自己調整する二分探索木であるスプレイ木を共同発明し、それらを用いて、全知の敵対者に対するオンラインアルゴリズムを評価するためのフレームワークである競争分析の先駆けとなりました。1985年にはマイケル・フレッドマンと共にフィボナッチヒープを開発しました。これは優先度付きキュー構造であり、ダイクストラの最短経路アルゴリズムやネットワーク最適化アルゴリズムを、それ以前のものよりも漸近的に高速にしました。彼の教科書『Data Structures and Network Algorithms』はフレデリック・W・ランカスター賞を受賞し、この分野の標準的な読み物となりました。

ホップクロフトとの平面性のブレイクスルー

彼のチューリング賞の引用で最も明確に評価されている単一の業績は、ジョン・ホップクロフトとの共同研究です。1974年に発表された、エッジが交差することなくグラフを平面上に描画できるかどうかをテストするための最初の線形時間アルゴリズムです。平面性テストは、彼らのアルゴリズムがそれを慎重な深さ優先トラバーサルの問題に還元するまでは、遅くて扱いにくい問題でした。この手法は彼らの解決策の中心であったため、タージャンの以前の深さ優先探索の形式化は、振り返ってみればホップクロフト・タージャンの結果を可能にしたツールとなりました。二人は1986年のACMチューリング賞を「アルゴリズムとデータ構造の設計と分析における基本的な業績」に対して共同受賞しました。この引用は、単一の論文ではなく、共同および並行した一連の業績を評価するものです。

40年にわたる評価

タージャンは1983年に情報科学におけるネヴァンリンナ賞の最初の受賞者となり、計算機科学の数学的側面への傑出した貢献を称えられました。1986年にチューリング賞を受賞し、1985年にアメリカ芸術科学アカデミー、1987年に全米科学アカデミー、1988年に全米工学アカデミーの会員に選出されました。1999年にはパリ・カネラキス理論・実践賞を、2010年にはカリフォルニア工科大学のDistinguished Alumni Awardを受賞しました。彼の出版記録は250本以上の論文に及び、引用数は数万件に達します。データ構造とセキュリティに関する12以上の米国特許を保持しており、プリンストンでの学術理論と、ベル研究所、NEC、マイクロソフトなどの産業研究所での応用研究の間を流動的に行き来したキャリアを反映しています。

ロバートが天才と呼ばれる理由

タージャンが天才と呼ばれる理由は、彼が単に個々の難しい問題を解決しただけでなく、深さ優先探索、償却分析、自己調整といった基礎となる組み合わせ論的メカニズムを特定し、それまで遅かったアルゴリズムのクラス全体を高速化したことにあります。しかも、それを一度だけでなく、40年にわたって繰り返し行いました。Union-Find分析やホップクロフト・タージャンの平面性アルゴリズムが教科書に載り続けているのは、それらが巧妙なトリックではなく、他の研究者が再利用できる一般的な手法だからです。その再利用性こそが、ネヴァンリンナ賞やチューリング賞の委員会が評価したものです。正直な複雑さは、彼の最も有名な結果である線形時間平面性アルゴリズムがジョン・ホップクロフトとの共同研究であり、チューリング賞の引用がどちらか一人をソロの天才として冠するのではなく、両名を共同で評価している点です。賞そのものが、この分野がこれを単一の発明ではなく共同の業績と見なしている証拠です。タージャンの他の画期的な結果も同様に、名前付きの共著者と共に構築されました。スプレイ木はダニエル・スレーターと、フィボナッチヒープはマイケル・フレッドマンと共同開発されました。議論の余地がないのは、彼の名前を冠した、今なお教えられている基礎的な結果の密度の高さであり、この分野でこれに匹敵する記録を持つ者はほとんどいません。

遺産

深さ優先探索、Union-Find、スプレイ木、またはフィボナッチヒープを学ぶすべての計算機科学の学生は、事実上、それらが書かれてから数十年経った今でもタージャンの論文から教わっています。彼の仕事は、コンパイラ、ネットワークルーティング、地理情報システムの下にあり、ユーザーのほとんどは彼の名前を知りません。これは、完全に成功したインフラストラクチャレベルの数学の静かな運命です。彼は70代になっても新しい結果を生み出し続け、プリンストンの教員と、インタートラスト・テクノロジーズのチーフサイエンティスト、マイクロソフトやヒューレット・パッカードの研究者としての役割の間を行き来しました。このキャリアの形自体が、彼を純粋に学術的な人物として扱うことに反対する論拠となっています。彼の最も引用された仕事の多くは、大学の真空の中ではなく、産業研究ラボの中で行われ、テストされ、適用されました。厳密な数学を発表しながら実用的なシステムを特許化するというこの二重の人生は、彼の記録を、アイデアがジャーナルの中に留まった理論家たちと区別する要素の一部です。