ロバート・タージャン

ロバート・タージャン（Robert Endre Tarjan、1948年4月30日 - ）は、アメリカ合衆国の計算機科学者。

などのグラフアルゴリズムを発見し、スプレー木とフィボナッチヒープというデータ構造を共同で発明した。2012年現在はプリンストン大学で計算機科学の教授を務めており、ヒューレット・パッカードのシニアフェローでもある。

学生時代まで 
カリフォルニア州ポモナで生まれる。父は精神薄弱が専門の小児精神科医で、州立病院の院長を務めていた。子どものころSFをよく読んだタージャンは、天文学者になりたいと思っていた。その後サイエンティフィック・アメリカン誌に連載されていたマーティン・ガードナーの「数学ゲーム」を読んで数学に興味を持つようになる。8年生のころ「非常に刺激的な」教師の影響で真剣に数学を志すようになる。

高校のとき、パンチカードの照合の仕事を経験。1964年の Summer Science Program で天文学を学ぶ中で、初めて実際のコンピュータに触れている。

1969年、カリフォルニア工科大学で数学の学士号を取得。スタンフォード大学に進学して計算機科学を専攻し、1971年には修士号、1972年には Ph.D. を取得した。スタンフォードでの指導教官はロバート・フロイドとドナルド・クヌースで、どちらも有名な計算機科学者である。博士論文は An Efficient Planarity Algorithm と題したものだった。タージャンは、数学が実用的インパクトを持つことができる分野として計算機科学を専門とすることを選択したという。

経歴 
その後、コーネル大学 (1972–73)、カリフォルニア大学バークレー校 (1973–1975) を経て、1977年からスタンフォード大学助教授、1981年からニューヨーク大学準教授、1985年からプリンストン大学教授を務めた。また1989年から1997年まで、NECの研究所のフェローを務めていた。

ベル研究所 (1980–1989)、InterTrust Technologies (1997–2001)、コンパック (2002) にも席を置いたことがあり、2006年以降はヒューレット・パッカードに在席している。ACMとIEEEのいくつかの委員会で委員を務め、学会誌の編集も務めたことがある。

アルゴリズムとデータ構造 
タージャンは様々な分野の問題を解くのに適した効率的なアルゴリズムやデータ構造を多数設計している。

グラフ理論のアルゴリズムとデータ構造についての先駆的業績がよく知られている。例えば、やがある。ホップクロフト-タージャンアルゴリズムは、世界初の線形時間の（グラフの）平面性判定アルゴリズムである。

また、フィボナッチヒープ（木構造群からなるヒープデータ構造）とスプレー木（平衡2分探索木の一種で、と共同開発）という重要なデータ構造を開発した。素集合データ構造の分析でも多大な貢献をしている。また、初めて逆アッカーマン関数の最適実行時間を証明した。

受賞歴 
 1982年 - ネヴァンリンナ賞受賞
 1984年 - NAS Award for Initiatives in Research
 1986年 - チューリング賞。ジョン・ホップクロフトと共同受賞。「アルゴリズムとデータ構造の設計と分析における基礎的貢献に対して」。
 1994年 - Association for Computing Machinery フェロー
 1999年 - Paris Kanellakis Award (ACM)
 2004年 - （）
 2010年 - Caltech Distinguished Alumni Award（カリフォルニア工科大学）

出典

参考文献 
 
 
 OCLC entries for Robert E Tarjan
 DBLP entry for Robert Endre Tarjan

関連項目 
 スプレー木
 素集合データ構造

外部リンク 
 DBLP: Robert Endre Tarjan
 List of Robert Tarjan's patents on IPEXL's Patent Directory
 Robert Tarjan's home page at Princeton.
 Mathematics Genealogy Project entry for Robert Endre Tarjan.

アメリカ合衆国の数学者
アメリカ合衆国の計算機科学者
オライリー・オープン・ソース賞の受賞者
ネヴァンリンナ賞の受賞者
チューリング賞受賞者
パリス・カネラキス実践的理論賞の受賞者

480430
-480430
数学に関する記事
プリンストン大学の教員
ニューヨーク大学の教員
ベル研究所の人物
ACMフェロー
米国科学アカデミー会員
全米技術アカデミー会員
カリフォルニア工科大学出身の人物
ポモナ出身の人物
1948年生
存命人物