ja.wikipedia.org

ロバート・タージャン - Wikipedia

  • ️Fri Apr 30 1948

ロバート・タージャン

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Robert Tarjan
ロバート・タージャン

ロバート・タージャン(2010)

生誕 1948年4月30日（76歳）
アメリカ合衆国の旗 アメリカ合衆国・カリフォルニア州ポモナ
国籍 アメリカ合衆国の旗 アメリカ合衆国
研究分野 計算機科学
研究機関 コーネル大学
カリフォルニア大学バークレー校
スタンフォード大学
ニューヨーク大学
プリンストン大学
ヒューレット・パッカード
出身校 カリフォルニア工科大学
スタンフォード大学
博士課程
指導教員		 ロバート・フロイド
主な業績 アルゴリズムとデータ構造
主な受賞歴 ネヴァンリンナ賞(1982)
チューリング賞(1986)
プロジェクト:人物伝
テンプレートを表示

ロバート・アンドレ・タージャン（Robert Endre Tarjan、1948年4月30日 - ）は、アメリカ合衆国の計算機科学者。 タージャンのオフライン最小共通祖先アルゴリズム（英語版）などのグラフアルゴリズムを発見し、スプレー木とフィボナッチヒープというデータ構造を共同で発明した。2012年現在はプリンストン大学で計算機科学の教授を務めており、ヒューレット・パッカードのシニアフェローでもある[1]。

カリフォルニア州ポモナで生まれる。父は精神薄弱が専門の小児精神科医で、州立病院の院長を務めていた[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分探索木の一種で、ダニエル・スレイター（英語版）と共同開発）という重要なデータ構造を開発した。素集合データ構造の分析でも多大な貢献をしている。また、初めて逆アッカーマン関数の最適実行時間を証明した。

  1. ^ “HP Fellows: Robert Endre Tarjan”. Hewlett-Packard. 2008年1月9日閲覧。
  2. ^ 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
  3. ^ a b c “Robert Endre Tarjan: The art of the algorithm (interview)”. Hewlett-Packard (September 2004). 2008年1月9日閲覧。
  4. ^ “Robert Endre Tarjan”. Mathematics Genealogy Project. 2008年1月9日閲覧。
  5. ^ Robert, Tarjan. “Curriculum Vitae”. 2012年8月21日閲覧。
  6. ^ 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
  7. ^ http://media.caltech.edu/press_releases/13332