The Art of Computer Programming

2010.10.10.

 

제가 개인적으로 읽고 있는 책입니다.

이 책은 Donald E. Knuth라고 하는 분이 쓰신 책인데요.  역작이라고 할 수 있습니다.

그러나 이 책을 읽기 위해서는 수학에 대해서 이해도가 높아야 하죠.  그렇지 않다면 조금 읽고서.. "이해 안 가"하면서 버릴만한 책이죠.

   

류광씨가 번역한 책이 한빛미디어를 통해서 판매되고 있으니 굳이 원서를 볼 이유는 없습니다.  오탈자가 좀 있는 것은 그런가 보다 이해하면 됩니다만..

   

틈나는대로 이 책에 대해서 글을 올릴까 합니다.  물론 책 전체를 다 번역한다는 것은 아닙니다.  제가 이해하는 부분을 쓰기 때문에 혹시 책을 보면서 알고 싶으신 내용있으면 같이 풀어나갔으면 합니다.

   

CHAPTER ONE

   

1.1 알고리즘(Algorithms)

알고리즘이란 것은 일의 순서를 나타내는 것으로 컴퓨터 프로그램의 기본을 이룹니다.

   

알고리즘이란 것은 "입력"과 "출력"이 있다면, "입력"을 가지고 "출력"을 만드는 방법을 기술한 것입니다.

실생활에서도 알고리즘을 적용할 수 있는데, 예를 들어서 음식의 레시피는 "알고리즘"의 대표적입니다.

   

"라면끓이기"

- 입력 : 라면 한봉지, 달걀

- 출력 : 라면 한그릇

A1 냄비에 물을 두컵 넣습니다.

A2 냄비에 물을 끓입니다. 

A3 물이 끓는다면, 라면 봉지를 뜯습니다.

A4 라면 스프를 끓는 물에 넣습니다.

A5 라면을 끓는 물에 넣습니다.

A6 2분이 경과하면 불을 끕니다.

A7 냄비에 있는 내용물을 그릇에 담습니다.

   

이와 같이 알고리즘이란 것은 "입력" 을 "출력" 에 넣는 과정입니다.

   

수학에서도 이런 알고리즘은 항상 적용됩니다.

3+4 를 생각한다면,

입력은 "3"과 "4" 입니다.  출력은 "3+4"를 계산한 "7"이 나오겠죠.

+는 앞의 숫자의 4번째 다음수를 뜻합니다.  어떤 수의 다음 수라는 것은 피아노 공리를 적용하면 됩니다.

   

x + y 를 계산하는 알고리즘을 표현하자면,

   

B1 : i ← 0, m ← x

B2 : m ← m', i ← i'   (m', i' 는 m과 i의 다음 수를 뜻합니다.)

B3 : 만약 i = y 라면, 이 알고리즘을 끝낸다.  결과는 m에 저장되어 있다.

B4 : B2 로 돌아간다.

   

이렇게 한다면 더하기에 대한 알고리즘이 완성되었습니다.

   

알고리즘은 정확해야 하며, 그 결과가 항상 원하는 결과를 보장해야 합니다.  그리고 효율적이어야 하고요.

   

더하기 알고리즘을 검증하자면, 일반적으로 수학적 귀납법(induction)으로 적용할 수 있습니다.

   

수학적 귀납법은 증명에 있어서 아주 유용합니다.

수학적 귀납법은 자연수의 완비성에 의해 그 증명이 완성됩니다.  피아노 공리를 보셔도 상관이 없습니다만, 여기서는 귀납법을 이용한 자연수의 정의를 살펴보도록 할께요.

I1 : 1은 자연수이다.

I2 : 어떤 수 a 가 자연수라면 a+1 도 자연수이다.

   

이를 이용하면 어떤 자연수라고 해도.. 무수한 닥질을 하면 자연수임을 밝힐 수 있습니다.

예를 들어서 3이 자연수인가 물어본다면,

2 + 1 = 3 이므로..

2가 자연수라면 3도 자연수입니다.

마찬가지로

1 + 1 = 2 이므로..

2는 자연수입니다.

그러므로 3도 자연수라는 것을 증명할 수 있습니다.

   

귀납법적 증명

1+2+3+...+n = n(n+1)/2

이다.

   

자 이것을 증명하면,

i) n = 1 일 때,

1 = 1(1+1)/2 이므로 성립

ii) n = k 일 때, 주어진 식이 올바르다고 가정하면,

iii) n = k+1 일 때,

(좌변) = 1 + 2 + ... + k + k+1 = k(k+1)/2 + k+1 = (k+1)(k/2 + 1) = (k+1)(k+2)/2 = (우변)

이므로 성립하므로,

n >= 1 일 때, 준식은 항상 성립한다.

   

라고 증명할 수 있습니다.