컴퓨터 과학자로서의 삶
로버트 플로이드(Robert W Floyd)는 1936년 6월 8일에 미국 뉴욕시에서 태어났다. 6살 때부터 신동으로 알려졌던 그는 손에 잡히는 책은 모조리 읽었다고 하는데 심지어 초등학교 1학년 때는 고학년 학생들을 가르칠 때 도우미로 활동하였다고 한다.2 가족의 잦은 이사에도 불구하고 그는 월반을 3번이나 하면서 14살에 고등학교를 졸업했다.
마침 당시에 시카고 대학교에서 영재를 위한 특별 입학 과정을 시행 중이어서 그는 15살의 나이에 장학금을 받고 대학교에 입학했다. 그리고 17살이던 1953년에 일반 교양 학사 학위를 받고 졸업한 후 아머 연구 재단Armour Research Foundation에 연구원으로 입사했다. 그는 후에 다시 물리학을 공부해서 1958년에 물리학 학사 학위를 받았다.3
아머 연구 재단은 시카고에 위치한 과학 연구소였다.‡ 이곳에서 플로이드는 컴퓨터와 운명적인 만남을 하게 된다. 이곳에 있는 IBM 650 컴퓨터의 운영작업자로 일하게 된 그는 독학으로 컴퓨터 공부를 시작했고 빠르게 프로그래머이자 분석가로 성장했다.4
포트란이 등장하고 알골에 대한 논의가 활발하던 1950년대 말은 컴파일러에 관한 관심이 퍼지던 시기였다. 플로이드도 컴파일러에 관심을 가지면서 관련 논문을 발표하기 시작했다.5,6
1962년에 컴퓨터 어소시에이츠Computer Associates로 자리를 옮긴 후에는 컴파일러 개발에 전념하게 되는데 이때 연산자-우선순위operator-precedence 방식의 파싱parsing을 제안하여 파싱 방식에 새로운 전기를 마련했다.7
1963년에 밥은 <문법적 해석과 연산자 우선순위7>라는 대가다운 논문을 발표했는데 여기서 그는 파싱 문제에 접근하는 중요한 새로운 방법을 제안했다. 이것은 현실성을 가진 최초의 문법 주도형syntax-directed 알고리듬이었다.2
연산자-우선순위의 파싱은 그때까지 통상적으로 받아들여졌던 하향식top-down 방식이 아니라 상향식bottom-up 방식이었고, 후에 도널드 커누스가 LR 파싱을 제안하는 데 영향을 주었다.
플로이드는 알고리듬 개발에도 관심을 가졌다. 1962년에는 최단거리 알고리듬을 제시했다.8 이 알고리듬은 그래프 내에서 임의의 두 지점 사이의 최단 거리를 한 번에 모두 구한다. 이 알고리듬은 버나드 로이Bernard Roy, 스티븐 워셸Stephen Warshall에 의해서도 발견되었기 때문에 플로이드-워셸 알고리듬, 로이-워셸 알고리듬, 로이-플로이드 알고리듬이라고도 불린다. 또한 그는 편지를 통해 커누스와 많은 의견을 나누었는데 그 과정에서 힙 정렬heapsort 알고리듬을 개선하기도 했다.
플로이드는 대학원을 나오지 않았고 컴퓨터를 독학으로 공부했지만 이렇듯 컴퓨터 과학 분야에서 눈에 띄는 결과물을 발표하며 주목받았다. 1964년에 도널드 커누스는 <컴퓨터 프로그래밍의 아름다운 세계9> 책에서 구문 분석syntax analysis에 관한 장의 초고를 마친 후, 플로이드에게 다음과 같은 편지를 보냈다.
내가 만든 방법(LR 파싱)이 너무 복잡해서 사과해야만 하겠어. (책에 넣기에는 정말로 너무 복잡하지.) 하지만 문제가 그러니 어쩔 수 없는 것 같아. 이 문제와 관련해서 가장 단순한 경우만을 다루는 박사 논문만 해도 최소한 세 개는 댈 수 있다네! 제10장을 쓰다 보니 더욱 확실해지는 것이 있어. 스캐닝scanning 기법과 관련해서 지금까지 발표된 논문 중에서 정말로 좋은 논문을 고르라면 다섯 개밖에 없는데 그 다섯 논문 모두의 저자가 바로 자네라네!2
1965년에 카네기멜런 대학교의 조교수로 임용된 그는 활발한 연구 활동을 이어갔다. 1967년에 플로이드는 기념비적인 논문을 발표했다. <프로그램에 의미 부여하기>10라는 제목의 이 논문은 컴퓨터 프로그램의 의미론semantics 연구를 본격화하면서 프로그램 증명이라는 분야의 문을 연 것으로 간주되고 있다.3
커누스와 함께 스탠퍼드 대학교로 자리를 옮긴 것이 1968년이다. 박사 학위는커녕 석사 학위도 없던 그가 스탠퍼드 대학교에 채용된 것은 커누스의 적극적인 지지 때문이었다. 커누스가 작성한 추천서에는 다음과 같은 내용이 있다.
플로이드는 박사 학위를 얻는 정식 과정을 밟은 적이 없습니다. 그것은 그가 겨우 16~17살 때에 실험적 속성 교육 프로그램의 일환으로 시카고 대학교에 입학했기 때문이라고 저는 믿습니다. 대학원 공부를 할 정도로 성숙한 나이가 아니었습니다. (그렇지만) 분명히 그는 제가 컴퓨터 과학 분야에서 지금까지 본 어떤 박사 학위 논문보다도 뛰어난 논문을 최소 열 편 이상 작성했습니다. 따라서 그가 정식으로 학위를 받지 못했음을 따지는 것은 아주 부적절하다고 봅니다.2
하지만 완전히 고려 사항에서 빠진 것은 아니었다. 커누스는 정교수로 임용되었지만 플로이드는 조교수로 임용되었다. 그렇지만 1970년에 플로이드는 정교수로 승진했다. 카네기 멜런 시절까지 합치면 조교수 5년 만에 정교수가 되었으니 그리 늦은 것도 아니라 할 수 있겠다. 그리고 1973년에는 컴퓨터 과학과 제2대 학과장을 맡게 된다. 스탠퍼드 대학교 컴퓨터 과학과의 제1대 학과장은 조지 포사이스George Forsythe였다. 1965년에 컴퓨터 과학과를 출범시킨 포사이스는 열정적으로 학과 발전에 힘쓰다가 55세의 젊은 나이로 갑자기 세상을 떠났다. 따라서 플로이드 입장에서는 갑작스럽게 큰 역할을 맡게 된 셈이었는데 캠퍼스의 여기저기에 흩어져 있던 컴퓨터 과학과를 한곳으로 모으는 일을 포함하여 3년 동안 학과를 잘 이끌었다.
그의 명성이 알려지면서 1970년대에는 국제적인 무대에도 모습을 드러냈다. 1970년에 니스에서 열린 국제 수학자 대회International Congress of Mathematicians에 초청받은 여덟 명의 컴퓨터 과학자 중 한 명이었고, 1971년에는 류블라냐Ljubljana에서 열린 IFIP(International Federation of Information Processing) 대회에서 두 개의 위원회로부터 기조연설을 부탁받기도 했다.
플로이드는 정치적인 문제에도 관심을 쏟았다. 1970년에 닉슨 행정부가 캄보디아를 공습하자 스탠퍼드 대학교 내에서 이에 반대하는 목소리가 터져 나왔다. 이때 플로이드와 커누스는 더 이상 가만히 있으면 안 된다고 판단하여 하루는 컴퓨터 센터에서 농성하고 있던 학생들에 합류했고 아무도 컴퓨터 센터에 들어오지 못하도록 했다. 하지만 커누스에 따르면 두 사람은 농성장에 앉아서 하루 종일 정렬 알고리듬 이야기만 했다고 한다.2
또한 칠레에서 피노체트 정권이 들어섰을 때는 감옥에 수감된 페르난도 플로레스Fernando Flores 교수를 구해내는 일에 힘썼다. 플로레스 교수는 칠레 가톨릭 대학교에서 일하면서 컴퓨터에 기반한 정보 시스템을 개발했고 아옌데 정권에서 장관을 역임했던 인물이었다. 그의 노력 덕분에 플로레스 교수는 3년 만에 감옥에서 풀려나와 1976년에 스탠퍼드 대학교의 연구원으로 채용되었다.2
학과장에서 물러난 그는 1976년에 의외의 알고리듬을 발표했다. 이미지 정보를 디더링dithering하는 플로이드-스타인버그 알고리듬이다. 이것은 이미지 원본 파일을 컴퓨터에서 표현할 때 픽셀 당 정보 크기가 제한적이더라도 이미지를 부드럽게 처리하기 위한 방법이다.11 플로이드-스타인버그 알고리듬은 오늘날에도 광범위하게 사용되고 있다.
플로이드가 직접 발표하지는 않았지만 그의 업적으로 간주하는 것들도 있다. 대표적인 것이 사이클 검출cycle detection 알고리듬이다. 이것은, 어떤 함수가 그 결과값을 다시 입력으로 사용하여 계속 반복되어 호출된다고 할 때 몇 번이나 호출되면 동일한 패턴이 시작되는지를 찾아내는 문제이다.12 플로이드는 메모리를 제한적으로 사용하면서도 속도가 빠른 알고리듬을 고안했다. 후에 커누스가 이 알고리듬을 처음 공개하면서 플로이드의 것이라고 밝혔다.
1994년에 그는 이른 나이로 교수직에서 은퇴했다. 피크병Pick’s disease 진단을 받았기 때문이었다. 이 병은 일종의 치매로서 뇌의 신경세포가 점진적으로 파괴되는 질환이다. 그의 병은 급격히 악화되었고 몇 년 만에 아무도 몰라보는 지경에 이르렀다. 그는 2001년에 캘리포니아에서 세상을 떠났다.
