로버트 타잔: 효율적인 알고리즘의 문법
컴퓨터 과학 전공자에게 깊이 우선 탐색으로 그래프를 추적하라고 하면, 그들은 알든 모르든 로버트 타잔이 호기심의 대상에서 학문으로 바꾼 기법을 실행하고 있는 것입니다. 그의 1972년 논문 "깊이 우선 탐색과 선형 그래프 알고리즘(Depth-first search and linear graph algorithms)"은 오늘날 기초 문법 교과서처럼 읽힙니다. 이 분야에 너무나 철저히 흡수되어 저자의 이름이 사람들이 그것에 대해 이야기하는 방식에서 거의 사라졌지만, 그의 이름은 그들이 매일 사용하는 수많은 구조와 연결되어 있습니다.
수학자의 기계로 향하는 길
로버트 엔드레 타잔(Robert Endre Tarjan)은 1948년 4월 30일 캘리포니아주 포모나에서 태어났습니다. 아버지 조지 타잔은 지적 장애를 전문으로 하는 아동 정신과 의사였고, 남동생 제임스는 체스 그랜드마스터가 되었습니다. 타잔은 어릴 때 천문학자가 되고 싶었지만, 사이언티픽 아메리칸의 마틴 가드너의 퍼즐 칼럼과 8학년 때의 영감을 주는 선생님 덕분에 수학으로 마음을 돌렸습니다. 1969년 칼텍에서 수학 학사 학위를 받았고, 1971년 스탠퍼드에서 컴퓨터 과학 석사, 1972년 박사 학위를 받았습니다. 박사 논문은 로버트 플로이드와 도널드 커누스의 지도하에 평면성 알고리즘에 관한 것이었습니다. 그는 나중에 자신의 분야 선택을 간단히 이렇게 설명했습니다. 컴퓨터 과학은 실질적인 영향을 미칠 수 있는 수학을 하는 방법이라는 것이며, 이 문장은 그의 전체 업적에 대한 설명으로도 통합니다.
툴킷 구축
타잔의 경력은 코넬, UC 버클리, 스탠퍼드, AT&T 벨 연구소, NYU, NEC 연구소, 마이크로소프트 리서치, 컴팩, 휴렛 패커드, 인터트러스트 테크놀로지를 거쳐 1985년 프린스턴 대학교의 제임스 S. 맥도넬 석좌 교수로 부임하기까지 이어졌습니다. 그가 만들어낸 알고리즘과 데이터 구조는 이론적 호기심을 넘어 인프라를 지탱하는 기반이 된 경우가 많았습니다. 그의 이름은 그래프에서 강연결 요소를 찾는 타잔 알고리즘, 최소 공통 조상을 계산하는 오프라인 알고리즘, 브리지를 찾는 선형 시간 알고리즘과 연결되어 있으며, 이 모든 것은 그가 형식화한 깊이 우선 탐색 프레임워크를 기반으로 합니다. 1975년에는 경로 압축과 결합된 유니온-파인드 데이터 구조에 대한 최초의 정확한 분석을 제시하여, 역 아커만 함수를 사용하여 거의 일정한 상각 실행 시간을 증명했습니다. 이 결과는 실제 성능과 밀접하게 연결되어 있어 크루스칼의 최소 신장 트리 알고리즘부터 컴파일러 최적화에 이르기까지 모든 것의 기초가 됩니다. 벨 연구소에서는 대니얼 슬리터와 함께 명시적인 균형 메타데이터 없이 사용을 통해 스스로 재균형을 잡는 이진 탐색 트리인 스플레이 트리를 공동 발명했으며, 이를 통해 전지전능한 적에 맞서 온라인 알고리즘을 평가하는 프레임워크인 경쟁 분석의 선구자가 되었습니다. 1985년에는 마이클 프레드먼과 함께 우선순위 큐 구조인 피보나치 힙을 개발하여 다익스트라의 최단 경로 알고리즘과 네트워크 최적화 알고리즘을 이전보다 점근적으로 더 빠르게 만들었습니다. 그의 교과서 Data Structures and Network Algorithms는 프레데릭 W. 랭커스터 상을 수상하며 이 분야의 표준 읽을거리가 되었습니다.
홉크로프트와의 평면성 돌파구
그의 튜링상 수상 이유에서 가장 명시적으로 언급된 단일 업적은 존 홉크로프트와의 공동 연구입니다. 1974년에 발표된, 에지가 교차하지 않고 그래프를 평면에 그릴 수 있는지 테스트하는 최초의 선형 시간 알고리즘입니다. 평면성 테스트는 그들의 알고리즘이 이를 신중한 깊이 우선 탐색 문제로 환원하기 전까지는 느리고 다루기 힘든 문제였습니다. 이 기법은 그들의 해결책의 핵심이었기에, 타잔의 이전 깊이 우선 탐색 형식화는 돌이켜보면 홉크로프트-타잔 결과를 가능하게 한 도구가 되었습니다. 두 사람은 1986년 ACM 튜링상을 "알고리즘 및 데이터 구조 설계와 분석에 대한 근본적인 업적"으로 공동 수상했습니다. 이 인용은 단일 논문이 아닌 공동 및 병행 연구 전체를 평가하는 것입니다.
40년에 걸친 인정
타잔은 1983년 정보 과학 분야 네반린나 상의 첫 번째 수상자가 되어 컴퓨터 과학의 수학적 측면에 대한 뛰어난 공헌을 인정받았습니다. 1986년 튜링상을 수상했고, 1985년 미국 예술 과학 아카데미, 1987년 미국 국립 과학 아카데미, 1988년 미국 국립 공학 아카데미 회원으로 선출되었습니다. 1999년 파리 카넬라키스 이론 및 실습 상을, 2010년 칼텍의 Distinguished Alumni Award를 받았습니다. 그의 출판 기록은 250편 이상의 논문에 달하며 인용 수는 수만 건에 이릅니다. 데이터 구조와 보안 분야에서 12개 이상의 미국 특허를 보유하고 있으며, 이는 프린스턴에서의 학문적 이론과 벨 연구소, NEC, 마이크로소프트와 같은 산업 연구소에서의 응용 연구 사이를 유연하게 오간 경력을 반영합니다.
로버트가 천재라고 불리는 이유
타잔이 천재라고 불리는 이유는 그가 단순히 어려운 문제를 해결했을 뿐만 아니라, 깊이 우선 탐색, 상각 분석, 자기 조정과 같은 근본적인 조합론적 메커니즘을 식별하여 이전에 느렸던 알고리즘 클래스 전체를 빠르게 만들었기 때문입니다. 그것도 한 번이 아니라 40년에 걸쳐 반복했습니다. 유니온-파인드 분석과 홉크로프트-타잔 평면성 알고리즘이 여전히 교과서에 실리는 이유는 그것들이 영리한 트릭이 아니라 다른 연구자들이 재사용할 수 있는 일반적인 기법이기 때문입니다. 그 재사용성이야말로 네반린나 상과 튜링상 위원회가 보상한 핵심입니다. 솔직히 복잡한 점은 그의 가장 유명한 결과인 선형 시간 평면성 알고리즘이 존 홉크로프트와의 공동 연구이며, 튜링상 인용이 두 사람을 공동으로 평가하고 있다는 점입니다. 상 자체가 이 분야가 이것을 단일 발명이 아닌 공동의 업적으로 간주한다는 증거입니다. 타잔의 다른 획기적인 결과들도 마찬가지로 공동 저자들과 함께 구축되었습니다. 스플레이 트리는 대니얼 슬리터와, 피보나치 힙은 마이클 프레드먼과 함께 개발되었습니다. 논쟁의 여지가 없는 것은 그의 이름을 딴, 지금도 가르쳐지는 기초적인 결과들의 밀도가 매우 높다는 점이며, 이 분야에서 이에 필적하는 기록을 가진 사람은 거의 없습니다.
유산
깊이 우선 탐색, 유니온-파인드, 스플레이 트리, 피보나치 힙을 배우는 모든 컴퓨터 과학 학생은 사실상 수십 년 전에 작성된 타잔의 논문을 통해 배우고 있는 셈입니다. 그의 연구는 컴파일러, 네트워크 라우팅, 지리 정보 시스템의 밑바닥에 깔려 있으며, 대부분의 사용자는 그의 이름을 알지 못합니다. 이것이 완전히 성공한 인프라 수준 수학의 조용한 운명입니다. 그는 70대가 넘어서도 새로운 결과를 만들어내며 프린스턴 교수직과 인터트러스트 테크놀로지의 수석 과학자, 마이크로소프트와 휴렛 패커드의 연구원 역할을 오갔습니다. 이러한 경력 형태 자체가 그를 순수하게 학문적인 인물로만 보는 것에 반대합니다. 그의 가장 많이 인용된 연구의 상당 부분은 대학의 진공 상태가 아닌 산업 연구소 내에서 수행되고 테스트되고 적용되었습니다. 엄격한 수학을 발표하면서 실용적인 시스템을 특허화하는 이 이중적인 삶은 그의 기록을 아이디어가 저널에만 머물렀던 이론가들과 구분 짓는 요소입니다.
