컴퓨터 과학자로서의 삶
존 호프크로프트(John E. Hopcroft)는 1939년 10월 7일에 미국 워싱턴주 시애틀에서 태어났다. 그의 집은 매우 가난했다. 영국 출신인 아버지는 제1차 세계대전 후에 직업을 구하기 위해 캐나다로 이주했고 얼마 후 불법으로 국경을 넘었다.3 그리고 시애틀에서 부인을 만나 정착하게 되었는데 존이 태어났을 무렵에는 건물청소부로 일했다.
그가 받은 급여는 최소 임금의 절반밖에 되지 않았습니다. 우리 가족은 아마도 아주 가난했었을 겁니다. 하지만 부모님은 굉장히 근검절약했고 나는 우리가 가난하다는 걸 몰랐습니다. 내가 생각하기에, 남들은 가지지 못했으나 내가 가졌던 장점이라면 부모님이 서로 사랑했다는 겁니다. 나는 아버지나 어머지가 상대방에 대해 험담하는 말을 한번도 들어본 적이 없었습니다.3
그의 부모는 고등학교도 졸업하지 못한 사람들이었지만 아들이 꼭 대학을 나와서 그들보다 더 나은 삶을 살기를 원했다. 존은 기대에 부응했다. 고등학교 시절에는 수학에 소질을 보였고 시애틀 대학교의 전기 공학과에 입학했다. 졸업할 무렵 그는 대학원에 진학하기로 마음 먹었는데 집에서 가까웠던 워싱턴 대학교에 갈 수가 없었다. 왜냐하면 그가 졸업한 시애틀 대학교는 가톨릭 예수회 대학이었고 공식적으로 교육과정을 인정받은 곳이 아니었기 때문이었다. 어찌해야 할지 모르던 존에게 워싱턴 대학교의 전기공학과 학과장은 스탠퍼드 대학교를 추천했다. 그리고 스탠퍼드 대학교는 그에게 대학원 입학을 허락했다.
그가 전기공학과를 선택한 이유는 어버지의 영향이 컸다고 한다. 건물청소부로 일하던 아버지는, 사무실에서 책상에 앉아 커피를 마시며 일하는 제도사를 부러워했는데, 자신보다 일은 덜하면서도 돈을 더 많이 벌기 때문이었다. 그는 이 제도사들이 전기 엔지니어라고 생각해서 아들에게 전기 엔지니어가 되라고 말하곤 했다.3 존은 수학과 과학을 좋아했기 때문에 거부감 없이 아버지의 조언을 받아들였다.
3년만에 석박사학위를 모두 딴 그가 전기 공학이 아닌 컴퓨터 과학의 길로 빠지게 된 것은 정말로 우연이었다.
내가 버니 위드로우 교수의 방 앞을 걸어 지나가고 있을 때, 마침 그의 방 문이 열려 있었습니다. 그는 전화기를 붙잡고 있었는데 나를 보더니 손짓을 하며 “존, 이리 와보게”라고 말했습니다. 그는 프린스턴 대학교의 에드 맥클러스키 교수와 통화중이었습니다. 맥클러스키 교수는 스탠퍼드 박사 졸업생 중에서 교수로 뽑을 만한 괜찮은 친구가 있는지를 알아보려고 전화를 걸었던 겁니다. 버니는 나에게 전화기를 넘기면서 “에드 맥클러스키와 이야기 좀 해봐”라고 말했습니다. 나는 전화기를 넘겨 받았고 맥클러스키는 면접을 위해 프린스턴에 와달라는 초청을 했습니다. 나는 거기서 일하겠다는 생각을 해본 적이 한번도 없었지만 그래도 최소한 면접은 가는 것이 좋겠다고 생각했습니다.3
프린스턴 대학교의 맥클러스키 교수는 호프크로프트가 마음에 들었고 바로 교수직을 제안했다. 그래서 아직 논문 한 편 발표한 적이 없는 호프크로프트는 프린스턴 대학교의 컴퓨터 과학과 교수로 채용되었다.
호프크로프트가 컴퓨터를 전혀 모르지는 않았다. 그는 시애틀 대학교 시절에 IBM 650용 포트란 프로그램을 디버깅한 경험이 있었고, 스탠퍼드 대학원 시절에는 스위칭 이론과 논리 설계에 관한 입문 과목을 듣기도 했었다. 하지만 맥클러스키 교수는 큰 그림을 그리고 있었다. 1960년대 중반까지만 해도 컴퓨터 이론이라면 주로 디지털 논리 설계가 주를 이루었다. 트랜지스터 단품으로 회로를 만들던 시절이었으므로 트랜지스터의 개수를 줄이기 위해 논리 회로를 최적화하는 일이 중요했다.1 그런데 논리 회로를 포함하는 반도체 부품이 등장하면서 패러다임의 전환이 요구되었다. 그래서 프린스턴 대학교도 논리 설계 중심의 교과과정을 벗어나려 했고 오토마타 이론을 가르치고 싶어했다. 오토마타에 관해서는 아는 바가 없었던 호프크로프트는 맥클러스키 교수에게 도움을 요청했다.
그는 나에게 여섯 개의 논문 제목을 적어 주면서 그 자료들이 오토마타 이론에 관한 좋은 배경지식이 될 거라고 말했습니다. 그 목록에는 워런 맥컬럭과 월터 피츠의 논문, 존 배커스와 피테르 나우어의 논문, 노엄 촘스키의 논문, 마이클 래빈과 데이나 스콧의 논문, 유리스 하트마니스와 리처드 스턴즈의 논문, 그리고 당연히 앨런 튜링의 논문이 들어 있었습니다.1
호프크로프트는 이 논문들을 통해서 컴퓨터 과학의 세계에 본격적으로 뛰어들었다. 아직 강의 교재로 쓸만한 책이 없던 시절이었으므로 그는 논문을 바탕으로 강의를 진행했다. 그 과정에서 강의 자료가 쌓였고 강의가 끝나자 그는 자료를 모아 책으로 펴낼 생각을 하게 되었다. 그는 함께 할 사람을 찾았고 당시 대학원생이었던 제프 울먼§이 뜻을 같이 했다. <정규 언어들과 그것들이 오토마타와 가지는 관계4>라는 제목의 이 책은 컴퓨터 과학 분야에서 초창기에 중요한 지침서로 자리매김했다.
그는 일련의 세미나도 진행했다. 이때 초대된 연사 중 한 명이 코넬 대학교의 유리스 하트마니스¶ 교수였다. 프린스턴을 방문한 하트마니스 교수는 코넬 대학교에서도 교수를 채용 중이라는 말을 꺼냈고 호프크로프트는 코넬 대학교가 급여도 더 높으면서 컴퓨터 과학과에 대한 지원이 더 적극적이라는 사실을 알게 되었다. 1967년에 그는 코넬 대학으로 자리를 옮겼다.
1969년에 <정규 언어들과 그것들이 오토마타와 가지는 관계>를 출간한 후 그는 연구 방향을 바꾸게 된다. 컴퓨터 과학의 영역을 더 확장할 필요가 있다고 그는 느꼈다. 그의 관심을 끈 것은 알고리듬이었다. 그는 알고리듬에도 이론 서적이 필요하다는 생각을 했고, ‘쪼개어 정복하기divide and conqure‘와 ‘깊이 우선 탐색depth-first-search‘을 포함하여 여러 알고리듬들을 개발했다. 그런 후 1970년 여름에 안식년을 보내기 위해 스탠퍼드 대학교로 향했다.3
로버트 타잔(Robert Endre Tarjan)은 1948년 4월 30일에 미국 캘리포니아주 포모나에서 태어났다. 그는 ‘밥(Bob)’이라는 애칭으로 불렸다. 그는 어렸을 때 과학 소설 읽기를 좋아했고 화성에 처음 발을 딛는 사람이 되고 싶었다고 한다.5
그는 상당히 일찍 컴퓨터를 접했다. 그의 아버지는 주립 정신 병원의 병원장이었고 연구소를 설립해서 이끌었다. 그는 아버지가 만든 연구소에서 고등학교 때 제표기를 사용하여 일했는데, 연구소에서 제표기를 컴퓨터로 교체하면서 벤딕스 G-15, 하니웰 컴퓨터 등에서 프로그램을 직접 작성해보는 경험을 했다. 또한, 여름 과학 학교에 참가했을 때는 기계식 계산기를 직접 사용하여 소행성 궤도 계산하기 같은 과제를 하기도 했고 UCLA에 견학 갔을 때는 직접 IBM 컴퓨터에서 포트란 프로그램을 작성하는 기회를 얻기도 했다.5
수학에 재능을 보인 그는 캘리포니아 공과대학Caltech에 입학해서 수학을 전공했다. 1969년에 학부를 졸업한 그는 스탠퍼드 대학교 대학원에 진학했다. 그는 매칭matching 문제, 조합적 계산, 계산 가능성, 오토마타 등 다양한 주제를 건드려 보았다. 당시 스탠퍼드 대학교에는 인공지능 분야의 대표 주자였던 존 매카시와 에드 파이겐바움이 있었기 때문에 그도 인공지능에 관심을 가졌다.
나는 인공지능을 해야 할지도 모르겠다는 생각을 했습니다. 하지만 내가 정말로 머릿속에 두고 있던 것은 계산 복잡도와 계산 가능성 쪽이었습니다… 몇 개의 과목을 들은 후에 나는, 인공지능이 너무 모호하다는 결론에 이르렀습니다. 충분히 수학적이지 못했습니다. 당시에 나는 밥 플로이드의 과목도 들었습니다. 그것은 문제 해결하기, 즉 알고리듬적으로 문제 해결하기로 가득차 있었습니다.5
대학원 첫 해에 박사 수료에 필요한 모든 학점을 다 이수한 그는 빠르게 논문 주제를 정했다. 그래프의 평면성을 검사하는 방법이 흥미를 끌었다. 사실 그는 첫 해에 존 맥카시 교수의 리스프 프로그래밍 강좌에서 평면성 검사 프로그램을 작성한 바가 있었다. 그래프의 평면성을 확인하는 방법은 이미 잘 알려져 있었다. 문제는 그 방법을 실제 소프트웨어 프로그램으로 작성하기가 쉽지 않았다. 그래서 그 수업을 들은 학생 중에서 이 프로그래밍에 도전한 이들은 모두 실패했다. 타잔만 예외였다. 그는 다행히 새로운 알고리듬을 소개한 논문을 찾아냈고 그것을 바탕으로 프로그램을 짜서 성공했다. 그런데 수행 시간이 문제였다. 이 알고리듬은 그래프에 있는 노드node의 개수에 제곱하는 비율로 수행 시간이 걸렸다. 예를 들어 노드가 10개일 때 100초라면 노드가 100개일 때는 10,000초가 걸렸다. 뭔가 이를 개선하는 방법이 있을 듯 싶었다. 그렇게 논문 주제를 정한 타잔의 방에 갑자기 등장한 이가 존 호프크로프트이다.
호프크로프트는 타잔이 고민하는 문제에 대한 해답을 금세 찾아낼 수 있었다. 이미 그는 깊이 우선 탐색이라는 방법이 가진 장점을 알고 있었기 때문에 이 방법을 도입하도록 추천했다.3 두 사람은 거기에서 멈추지 않았다.
우리는 n log n 의 규모로 수행되는 좀 복잡한 알고리듬을 만들었습니다. 그런데 선형 비례적인 규모의 시간에 끝나지 말라는 법이 없었습니다. 그래서 우리는 거의 일 년이라는 시간을 써가면서 선형 비례적인 규모로 수행되는 알고리듬을 찾으려 애썼고 마침내 답을 찾아냈습니다.5
두 사람의 결과물은 큰 반향을 일으켰다. 크게 두 가지 때문이었다. 첫 번째는 알고리듬의 성능을 판단하는 기준이었다. 그때까지만 해도 같은 문제에 대해서 A라는 알고리듬과 B라는 알고리듬이 있으면, 실제 프로그램을 작성한 후에 같은 데이터로 수행시켜서 실행시간을 비교하는 식이었다. 문제는, 이 프로그램들이 같은 언어로 작성되고 같은 기계에서 수행된다는 보장이 없었다. 특히나 컴퓨터가 귀하던 시절이었으므로 연구자가 사용할 수 있는 컴퓨터에 제한이 있었고 그러다 보니 알고리듬 검증에 사용되는 컴퓨터가 제각각이었다. 또한, 사용되는 데이터가 무엇이냐에 따라서도 성능 비교 결과가 달라질 수 있었다. 그래서 호프크로프트는 점근적 복잡도asymptotic complexity라는 개념을 지지했다. 이것은 알고리듬의 입력 데이터 크기를 변수로 잡고, 이 변수와 상관없는 요소들은 모두 무시하자는 것이다.
두 번째는 자료구조가 알고리듬의 성능에 영향을 줄 수 있음을 보여주었다. 평면성 검사 알고리듬이 선형 비례적 규모까지 개선될 수 있었던 결정적인 이유는 그래프 정보를 리스트 구조로 저장하고, 평면성 검사 과정에서는 쌍둥이 스택twin stack이라는 구조를 사용했기 때문이었다.6
점근적 복잡도라는 측면에서 이들이 만든 알고리듬은 분명히 우월했다. 하지만 과연 실제 프로그램으로 구현해도 마찬가지일까? 타잔이 소매를 걷고 직접 프로그램을 작성했다. 그는 알골 W 언어**를 사용해서 IBM 360 컴퓨터에서 프로그램을 완성했다. 900개의 노드와 2694개의 간선을 가지는 그래프의 평면성을 검사하는 데 12초가 걸렸다. 이것은 기존의 연구에 비해 최소 80배가 빨랐다.
일 년의 협업은 세상을 깜짝 놀라게 만드는 결과물을 낳았다. 그리고 두 사람의 인연은 조금 더 이어진다.
호프크로프트가 코넬 대학교로 돌아간 후에 타잔은 석사를 바로 마치고 박사 논문을 준비하기 시작했다. 그는 원래 도널드 커누스 교수를 지도교수로 원했으나 커누스 교수는 격년 단위로 박사 학생을 뽑았고 하필이면 그 해는 쉬어가는 해였다. 그래서 타잔은 밥 플로이드 교수의 지도를 받아 논문을 작성했다.5
72년에 박사 학위를 받은 타잔은 호프크로프트 교수가 있는 코넬 대학교의 교수로 임용되었다. 그런데 문제가 생겼다. 서부의 온화한 날씨에 익숙해져 있던 그에게 뉴욕 주 이타카의 추운 날씨는 도저히 견딜 수 없는 고통이었다. 결국 일 년 만에 그는 서부로 돌아와서 캘리포니아 대학교 버클리의 연구원으로 일했다. 그리고 1974년에 스탠퍼드 대학교 컴퓨터 과학과 교수로 자리를 옮겼다.
그는 탐색 트리search tree 와 관련된 연구에서 놀라운 성과를 냈다. 그 과정에서 벨 연구소를 방문하여 안식년을 보낸 그는 그곳의 연구 환경에 좋은 인상을 받았고 벨 연구소에서도 그에게 좋은 제안을 했다. 그는 스탠퍼드의 교수직을 그만 두고 1980년에 벨 연구소에 입사했다. 하지만 그가 완전히 학계와의 인연을 끊은 것은 아니었다. 그는 뉴욕 대학교, 프린스턴 대학교에서 틈틈히 강의를 했다. 1989년에 벨 연구소를 나온 그는 NEC 연구소, InterTrust, 컴팩, HP 등에서 수석 연구원 등으로 일하면서 왕성한 활동을 이어갔다.
알고리듬에 관한 서적의 부재가 호프크로프트의 연구를 촉발했다는 점을 기억한다면 그가 알고리듬에 관한 책을 발표했다는 사실이 자연스럽게 여겨질 듯싶다. 그는 1974년에 <컴퓨터 알고리듬의 설계 및 분석7>이라는 책을 발표했다. 이 책은 프린스턴 대학교 시절에 그의 제자였던 제프 울먼과 앨프리드 에이호††가 함께 저자로 참여했다. 이 책도 오랫동안 컴퓨터 과학 분야의 필독서였다.
그는 행정가로서도 능력을 보여주었다. 처음에는 마지못해 컴퓨터 과학과 학과장을 맡았던 그는 공대 학장을 역임했으며 1992년에는 당시 부시 미국 대통령에 의해 미국 과학 위원회National Science Board의 위원에 임명되기도 했다.
말년에는 아시아에 있는 대학들에서 교육 개혁에 참여하기도 했는데, 특히 중국에서 활발히 활동했다.
답글 남기기