ロバート・タージャン
ロバート・タージャン
生まれる
ロバート・エンドレ・タルジャン
（1948年4月30日）1948年4月30日
ポモナ、カリフォルニア州、米国
教育カリフォルニア工科大学( BS )スタンフォード大学( MS、PhD )
知られているアルゴリズムとデータ構造
受賞歴パリ・カネラキス賞（1999年）チューリング賞（1986年）ネヴァンリンナ賞（1982年）
科学者としてのキャリア
フィールドコンピュータサイエンス
機関プリンストン大学、ニューヨーク大学、スタンフォード大学、カリフォルニア大学バークレー校、コーネル大学、マイクロソフト研究所、インタートラストテクノロジーズ、ヒューレット・パッカード、コンパック、NECリサーチ、ベル研究所
論文効率的な平面性アルゴリズム （1972）
博士課程の指導教員ロバート・W・フロイド
その他の学術アドバイザードナルド・クヌース
博士課程の学生
Webサイトwww .cs .princeton .edu /~ret /

ロバート・エンドレ・タージャン（1948年4月30日生まれ）は、アメリカのコンピュータ科学者、数学者です。彼は、強連結成分アルゴリズムを含む複数のグラフ理論アルゴリズムの発見者であり、スプレー木とフィボナッチヒープの共同発明者でもあります。タージャンは現在、プリンストン大学のジェームズ・S・マクドネル特別教授（コンピュータサイエンス）を務めています。彼とジョン・ホップクロフトは1986年のACMチューリング賞を受賞しました。

私生活と教育

彼はカリフォルニア州ポモナで生まれました。彼の父ジョージ・タージャン（1912-1991）はハンガリーで育ち、[ 1 ]知的障害を専門とする児童精神科医で、州立病院を経営していました。[ 2 ]ロバート・タージャンの弟ジェームズはチェスのグランドマスターになりました。[ 3 ]子供の頃、ロバート・タージャンはSF小説をたくさん読み、天文学者になりたかったそうです。彼はサイエンティフィック・アメリカン誌に掲載されたマーティン・ガードナーの数学ゲームコラムを読んで数学に興味を持つようになりました。彼は「非常に刺激的な」先生のおかげで、8年生の時に本格的に数学に興味を持つようになりました。[ 4 ]

高校時代、タージャンはIBMのパンチカード照合装置で働き始めました。彼が初めて本物のコンピュータに触れたのは、1964年のサマーサイエンスプログラムで天文学を学んだ時でした。 [ 2 ]

タージャンは1969年にカリフォルニア工科大学で数学の学士号を取得しました。スタンフォード大学では1971年にコンピュータサイエンスの修士号、 1972年にコンピュータサイエンスの博士号（数学副専攻）を取得しました。スタンフォード大学では、ロバート・フロイド[ 5 ]とドナルド・クヌース[ 6 ]という2人とも非常に著名なコンピュータ科学者の指導を受け、博士論文は「効率的な平面アルゴリズム」でした。タージャンがコンピュータサイエンスを自分の興味のある分野として選んだのは、コンピュータサイエンスが実用的な影響を与える数学の手法であると信じていたからです。[ 7 ]

タージャンは現在、ニュージャージー州プリンストンとシリコンバレーに住んでいます。彼はナイラ・リズクと結婚しています。[ 8 ] 彼にはアリス・タージャン、ソフィー・ザワッキ、マキシン・タージャンの3人の娘がいます。[ 9 ]

コンピュータサイエンスのキャリア

タージャンは1985年からプリンストン大学で教鞭を執っている。[ 7 ]また、コーネル大学（1972～1973年）、カリフォルニア大学バークレー校（1973～1975年）、スタンフォード大学（1974～1980年）、ニューヨーク大学（1981～1985年）でも教鞭を執った。また、NEC研究所の研究員（1989～1997年）も務めた。[ 10 ] 2013年4月、プリンストン大学での職に加え、マイクロソフト・リサーチ・シリコンバレーに加わった。2014年10月、インタートラスト・テクノロジーズの主任研究員として復帰した。

Tarjan は、AT&T ベル研究所 (1980 ～ 1989 年)、Intertrust Technologies (1997 ～ 2001 年、2014 年～現在)、Compaq (2002 年)、および Hewlett Packard (2006 ～ 2013 年) で勤務しました。

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

タージャンはグラフ理論アルゴリズムとデータ構造に関する先駆的な研究で知られています。彼の著名なアルゴリズムには、タージャンのオフライン最小共通祖先アルゴリズム、タージャンの強連結成分アルゴリズム、タージャンのブリッジ検出アルゴリズムなどがあり、彼は中央値の中央値線形時間選択アルゴリズムの5人の共著者の1人でした。ホップクロフト・タージャンの平面性検定アルゴリズムは、平面性検定のための最初の線形時間アルゴリズムでした。[ 11 ]

タージャンは、フィボナッチヒープ（木の森からなるヒープデータ構造）やスプレー木（自己調整型二分探索木。タージャンとダニエル・スレイターが共同で発明）といった重要なデータ構造も開発しました。もう一つの重要な貢献は、分離集合データ構造の解析であり、逆アッカーマン関数の最適実行時間を初めて証明しました。[ 12 ]

受賞歴

タージャンは1986年にジョン・ホップクロフトと共同でチューリング賞を受賞しました。受賞の表彰状には次のように 記されています[ 10 ] 。

アルゴリズムとデータ構造の設計と分析における基礎的な業績に対して。

タージャンは1994年にACMフェローにも選出された。この賞の表彰状には次のように記されている。[ 13 ]

データ構造とアルゴリズムの設計と分析における画期的な進歩に対して。

Tarjan が受賞したその他の賞には以下のものがあります。

選定された出版物

タージャンの論文は合計94,000回以上引用されている。[ 20 ] 最も引用されている論文は以下の通りである。

  • 1972年：深さ優先探索と線形グラフアルゴリズム、R Tarjan、SIAM Journal on Computing 1 (2)、146-160 [ 21 ]
  • 1987年：フィボナッチヒープと改良ネットワーク最適化アルゴリズムにおけるその利用、ML Fredman、RE Tarjan、Journal of the ACM (JACM) 34 (3)、596-615 [ 22 ]
  • 1983年：データ構造とネットワークアルゴリズム、RE Tarjan、産業応用数学協会[ 23 ]
  • 1988年：最大フロー問題への新しいアプローチ、Vゴールドバーグ、REタージャン、ACMジャーナル（JACM）35（4）、921-940 [ 24 ]

特許

タージャンは少なくとも18件の米国特許を保有している。[ 6 ]これらには以下が含まれる。

  • J. Bentley、D. Sleator、およびR.E. Tarjan、米国特許第4,796,003号、データ圧縮、1989年[ 25 ]
  • N. ミシュラ、R. シュライバー、および RE タージャン、米国特許 7,818,272、内部接続の割合と外部オブジェクトによる接続の最大割合の差を使用して任意の無向グラフ内のオブジェクトのクラスターを発見する方法、2010年[ 26 ]
  • B. Pinkas、S. Haber、RE Tarjan、T. Sander、米国特許8220036、人間のユーザーとの安全なチャネルの確立、2012年[ 27 ]

注記

  1. ^ 「ACM AMチューリング賞のユダヤ人受賞者」jinfo.org。
  2. ^ a bシャシャ、デニス・エリオット、ラゼール、キャシー・A. (1998) [1995]. 「ロバート・E・タージャン：優れた構造を求めて」『Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists』コペルニクス/シュプリンガー、pp.  102–119 . ISBN 978-0-387-97992-2. OCLC  32240355 .
  3. ^メルビン・シャブシン（1984年8月）「ジョージ・タージャン医学博士 第112代大統領（1983-1984年）」アメリカ精神医学ジャーナル141 ( 8): 931–934 . doi : 10.1176/ajp.141.8.931 . PMID 6380318 . 
  4. ^ 「ロバート・タージャン：アルゴリズムの芸術」ヒューレット・パッカード。2012年2月6日時点のオリジナルよりアーカイブ。 2010年9月5日閲覧。
  5. ^ 「ロバート・エンドレ・タルジャン」。数学系譜プロジェクト。2008年1月9日閲覧。
  6. ^ a b Tarjan, Robert Endre (2019年11月15日). “Curriculum Vitae” (PDF) . 2019年11月23日時点のオリジナル(PDF)からのアーカイブ。 2019年11月23日閲覧。
  7. ^ a b「ロバート・エンドレ・タルジャン：アルゴリズムの芸術（インタビュー）」ヒューレット・パッカード、2004年9月。 2012年2月6日時点のオリジナルよりアーカイブ。 2008年1月9日閲覧。
  8. ^ “ネイラ・リズクとロバート・タージャン” .ニューヨークタイムズ紙。 2013 年 7 月。
  9. ^ 「ボブ・タージャン生誕60周年記念シンポジウムの写真」 DIMACS、2008年5月。
  10. ^ a b c d e King, V. 「Robert E Tarjan — AM Turing Award Laureate」 ACM . 2014年1月19日閲覧。
  11. ^ Kocay, William ; Kreher, Donald L (2005). 「平面グラフ」.グラフ、アルゴリズム、そして最適化. ボカラトン: Chapman & Hall/CRC. p.  312. ISBN 978-1-58488-396-8. OCLC  56319851 .
  12. ^ Tarjan, Robert E. ; van Leeuwen, Jan (1984). 「集合和集合アルゴリズムの最悪ケース解析」 . Journal of the ACM . 31 (2): 245– 281. doi : 10.1145/62.2160 . S2CID 5363073 . 
  13. ^ 「Fellows Award — Robert E. Tarjan」 ACM 1998年9月25日. 2005年11月18日閲覧。
  14. ^ 「ロルフ・ネヴァンリンナ賞受賞者」国際数学連合。2008年12月27日時点のオリジナルよりアーカイブ。 2014年1月19日閲覧。
  15. ^ 「ロバート・エンドレ・タルジャン」アメリカ芸術科学アカデミー. 2020年6月15日閲覧。
  16. ^ 「ロバート・タージャン」www.nasonline.org . 2020年6月15日閲覧。
  17. ^ “ロバート・E・タージャン博士” . NAE ウェブサイト。2020年6月15日に取得。
  18. ^ 「APS会員履歴」 . search.amphilsoc.org . 2022年4月19日閲覧。
  19. ^ 「Caltech、5人の優秀な卒業生を選出」（プレスリリース）カリフォルニア工科大学2010年3月15日オリジナルより2010年10月10日時点のアーカイブ。 2010年8月26日閲覧。
  20. ^ 「Robert Tarjan Google Scholar Page」 . Google Scholar . 2023年3月6日閲覧。
  21. ^ Tarjan, Robert (1972-06-01). 「深さ優先探索と線形グラフアルゴリズム」 . SIAM Journal on Computing . 1 (2): 146– 160. doi : 10.1137/0201010 . ISSN 0097-5397 . S2CID 16467262 .  
  22. ^ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). 「フィボナッチヒープと改良ネットワーク最適化アルゴリズムにおけるその利用」 . Journal of the ACM . 34 (3): 596– 615. doi : 10.1145/28869.28874 . ISSN 0004-5411 . S2CID 7904683 .  
  23. ^ 「バックマター」 .データ構造とネットワークアルゴリズム: 125– 131. 1983年1月. doi : 10.1137/1.9781611970265.bm . ISBN 978-0-89871-187-5。
  24. ^ Goldberg, Andrew V.; Tarjan, Robert E. (1988-10-01). 「最大フロー問題への新しいアプローチ」 . Journal of the ACM . 35 (4): 921– 940. doi : 10.1145/48014.61051 . ISSN 0004-5411 . S2CID 14492800 .  
  25. ^ Bentley, Jon L.; Sleator, Daniel DK; Tarjan, Robert E. (1989年1月3日). 「米国特許4796003 - データ圧縮」 .
  26. ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (2010年10月19日). 「米国特許7818272 - 内部接続の割合と外部オブジェクトによる接続の最大割合の差を用いて、任意の無向グラフ内のオブジェクトのクラスターを発見する方法」 .
  27. ^ Pinkas, Binyamin; Haber, Stuart A.; Tarjan, Robert E.; Sander, Tomas (2012年7月10日). 「米国特許8220036 — 人間のユーザーとの安全なチャネルの確立」 .

参考文献

ウィキメディア・コモンズには、ロバート・タージャンに関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Robert_Tarjan&oldid=1334543392」より取得