전산학 클래식 - Computers and Intractability

Bookmark and Share
PENTAX Corporation | PENTAX Optio S5z | Normal program | Center-weighted average | 1/100sec | F/2.6 | 0.00 EV | 5.8mm | ISO-200 | Off Compulsory

"Never increase, beyond what is necessary, the number of entities required to explain anything"
--- William of Ockham(1285-1349)

멋있게 이 말을 번역하긴 힘들 것 같지만, '어떤 것을 설명하는데 더도 말고 덜도 말고 딱 필요한 만큼의 말이 필요하다'. 정도일 것 같다. 전산학 (computer science)라는 학문의 클래식 중에서도 이 말과 딱 어울리는 책이 있다. 바로 <<Computers and Intractability : A Guide to the Theory of NP-completeness>>라는 책이다. 굉장히 어려운 주제를 다루는 책임에도 불구하고, 이 책은 요즘 보이는 대부분의 컴퓨터 관련 책보다 엄청나게 얇다.

내 생각에 컴퓨터가 '과학'이라고 불릴 수 있게 해 준 분야가 바로 이 책이 다루고 있는 분야라고 생각한다. 컴퓨터는, 하드웨어로만 본다면, 전자과에 기반을 둔 '공학'이다. 사실 내가 하고 있는 컴퓨터 시스템이라는 분야도 '공학'이다. 내가 생각하는 공학은 '최소 비용으로 최대 효율'을 *어떻게* 만들어 낼 것인가를 다루는 학문인데, 컴퓨터 시스템이 이런 공학의 대표적인 분야라고 할 수 있다. 사실 공학을 하는 사람들은 공돌이라고 낮게 부르는 말이 있지만 과학자에게는 그런 말이 없듯이, 엔지니어(engineer)보다는 과학자(scientist)가 좀 더 있어 보이는 것은 어쩔 수 없는 것 같다.

그런데 이런 컴퓨터쟁이들이 공돌이를 면할 수 있는 분야가 바로 "알고리즘" 분야다. 알고리즘이야말로 (이론상으론) 사실 컴퓨터시스템을 전혀 모르고도 할 수 있는 컴퓨터 전공분야다. 그리고 우리 시스템 하는 사람들 입장에서는 소위 말하는 *천재*들만 할 수 있는 분야라고 하기도 한다. 알고리즘은 쉽게 말해서, 어떤 문제가 주어졌을때, 그 문제를 어떻게 풀까를 다루는 분야다. 사실 인생에서 우리는 부딫히는 많은 문제들을 알게 모르게 풀고 살아가는데, 그 때 자기 나름의 문제를 푸는 방식과 방법이 있을 것이다. 그것이 바로 알고리즘의 하나라고 볼 수도 있을 것 같다.

"세상의 수 많은 문제들 중에는 어려운 것도 있고 쉬운 것도 있는데, 뭐가 어려운지 뭐가 쉬운지 알 수 있는 방법이 없을까" 같은 어찌보면 시덥잖은 고민을 하는 사람이 생겼다. ^^ 사실 이 질문은 굉장히 중요한데, 만일 그 문제를 풀지 않고도 그 문제가 굉장히 어렵다는 것을 알 수 있다면, 그 문제 풀기를 포기하던지, 아니면 그 문제를 조금 더 쉽게 바꾸어 풀 던지 하는 방법을 쓸 수가 있게 된다.

이런 질문을 하던 알고리즘맨들은 세상의 질문을 크게 3가지 정도로 나눠봤다. (더 자세하게도 나누겠지만...)
1) 절대 못 푸는 문제, 2) 풀 수는 있으나 엄청나게 시간이 많이 걸리는 문제, 3) 시간도 얼마 안 걸리고 풀 수 있는 문제.

풀 수만 있다면, 문제의 난이도는 바로 "시간"이다. 인간은 이 시간의 제약을 받고 이 세상을 살아가기 때문에, 어떻게해서든 빠른 시간 안에 문제를 풀어야 한다. 아무리 정확한 답을 구할 수 있더라도, 100년 200년이 걸린다면 그 답을 구한들 의미가 없을 것이다. (사실 100년 200년은 그나마 극복 가능한 시간이다. 하지만 2번 종류의 많은 문제들은 수십 세기가 지나도 못 푸는 것들이 많다)

소개가 길었는데, 바로 이 책이, 세상의 질문 중에 2번에 속하는 질문들에 대한 책이다. 그래서 제목도 우리말로 하면, '컴퓨터(계산기)와 풀기 억수로 어려운 문제에 대해서'라고 할 수 있다. 이 책 한페이지 한페이지를 읽을 때마다, 이런 사람들이 있었기에 컴퓨터 연구자들이 완전히 공돌이 취급만 받지 않을 수 있구나하는 것을 감사하게 생각한다. 아무리 읽어도 일반적인 나 같은 사람은 이해가 잘 안 된다. 심지어 한 페이지를 이해하는데 하루종일 걸리기도 했다.

PENTAX Corporation | PENTAX Optio S5z | Normal program | Center-weighted average | 1/60sec | F/3.5 | 0.00 EV | 10.2mm | ISO-200 | Off Compulsory

이번에 논문을 쓰면서 내가 풀고자 하는 문제가 2번에 속한다는 것을 증명해야 했다. 그래야 내가 푸는 문제가 하도 어려워서 엄청나게 많은 시간이 걸리니까, 나는 꽁수를 부려서 문제를 풀겠다는 것을 남들이 (사실은 교수님들이) 인정을 해 주기 때문이다. 그런데 2번에 속한다는 것을 증명하려니, 예전에 2학기 정도 알고리즘 공부를 한 것으로는 턱없이 모자라는 나의 기초지식이 문제였다.

그래서 어떻게 어떻게 구한 책이 바로 이 책이다. 많은 논문들과 최근에 나온 책들이 참조하고 있는 바로 '오/리/지/날' 그 책이다. 사진처럼 1979년에 처음 찍은 책이고, 그 때 까지 이 분야에서 나온 많은 이론들과 문제들을 이 책이 정리를 해 둔 것이다. 근데도 200페이지 남짓 밖에 안 된다. 정말 군더더기 없이 깔끔하게 정리를 해 놨는데... 그런 깔끔함 덕분에 책은 얇아졌는지 모르겠는데, 나는 이해하기가 더 힘들어진다! ^^;;

졸업을 하게 되면, 이 책의 도움을 많이 받게 되는 건데, 이 책을 사고 싶어서 좀 알아보니, 국내에는 이미 없었다. 사려면 미국에서 사와야 했는데, 새 책은 무려 50달러가 넘고... 200페이지 밖에 안 되는 책이 무슨 50달러... 헌책은 20달러 후반부터 있는 것 같다. 이 책은 꼭 사보고 싶네.

종종 보면 어느 어려운 책을 다시 설명한 책들이 많다. 처음에는 이런 책이 쉬워서 접근하기 쉽지만, 시간이 지나 점점 더 깊숙이 들어가게 되면 결국은 이런 *얇은* 오리지널 책을 가까이 하게 되는 것 같다. 마치 어릴 때는 만화 삼국지를 읽다가, 좀 커서는 그림 한장 없는 삼국지를 읽으면서 재밌어 하듯이 말이다.



신고
Trackback 0 Comment 1
  1. Favicon of http://5bpa.tistory.com BlogIcon 장작가 2008.09.26 13:49 신고 address edit & del reply

    다시 찾아보니. 340페이지 정도 되는 책이네요. 그래도 정말 얇습니다. ㅠㅠ
    근데, 한 페이지 이해하는데 반나절이 걸리네요.

prev 1 ··· 138 139 140 141 142 143 144 145 146 ··· 348 next


티스토리 툴바