로버트 타잔
1. 개요
로버트 타잔은 그래프 이론 알고리즘 및 데이터 구조 분야에서 선구적인 업적을 남긴 컴퓨터 과학자이다. 1969년 캘리포니아 공과대학교에서 수학 학사 학위를, 1972년 스탠퍼드 대학교에서 컴퓨터 과학 박사 학위를 받았다. 타잔은 튜링상, 네반린나상 등을 수상했으며, 홉크로프트-타잔 평면성 테스트 알고리즘, 피보나치 힙, 스플레이 트리 등 다양한 알고리즘과 데이터 구조를 개발했다. 1985년부터 프린스턴 대학교에서 교수로 재직 중이며, AT&T 벨 연구소, 마이크로소프트 등에서도 근무했다.
| 이름 | 로버트 엔드레 타잔 |
|---|---|
| 원어명 | Robert Endre Tarjan |
| 출생일 | 1948년 4월 30일 |
| 출생지 | 미국, 캘리포니아주 포모나 |
| 국적 | 미국 |
| 분야 | 컴퓨터 과학 |
| 직장 | 프린스턴 대학교 뉴욕 대학교 스탠퍼드 대학교 캘리포니아 대학교 버클리 코넬 대학교 마이크로소프트 리서치 인터트러스트 테크놀로지스 휴렛-팩커드 컴팩 NEC 리서치 벨 연구소 |
| 모교 | 캘리포니아 공과대학교 (이학사) 스탠퍼드 대학교 (이학 석사, 철학 박사) |
| 박사 학위 논문 제목 | 효율적인 평면성 알고리즘 (An Efficient Planarity Algorithm) |
| 박사 학위 논문 URL | An Efficient Planarity Algorithm |
| 박사 학위 논문 연도 | 1972년 |
| 지도 교수 | 로버트 W. 플로이드 |
| 학문적 조언자 | 도널드 크누스 |
| 주목할 만한 제자 | 토마스 렝가우어 모니카 헨칭거 라메시 시타라만 대니얼 슬리터 제프 웨스트브룩 |
| 알려진 업적 | 알고리즘과 자료 구조 |
| 수상 | 파리 카넬라키스 상(1999년) 튜링상(1986년) 네반린나상(1982년) |
| 웹사이트 | 로버트 E. 타잔 웹사이트 |
-
포모나 (캘리포니아주) 출신 -
톰 웨이츠
톰 웨이츠는 1949년 캘리포니아에서 태어난 미국의 가수, 작곡가, 배우로, 독특한 음악 스타일과 쉰 목소리, 소외된 자들의 삶을 묘사하는 가사, 그리고 영화계에서의 활약으로 유명하며 평론가들의 찬사와 함께 음악계에 큰 영향을 미쳤다. -
포모나 (캘리포니아주) 출신 -
질 켈리
질 켈리는 미국의 배우이자 성인 영화 배우로서, 10년 이상 420편이 넘는 성인 영화에 출연했고 여러 할리우드 영화에도 출연했으며, 다양한 성인 영화 시상식에서 수많은 상을 수상하며 성공적인 경력을 쌓았고, 자신의 프로덕션 회사를 설립하여 운영했으며, 양성애자임을 공개적으로 밝혔다. -
그래프 이론가 -
아서 케일리
아서 케일리는 대수학, 대수기하학, 조합론 등 여러 분야에 공헌한 영국의 수학자이자 변호사로, 삼차 곡면의 27개 선을 발견하고 규칙 곡면의 대수기하학적 이론을 창시했으며, 법조인 활동과 수학 연구를 병행하다 케임브리지 대학교 교수로 순수 수학 연구와 교육에 헌신하여 그의 업적을 기리는 다양한 수학 용어들이 존재한다. -
그래프 이론가 -
에르되시 팔
에르되시 팔은 헝가리 태생의 수학자로 조합론, 그래프 이론, 수론 등 다양한 분야에서 1,500편이 넘는 논문을 발표하며 20세기 수학계에 큰 영향을 미쳤고, 공동 연구를 즐기며 "괴짜 수학자"라는 별명을 얻었으며, 그와 공동 연구를 통해 연결된 정도를 나타내는 "에르되시 수"라는 개념이 만들어졌다. -
튜링상 수상자 -
얀 르쿤
프랑스 컴퓨터 과학자 얀 르쿤은 딥 러닝 분야의 선구자로서 합성곱 신경망을 제안하여 이미지 인식 발전에 기여했고, 뉴욕 대학교 교수이자 메타 AI 연구소 초대 소장을 역임했으며, 제프리 힌턴, 요슈아 벤지오와 함께 튜링상을 공동 수상했다. -
튜링상 수상자 -
마빈 민스키
마빈 민스키는 인지 과학자이자 인공지능 연구의 선구자이며, MIT 교수로 재직하며 MIT 컴퓨터과학·인공지능연구소를 설립하고, 헤드 마운트형 그래픽 디스플레이 발명, 로고 프로그래밍 언어 개발 등의 업적을 남겼다.
2. 어린 시절과 교육
로버트 타잔은 캘리포니아 포모나에서 태어났다. 그의 아버지는 정신지체를 전문으로 하는 아동 정신과 의사였으며 국립 병원을 운영했다. 어렸을 때 타잔은 공상과학 소설을 많이 읽었고 천문학자가 되기를 원했다. 그는 Scientific American에서 마틴 가드너의 수학 게임 칼럼을 읽은 후 수학에 관심을 갖게 되었다. 그는 "매우 자극적인" 선생님 덕분에 8학년 때 수학에 진지하게 관심을 갖게 되었다.
고등학교에 재학하는 동안 타잔은 IBM 펀치 카드 수집기에서 일했다. 그는 1964년 서머 사이언스 프로그램에서 천문학을 공부하면서 실제 컴퓨터로 처음 작업했다.
타잔은 1969년 캘리포니아 공과대학교에서 수학 학사 학위를 취득했다. 스탠포드 대학교에서 1971년 컴퓨터 과학 석사 학위를, 1972년 컴퓨터 과학 박사 학위(수학 부전공)를 받았다. 스탠포드에서 그는 로버트 플로이드와 도널드 커누스의 지도를 받았으며, 이 둘은 모두 저명한 컴퓨터 과학자이다. 그의 박사 학위 논문은 효율적인 평면 알고리즘이었다. 타잔은 컴퓨터 과학이 실제적인 영향을 미칠 수 있는 수학을 수행하는 방법이라고 믿었기 때문에 관심 분야로 컴퓨터 과학을 선택했다.
3. 컴퓨터 과학 경력
타잔은 그래프 이론 알고리즘 및 데이터 구조에 대한 선구적인 연구로 유명하다. 코넬 대학교(1972-73), 캘리포니아 대학교 버클리(1973-1975), 스탠퍼드 대학교(1974-1980), 뉴욕 대학교(1981-1985) 등에서 학술적 직위를 역임했으며, 1985년부터 프린스턴 대학교에서 가르치고 있다. 그는 또한 NEC 연구소(1989-1997)의 펠로우였으며, 2013년 4월 마이크로소프트 Research Silicon Valley에 합류했고, 2014년 10월 Intertrust Technologies에 수석 과학자로 다시 합류했다.
타잔은 AT&T 벨 연구소(1980–1989), Intertrust Technologies(1997–2001, 2014–현재), 컴팩(2002), 휴렛 팩커드(2006–2013)에서 근무했다.
3.1. 알고리즘과 데이터 구조
로버트 타잔은 그래프 이론 알고리즘 및 데이터 구조에 대한 선구적인 연구로 유명하다. 그의 잘 알려진 알고리즘에는 타잔의 오프라인 최소 공통 조상 알고리즘, 타잔의 강결합 요소 알고리즘, 타잔의 브리지 찾기 알고리즘이 있으며, 중앙값 선형 시간 선택 알고리즘의 5명의 공동 저자 중 한 명이다. 호프크로프트-타잔 평면성 테스트 알고리즘은 평면성 테스트를 위한 최초의 선형 시간 알고리즘이었다.
타잔은 또한 피보나치 힙 (나무 숲으로 구성된 힙 데이터 구조) 및 스플레이 트리 (자체 조정 이진 탐색 트리, 타잔과 다니엘 슬레이터가 공동 발명)와 같은 중요한 데이터 구조를 개발했다. 또 다른 중요한 기여는 disjoint-set 데이터 구조의 분석이었다. 그는 역 아커만 함수와 관련된 최적의 런타임을 최초로 증명했다.
4. 수상 경력
로버트 타잔은 존 홉크로프트와 공동으로 1986년 튜링상을 수상했다. 이 상의 인용문에는 "알고리즘과 자료 구조의 설계 및 분석에 대한 근본적인 업적"이라고 명시되어 있다.
타잔은 1994년에 ACM 펠로우로 선출되었으며, "자료 구조 및 알고리즘의 설계 및 분석에 대한 획기적인 발전"에 대한 공로를 인정받았다.
타잔의 기타 수상 경력은 다음과 같다.
| 연도 | 상 이름 | 수여 기관 | 비고 |
|---|---|---|---|
| 1982년 | 네반린나상 | ||
| 1983년 | 네반린나상 | 정보 과학 분야 | 최초 수상자 |
| 1984년 | 미국 국립 과학원 연구 혁신상 | 미국 국립 과학원 | |
| 1985년 | 미국 예술 과학 아카데미 회원 | ||
| 1986년 | 튜링상 | 존 홉크로프트와 공동 수상, "알고리즘과 데이터 구조의 설계와 분석에 대한 기본적인 공헌" | |
| 1987년 | 미국 국립 과학원 회원 | ||
| 1988년 | 미국 공학 아카데미 회원 | ||
| 1990년 | 미국 철학회 회원 | ||
| 1994년 | ACM 펠로우 | ACM | |
| 1999년 | 파리스 카넬라키스상 | ACM | |
| 2004년 | 블레즈 파스칼 메달독일어 | 유럽 과학 아카데미영어 | |
| 2010년 | 캘리포니아 공과대학교(칼텍) 공로 동문상 | 캘리포니아 공과대학교 | , |
5. 특허
로버트 타잔은 최소 18개의 미국 특허를 보유하고 있다. 그 중 일부는 다음과 같다.
* J. 벤틀리, D. 슬레이터, R. E. 타잔, 미국 특허 4,796,003, 데이터 압축, 1989
* N. 미쉬라, R. 슈라이버, R. E. 타잔, 미국 특허 7,818,272, 내부 연결의 비율과 외부 객체의 최대 연결 비율의 차이를 사용하여 임의의 무방향 그래프에서 객체 클러스터를 발견하는 방법, 2010
* B. 핀카스, S. 하버, R. E. 타잔, T. 샌더, 미국 특허 8220036, 사람 사용자와 안전한 채널 설정, 2012
6. 개인적인 삶
캘리포니아주 포모나에서 태어났다. 그의 아버지 조지 타잔(1912-1991)은 헝가리에서 자랐으며, 정신 지체 전문 소아 정신과 의사였고, 주립 병원을 운영했다. 로버트 타잔의 남동생 제임스는 체스 그랜드마스터가 되었다. 로버트 타잔은 어릴 때 많은 과학 소설을 읽었고, 천문학자가 되기를 원했다. 그는 사이언티픽 아메리칸에 실린 마틴 가드너의 수학 게임 칼럼을 읽고 수학에 관심을 갖게 되었다. 그는 "매우 자극적인" 선생님 덕분에 중학교 2학년 때 수학에 진지하게 관심을 갖게 되었다.
타잔은 고등학교 재학 중 IBM 펀치 카드 분류기와 함께 일하는 직업을 얻었다. 1964년 서머 사이언스 프로그램에서 천문학을 공부하면서 처음으로 실제 컴퓨터를 접했다.
1969년 캘리포니아 공과대학교에서 수학 학사 학위를 받았다. 스탠포드 대학교에서 1971년 컴퓨터 과학 석사 학위를 받았고, 1972년에는 컴퓨터 과학 철학 박사 학위(수학 부전공)를 받았다. 스탠포드에서 그는 로버트 W. 플로이드와 도널드 커누스의 지도를 받았으며, 그의 박사 학위 논문은 효율적인 평면성 알고리즘이었다. 타잔은 컴퓨터 과학이 실질적인 영향을 미칠 수 있는 수학을 하는 방식이라고 믿었기 때문에 자신의 관심 분야로 컴퓨터 과학을 선택했다.
현재 뉴저지주 프린스턴과 실리콘 밸리에서 거주하고 있다. 그는 나일라 리즈크와 결혼했다. 그는 앨리스 타잔, 소피 자와키, 맥신 타잔의 세 딸을 두고 있다.