📌 먼치 POINT

1.알고리즘

• 10세기에 활동한 수학자, 알 콰리즈미에서 유래

• 마방진, 유클리드 알고리즘 등 2천 년이 넘는 기간 동안 사용

• 컴퓨터로 인해 인간의 힘을 넘는 계산이 가능해졌지만, 의존도가 높아졌다는 단점 존재

2.알고리즘의 활용

• 영지식 검증 → 정보를 알려주지 않고 계산결과의 정확성 검증

• 영상 처리 → 두 영상의 거리 설정

• 수학적 증명 검증 → 프랑스에서 개발된 Coq 프로그램

알고리즘, 1천 년의 역사를 가진 개념

보통 알고리즘 하면 컴퓨터를 떠올리지만, 실제로는 컴퓨터가 있기 전에도 알고리즘이 존재했습니다. 알고리즘이라는 말 자체는 약 1천 년쯤 된 용어로, 10세기 정도에 활동했던 페르시아 수학자 알 콰리즈미에서 유래했습니다.

중학교 때 방정식을 풀 때를 생각해보면, 양쪽에 같은 수를 더하고 빼고 나누어서 미지수 x의 값을 구했습니다. 이런 식으로 어떤 절차에 따라서 문제를 푸는 과정을 체계적으로 정리한 사람이 알 콰리즈미였습니다. 나중에 이 내용들이 유럽으로 전해지면서 라틴어로 번역되었고, 알 콰리즈미가 발음이 어려워서 라틴어로 바뀌면서 알고리즘이 되었습니다.

2천 년을 살아남은 유클리드 알고리즘

알고리즘이라는 용어는 천 년밖에 안 되었을지 모르지만, 실제로 우리 생활에는 그것보다 훨씬 더 오래 있었습니다. 바둑을 둘 때도 알고리즘적으로 생각하고, 세종대왕도 마방진을 풀었는데 그것도 일종의 알고리즘이었습니다.

가장 의미 있는 알고리즘은 유클리드 알고리즘입니다. 두 숫자가 있으면 최대 공약수를 구하는 방법으로, 12와 18이 있으면 6이라는 최대 공약수를 빠르고 효율적으로 구하는 것을 정확하게 알고리즘으로 기술했습니다. 2천 년 전에 만들어진 이 알고리즘은 현재 공인인증서를 계산할 때 가장 중요한 알고리즘으로 사용되고 있습니다.

컴퓨터가 수학에 가져온 변화

컴퓨터가 수학에 미치는 영향은 양적인 변화와 질적인 변화로 나누어 볼 수 있습니다. 양적인 변화의 대표적인 예는 원주율 파이의 값을 구하는 것입니다. 고대로부터 중요한 문제였던 이 계산을 몇십 년 동안 해도 1천 자리를 넘는 게 인간의 힘으로는 불가능했지만, 컴퓨터가 개발되면서 천 자리, 만 자리를 얼마든지 넘어갈 수 있게 되었고, 현재는 몇 조까지 계산되어 있습니다.

질적인 변화도 굉장히 많은데, 20세기 후반 대수기하학에서 중요한 이론 중 하나인 부흐버거의 알고리즘이 대표적인 예입니다. 미지수가 하나인 방정식은 푸는 게 어렵지 않지만, 미지수가 2개가 되면 굉장히 복잡해집니다. 1960년대까지만 해도 굉장히 힘든 문제였던 이것을 오스트리아 수학자 부흐버거가 알고리즘을 만들어서 해결했습니다.

이 알고리즘은 손으로는 계산할 수 없는 내용이었지만, 컴퓨터로 구현하는 순간 대수기하 연구자들에게는 완전히 새로운 무기가 되었습니다. 현재 대수기하를 연구하는 분들은 관련 프로그램을 가지고 있어서, 필요한 계산이 있으면 프로그램에 넣어보고 결과물을 보고 공통점이나 구조를 파악해서 연구에 활용하고 있습니다.

컴퓨터 의존도에 대한 우려와 현실

스마트폰 사용으로 전화번호를 못 외우고 길을 못 찾게 되듯이, 수학자들도 컴퓨터에 대한 의존도가 늘어나면서 수학적 사고가 둔화될 수 있다는 우려가 있습니다. 하지만 외우지는 못해도 저장은 훨씬 더 많이 할 수 있듯이, 어느 한쪽이 잘 안 되면 다른 쪽에 도움이 생기는 것입니다.

수학자들은 원래 계산을 잘 못합니다. 그 이유는 계산의 결과에 집착하는 게 아니라 과정을 생각하기 때문입니다. 컴퓨터는 결과를 내는 데는 유용하지만, 과정을 생각하고 더구나 컴퓨터에 그 과정을 알고리즘으로 심어주려면 굉장히 많은 생각을 필요로 합니다. 그런 의미에서 수학자들에게는 컴퓨터가 계산을 빨리 해 주는 도구가 아니라 계산을 빨리 하게 하기 위해서 어떤 고민을 해야 되는지 하는 식으로 접근됩니다.

알고리즘으로 해결할 수 없는 수학 문제들

모든 수학 문제가 다 알고리즘으로 바뀌는 것은 아닙니다. 앨런 튜링이 수학을 계산 가능한 수학과 계산 가능하지 않은 수학으로 나누어 그 차이가 무엇인지를 이론적으로 제시했습니다.

힐베르트가 1900년에 20세기 수학자들이 풀어야 할 문제로 제시한 23개 문제 중 10번째 문제가 대표적인 예입니다. 어떤 주어진 정수계수 다항 방정식의 해가 존재하는지 존재하지 않는지를 판정할 수 있는 알고리즘을 만들어 보라는 문제였는데, 결론적으로 그런 알고리즘은 없다는 것이 증명되었습니다. 이 문제를 해결하는 과정에서 줄리아 로빈슨과 마티아세비치 같은 수학자들이 중요한 업적을 세웠습니다.

튜링 머신을 생각한 이유도 문제를 풀 수 있다는 것이 아니라, 컴퓨터로 많은 일을 할 수 있지만 컴퓨터로 풀 수 없는 문제가 존재한다는 것을 증명하기 위해서였습니다.

현대 알고리즘의 다양한 활용 분야

알고리즘이 다른 분야들과 공동으로 수학자들이 기여하는 부분들은 굉장히 많습니다. 특히 영지식 검증(Zero-Knowledge Proof) 같은 경우, 정보는 하나도 알려주지 않고 계산 결과의 정확성을 검증할 수 있는 알고리즘입니다. 예를 들어 의료보험을 들 때 건강 정보는 하나도 안 알려주고 적정한 보험료를 계산해서 보험회사에 보내면, 보험회사는 맞았는지 틀렸는지를 검증할 수 있는 종류의 알고리즘입니다.

영상 처리도 중요한 새로운 영역입니다. 영상을 어떻게 다루고, 두 영상이 얼마큼 차이가 있는지 거리를 설정하고, 두 영상 간의 거리를 설정하는 문제들은 여전히 수학자들이 관심 있고 해결해야 할 알고리즘 문제입니다.
또한 수학적 증명을 검증하는 알고리즘도 개발되어 있습니다. 어떤 주어진 전제로부터 논리적으로 결과를 이끌어내는 것은 그야말로 알고리즘이므로, 프랑스에서 개발한 Coq 같은 프로그램은 형식에 맞춰서 증명을 적어주면 그게 논리적으로 합당하게 유도되는 것인지를 확인해 주는 기능을 제공합니다.

마무리하며

알고리즘은 단순히 컴퓨터 시대의 산물이 아니라, 수천 년 동안 인간의 사고와 문제 해결 과정에서 중요한 역할을 해온 개념입니다. 컴퓨터의 발달과 함께 알고리즘은 수학 연구에 양적, 질적 변화를 가져왔고, 다양한 분야에서 새로운 가능성을 열어주고 있습니다. 동시에 모든 수학 문제가 알고리즘으로 해결될 수 있는 것은 아니라는 점도 분명히 하여, 수학의 깊이와 다양성을 보여주고 있습니다.

Created by 카오스 사이언스
CC BY 라이선스 | 교정 SENTENCIFY | 에디터 하윤아