클릭하시면 더 큰이미지를 보실 수 있습니다 그래픽 = 송재우 기자 jaewoo@
상구의 수학 여행 - ② 진화하는 알고리즘
오늘날 우리가 ‘알고리즘’이라고 부르는 것은 ‘주어진 상황에서 분명한 결과를 이끌어 내는 것으로, 개인의 감정이나 사용하는 주체 등과 상관없는 순수한 논리적 과정’을 뜻한다. 이 용어는 9세기의 수학자이자 천문학자인 무함마드 이븐 무사 알콰리즈미(콰리즈미 마을에 살던 모세의 아들인 무함마드)의 이름에서 유래했다. 그는 당시 이슬람 문화가 번창하던 바그다드의 ‘지혜의 집’에서 활동하면서 인도의 숫자와 이를 이용해 산술을 설명한 책을 썼는데, 이 책이 라틴어로 번역돼 유럽에 전해지면서 인도 숫자가 ‘아라비아 숫자’로 불리게 됐다. 알콰리즈미가 쓴 또 다른 책의 이름에서 오늘날 ‘대수학(代數學·알제브라)’이라는 용어가 탄생했으므로 그를 대수학의 아버지라고 부르는 이도 있다.
알고리즘은 우리 생활 곳곳에 들어 있다. 예를 들어 자동판매기에서 커피 한 잔을 얻으려 한다고 하자. 사용자는 동전이나 지폐를 판매기에 넣고 원하는 종류의 커피를 선택하는 버튼을 누른다. 그러면 기계는 컵을 먼저 뱉은 다음 소비자가 원하는 커피나 설탕, 크림 등을 제공하고, 필요하면 거스름돈을 준다. 이러한 과정은 노인이나 어린이를 차별하지 않고 심지어 원숭이가 사용해도 동일한 결과를 배출하는 ‘감정이 없는 냉정한 논리적 과정’이다.
아파트 5층에서 엘리베이터를 타고 내려간다고 하자. 이때 버튼을 누르면 1층에 있던 엘리베이터는 5층을 지나 9층에서 버튼을 누른 사람을 태우고 내려와 5층에 서서 문을 열어 나를 태운다. 너무 많은 사람이 타면 만원임을 알려 주기도 한다. 엘리베이터는 스스로 최선의 봉사를 하기 위해 감정이 없는 냉정한 판단을 한다. 엘리베이터는 편견을 갖고 있지 않고 돈 많은 사람이나 가난한 사람을 차별하지도 않는다. 알고리즘은 엘리베이터의 정신적 지주다. 좋은 정신을 가진 엘리베이터는 우리를 편안하게 해준다.
각종 기계의 작동 원리는 모두 목적에 적합한 방법으로 알고리즘이 짜여 있다. 심지어 화투놀이나 운동경기 등의 규정들도 모두 알고리즘이다. 나아가 학교 정책, 국회의원 선출 방법, 인위적인 법률 등 여러 사회제도까지도 알고리즘이라 할 수 있다. 자연의 법이 만민과 만물에 평등하게 작용하듯이 알고리즘도 사심 없이 냉정하게 적용된다.
교통신호등도 사람과 차량이 모두 안전하도록 작동하는 알고리즘의 한 보기이지만, 아직은 매우 유치한 방법으로 작동한다. 차량이 지나가지도 않는데 건널목에 빨간불을 켜 놓아 범법자를 양산하기도 하고, 혼잡한 교차로의 차량 흐름을 전혀 인식하지 못하는 어설픈 알고리즘도 널려 있다. 오락가락하는 국가 정책은 사회를 혼란하게 한다. 좋은 제도를 만드는 훈련이나 ‘옳고 그름’을 분석하고 증명하는 훈련은 어려서부터 해야 한다. 좋은 알고리즘은 좋은 사회를 만든다.
20세기 후반에 사회과학자들이 개발한 알고리즘 중에 주목할 만한 것은 ‘공평한 분배’에 관한 것이다. 제한된 공급과 수요 사이에서 서로 낯을 붉히거나 폭력으로 해결하지 않고, 신사 숙녀적으로 남의 입장을 존중하고 동시에 자기 몫을 챙기는 합리적인 방법이 있다는 것이다. 서로 다툴 필요없이 원하는 버튼을 누르면 각자의 몫이 배당되는 놀라운 알고리즘이다. 수학에서 사용하는 언어는 매우 정교한 데 ‘공평하다’는 말도 수학적 용어의 하나다. 이 용어는 2차 세계대전으로 많은 사람이 굶주리고 있을 때 폴란드의 수학자인 휴고 슈타인하우스(1887∼1972)가 다음과 같이 정의(定義)했다. “100명의 사람에게 한정된 떡을 분배하고자 할 때, ‘분배받을 사람 각자가 떡에 부여한 주관적 가치’의 100분의 1 이상이 각자에게 배당되면, 공평한 분배가 이뤄졌다고 말한다.” 물론 이 정의에서 ‘100’이나 ‘떡’이라는 용어는 훨씬 일반적인 의미로 사용됐다.
“선생님, 제가 땅을 분배하는 문제로 형님과 의견이 약간 대립됐는데요. 어떻게 하면 될까요?”
“상구야, 단디 듣거라. 무슨 일이든 노여워하지 마라. 땅 문제로도 다투지 마라. 형님께서 원하는 대로 땅을 두 부분으로 나누시라 하고, 너는 그중 하나만 선택하면 되느니라. 그게 싫으시면 네가 나누고, 형님께서 그중 하나를 선택하시라고 해라.”
역사적으로 가장 유명한 알고리즘은 유클리드의 저서 ‘원소’에 등장하는 것으로 두 자연수의 최대공약수를 구하는 아름다운 방법이다. 중학생이 되면 두 자연수의 최대공약수에 대해 배우지만, 최대공약수를 구하는 알고리즘은 교과과정에서는 금기라서 19세가 지나도 아무도 설명해 주지 않는다. 자연수의 약수를 구하는 일은 매우 어렵다. 예를 들어 2017은 약수가 몇 개나 있을까. 일반적인 자연수의 약수를 구하는 좋은 알고리즘을 알고 있다면 역사에 길이 이름을 남길 수 있고, 원하면 많은 돈도 벌 수 있다. 현대적인 암호 체계는 자연수의 성질에 크게 의존하고 있기 때문이다. 그러나 유클리드는 비록 개별적인 자연수의 약수를 구하는 것은 어려울지 모르나, 두 자연수의 최대공약수를 구하는 것은 매우 쉽다고 했다. 그는 “큰 수 대신 그것을 작은 수로 나눈 나머지로 대체하면 된다”고 말했다. 최대공약수를 구할 수 있으면 최소공배수도 구할 수 있다. 최소공배수는 인류가 자연의 주기를 이해하기 위해 매우 노력한 개념이다. 해와 달, 행성들의 주기를 이해하고 좋은 달력과 좋은 시계를 만들려는 노력의 바탕에는 모두 수의 성질이 깔려 있다. 밀물과 썰물, 꽃이나 열매, 생리나 곤충 등의 활동주기도 큰 관심사이고, ‘이들이 언제 모두 다 같이 발현할까’ 하는 질문은 매우 자연스럽다.
고대 그리스의 ‘피타고라스와 형제자매들’은 같은 종류의 양은 공통 양, 즉 공약수와 공배수를 가진다고 생각했다. 해와 달은 공통 주기를 가지고, 무거운 사람과 가벼운 사람도 공통 무게를 가지며, 이 마을에서 사용하는 자와 저 마을에서 사용하는 자도 공통 길이를 가진다고 생각했다. 이러한 생각을 ‘공측성’이라 하는데, 이에 대응하는 수를 합리적이고 이성적인 ‘유리수’라 했다. 공측성을 믿으면 도형의 넓이나 부피를 설명할 수 있고, 지렛대 원리도 설명하기가 쉽다. 그러나 피타고라스와 형제자매들은 공측성이 진실이 아니라는 것을 발견했고, 이를 비이성적이고 말(로고스)로 설명할 수 없는 무리수(아르곤)라 했다. 일부 작가들이 피타고라스가 무리수의 발견을 발설하지 말라고 했다고 주장하는데, 사실 무리수라는 단어가 바로 ‘말할 수 없다’는 뜻이다.
유클리드의 알고리즘 못지않게 유명한 알고리즘은 스위스의 수학자인 레온하르트 오일러(1707∼1783)의 한붓그리기 풀이법이다. 폴란드와 리투아니아 사이에 있는 발틱해의 항구도시인 쾨니히스베르크에는 강 사이의 섬들과 육지를 연결하는 7개의 다리가 있는데, 이곳 사람들은 이 7개 다리를 오직 한 번씩 모두 건너는 방법이 있는지 궁금해했다. 오일러는 1736년 이 문제풀이를 하면서 일반적인 네트워크에서 한붓그리는 방법을 발표했다.
쾨니히스베르크는 “생각하면 할수록 점점 더 새롭고 점점 더 큰 경탄과 외경으로 마음을 채우는 것이 두 가지 있는데, 그것은 내 위에 별이 빛나는 하늘과 내 안의 도덕법칙이다”는 말로 유명한 독일 철학자 이마누엘 칸트(1724∼1804)의 고향이다. 20세기 수학을 이끈 다비드 힐베르트(1862∼1943)와 아인슈타인의 스승인 헤르만 민코프스키(1864∼1909), 물리학자인 아놀드 조머펠트(1868∼1951)의 고향이기도 하다. 이 도시는 1945년 7월 포츠담 선언에 의해 러시아로 편입되면서 러시아의 정치가 이름을 따서 칼리닌그라드로 명칭이 바뀌었다.
<그림 1>을 붓을 떼지 않고 한 번만에 그릴 수 있을까.
오일러는 일반 그래프에서 한붓그리기 문제를 풀려면 먼저 선들이 만나는 점, 즉 분기점들을 분석하라고 했다. 분기점들은 그 점에서 빠져나가거나 들어오는 선들의 개수에 따라 홀짝으로 구별할 수 있다. 오일러는 홀수형 분기점들이 없거나 또는 두 개일 때만 한붓그리기가 가능함을 발견했고, 구체적으로 그 경로를 구하는 멋진 알고리즘도 설명했다.
19세기 말부터 20세기 초에 걸쳐 무한을 이해하고자 하는 수학자들과 유한한 것만을 대상으로 해야 한다는 수학자들 사이에 ‘매우 심각한 논쟁’이 있었다. 줄여서 말하면 ‘아날로그와 디지털 논쟁’이라 할 수 있다. 결국 모든 것을 설명하려고 했던 힐베르트의 꿈은 산산조각이 나고 그 부서진 조각 속에서 ‘보편 알고리즘’이 탄생했다. 보편 알고리즘이란 어떤 특수한 목적 대신 ‘저는 당신이 원하는 것은 무엇이든지 하겠습니다’는 임무를 띤 것을 뜻한다. 이를 계기로 인류는 기계가 무엇인지, 기계가 할 수 없는 일은 어떤 것인지 이해하기 시작했고, 이로써 인공지능을 논하게 됐다. 오늘 우리가 누리는 디지털 문명의 바탕에는 눈에 보이지 않는 알고리즘이 핵심적인 역할을 하고 있다.
“선생님, 디지털 혁명 다음에는 어떤 일이 벌어질까요?”
“상구야, 단디 듣거라. 유한의 너머에는 무한한 아날로그가 있단다.”
김홍종 서울대 수리과학부 교수
;){kind=link}