본문으로 이동

로버트 타잔

위키백과, 우리 모두의 백과사전.

로버트 엔드레 타잔(Robert Endre Tarjan, 1948년 4월 30일 ~ )은 미국의 컴퓨터 과학자이자 수학자이다. 그는 타잔의 오프라인 최하위 공통 조상 알고리즘 을 비롯한 여러 그래프 알고리즘의 발견자이자 스플레이 트리 와 피보나치 힙의 공동 발명가이다.[1]

어린 시절과 교육

[편집]

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

고등학교에 재학하는 동안 타잔은 IBM 펀치 카드 수집기에서 일하던 직장을 얻었다. 그는 1964년 여름 과학 프로그램에서 천문학을 공부하면서 실제 컴퓨터로 처음 작업했다.[2]

타잔은 1969년 California Institute of Technology에서 수학 학사 학위를 취득했다. 스탠포드 대학에서 1971년 컴퓨터 과학 석사 학위를 받았다. 1972년 컴퓨터 과학 박사(수학 부전공 포함). Stanford에서 그는 Robert Floyd[4]Donald Knuth[5]의 지도를 받았으며, 이 둘은 모두 저명한 컴퓨터 과학자이다. 그리고 그의 Ph.D. 논문은 효율적인 평면 알고리즘 이었다. 타잔은 컴퓨터 과학이 실제적인 영향을 미칠 수 있는 수학을 수행하는 방법이라고 믿었기 때문에 관심 분야로 컴퓨터 과학을 선택했다.[6]

컴퓨터 과학 경력

[편집]

타잔은 1985년부터 Princeton University에서 가르치고 있다.[6] 그는 또한 코넬 대학교 (1972-73), 캘리포니아 대학교 버클리 (1973-1975), 스탠포드 대학교 (1974-1980), 뉴욕 대학교 (1981-1985)에서 학술적 직위를 역임했다. 그는 또한 NEC 연구소(1989-1997)의 펠로우였다.[7] 2013년 4월에는 Princeton에서의 직책 외에 Microsoft Research Silicon Valley에 합류했다. 2014년 10월 그는 Intertrust Technologies에 수석 과학자로 다시 합류했다.

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

타잔은 그래프 이론 알고리즘 및 데이터 구조에 대한 선구적인 작업으로 유명하다. 그의 잘 알려진 알고리즘 중 일부는 타잔의 오프라인 최소 공통 조상 알고리즘 및 타잔의 강력하게 연결된 구성 요소 알고리즘 을 포함하며 중앙값 선형 시간 선택 알고리즘 의 5명의 공동 저자 중 한 명이다. Hopcroft-타잔 평면성 테스트 알고리즘은 평면성 테스트를 위한 최초의 선형 시간 알고리즘이었다.[8]

타잔은 또한 피보나치 힙 (나무 숲으로 구성된 힙 데이터 구조) 및 스플레이 트리 (자체 조정 이진 검색 트리, 타잔과 Daniel Sleator 가 공동 발명)와 같은 중요한 데이터 구조를 개발했다. 또 다른 중요한 기여는 disjoint-set 데이터 구조의 분석이었다. 그는 역 Ackermann 함수와 관련된 최적의 런타임을 최초로 증명했다.[9]

각주

[편집]
  1. “Intertrust Leadership”. 《intertrust.com》. 
  2. 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. 102–119쪽. ISBN 978-0-387-97992-2. OCLC 32240355. 
  3. “Robert Tarjan: The Art of the Algorithm”. Hewlett-Packard. 2012년 2월 6일에 원본 문서에서 보존된 문서. 2010년 9월 5일에 확인함. 
  4. “Robert Endre Tarjan”. Mathematics Genealogy Project. 2008년 1월 9일에 확인함. 
  5. Tarjan, Robert Endre (2019년 11월 15일). “Curriculum Vitae” (PDF). 2019년 11월 23일에 원본 문서 (PDF)에서 보존된 문서. 2019년 11월 23일에 확인함. 
  6. “Robert Endre Tarjan: The art of the algorithm (interview)”. Hewlett-Packard. September 2004. 2012년 2월 6일에 원본 문서에서 보존된 문서. 2008년 1월 9일에 확인함. 
  7. King, V. “Robert E Tarjan — A.M. Turing Award Laureate”. ACM. 2014년 1월 19일에 확인함. 
  8. Kocay, William; Kreher, Donald L (2005). 〈Planar Graphs〉. 《Graphs, algorithms, and optimization》. Boca Raton: Chapman & Hall/CRC. 312쪽. ISBN 978-1-58488-396-8. OCLC 56319851. 
  9. 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. 

외부 링크

[편집]