ロバート・タージャン
ロバート・アンドレ・タージャン（Robert Endre Tarjan、1948年4月30日 - ）は、アメリカ合衆国の計算機科学者。 タージャンのオフライン最小共通祖先アルゴリズムなどのグラフアルゴリズムを発見し、スプレー木とフィボナッチヒープというデータ構造を共同で発明した。2012年現在はプリンストン大学で計算機科学の教授を務めており、ヒューレット・パッカードのシニアフェローでもある[1]。
| Robert Tarjan ロバート・タージャン | |
|---|---|
 ロバート・タージャン(2010) | |
| 生誕 |
1948年4月30日（76歳） アメリカ合衆国・カリフォルニア州ポモナ |
| 国籍 |
アメリカ合衆国 |
| 研究分野 | 計算機科学 |
| 研究機関 |
コーネル大学 カリフォルニア大学バークレー校 スタンフォード大学 ニューヨーク大学 プリンストン大学 ヒューレット・パッカード |
| 出身校 |
カリフォルニア工科大学 スタンフォード大学 |
| 博士課程 指導教員 | ロバート・フロイド |
| 主な業績 | アルゴリズムとデータ構造 |
| 主な受賞歴 |
ネヴァンリンナ賞(1982) チューリング賞(1986) |
| プロジェクト:人物伝 | |
学生時代まで
編集カリフォルニア州ポモナで生まれる。父は精神薄弱が専門の小児精神科医で、州立病院の院長を務めていた[2]。子どものころSFをよく読んだタージャンは、天文学者になりたいと思っていた。その後サイエンティフィック・アメリカン誌に連載されていたマーティン・ガードナーの「数学ゲーム」を読んで数学に興味を持つようになる。8年生のころ「非常に刺激的な」教師の影響で真剣に数学を志すようになる[3]。
高校のとき、パンチカードの照合の仕事を経験。1964年の Summer Science Program で天文学を学ぶ中で、初めて実際のコンピュータに触れている[2]。
1969年、カリフォルニア工科大学で数学の学士号を取得。スタンフォード大学に進学して計算機科学を専攻し、1971年には修士号、1972年には Ph.D. を取得した。スタンフォードでの指導教官はロバート・フロイド[4]とドナルド・クヌース[5]で、どちらも有名な計算機科学者である。博士論文は An Efficient Planarity Algorithm と題したものだった。タージャンは、数学が実用的インパクトを持つことができる分野として計算機科学を専門とすることを選択したという[3]。
経歴
編集その後、コーネル大学 (1972–73)、カリフォルニア大学バークレー校 (1973–1975) を経て、1977年からスタンフォード大学助教授、1981年からニューヨーク大学準教授、1985年からプリンストン大学教授を務めた[3]。また1989年から1997年まで、NECの研究所のフェローを務めていた[要出典]。
ベル研究所 (1980–1989)、InterTrust Technologies (1997–2001)、コンパック (2002) にも席を置いたことがあり、2006年以降はヒューレット・パッカードに在席している。ACMとIEEEのいくつかの委員会で委員を務め、学会誌の編集も務めたことがある[要出典]。
アルゴリズムとデータ構造
編集タージャンは様々な分野の問題を解くのに適した効率的なアルゴリズムやデータ構造を多数設計している。
グラフ理論のアルゴリズムとデータ構造についての先駆的業績がよく知られている。例えば、タージャンのオフライン最小共通祖先アルゴリズムやタージャンの強連結成分アルゴリズムがある。ホップクロフト-タージャン平面性判定アルゴリズムは、世界初の線形時間の（グラフの）平面性判定アルゴリズムである[6]。
また、フィボナッチヒープ（木構造群からなるヒープデータ構造）とスプレー木（平衡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（カリフォルニア工科大学）[7]
出典
編集- ^ “HP Fellows: Robert Endre Tarjan”. Hewlett-Packard. 2008年1月9日閲覧。
- ^ a b Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. “Robert E. Tarjan: In Search of Good Structure”. Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Copernicus/Springer. pp. 102–119. ISBN 978-0-387-97992-2. OCLC 32240355
- ^ a b c “Robert Endre Tarjan: The art of the algorithm (interview)”. Hewlett-Packard (September 2004). 2008年1月9日閲覧。
- ^ “Robert Endre Tarjan”. Mathematics Genealogy Project. 2008年1月9日閲覧。
- ^ Robert, Tarjan. “Curriculum Vitae”. 2012年8月21日閲覧。
- ^ Kocay, William; Kreher, Donald L (2005). “Planar Graphs”. Graphs, algorithms, and optimization. Boca Raton: Chapman & Hall/CRC. p. 312. ISBN 978-1-58488-396-8. OCLC 56319851
- ^ http://media.caltech.edu/press_releases/13332
参考文献
編集- Tarjan, Robert E. (1983). Data structures and network algorithms. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-187-5. OCLC 10120539
- Tarjan, Robert E.; Polya, George; Woods, Donald R (1983). Notes on introductory combinatorics. Boston: Birkhauser. ISBN 978-0-8176-3170-3. OCLC 10018128
- OCLC entries for Robert E Tarjan
- DBLP entry for Robert Endre Tarjan