알고리듬(Algorithm)이 뭐에요?
라는 아이의 질문에 대답하기는 쉽지 않습니다.
알고리듬이라는 단어는 9세기 페르시아 수학자 Muhammad ibn Musa al-Khwarizmi에 의해 처음 사용되었고.
어떤 문제를 해결하기 위한 계산 절차, 처리과정 쯤으로 생각하면 될 듯합니다.
그 예로는 유클리드의 최대공약수 알고리듬이 있습니다.
(Euclid's algorithm)
양수의 정수 m과 n이 주어졌을때, 가장 큰 공약수를 구하는 알고리듬입니다.
E1. [나머지 찾기] m을 n으로 나누고 그 나머지를 r이라고 합니다. (0 <= r < n 범위의 r이 구해질 것입니다.)
E2. [0인지 확인] 만약 나머지 r 값이 0이라면 (r=0) 알고리즘은 종료되고, 결과값은 n이 됩니다.
E3. [환원 과정] m <- n, n <- r 그리고 E1 과정으로 돌아갑니다. ❚
위의 간단한 예에서 각각의 절차는 알파벳 E와 숫자로 시작하고 그 뒤에는 꺽쇠가로 내의 간단한 정의 그리고 절차의 명확한 내용이 나옵니다.
E3에서의 m <- n, n <- r 의미는 다음에 진행될 연산 E1에서 사용될 값 m과 n을 재정의 한다는 말인데, m에는 n의 값을 대입하고 n에는 r값을 대입하라는 말입니다.
TAOCP(The Art of Computer Programming)이라는 책에서는 알고리듬이 성립하기 위한
다섯가지 조건들에 대해서 이야기합니다.
다들 아래의 내용들에 대해서 동의 하실지 모르겠지만,
첫번째 조건은 유한성(Finiteness)입니다.
즉 알고리듬이 일정한 횟수만큼의 연산 후에 종료되어야 한다는 말입니다. (반례로 Reactive process를 드는데 이는 환경과 지속적으로 상호 소통하는 프로세스를 이야기합니다. 그렇다면 요즘 사용하는 웹서버 애플리케이션을 하나의 큰 알고리듬이라고 할 수는 없는 걸까요?)
두번째 조건은 명확성(Definiteness)인데 각각의 절차가 정확하게 정의되어야 한다는 말입니다. 여기에는 절자의 제약조건에 대한 내용도 포함되어야합니다. 이는 보통의 언어로도 표현이 가능하지만 소프트웨어 개발자들은 이를 '프로그램'을 통해서 표현합니다.
세번째 조건은 입력값(Input)인데, 0개 혹은 여러개의 입력값을 알고리듬에 입력할 수 있어야합니다. 이는 주로 함수의 인수와 비교되기도합니다.
네번째 조건은 결과값(Output)입니다. 이는 하나 혹은 여러개일 수 있는데, 함수의 치역과 비교되는 값입니다.
다섯번째 마지막 조건은 효율성(Effectiveness)입니다. 이는 비교적 간단한 연산들을 사용해 충분히 효율적으로 문제를 해결할 수 있어야한다는 말인데, 결국에는 가장 어렵고 중요한 조건이지 않나 생각됩니다.
그래서 아이가 알고리듬이 뭐야? 라고 물어본다면...
나도 아직 잘 모르겠어라고 답해야 할 것 같습니다.
