ロバート・タージャン

ロバート・アンドレ・タージャンの生涯と業績

ロバート・アンドレ・タージャン（Robert Endre Tarjan）は、1948年4月30日にアメリカのカリフォルニア州ポモナで誕生しました。彼の父親は精神薄弱の専門医であり、州立病院の院長を務めていました。タージャンは子供の頃からサイエンスフィクションを好み、天文学者になる夢を抱いていました。しかし、マーティン・ガードナーが『サイエンティフィック・アメリカン』誌で連載していた「数学ゲーム」を読み、数学への興味が湧きました。さらに、中学校で出会った刺激的な教師に影響を受け、本格的に数学を学ぶことを決意します。

高校時代、タージャンはパンチカード照合の仕事を体験し、1964年のSummer Science Programで天文学を学びながら初めてコンピュータに触れました。その後、1969年にはカリフォルニア工科大学で数学の学士号を取得し、スタンフォード大学に進学。1971年には修士号、1972年にはPh.D.を取得しました。指導教官には著名な計算機科学者であるロバート・フロイドとドナルド・クヌースが名を連ねており、彼の博士論文は「An Efficient Planarity Algorithm」という題名でした。タージャンは、計算機科学が数学の実用的な側面を実現する分野と考え、そちらに進む道を選びました。

経歴

キャリアを積む中で、タージャンはコーネル大学やカリフォルニア大学バークレー校を経て、スタンフォード大学の助教授、ニューヨーク大学の準教授、そして1985年からはプリンストン大学で教授として活躍します。また、1989年から1997年までNECの研究所でフェローを務め、ベル研究所やInterTrust Technologies、コンパックにも関与しました。2006年以降はヒューレット・パッカードに所属し、ACMやIEEEの各委員会で活動、学会誌の編集にも携わりました。

アルゴリズムとデータ構造

タージャンは多くの異なる問題に対応した効率的なアルゴリズムやデータ構造を設計しており、特にグラフ理論における業績が幅広く認識されています。彼が発見したオフライン最小共通祖先アルゴリズムや強連結成分アルゴリズムはその一例です。彼の平面性判定アルゴリズムは、歴史上初の線形時間での判定が可能なものであり、その革新性は高く評価されています。また、フィボナッチヒープやスプレー木など、重要なデータ構造も彼の手によって開発されました。さらに、逆アッカーマン関数の最適実行時間を初めて証明したことでも知られています。

受賞歴

タージャンの業績は数多くの賞によって認められています。1982年にはネヴァンリンナ賞、1984年にはNAS Award for Initiatives in Researchを受賞。1986年にはジョン・ホップクロフトと共にチューリング賞を受賞し、アルゴリズムとデータ構造の設計における基礎的貢献が評価されました。その後も、Association for Computing Machineryのフェローに選出されたり、ブレーズ・パスカル・メダルを受賞するなど、数々の栄誉に輝いています。

タージャンの貢献は計算機科学における新しい道を切り開き、今なお多くの研究者に影響を与え続けています。彼の業績は計算機科学の発展に欠かせないものです。

もう一度検索