로버트 타잔

Robert Tarjan
로버트 엔드레 타잔
Bob Tarjan.jpg
태어난 (1948-04-30) 1948년 4월 30일(74세)
시민권아메리칸
모교캘리포니아 공과대학(BS)
스탠퍼드 대학교 (MS, 박사)
로 알려져 있다알고리즘 및 데이터 구조
어워드파리 카넬라키스상(1999년)
튜링상(1986년)
네반린나상(1982)
과학 경력
필드컴퓨터 공학
기관프린스턴 대학교
뉴욕 대학교
스탠퍼드 대학교
캘리포니아 대학교 버클리
코넬 대학교
마이크로소프트 리서치
인터트러스트 테크놀로지
휴렛패커드
컴팩
NEC 리서치
벨 연구소
논문효율적인 평탄도 알고리즘 (1972)
박사 어드바이저로버트 W.플로이드
기타 학술 어드바이저도널드 크누스
박사과정 학생
웹 사이트www.cs.princeton.edu/~ret/

로버트 엔드레 타잔(Robert Endre Tarjan, 1948년 4월 30일 ~ )은 미국의 컴퓨터 과학자, 수학자이다.그는 Tarjan의 오프라인 최저 공통 조상 알고리즘을 포함한 여러 그래프 알고리즘의 발견자이자 스플레이 트리와 피보나치 힙의 공동 발명자입니다.Tarjan은 현재 Princeton University James S. McDonnell Distinguished University 교수Intertrust Technologies Corporation[1]최고 과학자입니다.

초기 생활과 교육

그는 캘리포니아 포모나에서 태어났다.헝가리에서 [2]자란 그의 아버지는 정신지체를 전문으로 하는 아동 정신과 의사였고 주립 [3]병원을 운영했다.어렸을 때, 타잔은 많은 공상 과학 소설을 읽었고 천문학자가 되고 싶었다.그는 Scientific American에서 마틴 가드너의 수학 게임 칼럼을 읽고 수학에 관심을 갖게 되었다.그는 "매우 자극적인"[4] 선생님 덕분에 8학년 때 수학에 심각한 관심을 갖게 되었다.

타잔은 고등학생 때 IBM 펀치 카드 콜레이터에서 일했습니다.그는 1964년 [3]여름 과학 프로그램에서 천문학을 공부하면서 처음으로 실제 컴퓨터로 일했다.

타잔은 1969년에 캘리포니아 공과대학에서 수학 학사 학위를 취득했습니다.스탠포드 대학에서, 그는 1971년에 컴퓨터 공학 석사 학위를 받았고 1972년에 컴퓨터 공학 박사 학위를 받았다.스탠포드에서 그는 저명한 컴퓨터 과학자인 로버트[5] 플로이드와 도널드 [6]크누스의 지도를 받았고 박사학위 논문은 효율적인 평탄화 알고리즘이었다.타잔은 컴퓨터 공학이 실질적인 [7]영향을 미칠 수 있는 수학의 한 방법이라고 믿었기 때문에 컴퓨터 과학을 그의 관심 분야로 선택했습니다.

컴퓨터 공학 경력

타잔은 [7]1985년부터 프린스턴 대학에서 가르치고 있다.그는 또한 코넬 대학교, 캘리포니아 대학교 버클리, 스탠포드 대학교, 그리고 뉴욕 대학교(1981년-1985년)에서 학사직을 역임했습니다.그는 또한 NEC 연구소의 펠로우(1989-1997)[8]였다.2013년 4월, 프린스턴의 직책 외에 Microsoft Research Silicon Valley에 입사했습니다.2014년 10월에는 Intertrust Technologies에 수석 과학자로 복귀했습니다.

Tarjan은 AT&T Bell Labs(1980–1989), Intertrust Technologies(1997–2001, 2014–현재), Compaq(2002), Hewlett Packard(2006–2013)에서 근무했습니다.

알고리즘 및 데이터 구조

Tarjan은 그래프 이론 알고리즘과 데이터 구조에 대한 선구적인 연구로 알려져 있습니다.잘 알려진 알고리즘으로는 Tarjan의 오프라인 최소 공통 조상 알고리즘과 Tarjan의 강력한 연결 성분 알고리즘이 있으며, 그는 중위수 선형 시간 선택 알고리즘의 5명의 공동 저자 중 한 명이었다.홉크로프트–타잔 평탄도 테스트 알고리즘은 평탄도 테스트를 [9]위한 최초의 선형 시간 알고리즘이었다.

Tarjan은 또한 Fibonacci 힙(나무 숲으로 구성된 힙 데이터 구조) 및 스플레이 트리(Tarjan과 Daniel Sleator가 공동 개발한 자가 조정 이진 검색 트리)와 같은 중요한 데이터 구조를 개발했습니다.또 다른 중요한 공헌은 분리 집합 데이터 구조의 분석이었다. 그는 역 애커만 [10]함수를 포함하는 최적의 런타임을 최초로 증명했다.

어워드

타잔은 1986년 존 홉크로프트와 공동으로 튜링상을 받았다.이 상에는[8] 다음과 같은 내용이 기재되어 있습니다.

알고리즘 및 데이터 구조의 설계 및 분석에서 기본적인 성과를 얻습니다.

Tarjan은 또한 1994년에 ACM 펠로우로 선출되었다.이 상에는 다음과 같은 [11]내용이 기재되어 있습니다.

데이터 구조 및 알고리즘의 설계 및 분석에서 중요한 발전을 위해 사용됩니다.

Tarjan에게 수여된 기타 상에는 다음과 같은 것이 있습니다.

특허

타잔은 적어도 18개의 미국 [6]특허를 보유하고 있다.여기에는 다음이 포함됩니다.

  • J. 벤틀리, D.Sleator 및 R. E. Tarjan, 미국 특허 4,796,003, Data Compaction[18],
  • N. Mishra, R. Schreiber 및 R. E. Tarjan, 미국 특허 7,818,272. 내부 연결 부분과 외부 개체에 의한 최대 연결 부분 간의 차이를 사용하여 임의의 무방향 그래프에서 개체의 클러스터를 발견하는 방법, 2010년[19]
  • B. Pinkas, S. Haber, R. E. Tarjan 및 T. Sander, 미국 특허 8220036, 인간 사용자와의 안전한 채널 확립, 2012[20]

연구 논문

구글 스콜라에 따르면 그는 8만 번 [21]이상 인용된 500편 이상의 연구 논문을 발표했다.

그의 주요 논문에는 다음이 포함됩니다.

  • 1972년: 깊이 우선 탐색 및 선형 그래프 알고리즘, R Tarjan, SIAM Journal on Computing 1(2), 146-160[22]
  • 1987년: Fibonacci 힙 및 네트워크 최적화 알고리즘 개선에서의 사용, ML Fredman, RE Tarjan, Journal of the ACM(JACM) 34(3), 596-615[23]
  • 1983: 데이터 구조와 네트워크 알고리즘, RE Tarjan, 산업 및 응용 수학[24] 학회
  • 1988: 최대 흐름 문제에 대한 새로운 접근법, V Goldberg, RE Tarjan, JACM(Journal of the ACM) 35(4), 921-940[25]

메모들

  1. ^ "Intertrust Leadership". intertrust.com.
  2. ^ "Jewish Recipients of the ACM A.M. Turing Award". jinfo.org.
  3. ^ 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.
  4. ^ "Robert Tarjan: The Art of the Algorithm". Hewlett-Packard. Retrieved 2010-09-05.
  5. ^ "Robert Endre Tarjan". Mathematics Genealogy Project. Retrieved 2008-01-09.
  6. ^ a b Tarjan, Robert Endre (November 15, 2019). "Curriculum Vitae" (PDF). Archived from the original (PDF) on 2019-11-23. Retrieved 2019-11-23.
  7. ^ a b "Robert Endre Tarjan: The art of the algorithm (interview)". Hewlett-Packard. September 2004. Retrieved 2008-01-09.
  8. ^ a b c d e King, V. "Robert E Tarjan — A.M. Turing Award Laureate". ACM. Retrieved 2014-01-19.
  9. ^ 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.
  10. ^ Tarjan, Robert E.; van Leeuwen, Jan (1984). "Worst-case analysis of set union algorithms". Journal of the ACM. 31 (2): 245–281. doi:10.1145/62.2160. S2CID 5363073.
  11. ^ "Fellows Award — Robert E. Tarjan". ACM. September 25, 1998. Retrieved 2005-11-18.
  12. ^ "Rolf Nevanlinna Prize Winners". International Mathematical Union. Archived from the original on 2008-12-27. Retrieved 2014-01-19.
  13. ^ "Robert Endre Tarjan". American Academy of Arts & Sciences. Retrieved 2020-06-15.
  14. ^ "Robert Tarjan". www.nasonline.org. Retrieved 2020-06-15.
  15. ^ "Dr. Robert E. Tarjan". NAE Website. Retrieved 2020-06-15.
  16. ^ "APS Member History". search.amphilsoc.org. Retrieved 2022-04-19.
  17. ^ "Caltech Names Five Distinguished Alumni" (Press release). California Institute of Technology. 2010-03-15. Archived from the original on 2010-10-10. Retrieved 2010-08-26.
  18. ^ Bentley, Jon L.; Sleator, Daniel D. K.; Tarjan, Robert E. (January 3, 1989). "United States Patent 4796003 — Data compaction".
  19. ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (October 19, 2010). "United States Patent 7818272 — Method for discovery of clusters of objects in an arbitrary undirected graph using a difference between a fraction of internal connections and maximum fraction of connections by an outside object".
  20. ^ Pinkas, Binyamin; Haber, Stuart A.; Tarjan, Robert E.; Sander, Tomas (July 10, 2012). "United States Patent 8220036 — Establishing a secure channel with a human user".
  21. ^ "Robert Tarjan". scholar.google.com. Retrieved 2021-02-02.
  22. ^ Tarjan, Robert (1972-06-01). "Depth-First Search and Linear Graph Algorithms". SIAM Journal on Computing. 1 (2): 146–160. doi:10.1137/0201010. ISSN 0097-5397.
  23. ^ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM. 34 (3): 596–615. doi:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.
  24. ^ "Back Matter". Data Structures and Network Algorithms: 125–131. January 1983. doi:10.1137/1.9781611970265.bm. ISBN 978-0-89871-187-5.
  25. ^ Goldberg, Andrew V.; Tarjan, Robert E. (1988-10-01). "A new approach to the maximum-flow problem". Journal of the ACM. 35 (4): 921–940. doi:10.1145/48014.61051. ISSN 0004-5411. S2CID 14492800.

레퍼런스

외부 링크