도널드 크누스(Donald Knuth)

도널드 크누스는 1938년 미국 위스콘신주 밀워키에서 태어났습니다. 아버지는 루터교 학교에서 부기를 가르치며 집 지하실에서 작은 인쇄 일을 했습니다. 그가 대학에 들어간 1950년대 후반, 컴퓨터는 막 대학에 들어오기 시작한 기계였고 프로그래밍은 요령과 경험으로 익히는 기술이었습니다. 어떤 프로그램이 다른 프로그램보다 빠른지는 돌려 보고서야 알았고, 그것을 수학으로 따지는 분야는 없었습니다. 크누스는 프로그램이 몇 걸음 만에 끝나는지를 정확히 세는 일, 곧 알고리즘 분석을 하나의 수학 분야로 세웠고, 그 결과를 필생의 책 『컴퓨터 프로그래밍의 기술』에 담고 있습니다.

나이 세 ·

어려서부터 그는 무엇이든 끝까지 세는 아이였습니다. 중학생 때 한 과자 회사가 연 대회에서 상품 이름 '지글러의 자이언트 바'의 글자로 만들 수 있는 낱말을 4,500개 남짓 찾아 심사위원들의 목록을 훌쩍 넘어섰다는 이야기가 전합니다. 1956년 오하이오주 클리블랜드의 케이스 공과대학에 물리학을 공부하러 들어갔다가 수학으로 옮겼고, 학교의 IBM 650 컴퓨터에 빠져 농구팀 선수들의 기여도를 셈하는 프로그램을 짜기도 했습니다. 1957년에는 잡지 『매드』에 우스개 도량형 '포츠레비 체계'를 실었습니다. 1960년 졸업할 때 학교는 그의 실력을 인정해 학사와 석사 학위를 한꺼번에 주었습니다.

그는 캘리포니아 공과대학(칼텍)에서 마셜 홀 2세의 지도로 1963년 박사 학위를 받았습니다. 주제는 유한한 사영 평면⁠(projective plane)⁠이었습니다. 사영 평면에서는 어떤 두 점도 꼭 한 직선 위에 있고, 어떤 두 직선도 꼭 한 점에서 만납니다. 점이 유한 개인 사영 평면은 더하고 곱하고 나눌 수 있는 유한한 수 체계(유한체⁠, finite field⁠)에서 좌표를 빌려 만들 수 있습니다. 크누스는 곱셈의 결합 법칙이 성립하지 않아도 되는 수 체계⁠(number system)⁠인 '반체⁠(semifield)⁠'를 새로 찾아, 유한체에서는 나오지 않는 새로운 사영 평면들을 만들었습니다. 박사 과정에 있던 1962년 출판사 애디슨웨슬리가 그에게 컴파일러⁠(compiler)⁠에 관한 책을 써 달라고 청했고, 이 청탁이 평생의 일이 되었습니다.

그해 여름 그는 알고리즘 분석의 첫 걸음이 된 계산을 했습니다. 해시 테이블⁠(hash table)⁠은 자료를 $m$개의 칸 가운데 해시 함수⁠(hash function)⁠가 정한 칸에 넣는데, 그 칸이 이미 차 있으면 다음 칸, 그다음 칸으로 빈칸이 나올 때까지 옮겨 갑니다(선형 탐사⁠, linear probing⁠). 칸의 비율 $\alpha$가 차 있을 때 평균⁠(mean)⁠ 몇 칸을 보아야 할까요? 크누스는 있는 자료를 찾을 때는 대략 $\tfrac12\bigl(1 + \tfrac{1}{1-\alpha}\bigr)$칸, 없는 자료를 찾을 때는 $\tfrac12\bigl(1 + \tfrac{1}{(1-\alpha)^2}\bigr)$칸이라는 것을 정확히 계산했습니다. 표가 90% 차면 앞의 값은 5.5칸이지만 뒤의 값은 50.5칸으로 치솟습니다. 차 있는 칸들이 덩어리로 뭉치며 서로를 키우기 때문입니다. '대충 빠르다'가 아니라 기댓값⁠(expected value)⁠을 식으로 얻을 수 있다는 이 경험이, 그의 말로는 책 전체의 방향을 정했습니다.

컴파일러 한 권으로 계획한 책은 일곱 권짜리 연작으로 불어났습니다. 1968년 1권 『기초⁠(basics)⁠ 알고리즘』, 1969년 2권 『준수치 알고리즘』, 1973년 3권 『정렬과 탐색』이 나왔고, 2011년 4A권과 2022년 4B권이 조합 알고리즘을 다루었습니다. 그는 실제 기계의 속도⁠(velocity)⁠에 휘둘리지 않도록 가상의 컴퓨터 MIX와 그 기계어를 만들어, 명령이 몇 번 실행되는지를 정확히 셌습니다. 예컨대 호어의 퀵정렬⁠(quicksort)⁠이 서로 다른 수 $n$개를 정렬할 때 평균 비교 횟수는 $2(n+1)H_n - 4n$입니다. 여기서 $H_n = 1 + \tfrac12 + \cdots + \tfrac1n$은 조화급수⁠(harmonic series)⁠의 부분합⁠(partial sum)⁠으로 대략 $\ln n$이므로, 이 값은 약 $1.39\, n \log_2 n$이고 어떤 비교 정렬⁠(comparison sort)⁠도 넘을 수 없는 하한⁠(lower bound)⁠ $\log_2 n!$보다 39%쯤 많습니다. 이런 식을 얻는 도구가 점화식⁠(recurrence relation)⁠과 생성함수⁠(generating function)⁠이고, 책은 그 도구를 가르치는 수학책이기도 합니다. 책의 잘못을 처음 찾아 알린 사람에게 그는 2.56달러, 곧 '16진법⁠(positional notation)⁠의 1달러'짜리 수표를 보냅니다.

책을 쓰며 그는 역사를 캐는 사람이 되었습니다. 1970년 폰 노이만이 1945년 EDVAC을 위해 손으로 적은 병합 프로그램을 찾아 분석했고, 기수 정렬⁠(radix sort)⁠이 1929년 천문학자 레슬리 코미의 글에 처음 출판되었다는 것, 이진 탐색⁠(binary search)⁠이 1946년 존 모클리의 강의에서 처음 언급되었지만 모든 경우에 맞게 작동하는 판은 1960년에야 나왔다는 것도 그가 찾아 기록했습니다(정렬 알고리즘⁠(sorting algorithm)⁠, 이진 탐색). 알고리즘을 말하는 언어도 다듬었습니다. 1976년 그는 알고리즘 연구자들에게 보낸 글에서, $O(g)$가 '$g$의 상수배를 넘지 않음'이라는 위쪽 한계만 뜻하므로 아래쪽 한계 $\Omega(g)$와 위아래를 함께 묶는 $\Theta(g)$를 따로 쓰자고 제안했고, 이것이 오늘날의 표준이 되었습니다(위의 식, 점근 표기법⁠(asymptotic notation)⁠). 1974년에는 동료들에게 설문을 돌려 P 대 NP 문제⁠(P versus NP problem)⁠에서 쓰는 'NP-난해⁠(NP-hard)⁠'라는 이름을 정하는 데 앞장섰고, 1976년에는 $3\uparrow\uparrow 3 = 3^{3^3} = 3^{27}$(약 7조 6천억)처럼 거듭제곱을 거듭하는 큰 수를 적는 화살표 표기도 내놓았습니다.

그는 프로그래밍 언어의 이론에도 기초를 놓았습니다. 1965년 논문에서 그는 문맥 자유 문법⁠(context-free grammar)⁠ 가운데, 컴퓨터가 글을 왼쪽에서 오른쪽으로 한 번 읽어 내려가며 몇 글자만 앞을 내다보고 되돌아가지 않고도 구문 트리⁠(tree)⁠를 만들 수 있는 부류를 LR 문법으로 정확히 규정했습니다. 오늘날 프로그래밍 언어의 구문 분석기⁠(parser)⁠를 자동으로 만드는 도구들이 이 이론 위에 서 있습니다. 1968년에는 문법 규칙마다 뜻을 계산하는 규칙을 붙이는 속성 문법⁠(attribute grammar)⁠을 내놓았습니다. 1974년 논문 「goto 문을 쓰는 구조적 프로그래밍⁠(structured programming)⁠」은 데이크스트라가 촉발한 goto 논쟁을 차분히 정리한 글인데, 작은 효율을 위해 이르게 최적화⁠(optimization)⁠하는 것을 경계하면서도 정말 중요한 몇 퍼센트의 부분은 놓치지 말라고 적은 대목이 지금도 자주 인용됩니다.

1977년에는 제임스 모리스, 본 프랫과 함께 글 속에서 낱말을 찾는 빠른 방법을 발표했습니다(KMP 알고리즘). 'ABABC'를 찾다가 'ABAB'까지 맞고 다섯째 글자에서 어긋났다면, 한 칸 옮겨 처음부터 다시 비교할 필요가 없습니다. 방금 맞은 'ABAB'의 끝 'AB'가 찾는 낱말의 처음 'AB'와 같으니, 두 글자는 이미 맞은 것으로 치고 이어서 비교하면 됩니다. 찾는 낱말만 보고 '어긋나면 어디로 돌아갈지'를 미리 표로 만들어 두면, 글자 하나를 두 번 넘게 볼 일이 없어 전체 걸음은 글의 길이와 낱말의 길이의 합에 비례합니다. 이 표는 낱말을 알아보는 유한 오토마톤⁠(finite automaton)⁠을 만드는 것과 같습니다.

가장 널리 쓰이는 그의 작품은 책 밖에서 나왔습니다. 1976년 2권 개정판의 교정쇄가 돌아왔을 때, 활자를 녹여 붓던 옛 조판 대신 새로 쓰인 사진 식자로 짠 수식은 그의 눈에 보기 흉했습니다. 그는 금방 끝나리라 여기고 1977년 조판 프로그램 TeX과 글꼴을 설계하는 프로그램 METAFONT를 만들기 시작했는데, 일은 10년 가까이 걸렸습니다. 그 안에는 수학이 있습니다. 문단을 줄로 나눌 때 한 줄씩 채우는 대로 끊는 욕심쟁이 방법⁠(greedy algorithm)⁠ 대신, 끊을 수 있는 모든 자리를 점으로 보고 줄마다 낱말 사이가 얼마나 늘거나 줄었는지로 '보기 흉함' 점수를 매긴 뒤, 문단 전체의 점수 합이 가장 작은 끊기를 동적 계획법⁠(dynamic programming)⁠으로 찾습니다. 점수를 길이로 보면 문단의 첫 자리에서 끝 자리까지의 최단 경로⁠(shortest path)⁠ 문제입니다. TeX의 판 번호는 고칠 때마다 한 자리씩 늘어 3.14159265…로 π에 다가가고, METAFONT의 판 번호는 e에 다가갑니다. 오늘날 수학자와 물리학자는 거의 모두 TeX으로 논문을 쓰고, 이 위키의 수식도 TeX의 문법으로 적혀 있습니다.

그는 프로그램을 사람에게 읽히는 글로 쓰자고도 했습니다. 1984년 제안한 '문학적 프로그래밍⁠(literate programming)⁠'은 설명과 코드를 한 문서에 섞어, 사람이 읽기 좋은 순서로 쓰면 도구가 그 안에서 컴퓨터용 코드를 뽑아내게 하는 방식이고, TeX 자체가 이렇게 쓰였습니다. 1975년 몬트리올에서 한 강의는 이듬해 프랑스어 책 『안정된 결혼』이 되어, 게일과 섀플리의 안정 매칭⁠(stable matching)⁠을 알고리즘 분석의 교과서적인 예로 만들었습니다. 존 콘웨이의 새로운 수 체계를 두 사람의 대화로 풀어 쓴 소설 『초현실수』(1974), 스탠퍼드 강의를 로널드 그레이엄, 오렌 파타슈닉과 함께 묶은 『구체 수학』(1989)도 썼습니다. 책 제목의 '구체(Concrete)'는 연속(continuous)과 이산(discrete)을 합친 말입니다.

1968년부터 스탠퍼드 대학에 있던 그는 1974년 튜링상⁠(Turing Award)⁠, 1979년 미국 국가 과학 훈장, 1996년 교토상을 받았습니다. 1990년에는 연작 집필에 집중하려고 전자우편을 끊었고, 1993년 일찍 은퇴해 '『컴퓨터 프로그래밍의 기술』 명예교수'라는 직함으로 계속 쓰고 있습니다. 집에 파이프 오르간을 들여놓은 오르간 연주자이고, 성경 구절을 표본⁠(sample)⁠ 추출해 읽은 책을 내기도 한 독실한 루터교 신자입니다. 해마다 스탠퍼드에서 여는 크리스마스 강연은 수학과 알고리즘의 새 이야기를 기다리는 사람들로 붐빕니다.

이어지는 곳. 크누스가 센 걸음 수를 어림하는 언어가 점근 표기법이고, 그의 셈이 가장 풍성한 곳이 정렬 알고리즘과 비교 정렬의 하한⁠(comparison sorting lower bound)⁠, 해시 테이블입니다. 쪼개어 풀고 합치는 분할 정복⁠(divide and conquer)⁠의 비용은 점화식으로, 경우의 수⁠(number of cases)⁠를 한꺼번에 세는 일은 생성함수와 카탈랑 수⁠(Catalan number)⁠로 이어집니다. 알고리즘이라는 말 자체의 뿌리는 알콰리즈미와 알고리즘에, 빠른 계산과 느린 계산의 경계는 P 대 NP 문제에 있습니다.

관계.

• 영향을 받음 존 폰 노이만 — 1970년 폰 노이만이 1945년 EDVAC을 위해 손으로 적은 병합 프로그램 원고를 찾아 분석하고, 저장 프로그램 컴퓨터⁠(stored-program computer)⁠를 위해 쓰인 가장 이른 프로그램 가운데 하나로 소개했습니다.
• 논쟁 에츠허르 데이크스트라 — 데이크스트라가 goto 문을 해롭다고 한 뒤 벌어진 논쟁에서, 1974년 논문으로 goto를 무조건 없애기보다 잘 쓰는 법을 논하며 구조적 프로그래밍의 논의를 정리했습니다.
• 영향을 받음 토니 호어 — 호어의 퀵정렬이 평균적으로 비교를 몇 번 하는지를 정확한 식으로 계산해, 알고리즘 분석이 무엇을 할 수 있는지 보여 주는 대표적인 예로 삼았습니다.
• 영향을 받음 데이비드 게일 — 게일과 섀플리의 1962년 안정 매칭 논문을 1975년 몬트리올 강의의 주제로 삼아, 안정 매칭의 구조와 알고리즘 분석의 열린 문제 열두 가지를 정리했습니다.
• 영향을 받음 노엄 촘스키 — 촘스키가 정의한 문맥 자유 문법 가운데 컴퓨터가 한 번 읽어 내려가며 되돌아가지 않고 분석할 수 있는 넓은 부류를 1965년 LR 문법으로 정확히 규정했습니다.

연표.

• 1957년 잡지 『매드』에 우스개 도량형 '포츠레비 체계'를 싣다
• 1960년 케이스 공과대학에서 학사와 석사 학위를 함께 받다
• 1962년 해시 테이블의 선형 탐사를 분석하고, 컴파일러 책을 써 달라는 청탁을 받다
• 1963년 유한 반체와 사영 평면에 관한 논문으로 칼텍에서 박사 학위를 받다
• 1965년 왼쪽에서 오른쪽으로 읽으며 구문을 분석하는 LR 파싱⁠(LR parsing)⁠을 발표하다
• 1968년 『컴퓨터 프로그래밍의 기술』 1권을 펴내고 스탠퍼드로 옮기다
• 1973년 3권 『정렬과 탐색』을 펴내다
• 1974년 튜링상을 받고, 「goto 문을 쓰는 구조적 프로그래밍」을 발표하다
• 1976년 Ω와 Θ 표기를 제안하고, 몬트리올 강의록 『안정된 결혼』을 펴내다
• 1978년 조판 프로그램 TeX의 첫 판을 내놓다
• 1984년 '문학적 프로그래밍'을 제안하다
• 1993년 스탠퍼드에서 은퇴해 연작 집필에 전념하다
• 2011년 『컴퓨터 프로그래밍의 기술』 4A권을 펴내다