Randomized Algorithms

이 책은 한국에서 Amazon으로 산 것으로 기억 난다. 꽤 오래 가지고 있었던 것 (석사 때 언젠가 산 듯) 같은데 항상 봐야지 봐야지 하고 있다가 올해 봄에 시작을 하게 되었다. 처음 한 챕터를 읽으면서 바로 '바이블 격이 될 만한 책'이라는 느낌이 확 들었다. 왜, 무슨 동기로 샀는 지는 기억이 안나는데 현재 내가 부족하다고 느끼던 부분을 시원하게 긁어주는 그런 느낌이었다. 1-epsilon 이 들어간 증명이나 각종 guarantee들을 해주는 논문들을 보면 분명 내가 아는 확률들을 쓰고 있는데 전혀 다른 나라의 언어로 말하고 있는 느낌이 들 때가 많았다. 그리고 다음과 같은 황당한 질문들에 대한 답을 보면 정말 어떻게 저런것들을 증명하나... 하는 생각을 자주 했다.
- 이 문제에서 어떤 randomized algorithm도 최소 얼마의 시간이 걸린다.
- 이런 이런 문제에서 이런 이런 성질을 만족하는 답이 존재한다.
- 어떤 deterministic 알고리즘도 최소 이 정도의 시간이 걸린다. 우리 알고리즘은 이 만큼 잘한다.
젠장...&*#%#$%#*

이 책은 여러 radmonized algorithm들에 자주 쓰이는 기법, 중요한 아이디어들을 grouping하여 중요한 알고리즘과 예를 보여주는데 Textbook의 확률과 실제 논문에 쓰이는 것들의 갭을 이어준다고나 할까. 아주 약간 예를 들면 교과서에 (정석 레벨) 에서 다음과 같은 기본을 배운다고 치면
- 까만공 3, 빨간 공 4에서 두 개를 뽑을 때 두 개 다 빨간 공일 확률
이 책에서 어떻게 다음과 같은 질문에 접근하는 지를 설명해 준다.
'm개의 공을 n개의 bin에 랜덤하게 던질 때'
- 매우 높은 확률로 어떤 bin도 k개 이상의 공을 가지진 않는다.
- 빈 bin의 갯수의 평균(expectation) 은 얼마이고 이 값에서 얼마 이상 벗어날 확률은 매우 작다.

내가 무척 어렵다고 생각했던 논문들이 어려운 것도 있겠지만, 그 이전에 내가 그런 논문을 읽을 기본이 좀 덜 되 있었다고나 할까... 그런 생각이 든다. 어떤 기본 가락이랄까, 많이 쓰는 toolkit들 자체를 모르고 있었던 듯한 느낌.

책을 보는 건 좋은데 문제는 시간이 정말 오래 걸린다는 것이다. 책은 여러 개념들을 아주 자세하게 설명하고 있고 어려운 theorem 등을 원래 논문보다 좀 더 간략하게 하여 보여주는 데, 그렇다고 절대 만만치 않다. 자세하지만 아주 dense하다. 우연히 옆의 포닥이 Probability and Computing이라는 책을 가지고 있어서 빌렸는데 지금 내가 지금 1/4 조금 넘게 본 상태에서 보니 웬만한 그 책의 목차에 있는 내용을 다 커버했다. -.-;; 가끔 그냥 증명이 없는 단 한줄짜리 기술이나 corollary, 또는 "Clearly,..." 이런 문장 하나가 빡 돌게 만든다. 같이 공부하는 사람이 있는 것도 아니고, 웹에 답이 있는 것도 아니고... 가끔 웹에 강의 노트에 생략된 부분을 좀 더 보충해 놓은 경우를 찾는 경우가 있는데 이 때 보면 핫 이런 간단한 것을 이럴 때도 있지만. 허거덕... 하는 경우도 많다. 정확하게 '정석 II' 처음으로 보는 느낌이 들고, 그 정도의 시간이 들 것 같다. (정석은 해설집이라도 있었지. 쩝...)

증명을 따라 가기 어려운 경우가 많아서 (이해는 된다. 중요한 개념 설명에 그런 것들까지 세세하게 하면 책 두께가 흘...) 별 다섯개에 다섯개는 주기 힘들 것 같다. 사실 지금 방금 5.5 The Lovasz Local Lemma의 4페이지를 근 며칠 만에 끝내고, 정말 또 하나 긴 터널을 지난 느낌이 들어서 이 글을 그적거리고 있었는데 아마존에 가서 review를 읽다 보니 혼자가 아니라는 느낌이 든다.

Overall, the authors explain core concepts, the examples and the possible applications well. However, the readibility of their proof is far from that of the above three. Honestly some proofs should be re-written completely.

For example, in page 116, they try to use the induction method to prove Lova(')sz Local Lemma. After reading that page many times, I still didn't understand the structure of their proof.

I was TA for under-grad level algorithm course, got A+ in advanced Calculus II and A in intro. to PDE (both in under-grad level), really knew something about induction method and a little bit about algorithm. I am not smart, but far from stupid.

In the end, I google the internet and found a 3-page proof for the same thing. That's easy to catch in few minutes, and then, I understand the 1-page proof in the book. Is it ironic?

푸할할... 이게 사실 내가 정확하게 밟은 길이었다. induction으로 증명을 했는 데 그 구조가 정확하게 파악이 안돼 해매고 있었는데  빌린 'Probability and Computing'에 아주 자세하게 나와 있어서 그 챕터를 다 읽고 다시 봤더니 이해가 됐었다. 이러니 한 챕터 시작하기가 겁난다.

다음 review가 정확하게 이 책을 요약한 것 같고 약간의 희망을 준다.

 An enciclopedia for randomized algorithms., July 20, 2001 The book has an exoustive amount of algorithms. Not everything is proved. Sometimes the proof contains to few steps to be understood. There are many algorithms explained well. After reading this book it is easy to create your own randomized algorithms.
by 호빵 | 2008/12/07 17:22 | | 트랙백 | 덧글(0)
트랙백 주소 : http://zoolook.egloos.com/tb/4005391
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]

:         :

:

비공개 덧글



< 이전페이지 다음페이지 >