로버트 타잔

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

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

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

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

컴퓨터 과학 경력 
타잔은 1985년부터 Princeton University에서 가르치고 있다. 그는 또한 코넬 대학교 (1972-73), 캘리포니아 대학교 버클리 (1973-1975), 스탠포드 대학교 (1974-1980), 뉴욕 대학교 (1981-1985)에서 학술적 직위를 역임했다. 그는 또한 NEC 연구소(1989-1997)의 펠로우였다. 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-타잔 평면성 테스트 알고리즘은 평면성 테스트를 위한 최초의 선형 시간 알고리즘이었다.

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

각주

외부 링크 

 IPEXL의 특허 디렉토리에 있는 Robert Tarjan의 특허 목록
 Princeton에 있는 Robert Tarjan의 홈페이지 .
 

그래프 이론가
포모나 (캘리포니아주) 출신
캘리포니아 공과대학교 동문
ACM 석학회원
튜링상 수상자
이론 컴퓨터 과학자
미국의 컴퓨터 과학자
미국 과학 아카데미의 회원
살아있는 사람
1948년 출생