도널드 어빈 커누스(Donald Ervin Knuth, 1938년 1월 10일 출생)는 미국의 컴퓨터 과학자이자 수학자이다. 그는 스탠퍼드 대학교의 명예 교수이며, 컴퓨터 과학의 노벨상으로 비공식적으로 간주되는 1974년 ACM 튜링상을 수상했다. 커누스는 "알고리즘 분석의 아버지"로 불리며, 다권 저작 The Art of Computer Programming의 저자이다.
커누스는 계산 복잡성에 대한 엄밀한 분석의 발전에 기여했고, 이를 위한 형식적 수학 기법을 체계화했으며, 점근 표기법을 대중화했다. 그는 또한 TeX 컴퓨터 조판 시스템, METAFONT 글꼴 정의 언어, 그리고 Computer Modern 서체의 창시자이기도 하다. 작가이자 학자로서 그는 문헌적 프로그래밍을 위한 WEB 및 CWEB 프로그래밍 시스템을 만들었고, MIX/MMIX 명령어 집합 아키텍처를 설계했다. 그는 소프트웨어 특허에 강하게 반대하며, 미국 특허상표청과 유럽 특허청에 자신의 견해를 표명했다.
초기 생애와 교육
커누스는 위스콘신주 밀워키에서 어빈 헨리 커누스(Ervin Henry Knuth)와 루이즈 마리 보닝(Louise Marie Bohning) 사이에서 태어났다. 그는 자신의 혈통을 "중서부 루터교 독일인"이라고 묘사한다. 그의 아버지는 작은 인쇄 사업체를 소유했고 부기(簿記)를 가르쳤다. 밀워키 루터교 고등학교 재학 중, 커누스는 초기 문제 해결 능력을 보여주었다. 8학년 때, 그는 "Ziegler's Giant Bar"의 글자들로 재배열할 수 있는 단어의 수를 찾는 대회에 참가했다. 심사위원들은 2,500개의 단어를 확인했지만, 커누스는 가짜 병가를 내고 무삭제 사전을 사용하여 4,500개 이상의 단어를 찾아내 우승했다. 학교는 텔레비전과 모든 학생들을 위한 사탕 바를 받았다.
커누스는 1956년 케이스 공과대학(현재 케이스 웨스턴 리저브 대학교의 일부)에서 물리학 장학금을 받았다. 그는 세타 카이(Theta Chi) 형제회의 베타 누 지부에 가입했다. 초기 상업용 컴퓨터인 IBM 650을 접한 그는 그 매뉴얼을 읽고, 자신이 더 잘할 수 있다고 믿어 그 기계의 어셈블리 및 컴파일러 코드를 다시 작성하기로 결정했다. 1958년, 그는 농구팀이 이길 수 있도록 선수들에게 "가치"를 할당하여 득점 확률을 측정하는 프로그램을 만들었다. 이는 Newsweek와 CBS 이브닝 뉴스에 보도된 새로운 접근 방식이었다.
커누스는 1959년 전국상을 수상한 Engineering and Science Review의 창립 편집자였다. 그는 물리학에서 수학으로 전공을 바꾸어 1960년에 이학사와 석사 학위를 모두 받았으며, 석사 학위는 특별 교수진 상으로 수여되었다. 4학년 말에 그는 버로우스 코퍼레이션(Burroughs Corporation)에 B205용 ALGOL 컴파일러를 $5,500에 작성하겠다고 제안했다. 그 제안은 수락되었고, 그는 케이스와 캘리포니아 공과대학 사이에서 그 작업을 수행했다. 1963년, 그는 캘리포니아 공과대학에서 마셜 홀(Marshall Hall)을 지도교수로 하여 논문 Finite Semifields and Projective Planes로 수학 박사 학위를 받았다.
초기 경력과 The Art of Computer Programming
박사 학위를 받은 후, 커누스는 1963년 캘리포니아 공과대학 교수진에 조교수로 합류했다. 그는 또한 버로우스 코퍼레이션의 컨설턴트가 되어 B220용 ALGOL 컴파일러 작업을 수행했다. 그는 그린 트리 코퍼레이션(Green Tree Corporation)으로부터의 $100,000 계약을 거절하고 캘리포니아 공과대학과 버로우스에 남았다. 그는 국립과학재단과 우드로 윌슨 펠로우십을 거절했는데, 이는 컨설팅 작업을 방해했을 것이기 때문이다. 1962년 여름, 그는 Univac용 FORTRAN 컴파일러를 작성했으며, 나중에 "악마에게 영혼을 팔았다"고 말했다.
버로우스에서 커누스는 하나의 기호가 기호 문자열을 나타낼 수 있도록 하는 심볼 테이블의 확장을 제안했고, 이는 버로우스 ALGOL의 DEFINE의 기초가 되었다. 에츠허르 데이크스트라(Edsger Dijkstra)는 처음에 그 아이디어를 좋아하지 않았다. 커누스는 또한 시뮬레이션 언어 작업을 하여 J. 맥닐리(J. McNeeley)와 함께 SOL을 만들었고, 1967년 노르웨이에서 열린 회의에 참석한 후 버로우스가 시뮬라(Simula)를 채택하도록 영향을 미쳤다. 그의 버로우스와의 컨설팅 관계는 1960년부터 1968년까지 지속되었다.
1962년, 애디슨-웨슬리(Addison-Wesley)는 커누스에게 컴파일러에 관한 책을 쓰도록 의뢰했다. 그 책을 작업하는 동안, 그는 컴퓨터 프로그래밍의 기초 이론이 필요하다는 것을 깨달았고, 그것이 The Art of Computer Programming이 되었다. 원래 한 권으로 계획되었지만, 여섯 또는 일곱 권으로 확장되었다. 첫 번째 권은 1968년에 출판되었다. 출판 직전에 커누스는 캘리포니아 공과대학을 떠나 프린스턴에 있는 국방 분석 연구소의 통신 연구 부서에서 일하며 국가안보국(NSA)을 위한 암호학 수학 연구를 수행했다.
컴퓨터 과학에 대한 기여
커누스의 The Art of Computer Programming 작업은 알고리즘 분석을 엄밀한 학문으로 확립했다. 그는 알고리즘 효율성을 설명하기 위해 점근 표기법(예: 빅 오 표기법)을 도입하고 대중화했다. 그의 책들은 정밀성, 역사적 주석, 난이도별로 구분된 연습 문제로 유명하다. 이 시리즈는 컴퓨터 과학의 기초 참고 자료로 간주된다.
커누스는 또한 고품질 수학 조판을 가능하게 하는 TeX 조판 시스템(1978년 출시)과 METAFONT를 개발했다. TeX는 학술 출판의 표준이 되었다. 그는 코드와 문서를 단일 소스로 결합하는 문헌적 프로그래밍을 위한 WEB 및 CWEB 시스템을 만들었다. 그의 MIX 및 MMIX 어셈블리 언어는 그의 책에서 저수준 프로그래밍 개념을 설명하는 데 사용된다.
후기 경력과 인정
커누스는 1969년 스탠퍼드 대학교에 합류하여 교수와 나중에 명예 교수가 되었다. 그는 알고리즘 분석과 프로그래밍 언어 설계에 대한 주요 기여로 1974년 튜링상을 받았다. 그는 또한 국가 과학 메달(1979년), 존 폰 노이만 메달(1995년), 교토상(1996년)을 받았다. 커누스는 그의 책에서 발견된 오류에 대해 금전적 보상을 제공하는 등 세부 사항에 대한 주의로 유명하다.
커누스는 소프트웨어 특허에 대해 공개적으로 반대해 왔으며, 의견서를 제출하고 특허청에서 증언했다. 그는 1990년대에 The Art of Computer Programming을 완성하는 데 집중하기 위해 적극적인 연구에서 은퇴했으며, 4A권과 4B권이 2011년과 2022년에 출판되었다. 그의 작업은 MIT와 카네기 멜론 대학교의 많은 사람들을 포함한 여러 세대의 컴퓨터 과학자들에게 영향을 미쳤다.
유산
커누스의 영향력은 알고리즘, 조판, 프로그래밍 방법론에 걸쳐 있다. 그의 교과서는 여러 언어로 번역되었으며 여전히 널리 사용된다. TeX 시스템과 그 파생물(예: LaTeX)은 과학 출판의 필수 도구이다. 그의 문헌적 프로그래밍 개념은 현대 문서화 관행에 영향을 미쳤다. 알고리즘 분석에 대한 커누스의 수학적 엄밀성에 대한 주장은 이 분야의 표준을 설정했으며, 인공지능 및 관련 분야에 대한 그의 기여는 수많은 명예 학위와 상을 통해 인정받고 있다.
고전적인 컴퓨터 과학에 초점을 맞추었음에도 불구하고, 커누스의 작업은 기초적인 알고리즘 기법을 제공함으로써 기계 학습과 신경망을 포함한 많은 현대적 발전을 뒷받침한다. 그의 유산은 컴퓨터 과학의 기초에 대한 탁월한 기여를 위해 수여되는 연례 커누스상(Knuth Prize)으로 기념된다.