The Art of Computer Programming - 제1장 기본 개념 1.1 알고리즘

아침 6시에 일어나 씻고 30분간 1장의 1.1 알고리즘 부분을 보았다.

정말 기본 개념인만큼 알고리즘의 이름의 기원부터 시작을 하였는데,

예전에는 algorism밖에 없었다가 1957년에 algorithm으로 Webster's New World Dictionary에 올랐다고 한다.

초기 언어학자는 이 단어의 기원을 알아내려다가 algiros(고통스러운)+arithmos(수) 라는 합성어가 아닌가 하는 추측을 했다고 한다.

(맞는지도...)

알고리즘이 뭔지를 설명하기 위해서 간단한 유클리드 알고리즘부터 설명을 하였고 그 과정에서의 n<-r, m<-r 을 n <- m <- r 로 표현이

가능하다는 것을 알려주어 알고리즘에서 어떻게 하면 단계를 줄여나가는지를 알려주려한거 같았다.

그리고 m = 119와 n = 544의 몫이 당연히 0으로 나오는 예제를 말하여 만일 m < n 이면 m <-> n으로 교환한다를 추가하여 한번 더 단계를 줄이는 구조를 선보였다. (신기하다 신기해)

그리고 아마 이 장에서 가장 중요한게 아닐까 하는 알고리즘의 5개 규칙이 있었다.

1. 유한성

반드시 유한한 횟수로 거친 후에 종료해야 한다.

당연한 것인거 같다. 아마 프로그래밍으로 생각하면 무한포문을 의미한게 아닐까?

아 참고로 유한성만을 제외한 알고리즘의 다른 모든 특징을 가진 것은 계산적 방법(computational method)라고 한다.

2. 명확성

이름 그대로 명확해야 한다는 것이다

유클리드 알고리즘에서 -8을 -파이로 나눈다던지 59/13을 0으로 나눈다던지의 경우 나머지에 대한 보편적인 합의가 존재하지 않는다.

(사실 보편적인 합의가 존재하지 않는다는게 이해가 안된다. 그냥 59/13을 0으로 나누면 0으로 나눌수 없어서 망하는게 아닐까?)

그래서 이 명확성을 지키려면 m과 n의 값이 항상 양의 정수가 되도록 보장해야 한다고 한다.

3. 입력

input인데 말 그대로 m과 n에 어떤 값을 넣고

프로그래밍에서는 매개변수를 받듯이 입력이 있어야 한다.

4. 출력

output인데 말 그대로 m과 n에 어떤 값을 넣고 계산을 통해 나온 결과값이 있듯이

프로그래밍에서는 plus 메소드가 있다면 return sum1+sum2를 하여 output을 내보내는 것 같다.

5. 효과성

알고리즘은 충분히 단순해야 한다는 것이다.

음 예를 들자면 어떤 알고리즘에 쓰이는 값들이 무한히 확장가능한 실수거나 정확히 예측이 안되는 선분의 길이면 연산들이 효과적이지 않은데

그냥 이해가 안간다^^

따로 알아보고 올려야겠다.

이렇게 5개 정도의 알고리즘의 규칙이 있었는데 그 뒤에 나오는 말들은 덧붙이는 설명 같았다.

가장 기억에 남는 것은 알고리즘 책을 필자가 프로그래머용 요리책이라고 하고 싶었다는데 조리법의 경우는 명확성이 없다고 한다.

예를 들어 소금을 약간 치세요 같은 문장은 두가지 문제가 발생한다.

소금을 약간 치세요

도대체가 약간의 정도는 얼마 만큼이고 누구한테 치라는건가?

약간은 사람마다 다 다르게 느껴지고 치세요는 내 옆에 있는 친구 머리에 칠 수도 있다.

숙달된 요리사는 물론 다 이해가 가능하고 훌륭한 요리를 만들어 내겠지만 초심자들은 매우 어렵다.

음 그렇다고 한다.

이정도까지 정리를 마치고 저녁에 효과성에 대해 다시 알아봐야겠다.

----PM 10:42

아침엔 졸려서 정신이 없었나보다

효과성은 결국 간단하게 말하면 그 알고리즘을 사람이 그려나가면서 풀 수 있을 정도로 간단한지를 의미하는 것 같다