Robert E. Tarjan
(미국 컴퓨터과학자, 1948~)
.........알고리즘과 자료구조의 설계, 분석에 발전에 공헌, 1986 튜링상을 수상 ............
Robert E. Tarjan Homepage : Princeton Univ., Computer Science
로버트 앙드레 타잔은 1948 년 캘리포니아 주 포모나에서 태어났다. 어린 나이부터 그는 과학에 흥미를 느꼈다. 소아정신과에서 정신 지체 분야 전문의였던 타잔의 아버지는 주립 병원을 운영하고 있었다. 타잔은 중학교 시절 그 곳에서 일자리를 얻어 그가 '예비 컴퓨터 (precomputer)' 라 불렀던 IBM 천공 카드 조합기들에 대한 작업을 하였다. 1964 년 중학 과정에 이어진 하계과학 프로그램에서 타잔은 처음으로 실제 컴퓨터들을 가지고 작업을 하게 되었다.
칼테크에서 타잔은 수학을 전공하였지만, 컴퓨터 과학쪽에서도 대학원생들에게 개설된 과정은 빠짐없이 수강하였다. 스탠퍼드는 도널드 크누스와 존 매커시를 포함해 컴퓨터 과학의 선구적 인물들을 배출했다는 것을 자랑스럽게 여기고 있었다.
또 한명의 고무적인 인물은 코넬에서 안식년을 맞아 스탠퍼드에 와 있었던 존 홉크로프트였다. 그는 타잔이 대학원 2 학년 과정을 시작하기 전이었던 여름에 그 곳에 도착하여 그의 옆방에 들어왔다. 그 두 사람은 곧 공동 연구를 시작하여 마침내 1986 에는 튜링상을 수상하기에 이른다........
그가 스탠퍼드 대학에서 존 홉크로프트 (John Hopcroft) 와 함께 한 박사 과정의 연구는 평면 검사 (planarity testing) 와 그 밖의 그래프 알고리즘들에 대한 것으로서, 보다 효율적인 칩 레이아웃에서 보다 나은 도형 (map) 레이아웃에 이르기까지 다양한 응용 프로그램을 탄생시켰다. 이들 알고리즘은 모든 학부생들이 배우게 되는 '깊이 우선 검색 (depth-first search)' 이라는 프로그래밍 기술의 위력을 강조한다. 또한, 깊이 우선 검색은 게임이나 스프레드 시트, 그래픽 프로그램 등의 분야에서도 하루에 수십억 차례씩 사용되고 있다. 이후 타잔이 댄 슬리터 (Dan Sleator), 앤드류 골드버그 (Andrew Goldberg) 와 함께 진행하였던 효율적인 네트워크 흐름에 대한 연구는 설계자들이 연안의 석유에서 전화 통화에 이르기까지 모든 것의 흐름을 개선하기 위해서는 네트워크에서 각각의 연결에 얼마나 많은 용량을 부여해야 하는지를 알아내는 데 도움을 주었다. 뿐만 아니라, 상향 트리 (up-tree) 와 사선 트리 (splay-tree) 라고 알려져 있는 한 쌍의 단순한 자료 구조에 대한 그의 연구는 알고리즘의 효율성을 측정하는 새로운 기법을 도입시켰다.
닐 사나크 (Neil Sarnak), 슬리터, 제임스 드리스콜 (James Driscoll) 등과 함께 한 또 다른 연구는 현재 뿐만 아니라 과거에 대한 정보까지 보유할 수 있는 자료 구조를 아주 효율적인 형태로 제시하였다. 그처럼 '영속적인' 자료 구조는 오늘날 로봇 공학과 데이터 베이스 시스템 분야에서 점점 더 사용이 늘고 있다.
타잔은 또한 컴퓨터 과학의 연구에 문화적 변화를 가져왔다. 그것은 적절한 '큰 아이디어 (big idea)' 를 얻은 다음, 그것을 가장 효율적으로 지원할 자료 구조를 만들어 내는 방식이다. 그를 비롯해 여러 사람이 그러한 전략으로 다이크스트라의 최단 경로 알고리즘과 또 다른 기본 알고리즘들에서 중대한 개선을 밀어붙였다.
그의 연구는 미니멀리즘 (minimalism), 세련됨, 그리고 보편성을 향한 무언의 추구 등으로 특징지을 수 있다.
"좋은 아이디어는 보다 단순해져 원래 목표했던 것 이외의 문제들까지 해결할 수 있는 방법을 가지고 있습니다."
"난 보다 응용력 있는 유형의 수학이라는 이유 때문에 컴퓨터 과학을 하고 싶었습니다. 대체로 논리와 정리 증명의 측면에서 인공지능에 흥미를 느꼈지요. 하지만 정작 스탠퍼드에 들어가 AI 과정을 시작하게 되었을 때에는 그것이 아주 모호한 것이라는 결론을 내렸습니다."
"크누스는 우선 고무적이었습니다. 그가 아주 구체적인 분석에 관심의 초점을 두었다는 점에서 고무적이었지요. 그는 항상 정확한 결과를 얻어내는 수학의 엄밀성에 흥미를 보이고 있었습니다."
"난 매커시의 기호 처리 과정을 택했습니다. 그 강의는 대부분 리스프에 대한 내용이었지요. 그는 학생들에게 그래프가 평면인지 아닌지를 식별하는 프로그램을 쓰도록 제안하였습니다." ............ (Dennis Shasha 1995)
term :
수학 (Mathematics) 알고리즘 (Algorithm) 그래프 (Graph) 인공지능 (Artificial Intelligence) 깊이우선 탐색 (Depth First Search) John Hopcroft John McCarthy Donald Knuth A.M. Turing Award
site :
paper :