로버트 타잔
로버트 엔드레 타잔(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]