존 홉크로프트: 한 분야를 훈련시킨 교과서

수백만 명의 컴퓨터 과학 전공 학생들은 존 홉크로프트가 연구 저널에 쓴 글을 한 번도 읽어본 적이 없을지 모르지만, 거의 모두가 그에게서 배웠다. 제프리 울먼(Jeffrey Ullman) 및 알프레드 아호(Alfred Aho)와 이름을 나란히 한 오토마타 이론 및 알고리즘 교과서를 통해서인데, 이 책들은 표준 커리큘럼으로 널리 채택되어 해당 학문이 스스로를 가르치는 방식을 형성했다.

관리인의 아들에서 스탠퍼드로

존 에드워드 홉크로프트는 1939년 10월 7일 워싱턴주 시애틀의 노동자 계급 가정에서 태어났다. 아버지는 제1차 세계 대전의 영국 참전 용사로 관리인으로 일했으며, 부모님 모두 고등학교를 졸업하지 못했다. 그는 또한 시애틀-타코마 박스 컴퍼니(Seattle-Tacoma Box Company)의 창립자인 제이콥 니스트(Jacob Nist)의 손자이기도 했다. 제한된 학력에도 불구하고 부모님은 그의 지적 호기심을 장려했고, 그는 1961년 시애틀 대학교에서 전기공학 학사 학위를, 1962년 석사 학위, 1964년 박사 학위(모두 전기공학)를 스탠퍼드 대학교에서 받았다. 순수 수학이나 컴퓨터 과학 배경이 아닌 이러한 공학적 훈련은 이론적으로 우아할 뿐만 아니라 실제로 실행 효율이 높은 알고리즘에 대한 그의 후기 직관을 형성했다.

학문의 교과서 구축

홉크로프트는 프린스턴 대학교에서 조교수로 학문적 경력을 시작한 후 코넬 대학교로 옮겨 경력의 대부분을 보냈다. 결국 IBM 공학 및 응용수학 교수라는 직함을 얻었고 학과장 및 공과대학 학장을 포함한 지도적 역할을 수행했다. 코넬 대학교에서 그는 제프리 울먼, 나중에는 알프레드 아호와 함께 형식 언어, 오토마타 이론, 알고리즘 설계에 관한 일련의 교과서를 공동 집필했는데, 이는 전 세계 컴퓨터 과학 학생들을 위한 기본 교육 텍스트가 되었다. 이 책들은 기존 지식을 요약하는 것 이상의 역할을 했다. 점근적 복잡성 분석과 형식 언어 이론을 오늘날에도 입문 이론 과정에서 가르치는 형태로 성문화하여, 해당 어휘가 다른 곳에 완전히 존재하기 전에 이 분야에 공유된 어휘를 제공했다.

오늘날에도 실행되는 알고리즘

교과서 외에도 홉크로프트 자신의 연구는 여전히 활발히 사용되는 도구를 생산했다. 리처드 카프(Richard Karp)와 함께 개발한 홉크로프트-카프 알고리즘(Hopcroft-Karp algorithm)은 이분 그래프에서 최대 매칭을 이전의 어떤 방법보다 빠르게 찾으며, 네트워크 흐름 및 할당 문제에서 표준 기술로 남아 있다. 그는 또한 결정적 유한 오토마타를 최소화하는 효율적인 알고리즘을 개발했는데, 이는 컴파일러 설계 및 형식 검증의 기초 도구가 되었다. 그러나 그의 가장 유명한 성과는 로버트 타잔(Robert Tarjan)과의 공동 연구였다. 1974년에 발표된 그래프가 평면인지(가장자리가 교차하지 않고 평면에 그릴 수 있는지) 테스트하기 위한 최초의 선형 시간 알고리즘이다. 두 사람은 깊이 우선 탐색의 체계적인 사용을 중심으로 알고리즘을 구축하여, 느리고 임시방편이었던 문제를 그래프 크기에 비례하는 시간에 해결할 수 있는 문제로 바꾸었다.

튜링상과 그 공유된 성격

1986년 홉크로프트와 타잔은 "알고리즘 및 데이터 구조의 설계와 분석에 대한 근본적인 업적"으로 컴퓨터 과학의 최고 영예인 ACM A.M. 튜링상을 공동 수상했다. 수상 이유는 두 사람을 함께 지명하며 단일 개인의 돌파구가 아닌 협력적이고 병렬적인 일련의 작업을 인정하고 있다. 평면성 알고리즘이 수상 이유가 염두에 둔 주요 업적이며, 그 외에 알고리즘 설계라는 더 넓은 분야에 대한 각자의 독립적인 기여가 포함되었다.

중국에서의 제2의 경력

튜링상 수상 후 수십 년 동안 홉크로프트는 에너지의 상당 부분을 미국 밖, 특히 중국의 컴퓨터 과학 교육 강화에 쏟았다. 그는 베이징 대학교 계산 연구 프론티어 센터의 공동 이사가 되었고, 상하이 자오퉁 대학교와 화중 과학기술 대학교에서 자신의 이름을 딴 센터를 이끌며 학생들을 지도하고 알고리즘 및 최근에는 딥러닝 연구 프로그램을 구축하는 데 도움을 주고 있다. 중국은 2016년에 그에게 우의상을 수여했는데, 이는 국가 발전에 뛰어난 기여를 한 외국 전문가에게 주어지는 인정으로, 상을 받은 작업에서 이미 수십 년이 지난 튜링상 수상자에게는 이례적인 제2의 인생이다.

인식

홉크로프트는 1989년 미국 공학한림원 회원으로 선출되었고, 1994년 ACM 펠로우가 되었으며, 1986년 튜링상과 2016년 중국 우의상 외에도 컴퓨터 과학 및 공학 분야의 뛰어난 업적으로 2010년 IEEE 존 폰 노이만 메달을 수상했다.

존이 천재라고 불리는 이유

홉크로프트가 천재라는 주장은 단 하나의 눈부신 증명이 아니라 더 드문 조합에 근거한다. 분야 최고상을 받을 만큼 실질적인 연구 기여와, 그 분야의 기초를 가르칠 수 있는 형태로 증류하는 비할 데 없는 재능이다. 평면성 알고리즘과 홉크로프트-카프 매칭 알고리즘은 이론 컴퓨터 과학자들이 진정으로 영리하다고 지적하는 결과물로, 구조적 통찰력을 통해 무차별 대입 검색이 필요해 보이던 문제를 선형 또는 선형에 가까운 시간으로 줄였다. 그러나 튜링상 수상 이유 자체가 명시하는 정직한 틀은 그의 가장 유명한 결과물이 그와 로버트 타잔의 공동 소유라는 것이다. 두 사람의 수상 이유는 단독으로 성립하지 않으며, 상은 개인의 돌파구가 아닌 공유된 업적에 대한 것이었다. 덜 공유되고 "천재"로 덜 자주 칭송받는 그의 두 번째 재능은 세 권의 공동 집필 교과서인데, 너무 잘 구성되어 있어 학문 전체가 자신의 기초를 가르치는 기본 방식이 되었다. 이는 개인의 발명보다는 마스터 티칭에 가까운 지적 기여의 형태이다.

유산

홉크로프트의 유산은 한 경력에서 거의 일치하지 않는 두 개의 평행 궤도를 달린다. 알고리즘 분야의 튜링상 수상 연구 기록과, 중국에서 컴퓨터 과학 교육 인프라를 구축하는 수십 년간의 제2의 인생이다. 이 분야 역사상 가장 널리 지정된 교과서의 저자만큼 직접적으로, 또는 오랫동안 가르치는 방식을 형성한 인물은 거의 없다. 1960년대와 70년대에 계산 이론을 형식화하는 데 도움을 준 사람이 2010년대에는 베이징 대학교에서 딥러닝 학생들을 지도하고 있었다는 사실은 그의 노동 인생의 이례적인 길이와 폭에 대해 무언가를 말해준다. 진공관에 가까운 전기공학 시대에 시작되어 신경망 시대로 이어진 경력이지만, 다음 세대에게 해당 분야의 기본 구조를 가르친다는 일관된 줄기를 잃지 않았다.