Selected Papers on Computer Science

논문도 다 썼겠다 놀면서 요즘 읽는 책입니다.

This book assembles under one roof all of the things I’ve written about computer science for people who aren’t necessarily specialists in the subject—for scientists and mathematicians in general, and for educated people in all fields. I’m grateful for this opportunity to put the materials into a consistent format, and to correct errors in the original publications that have come to my attention. If any of this work deserves to be remembered, it is now in the form that I most wish people to remember it.

보시는 바와 같이 Knuth 교수가 8권의 시리즈 물중 하나로 1996년에 출판한 책입니다. 설명에는 비 전문가도 읽을 수 있다고 되어있으나 최소한 수식을 따라갈 정도는 되야 읽을만한 듯. 인상 깊은 구절은, “컴퓨터 과학이 무엇인가?”에 대한 설명.

My favorite way to describe computer science is to say that it is the study of algorithms. An algorithm is a precisely-defined sequence of rules telling how to produce specified output information from given input information in a finite number of steps.

매우 클리어하죠? 다행히 제가 생각하는 CS의 정의와 잘 맞습니다 ^^;

하지만 Knuth 는 이어 컴퓨터는 기계에대한 학문이기도 하며, 따라서 전자, 과학 등의 모든 분야를 통칭하는 것으로 봐야하고, 따라서 Computer Science(CS)는 단지 알고리즘의 연구라고 말할때에는 CS를 둘러싼 현상 중 하나만 짚은 것임을 알아야한다고 말합니다.

1장에서는 수학과 컴퓨터 과학은 상호 유사하지만 다름을 설명합니다. 그리고 가장 큰 차이가 바로 finite nubmer of steps에 알고리즘이 완료되야 한다는 것입니다. 하지만 수학과 컴퓨터 과학은 상호 연관된 학문으로 서로의 문제를 풀기도 하고 새로운 연구거리를 서로에 제공하기도 한다고 말합니다. 그러한 예로 그는 hashing의 collision 의 해결책 중 하나인 linear probing의 average time complexity 계산의 예를 보여줍니다. 풀이 과정이야 worst case analysis가 아니므로 많이 복잡합니다… 따라가기야 하겠지만, “내가 과연 저걸 생각할 수 있을까?”에는 의문이 드는;;; 한편 그 과정에서 Concrete Mathematics라는 그의 또 다른 저서를 알게되었는데요. ConCrete는 CONtinuous + disCRETE 의 합성어라는데, 도서관에서 잠깐 읽어보니 따라가기 쉽게 고등학교 수준(시그마가 무엇인가. k를 1 부터 n까지 더하면 얼마인가)부터 convolution등의 주제에 이르기까지 폭 넓게 잘 되어있더군요. 박사를 가는 게 확정되면 읽어봐야겠다는 생각이 들었습니다.

2장의 주제는 “유한(finiteness)”이라는 것입니다. 여기서부터는 아직 읽고 있으니.