Loading article…
ロバート・タージャン | |
|---|---|
 | |
| 生まれる | ロバート・エンドレ・タルジャン 1948年4月30日 |
| 母校 | カリフォルニア工科大学( BS ) スタンフォード大学( MS、PhD ) |
| 知られている | アルゴリズムとデータ構造 |
| 受賞歴 | パリ・カネラキス賞(1999) チューリング賞(1986) ネヴァンリンナ賞(1982) |
| 科学者としてのキャリア | |
| フィールド | コンピュータサイエンス |
| 機関 | プリンストン大学 ニューヨーク大学 スタンフォード大学 カリフォルニア大学バークレー校 コーネル大学マイクロソフト 研究所インタートラストテクノロジーズヒューレット・パッカードコンパックNEC研究所ベル研究所 |
| 論文 | 効率的な平面アルゴリズム (1972) |
| 博士課程の指導教員 | ロバート・W・フロイド |
| その他の学術アドバイザー | ドナルド・クヌース |
| 博士課程の学生 | |
| Webサイト | 詳しくはこちら |
ロバート・エンドレ・タージャン（1948年4月30日生まれ）は、アメリカのコンピュータ科学者、数学者。彼は、強連結成分アルゴリズムを含むいくつかのグラフ理論アルゴリズムの発見者であり、スプレー木とフィボナッチヒープの共同発明者でもある。タージャンは現在、プリンストン大学のジェームズ・S・マクドネルコンピュータサイエンス特別教授である。
私生活と教育
彼はカリフォルニア州ポモナで生まれた。彼の父ジョージ・タージャン（1912-1991）はハンガリーで育ち、[1]精神遅滞を専門とする小児精神科医で、州立病院を経営していた。[2]ロバート・タージャンの弟ジェームズはチェスのグランドマスターになった。[3]子供の頃、ロバート・タージャンはSF小説をたくさん読み、天文学者になりたかった。彼はサイエンティフィック・アメリカン誌のマーティン・ガードナーの数学ゲームコラムを読んで数学に興味を持った。彼は「とても刺激的な」教師のおかげで、8年生の時に数学に真剣に興味を持つようになった。[4]
高校生の頃、タージャンはIBMのパンチカード照合機で働き始めました。1964年にサマーサイエンスプログラムで天文学を勉強していた時に、初めて本物のコンピュータを扱いました。 [2]
タージャンは1969年にカリフォルニア工科大学で数学の学士号を取得した。スタンフォード大学では1971年にコンピュータサイエンスの修士号を、1972年にはコンピュータサイエンス（数学副専攻）の博士号を取得した。スタンフォードでは、非常に著名なコンピュータ科学者であるロバート・フロイド[5]と ドナルド・クヌース[6]の指導を受け、博士論文は「効率的な平面アルゴリズム」であった。タージャンがコンピュータサイエンスを自分の興味のある分野として選んだのは、コンピュータサイエンスが実用的な影響を与える数学の方法であると信じていたからである[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人の共著者の一人でした。ホップクロフト-タージャンの平面性テストアルゴリズムは、平面性テストのための最初の線形時間アルゴリズムでした。[11]
タージャンは、フィボナッチヒープ（木の森からなるヒープデータ構造）やスプレイツリー（自己調整型二分探索木、タージャンとダニエル・スレーターが共同発明）などの重要なデータ構造も開発しました。もう1つの重要な貢献は、分離集合データ構造の解析であり、逆アッカーマン関数を含む最適実行時間を初めて証明しました。[12]
受賞歴
タージャンは1986年にジョン・ホップクロフトと共同でチューリング賞を受賞しました。受賞の理由については[10]に次のように記されています。
アルゴリズムとデータ構造の設計と分析における基礎的な業績に対して。
タージャンは1994年にACMフェローにも選出された。この賞の表彰状には次のように記されている。[13]
データ構造とアルゴリズムの設計と分析における画期的な進歩に対して。
Tarjan が受賞したその他の賞には以下のものがあります。
- ネヴァンリンナ情報科学賞（1983年） [10] – 最初の受賞者[14]
- アメリカ芸術科学アカデミー会員、1985年選出[15]
- 米国科学アカデミー研究奨励賞（1984年）[10]
- 米国科学アカデミー会員、1987年選出[16]
- 米国工学アカデミー会員、1988年選出[17]
- アメリカ哲学協会会員、1990年選出[18]
- パリ・カネラキス理論と実践賞、 ACM（1999）[10]
- カリフォルニア工科大学優秀卒業生賞（2010年）[19]
主な出版物
タージャンの論文は合計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、およびRE 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]
注記
- ^ 「ACM AMチューリング賞のユダヤ人受賞者」jinfo.org。
- ^ ab Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. 「Robert E. Tarjan: 優れた構造を求めて」. 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.
- ^メルビン・シャブシン（1984 年8月） 。「ジョージ・タージャン医学博士、第112代大統領、1983-1984年」。アメリカ精神医学ジャーナル。141 （8）：931-934。doi ：10.1176/ajp.141.8.931。
- ^ 「ロバート・タージャン：アルゴリズムの芸術」ヒューレット・パッカード。 2010年9月5日閲覧。
- ^ 「Robert Endre Tarjan」。数学系譜プロジェクト。2008年1月9日閲覧。
- ^ ab Tarjan, Robert Endre (2019年11月15日). 「履歴書」(PDF) 。 2019年11月23日時点のオリジナル(PDF)からアーカイブ。 2019年11月23日閲覧。
- ^ ab 「Robert Endre Tarjan: アルゴリズムの芸術 (インタビュー)」。Hewlett-Packard。2004 年 9 月。2008 年 1 月 9 日閲覧。
- ^ 「ナイラ・リズクとロバート・タージャン」ニューヨーク・タイムズ、2013年7月。
- ^ 「ボブ・タージャン生誕60周年記念シンポジウムの写真」DIMACS、2008年5月。
- ^ abcde King, V. 「ロバート・E・タージャン — AMチューリング賞受賞者」ACM . 2014年1月19日閲覧。
- ^ Kocay, William; Kreher, Donald L (2005). 「平面グラフ」。グラフ、アルゴリズム、最適化。ボカラトン: Chapman & Hall/CRC。p. 312。ISBN 978-1-58488-396-8. OCLC 56319851.
- ^ Tarjan, Robert E. ; van Leeuwen, Jan (1984). 「集合和集合アルゴリズムの最悪ケース分析」Journal of the ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID 5363073.
- ^ 「Fellows Award — Robert E. Tarjan」ACM 1998年9月25日2005年11月18日閲覧。
- ^ 「ロルフ・ネヴァンリンナ賞受賞者」国際数学連合。2008年12月27日時点のオリジナルよりアーカイブ。2014年1月19日閲覧。
- ^ 「ロバート・エンドレ・タルジャン」アメリカ芸術科学アカデミー。 2020年6月15日閲覧。
- ^ “ロバート・タージャン”. www.nasonline.org . 2020年6月15日閲覧。
- ^ “ロバート・E・タージャン博士”. NAEのウェブサイト。2020年6月15日に取得。
- ^ 「APS会員履歴」. search.amphilsoc.org . 2022年4月19日閲覧。
- ^ 「Caltech が 5 人の著名な卒業生を指名」(プレスリリース)。カリフォルニア工科大学。2010 年 3 月 15 日。2010 年 10 月 10 日時点のオリジナルよりアーカイブ。2010年 8 月 26 日閲覧。
- ^ 「Robert Tarjan Google Scholar Page」。Google Scholar 。 2023年3月6日閲覧。
- ^ Tarjan, Robert (1972-06-01). 「深さ優先探索と線形グラフアルゴリズム」. SIAM Journal on Computing . 1 (2): 146–160. doi :10.1137/0201010. ISSN 0097-5397. S2CID 16467262.
- ^ 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.
- ^ 「バックマター」。データ構造とネットワークアルゴリズム: 125–131。1983年1月。doi : 10.1137 /1.9781611970265.bm。ISBN 978-0-89871-187-5。
- ^ 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.
- ^ Bentley, Jon L.; Sleator, Daniel DK; Tarjan, Robert E. (1989 年 1 月 3 日)。「米国特許 4796003 - データ圧縮」。
- ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (2010 年 10 月 19 日)。「米国特許 7818272 - 内部接続の割合と外部オブジェクトによる接続の最大割合の差を使用して、任意の無向グラフ内のオブジェクトのクラスターを検出する方法」。
- ^ Pinkas, Binyamin; Haber, Stuart A.; Tarjan, Robert E.; Sander, Tomas (2012 年 7 月 10 日)。「米国特許 8220036 — 人間のユーザーとの安全なチャネルの確立」。
参考文献
- Tarjan, Robert E. (1983)。データ構造とネットワークアルゴリズム。フィラデルフィア: 産業応用数学協会。ISBN 978-0-89871-187-5. OCLC 10120539.
- Tarjan, Robert E.; Pólya, George; Woods, Donald R. (1983).入門的組合せ論に関するノート。ボストン: Birkhauser。ISBN 978-0-8176-3170-3. OCLC 10018128.
- Robert E Tarjan の OCLC エントリー
- DBLP書誌サーバーの Robert E. Tarjan
外部リンク
ウィキメディア・コモンズには、ロバート・タージャンに関連するメディアがあります。
- DBLP書誌サーバーの Robert E. Tarjan
- IPEXL の特許ディレクトリにある Robert Tarjan の特許リスト
- プリンストン大学の Robert Tarjan のホームページ。
- 数学系譜プロジェクトのロバート・エンドレ・タルジャン