ロバート・タージャン

ロバート・アンドレ・タージャン（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（カリフォルニア工科大学）http://media.caltech.edu/press_releases/13332

 出典 

 参考文献 


 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.

Category:20世紀アメリカ合衆国の数学者
Category:21世紀アメリカ合衆国の数学者
Category:アメリカ合衆国の計算機科学者
Category:チューリング賞受賞者
480430
-480430
Category:数学に関する記事
Category:プリンストン大学の教員
Category:ニューヨーク大学の教員
Category:スタンフォード大学の教員
Category:マサチューセッツ工科大学の教員
Category:ベル研究所の人物
Category:ACMフェロー
Category:SIAMフェロー
Category:グッゲンハイム・フェロー
Category:アメリカ科学振興協会フェロー
Category:米国科学アカデミー会員
Category:全米技術アカデミー会員
Category:アメリカ哲学協会会員
Category:アメリカ芸術科学アカデミー会員
Category:カリフォルニア工科大学出身の人物
Category:ポモナ出身の人物
Category:1948年生
Category:存命人物