1-(1) The role of algorithms in computing

해당 단원은 알고리즘의 정의와 그 역활에 대해 서술하는 단원이다.

 

서술에 의하면, 알고리즘이란 잘 정의된 계산 문제(Well-specified computing problem)에서 input으로부터 원하는 output을 얻어내는 과정의 computational procedure라 얘기하고 있다. 그냥 수학적 문제를 푸는 방법의 수학적 서술이라 생각하면 될 것 같다. 대부분의 사람들이 갖고 있는 insight와 크게 다른 것을 제시하는 것 같지는 않다.

 

이런 알고리즘의 correctness는 모든 input에 대해 원하는 output을 얻어내는 성질로서 정의되며 알고리즘의 표현은 사람의 언어를 통해 이루어질 수도 있고 컴퓨터 언어를 통해 이루어질 수도 있다. 표현에서 중요한 것은 수학적인 형식으로 명확하게 표현되어야 하는 성질이다.

 

또한 알고리즘을 통해 해결할 수 있는 문제들을 제시하고 있는데, 대부분의 사람들이 알고있는 정렬 문제 같은 것부터 복잡해 보이는 수학적 문제들까지 제시하고 있다. 그리고 이런 알고리즘을 효과적으로 운용하고 적용하기 위해서는 자료구조에 대한 이해가 필요하다고 말하고 있다. 실제로 목차를 보면 '특정 자료구조의 제시- 자료구조를 이용하여 수행할 수 있는 알고리즘'으로 구성된 단원이 많다. 이런 서술들을 볼 때 자료구조와 알고리즘은 크게 관련있는 과목이라는 것을 생각해볼 수도 있다.

 

그렇다면 문제 해결 시 알고리즘의 성능 평가는 어떻게 하는가? 사용하는 자원의 측면에서 생각해보면 문제 해결 시 컴퓨터의 높은 층위 측면(사람에 가까운)에서 생각해볼 때 사용되는 자원은 시간과 메모리일 것이다. (알고리즘은  그 방법이 다루는 자료들을 저장하기 위해 메모리 자원을 필요로 한다.)일단 여기서는 시간만을 얘기하고 있지만, 실제로는 시간만이 중요한 것은 아니다. 만약 임베디드 시스템과 같이 그 메모리 자원이 매우 한정된 환경이 주어진다면 우리는 "작동하는" 알고리즘 구현을 위해서 시간을 조금 포기해야 할 수도 있다. 여기서 하드웨어 상의 성능 한계와 최적해를 알 수 없는 NP problem도 얘기하고 있지만 조금 벗어나는 얘기니까 이 정도로 정리하자. 

 

그렇다면 이런 알고리즘의 평가는 어떻게 하는가? 이것은 상기 서술한 내용들을 바탕으로 정리해보면 다음과 같을 것이다.

(1) 정확한 해를 내는가?

(2) 자원효율적인가?

책은 (1)의 측면에서는 무한히 빠르고 memory-free한 컴퓨터가 있어도 알고리즘이 필요한 이유를 제시하고 있다. 모든 비효율적인 알고리즘들이 수행될 수 있는 컴퓨터라 하더라도 문제를 정당히 푸는 수학적 방법에 대한 묘사는 필요하기 때문이다. 또한 알고리즘에 이런 정당성을 부여하는 correctness proof는 아마 조금 뒤에서 다루어지는 내용인 것 같다.

또한 (2)의 측면에서는 그것을 평가하는 척도(방법)를 얘기하고 있는데 빅 오 방법을 그 이름 없이 다루는 것 같다. 이건 나중에 제대로 책에서 다루겠거니 싶은데 다루지 않으면 문서를 따로 빼서 작성하겠다.