그들은 알고리즘을 알았을까? by Martin Erwig

[ 밑줄 ]

 

ㅇ 계산은 표상을 변형시키는 것이다. 그러나 모든 변형 방식을 모든 표상에 적용할 수 있는 것은 아니다. 곱셉은 숫자끼리는 가능하지만 선분이나 도형에 적용할 수 없고, 길이의 측정이나 면적의 계산은 숫자에 대해서는 적용할 수가 없는 것처럼 말이다.

 

ㅇ 세부 사항을 무시하는 과정을 추상화라고 한다. 추상화는 컴퓨터 과학의 핵심이다.

 

ㅇ 알고리즘의 위력은 반복적으로 수행할 수 있다는 점에 있다. 미국에는 '있는 바퀴를 뭐하러 다시 발명하랴'는 속담이 있는데, 이 말처럼 좋은 알고리즘은 한 번 만들어지면 영원히 제 역할을 다한다.

 

ㅇ '계산은 문제를 해결한다'라는 기능적 관점은 어떤 문제를 적절하게 표현하고 하위 문제로 나눌 수 있다면, 계산을 통해서 문제가 해결될 수 있음을 강조한다. 이 관점은 컴퓨터 과학이 어떻게 다양한 사회 영역에 지대한 영향을 미칠 수 있었는지, 그리고 왜 계산이 모든 인간 활동에 있어 핵심적인 역할을 담당하고 있는지를 설명해 준다.

 

ㅇ '계산은 알고리즘의 실행이다.'라는 실체적 관점. 하나의 알고리즘은 그것을 실행하는 계산을 정확하게 설명해 줌과 동시에, 계산을 자동화하고 분석할 수 있게 만들어 준다. 이러한 관점에서 계산은 여러 단계로 구성된 절차로 설명하며, 왜 계산이 문제 해결에 효과적인지를 설명한다.

 

ㅇ 표상(representation)없이는 계산되 없다. 문제를 해결하려면 계산을 통해 현실 세게에서 의미가 있는 어떤 것에 대한 표상을 조작해야 할 필요가 있습니다. 헨젤과 그레텔의 위치는 두 가지 상태 중 하나에 대응됩니다. 숲속의 모든 위치는 죽을 수도 있는 위험의 상태에 대응되며, 집은 안전 및 상존의 상태로 문제의 해결에 대응됩니다. 그렇기 때문에 헨젤과 그레텔을 집으로 데려오는 계산이 문제를 해결할 수 있습니다. 이 계산은 그들이 위험 상태에서 안전 상태로 이동하도록 해 줍니다. 이에 비해, 숲속의 어떤 곳에서 숲속의 다른 지점으로 인도하는 계산은 안전한 상태로의 이동이라는 목적을 달성하지 못합니다. 

ㅇ  헨젤과 그레텔이 숲과 집이라는 지점 간의 이동으로 정의된 계산을 수행하기 때문에, 둘은 각 지점의 위치를 인식할 수 있어야 한다. 그래서 헨젤이 자갈을 도중에 떨어드리는 것이다. 자갈은 위치를 표시함으로써 컴퓨터, 즉 헨젤과 그레텔이 계산의 각 단계를 실제로 수행할 수 있도록 한다. 다층의 표상 계층을 갖는 일반적이다. 이 이야기의 경우 문제를 정의하는 표상(위치)와 해결책을 계산할 수 있도록 하는 표상(조약돌)이 있다. 모든 조약돌은 모두 모여 또 다른 계층의 표상을 구성한다. 모든 조약돌을 더하면 집으로 돌아가는 길을 나타낼 수 있기 때문이다. 

ㅇ 계산을 통한 문제 해결을 그림으로 요역하면 아래와 같다. 이것은 헨젤과 그레텔의 길찾기를 일련의 단계를 통해 계산으로 표상을 조작하는 관점으로 보여 주고 있다. 계산은 특정 문제를 해결하기 위한 과정이다. 일반적으로 계산은 여러 단계로 구성된다. 우선 문제를 표상하고, 각 단계에서는 해답을 얻을 때까지 이 표상을 변형한다. 헨젤과 그레텔은 숲에서 집으로 그들의 위치를 단계별로 그리고 조약돌별로 바꾸는 과정을 통해 생존의 문제를 해결한다.

ㅇ 계산과 문제 해결은 개별적으로 존재한다. 이들이 겹치는 경우가 종종 있지만, 일부 계산에서는 문제를 해결하지 못하며, 일부 문제는 계산을 통해 해결하지 않는다......명백한 의미가 없는 절차는 계산에 해당하기는 하지만, 문제 해결로 생각하기는 어렵다....논쟁의 소지가 좀 있기는 하지만, 모든 계산은 일단 문제 해결로 간주할 수 있다. 그 여부는 항상 표상과 연관된 의미에 달려 있다. 예를 들어 숲 안의 고리 형태의 경로를 따라가는 것은 헨젤과 그레텔에게는 무의미하지만, 운동을 하려는 사람에게는 체력 단련의 문제를 해결할 수 있게 해준다. 따라서 어떤 계산이 문제를 해결하는지 여부는 보는 사람의 눈, 즉 계산의 유용성에 달려 있다. 어쨌든, 특정 계산이 문제 해결을 하고 있는지는 계산의 본질에 영향을 미치지 않는다.

 

ㅇ 문제가 규정된 방법을 따르지 않고 임시적인 방법으로 해결되면 계산이 아니다. 즉, 계산은 반드시 체계적이어야 한다.....해결책은 재현할 수 있고 많은 유사한 문제를 해결할 수 있어야 한다. 즉, 조약돌을 따라가서 문제를 해결하는 방법은, 조약돌의 배치를 바꾸어도 반복적으로 실행할 수 있기 때문에 차별화된다. 

 

ㅇ 문제 해결과 계산 사이의 구분. 현실 세계에서 의미 있는 효과를 만들어 내지 못하는 계산은 문제를 해결하지 못한다. 재현 불가능한 임시적인 문제 해결 방법 또한 계산이 아니다.

ㅇ 문제 해결 관점은 계산이 체계적이고 분해 가능한 과정임을 보여 주지만, 계산에 대한 포괄적이고 정확한 그림을 제시하기에는 충분하지 않다. 계산을 문제 해결로 보면 계산이 모든 상황에서 활용 가능하며 그에 따른 계산의 중요성을 나타낼 수 있겠지만, 이 관점은 계산이 작동하는 방식과 왜 다양한 방식으로 성공적으로 적용될 수 있는지를 설명해 주는 몇 가지 특성을 간과하게 된다.

 

ㅇ 알고리즘을 언어화하여 표현하게 되면 더 많은 사람들이 더 많은 계산을 할 수 있게 되어 계산이 확산될 수 있다. 알고리즘을 표현하고 있는 언어를 컴퓨터가 이해할 수 있다면, 계산은 끝없이 확산될 수 있으며 오직 컴퓨터를 구축하고 운영하는 데 필요한 자원의 제약에 의해서만 제한될 것이다.

- 알고리즘은 실행을 위해 컴퓨터가 이해할 수 있는 언어로 표현될 수 있어야 함

- 알고리즘의 설명은 무한히 계속되어선 안 되고 한정되어야 함

- 알고리즘의 각 단계는 모두 어떤 결과를 만들어 내야 함

- 알고리즘은 항상 종료되며 정확한 결과를 제공하는 계산을 만들어 내야 함

 

ㅇ 모든 컴퓨터는 알고리즘에서 사용되는 표상에 접근할 수 있어야 한다. 특히 컴퓨터는 각 표상에 필요한 변경을 만들어 낼 수 있어야 한다......모든 컴퓨터는 알고리즘 작동의 대상이 되는 표상을 읽고 조작할 수 있어야 하며 범용 컴퓨터는 알고리즘이 기술된 언어를 이해해야 한다. 

 

ㅇ 계산은 표상을 조작함으로써 작동하는데, 표상이란 의미 있는 어떤 것을 나타내는 상징이나 기호 같은 것이다. 

 

ㅇ 표상은 최소한 두 개의 부분으로 나뉜다. 표현의 대상과 대상을 무엇으로 표현하는가다. 

 

 

[ 자평 ] 기가 막힌 책...

 

저자는 미국 대학의 컴퓨터공학과 교수이다.

책이 내용도 컴퓨터공학분야의 '자료구조/알고리즘'에 관한 것으로 분류되는 책이다.

 

알고리즘에 대한 책이 이렇게 철학적일 수 있다니, 정말 기발하고 감탄스러운 책이다. 

원서의 제목은 'Once Upon an Algorithm: How Stories Explain Computing' (2017년)이다.

 

보통 내가 대학교에서 자료구조/알고리즘을 배웠던 90년대 초반은 이런 책을 읽었던 것 같다.

즉, 바로 알고리즘으로 들어 가는 것이다.

 

일단 필요한 부분을 먼저 읽었다.

Chartper 01 계산과 알고리즘: 헨젤과 그레텔

01. 계산을 이해하는 길

02. 정말로 가 보기: 계산이 실제로 벌어질 때

 

무언가가 왜 만들어 졌는가?를 안다는 것은 더 깊은 원리를 안다는 것이다.

원리를 더 깊게 아는 것은 또 다른 응용을 넘아 한 차원 다른 응용을 낳는다.

 

왜 'C로 배운 알고리즘'을 달달 외우듯이 배운 우리 컴퓨터 공학자들이, 

OS를 만들지 못하는지? 알파고를 만들지는 못하는지? 

 

나는 그들과 우리가 지식을 추구하는 깊이와 차원에서 뭐가 다른지 얼핏 알 수 있었다.

더 깊이 안다는 것은 더 높이 본다는 것이다.