제바스티안 슈틸러, <알고리즘 행성 여행자들을위한 안내서> -

1. 니콜라우스의 집

---

니콜라이수의 집에는 변edge이 세 개인 지점이 둘 있다. 사각형의 왼쪽과 오른쪽 아래 지점이 바로 그곳이다. 이 두 지점 중 어느 한 곳에서 시작해야만 손을 떼지 않고 집을 그릴 수 있다. 이 때 나머지 한 곳은 마침점이 된다. 

2. 하나의 질문으로는 충분하지 않다. - 어려운 문제를 구성하기 위한 원칙

---

여기에서 말하는 한 질문 혹은 한 문제는 두 말할 것 없이 늘 무한한 양으로 응용 가능하지만 본질은 똑같은 질문과 문제를 의미한다. 임의의 레벨에서 배관공 마리오에게 길이 있는지 없는지를 결정하는 문제가 바로 그런 문제 집합이다. 

이런 식의 문제 집합에는 모두 임의의 크기의 문제들이 포함되어 있다. 가장 작은 문제들은 쉽게 풀 수 있다. 문제 집합의 난이도를 결정하는 것은 문제의 크기와 더불어 비용이 얼마나 크게 증가하느냐 하는 것이다.

3. 마타판 곶과 사라진 'L'

---

메이비스 배티mavis batey의 눈에는 에니그마의 약점이 보였다. 에니그마는 절대로 어떤 알파벳을 있는 그래도 사용하지 않았다는 점이다. 다른 모든 알파벳은 'L'대신에 사용될 수 있어도, 정작 진짜 'L'은 'L' 대신에 쓰일 수 없었다. 자기가 결코 자기 자신으로 코딩될 수 없다니 얼마나 웃기는 일인.

4. 큐비트에 대하여 (Peter Sohr)

---

일반 컴퓨터는 비트를 읽고 쓴다. 양자컴퓨터는 기본적으로 튜링 기게와 똑같이 작동한다. 다만 비트 대신에 큐비트라는 양자 비트로 작업할 뿐이다. 큐비트는 스크래치 복권과도 같다. 복권을 긁지 않고 흠 없이 보관만 하고 있으면, 그건 0도 아니고 1도 아니다. 긁었을 때 0 또는 1이 될 수 있는 확률분포에 지나지 않는다.

큐비트는 0 또는 1이 아니라, 0과 1 사이의 확률분포다. 그러나 이것만으로는 고전적인 튜링 기게를 넘어서지 못한다. 이 컴퓨터 모델이 튜링 기계로 대체되는 일이 없도록 하기 위해서는 큐피트의 또 다른 두 가지 특성을 이용해야만 한다.

1) 우리가 얽힌 큐비트를 만들어낼 수 있다는 점 (둘 중 하나를 측정하면 나머지 하나에서 무엇이 나올지에 대한 확실성을 갖게 된다)

2) 우리가 큐비트를 단지 쓰고 지울 수 있을 뿐만 아니라 회전시킬 수도 있다는 점 (확률은 회전가능하고 어느 정도 변경할 수 있다)

우리가 측정해내는 큐피트는 그 시점까지의 확률분포를 의미하는 것으로, 그것을 연결할 수 있으며, 회전시킬 수도 있다.

5. 중국인의 나머지 정리

6. 구글의 차점가격 경매 적용 방법

---

광고 자리를 입찰가가 높은 순서대로 분배한다. 그리고 첫 번째 자리에 대해서는 두 번째로 높은 입찰가를 지불하도록 하고, 두 번째 자리에 대해서는 세 번째로 높은 입찰가를 지불하도록 한다. 이걸 가리켜 일반화된 이차가격 경매 Generalized Second Price Auction, GSP 라고 한다. 그런데 이 경매방식은 자기가 생각하는 그 광고의 가치를 가격으로 써내는 것이 입찰자에게 꼭 최선의 전략이 아닐 수도 있다는 문제점이 있다. 이것이 바로 비크리 경매가 보여주는 위트다.

VCG 매커니즘 (Vickrey Clarke Groves Mechanism)

만약 내가 최고가를 써낸 입찰자로서 물건을 받는다면, 나는 다른 모든 입찰자에게서 그 물건을 가로챈 사람이 된다. 그렇기 때문에 나는 내가 경매에 참여하지 않았을 경우에 그 물건이 다른 사람들에게 갖고 있는 가치를 지불해야만 한다. 물건이 하나일 경우, 그 가치는 바로 두 번째로 높은 가격이다. 물건이 여러 개인 경우, VCG 매커니즘은 똑같은 원칙에 따라 계속 되풀이 된다. 내가 광고 자리를 얻음으로써 다른 사람이 고통스러워진 만큼 비용을 지불한다. 이 경매 방식은 각각의 입찰자가 자신의 솔직한 평가 가치를 제시하게 된다는 아름다운 특성르 보인다. 구글은 VCG 매커니즘을 사용할 수도 있었지만 구글은 일반회된 이차가격 경매를 사용한다. 그게 더 간단하기 때문이다.

7. 파트너 선택 문제

---

1) 블로킹 페어

2) 게일-섀플리 알고리즘 Gale-Shapley Algorithm

8. 다빈치의 시각 : 그림을 그린다는 것은 이해한다는 뜻이다.

---

파리 필사본 M에는 다 빈치의 나무 그리는 법에 대한 조언이 실려 있는데, 이 조언은 하나의 나무에 대한 것이 아니라 나무를 그리는 일반적인 '문제'에 대한 것이다. 다 빈치는 나무가 어떻게 가지를 뻗는지 좀 더 정확하게 관찰했다. 하나의 가지가 굵기가 서로 다른 두 개의 가지로 뻗어 나가면, 새로 뻗은 가지들 중 더 굻은 가지는 더 얇은 가지에 비해 본래 가지가 자라는 방향과 각도 오차가 덜하다. 대충 이런 식이다. 뭔가를 제ㅔ대로 바라보기 위해 다 빈치는 거기에 어떤 규칙이 있는지 이해하려고 노력했다.

'현상을 이해하려면 모든 것을 가능한 한 단순화해 한다'

9. 선호적 연결 Preferential Attachment

---

유명한 웹사이트, 즉 링크를 많이 갖고 있는 웹사이트는 유명하지 않은 웨바이트에 비해 또 다른 웹사이트에 의해 연결될 확률이 더 높다. 이것이 바로 선호적 연결이다.

10. 스몰월드

---

편지가 6~7단계 만에 목적지에 당도한다면, 네트워크의 한 노드와 다른 노드 사이에 짧은 경로가 있는게 분명하다. 여기까지는 통상적으로 생각할 수 있는 수준이다. 하지만 알고리즘 학자로서 존 클라인버그 Jon Kelinberg 는 이것으로 만족하지 않았다. 그런 경로가 있다면 그걸 어떻게 찾아야 한단 말인가? 예를 들어, 데이크스트라 알고리즘은 최단 경로를 찾아낼 수 있지만, 그러려면 모든 인맥 그래프를 입력해야 한다. 이 실험에서 사람들은 그 짧은 경로를 어떻게 찾아냈단 말인가?

클라인버그의 모델에서는 사람들이 각자의 이웃을 지역적으로, 사회적으로 잘 알고 있다고 가정한다. 또한 이 모델에서는 사람들이 서로 아주 멀리 떨어져 있어도 연결고리가 만들어지는 우연의 변들이 일부 추가돼 있다. 이 변들은 예상하지 못한 우연의 인맥 또는 멀리 떨어져 살고 있는 오랜 친구를 상정한다. 몇 개 안되는 이런 우연의 변들이 하나의 작은 세상, 즉 대다수의 노드들을 단거리로 연결하는 네트워크를 만들어낸다는 사실을 우리는 알고 있다.

11. 진화의 알고리즘

---

알고리즘적 시각에서 보면, 유성생식을 통한 번식의 결과는 중요한 의미를 갖는다. 만약 우리가 최적화 문제에 약간의 변화를 주면, 즉 유기체의 생활환경이 달라지면, 기존 환경에 완벽하게 적응한 무성생식의 결과물은 금세 기회를 잃게 된다. 무성생식을 통해 나온 이 유기체는 너무나 특수해서 서식지의 변화를 이겨낼 수 없다. 유성생식에서 발새한 해결책은 기존 조건에 완벽하지는 않지만, 그래도 잘 적응한다. 그래서 우리가 최적화 문제에 약간의 변화를 줘도 이 해결책은 여전히 성공적이다. 유성생식을 통한 잔화는 최강자의 생존이 아닌, 다양성의 생존으로 이어진다.

알고리즘적 원칙을 이해하는 것이야말로 그 변화를 따라갈 수 있는 유일한 방법이다.

알고리즘 행성 여행자들을 위한 안내서 국내도서 저자 : 제바스티안 슈틸러(Sebastian Stiller) / 김세나역 출판 : 와이즈베리 2017.04.07 상세보기