[BOOK]미래를 바꾼 아홉가지 알고리즘

알고리즘이란?

문제를 푸는 데 필요한 단계의 순서를 명확히 명시하는 구체적인 계산법. 또는 정확하고 기계적인 계산법

1. 시작하며:컴퓨터를 움직이는 위대한 아이디어들

<어느 수학자의 변명>이란 도서에서 ‘아름다움은 가장 중요한 시험대다. 추한 모습의 수학이 영원히 자리잡을 곳은 이 세상 어디에도 없다’라는 인용문에서 나오는 아름다움 시험대라는 잣대를 활용하여 저자가 개인적으로 각 알고리즘에서 느낀 아름다움을 일부라도 전달하고자 알고리즘을 선택하는 여러 기준 중 하나로 사용.

책을 읽는다고 해서 숙련된 컴퓨터 사용자가 될 수는 없겠지만, 컴퓨터 장치에서 매일 끊임없이 이용하는 알고리즘의 아름다움을 훨씬 깊이 느낄 수 있게 될것이다.

이게 왜 좋은가? 저자의 비유로 천문학에 대해 상당히 무지하지만 짧게 배운 천문학 지식 덕분에 밤 하늘을 볼 때마다 즐거움이 배가된다는 것이다. 내가 바라보는 대상에 관한 이해가 만족감과 경탄을 낳기 마련이고, 컴퓨터를 사용하면서 이런 기쁨을 가끔은 느끼게 되길 진심으로 바란다고 한다.

2. 검색엔진 인덱싱: 세상에서 가장 큰 건초 더미에서 바늘 찾기

검색엔진의 두 가지 주요 과제는 매칭(matching)과 랭킹(ranking)이다.

매칭 인덱스(index)란 개념은 글쓰기 만큼이나 오래도ㅒㅆ다. 오래전 주제에 따라 문자판을 분류해 놓은것과 같다

웹 검색엔진용 인덱스에는 각 페이지

1. i am bot
2. i am dog

i 1, 2 am 1, 2 bot 1 dog 2 와 같이 각 단어가 나타난 페이지를 적는 형식

단어 위치 트릭 - 페이지 뿐만 아니라 위치도 같이 적는 방법.

랭킹과 근접성 랭킹은 고품질의 검색엔진에 절대적으로 필수. 메타워드 트릭 <title></title> 과 같이 HTML에서는 태그를 사용.

인덱싱과 매칭트릭이 전부는 아니다. 구글이 뺴어난 매칭 알고리즘을 지녔던 알타비스타를 몰락시키는데는 랭킹 알고리즘의 역할이 컸다.

3.페이지 랭크: 구글을 출범시킨 기술

구글의 창업자인 래리 페이지가 만든 웹 페이지 순위를 매기는 알고리즘인 동시에 래리 페이지가 개발한 랭킹 알고리즘 하이퍼링크 트릭 - 누가 더 많은 참조를 받고있는가? but. 혹평과 추천의 구분을 못하는 결점 권위 트릭(authority trick) - 인커밍 링크의 개수를 합산하여 권위를 매김 but. 사이클이 생길 수 있다는 결점. 무작위 서퍼 트릭 - 컴퓨터가 시뮬레이션을 돌려 무작위 페이지에서 시작하여 각 페이지로 가는 확률들을 계산하는 방법 - 인커ㅗ밍 링크의 질과 양을 모두 계산. 오늘날에는 더 복잡한 요인이 작용. 이러한 하이퍼링크를 부풀리는 웹 스팸(web spam)을 탐지하는 검색엔진이 웹 스패머에 맞서 군비 경쟁(arms race)를 하게 되었다. 이런 웹 하이퍼링크 구조를 이용하는 여타 알고리즘의 종류를 대게 링크 기반 랭킹 알고리즘이라 부른다.

페이지 랭크의 핵심아이디어인 권위 트릭은 웹페이지라는 건초 더미에서 바늘을 찾 을 수 있는 보석 같은 알고리즘이다.

4. 공개 키 암호화: 공개 엽서에 비밀을 적어 아무도 모르게 보내는 방법

이너넷과 연결을 하기 위해서는 라우터에 접속해야하는데 누구든지 메시지 내용을 볼 수 있어 이러한 해결책을 제공한다.

공유비밀로 암호화 세명의 사람이 같은 방안에 있을때 두 사람만 아는 내용(공유 비밀)으로 말을 주고 받으면 암호화 할 수있다. 공유비밀을 공개적으로 설정하기. 하지만 두 사람이 모르는 사람이라면 어떻게 해야 할까?

디피-헬먼 키(페인트 혼합트릭) - 각 자 개인 색을 가져가고 공유색과 개인색을 섞은 페인트를 공개하면 해당 공개한 내용을 메시지를 주고 받고 싶은 사람과 공유하면 같은 결과를 가지게 된다. 페인트 혼합트릭을 숫자로 번역하려면 일방향 행위(원 상태로 되돌릴 수 없는 방법)가 필요하다. 이를 행할때 혼합 계산은 이산 누승법(discrete exponentiation)이라 하고 원 상태로 돌리는 계산은 이산로그(discrete logarithm)이라 한다. 컴퓨터는 이산 로그를 효율적으로 계싼할 방법이 없기에 이산 누승법은 일방향 행위의 종류가 된다. 해당 방법을 사용하귀 위해서는 나머지 연산(modular arithmetic)이라고 불리는 시계 연산(clock arithmetic)이라는 개념을 알고 있어야한다. 시계 크기라는 특정 k를 정하고 원하는 수를 k로 나눈 나머지를 구하는 방법이다 그리고 거듭제곱 표기법을 알아햐한다. 각자 개인 수를 정하고 공개 수 (시계크기, 기저수 : base)를 공유한다. 이를 활용하여 각자 공개-개인수(PPN)=기저수^개인 수 (시계 크기)를 구한다. 이렇게 된 후 각자 통신을 원하는 상대의 PPN을 가져가 공유 비밀 = 상대방의 PPN^개인 수 (시계 크기)로 개산하면 같은 값이 나오게 된다. 이는 디피-헬먼 키 교환 프로토콜이라 부르는 https라는 보안된 웹사이트에서 공유 비밀을 제작한다. 실제로 수백만 자리의 시계크기와 수 많은 개인 수를 제작한다(공개 수에서 가장 중요한 속성은 시계 크기가 소수(prime numbver)이어야한다. 또한 기저수가 시계크기의 원시근(primitive root)이어야한다. 이는 기저수의 제곱수가 결국 시계에서 가능한 모든 값을 따라 순환한다는 뜻이다.

5. 오류 정정 코드 : 데이터 오류를 스스로 찾아 고치는 마법

벨 전화 연구소에서 일하던 리처드 해밍은 데이터를 읽는 도중 발생한 오류때문에 반복되는 충돌에 해밍이 좌절을 느껴 최초의 오류 정정코드를 제작했다. 오류 정정 코드가 없으면 컴퓨터와 통신 시스템은 오늘날 컴퓨터에 비할수도없을만큼 느려지고 강력하지도 않고 신뢰하기도 어려웠을 것이다. 데이터의 전송과 저장은 핵심적인 기능이다. 그러나 이에는 큰 난고나이 있는데 데이터는 정확해야한다는점이다. 컴퓨터에 99.999999%의 정확성은 필요없고 100%의 정확성이 필요하다는 것이다. 반복 트릭 - 전송을 여러번 반복, 하지만 이는 여러번 반복하는 것은 실용적이지 않다 리던던시(redundancy) 트릭 - 5 1을 보내는데 five one이라 보냄 이러한 부가적인 잉여정보를 리던던시라 부른다. 심벌(symbol)이라 부르는 요소(0~9 같은)에 영어처럼 알려진패턴인 코드워드(code word)를 할당. 이런 영어보다 더 복잡한 코드 워드로 (7,4)해밍코드(hamming code)를 사용한다. 이러한 트릭을 사용하면 flve라고 전송이 되어도 five -> 5로 쉽게 오류를 정정할수있다. 반복 트릭보다 선호되는 주된 이유는 오버헤드(overhead, 메시지가 정확하게 수신되었는지 확인하기 위해 보내야하는 잉여 정보의양)라는 맥락에서상대적으로 적기때문이다. 체크섬(check sum, 검사합) 트릭 - 오류 정정은 신경쓰지 않고 검출에만 집중, 대부분 오류 검출이면 충분하기에 오류가 없는 사본을 받을때까지 반복 요청할 수 있다. 데이터를 보낼때 마지막 부분에 단순 합부분을 추가해서 전송해 결과를 비교 그러나 오류가 발생했어도 같을 수있기에 계단(staircase) 체크섬이라는 방법을 사용. 각 숫자에 계단 숫자를 곱하여 합하는 방식. 이러한 경우도 악성 오류(의도적으로 바꾼)가 발생하면실패할수도 있기에 암호학적 해시 함수(cryptographic hash function)이라 부르는 특정 유형의 체크섬을 요함. 핀포인트 트릭 - 리던던시 트릭 수행에 이용할수있는 또 다른 코드워드 집합에 관해, 16자리 메시지를 왼쪽에서 오른쪽으로 위쪽에서 아래쪽으로 채우고 각행과 열에 단순 체크섬을 계산해 추가한다. 이 처럼 새로 만든 열과 행에는 수신자가 받은 값과 계산한 값을 보고 이들이 모두 같다면 정확할 가능 성이 매우 크지만 오류가 있을시 오류가 난 각 행과 행과 열에 해당하는 위치를 찾고 값을 수정할수있다. 이것을 이차원 패리티(two-dimensional parity)라하고 리던던시 트릭보다 비효율적이다. 오류 정정 코드는 정보이론(information theory)이라는 더 큰 분야 중 하나. 체크섬은 오류 정정보다 오류 검출에 널리 사용되고 보편적으로 이더넷(Ethernet)이다. 이더넷은 거의 모든 컴퓨터가 쓰는 네트워킹 프로토콜이고 CRC-32라는 체크섬을 이용하고 TCP도 보내는 데이터의 각 청크(chunk)또는 패킹(packet)에 체크섬을 이용한다. MD5, SHA-1도 암호학적 해시 함수로 고안되 인터넷상에 배포되는 소프트웨어 패키지의 검사 합계를 이용해 검증된다. 우리가 컴퓨터로 누리는 대부분의 것들은 리처드 해밍이 느낀 좌절감에서 출발했다.

6. 패턴인식과 인공지능:사람처럼 학습하고 생각하는 컴퓨터

인간의 타고난 이점을 활용하는 분야, 패턴 인식(pattern recogniation), 인공지능의 하위 분야, 패턴 인식은 변수가 많은 입력데이터에 맞게 컴퓨터가지적으로 행동하게하는과제라고정의. 1843년 에이다 러브레이스느 해석기관(analytical engine)인 초기 기계 컴퓨터 설계에 관해 언급. 컴퓨터가 지능을 가질 수있는 논쟁은 철학자 신경과학자 신학자가 개입하면서 복잡해짐. 그러나 이 역설에 관한 논쟁은 지적이란 단어를 유용한이라는 단어를 사용한다 인접이웃 트릭 - 가장 가까운 k개의 샘플 중 제일 많은 요소로 활용종류의 인접아웃 다양한 종류의 인접이웃 트릭 - 인접이웃 트릭을 활용하기 위해서는 각 요소간의 거리를 활용해서 측정한다. 지도 라면 지리적거리를 이용하지만 손글씨의 경우는 어떻게 거리를 측정해야할까? 서로 다른 두 손으로 쓴 숫자 사이의 거리를 계산할 방법이 필요하다. 기본 아이디어는 거리가 아니라 두 숫자의 차이를 활용한다. 인접이웃 분류자는 99.5%의 성능으로 SVM이나 CNN 등과 같은 복잡한 패턴 인식 시스템의 성능에 견줄만하다. 실로 탁월한 효과와 우아한 단순성을 잘 결합한 컴퓨터 과학의 경이로운 대상이다. 스무고개 트릭 - 의사결정나무,좋은 질문과 나쁜 질문에 관한 이런 직관이 정보 이론이라는 매력적인 분야의 중심에 있다.그리고 이는 의사결정나무라는 패턴 인식 기법의 핵심이기도 하다, 신경망 - 생물학적 신경망 - 뉴런에 대하나 설명으로 특정 시점에 뉴런이 쉬는지 동작하는지 알아보는것, 뉴런이 작동을하면 외부로 향한 모든 연결을 통해 빈번하게 신호를 보낸다. 신호의 강도는 들어오는 신호가 총 신호가 강하면 신호 전송을 시작하고 그렇지 않으면 쉬는 상태로 변한다.흥분성(ㄷㅌ챳ㅁ새교) 및 억제성(inhibitory)로 흥분성 입력의 강도는 더하고 억제성 입력은 총합에서 뺀다. 역치(threshold)라는 값을 각 뉴련에 할당해 이 역치에 이르면 신호를 쏘고 그렇지 않으면 쉬는 상태를 유지한다. 가중신호 더하기 - 세가지 중요한 강화(enhancement)를 더한다. 강화 1 신호는 0부터 1사이 값을 취할수있다.강화2 총 입력은 가중합계로 계산한다 강화3 역치의 효과는 약화된다, 출력은 0이나 1이 될도록 고정하지않는다 출력은 0에서 1사이의 값이 되도록 가중합이 10인데 역치가 1이면 출력은 0.95가 되는 형식으로되어야한다. 학습에 의한 신경망조율 - 훈련 샘플을 제시하면 이상적인 목표값이 들어가있다. 따라서 학습은 출력값이 목표값에 가까이 갈 수 있도록 역방향으로 계산을 하게 딘다. 이 미세한 조정을 계산하는 방법은 추계적 하강(stochastic gradient descent)라 부른다. 패턴인식의 과거, 현재, 미래 - 앞서 언급했든 패턴인식은 인공지능의 하위분야이다.패턴 인식은 소리, 사진, 영상과 같은 가변적인 입력데이터를 다루고 인공지능은 더 다양한 과제를 다룬다.’학습의 모든 측면이나 지능의 여타 특징은 이론상 매우 정확히 기술도리수 있어 기계가 이를 시뮬레이션하게 만들수있다라는 가설을 토대로 인공지능은 느리지만 명확하게 인간 고유의 것이라 정의할수도있는 사고 과정의 집합을 조금씩 밝혀내고있다. 인공지능의 성공 이야기는 일반인의 삶에도 스며들고 있다. 직관이 좌우하는 업무에서 기계적인 업무로의 점진적 변화는 꾸준히 이어지고있다.

7. 데이터 압축:책한권을 종이한장에 담기

무손실압축 - 런-렝스 인코딩:반복된문자열을 줄이는 방법 그러나 특정한 유형만 유용하다. 그래서 반복이 인접하지 않아도 더 잘 작동하는 트릭을 고안했는데 점과 같음 트릭(same-as-ealier trick)과 더 짧은 심벌 트릭(shorter-symbol trick) 두가지만 다룬다. 전과 같음 트릭 - 앞으로 돌아가 반복되는 문자열의 시작과 길이를 넣는다. 더짧은심벌트릭 - 자주쓰는 구문 또는 글자를 축약어를 사용하여 줄임,그러나 컴퓨터는 빈칸을 저장하지 않는다 그래서 이러한 문제점을 해결하기 위해 희생을 해야한다 코드의 자릿수를 결정하는 숫자를 입력해 벗어난다. 7로시작하면 두자리 8로 시작하면 한자리 같은 케이스로.

손실 압축 - 이미지나 영상에서 많이 사용하는 방법인데 사람의 눈으로 보면 똑같은 이미지라면 컴퓨터나 카메라에 저장된 데이터가 같을 필요가 없다. 생략트릭 - 이미지는 1920 x 1080개라면 픽셀이 1920행 1080열 이라는 이야기인데 이것을 압축하면 짝수 행이나 열을 날려버리는 형식으로 진행한다. 다시 이 이미지를 압축 해제하면 픽셀의 일부가 삭제됐기에 추측을 통해 만들어야한다. 근처 픽셀의 색상을 부여하는 방법을 감수해야한다. 이렇게 보면 세부 묘사에서 손실이 있음을 볼 수 있고 세부 묘사나 복잡한영역에서 잘 들어나며 이러한 부분을 압축 가공물(compression artifact)라고 한다. 이렇게 이미지 파일은 JPEG등으로 잘압축이 가능하지만 소리나 음악은 어떨까? 이러한 부분은 인간의 귀에 잘 들리지 않는 부분을 제거하는 방식으로 산출물의 품질을 떨어뜨리지 않으면서 제거가 가능하다. 압축 알고리즘의 기원 - 벨 전화 연구소의 섀넌은 압축 알고리즘의 출현에도 중요한 역할을 했다. 오류 정정코드와 압축 알골지즘은 동전의 야면과 같아 앞에서 다룬 리던던시라는 개념으로 압축이 된다. 그러나 압축 알고리즘은 정반대의 작업을 수행한다. 추후에 나온 허프만 코딩은 본질적인 압축알고리즘으로 통신과 데이터 저장시스템에서 널리쓰인다.> ## 8. 데이터베이스:일관성을 향한 여정 데이터 베이스는 거래 과정에서 두 가지 주요 사안을 처리한다. 바로 효율성과 신뢰성이다. 이 장에서는 데이터 베이스 이면의 근본적인 알고리즘 세가지를 다룬다. 데이텁 ㅔ이스 실무자들은 일관성에 집착한다. 간단히 말해 일관성은 정보가 모순되지 않음을 뜻한다. 최악의 악몽은 불이치이다. 트랜잭션과 할일목록 트릭 - 트랜잭션은 일관적인 경우 모두 일어나야 하는 데이터 베이스 변화의 집합이다. 만약 이 트랜잭션이 충돌 및 재식작후 데이터베이스가 트랜잭션 시작전과 같은 상태로 돌아갈수있다. 이를 롤백이라고 한다. 할일목록은 미리쓰기 로그라고도 한다. 트랜잭션에서 동작이 수행되기 전에 모든 동작은 로그에 기록되고 디스크에 저장된다 트랜잭션이 성공적으로 실행읻 ㅚ면 할일목록에서 삭제한다. 그러나 트랜잭션이 실행 중에 충돌하게 되면 어떻게 되는가? 로그에 정보가 있으므로 트랜잭션 도중임을 알 수 있기다 그러나 할일목록에 있는 로그를 구분할 필요가 없다 몇번 수행되든 상관없이 같은 효과를 내도록 고안됐기때문이다 이를 멱등(idenmpotent)이므로 모든 동작은 멱등이어야한다고 한다. 은행을 예시로 10원에서 12원으로 변경과 같이 멱등이도록 고안. 트랜잭션은 원자성(atomicity)를 띈다.

우리는 아직 신뢰성과 효율성에 도다하지 못했다. 데이터 베이스는 복제될수있고 때로는 데이터 베이스 트랜잭션이 취소돼야한다. 중복 데이터 베이스 - 데이터를 잃어버린다면 매우 큰 문제가 발생할수있다. 따라서 데이터 베이스의 사본(복제품, replica)를 유지해야한다. 이는 데이터의 백업 유지라는 개념과 조금은 다르게 작동한다. 백업은 스냅샷을 찍지만 최신상태를 유지하진않는다. 사본은 늘 최신 변화를 반영해야한다. 이는 데이터 손실로부터 데이터를 지킬수있는 훌륭한 방법이다 그러나 복제에도 위험이있다 만약 두 복제본이 동일하지 않다면 어떻게해야하나. 트랜잭션 복귀- 바쁜 데이터 베이스에서는 대게 동시에 실행중인 트랜잭션이 많다. A를 처리하면 A를 lock하게 되는데 도중 B를 처리하면서 B를 잠그는 상황에서 서로 참조해야하는 데이터가 같다면 교착 상태(dead lock)에 빠지게 된다이 트랜잭션은 영원히 완료될 수없다. 그래서 트랜잭션 하나를 취소하는 복귀하는 능력이 필요하다. 여기서 미리쓰기 로그를 통해 트랜잭션에 있는 작업을 역순으로 되돌릴수있다 준비후 커밋 - 만약 여러 사람에게 약속을 잡는 경우라면 한명씩 물어보고 모두 동의를 하면 확정을 짓거나 변경을 해야하면 먼저 잡은 약속을 취소하는 방법이다. 이를 prepare-then-commit trick이라 한다. 이 비유에는 데이터 베이스 잠금 개념이 있다. 당신이 연락을 받아 약속이 확정이나 취소가 되기전까지 기다리는 경우에 당신의 해당 시간대는 잠기게 된다. 그리고 다른 사람들은 그 시간에 당신을 부를 수 없게된다.

여태까지는 테이블 하나만으로 구성했지만 오늘날 데이터베이스 기술의 진짜 힘은 복수의 테이블을 가진 데이터베이스에 촉발됐다. 기본 아이디어는 서로 다른 정보의 집합을 테이블로 저장하지만 대다수의 테이블들은 서로 연결된다는 것이다. 이는 반복되는 정보를 줄일수있어 저장공간 절약의 효과는 막대하다 그리고 테이블을 정확히 설계하면 데이터베이스에 쉽게 변화를 줄수있다. 키-테이블에 있는 상세 정보를 이용 열을 키라고한다. 이는 사람이 사전에서 단어를 찾는 방식과 유사하다. 빠르게 키를 찾고자 사전에 계산된 묶음의 집합을 B-트리라 한다. 가상 테이블 트릭 - 데이터베이스의 모든 정보는 고정된 테이블에 저장되어있고 필요한 정보를 그때마다 새로운 테이블로 생성할수는 있다. 그러나 해당 테이블은 실제로 저장되지 않는다. 할일목록 트릭덕분에 수천명의 고객이 동시에 데이터베이스와 데이터를 주고받을때도 일관성을 유지하는 원자적 트랜잭션이 가능하고 대규모 일시 처리는 가상테이블 트릭을 기반으로 대용량 데이터베이스를 효율적으로 만든다 또 준비후 커밋트릭과 결합하면 데이터의 일관성과 내구성을 확보한다. 이는 장애허용(fault tolerance, 부품 일부가 고장나도 제대로 동작하는)라고 알려진 신뢰할수없는 부품에 대한 데이터베이스의 엄청난 승리이다.

9. 디지털 서명 : 진짜 누가 이 소프트웨어를 작성했을까?

종이 서명에서는 상대방에게 보낼 내용에 서명을 하지만 디지털 서명은 상대방이 여러분에게 내용을 보내기 전에 서명을 한다. 종이서명-종이로 된 서명을 받았다고 한들 정말 본인이 작성한 서명인지 알 방법이 없다 그래서 신뢰할 만한 기관에 모든 사람의 서명을 파일에 보관하고 있다고하자 그럼 여기에 가서 서명을 비교하면 된다 하지만 여기에는 두가지 가정이 있다. 기관의 직원이 믿을만하고 서명은 베낄수없다는 가정이다. 여기에서 디지털 서명으로 가는 첫 단계는 종이 서명을 모두 폐기하고 자물쇠, 키, 금고라는 새로운 채택방법을 선택하는것이다.A가 B에게 한 약속의 문서를 증명하는 방법은 A가 문서를 A의 금고에 넣어 키로 잠그고 B에게 건네는 방법이다 그러나 여기에서 B가 증명을 하려고 할때 A의 도움이 필요하다는 것이다. A가 협력을 거부할 수도 있기에 3자에게 의존할 필요가 있는데 신뢰할만한 기관에 키를 맡겨 해결한다. 신뢰할만한 기관에서 B가 A가 한 약속의 문서를 증명하려고 A의 키를 가져와 금고가 열린다면 이는 A만 열수있는 자물쇠이기에 A에게 책임이 있다는것을 나타낸다. 지금까지 ㄱ키 및 자물쇠를 디지털 방식으로 해석해야하는 수학적 대상과 교체할단계이다 구체적인 수가 자물쇠와 키를 의미하고 시계연산에서곱셈이 잠금 및 잠그해제를 의미한다. A가 문서를 작성해서 금고에 넣어 잠글때 A는 한가지 숫자인 시계크기를 고르고 그 시계크기보다 작은 숫자인 자물쇠의 숫자를 고른다 그러면 해당 메시지에 자물쇠의 숫자를 곱한 후 시계크기로 나눈 나머지인 문서(서명)값이 나오게 된다. 다시 이 서명값을 잠금해제하려고 할때 A의 키를 이용한다 서명값에 x란는 값을 곱하고 시계크기로 나누면 원래 문서의 값이 나오게 된다. 자물쇠에 대응하는 키값이 존재. A의 자물쇠 숫자는 비공개적이어야하고 키 숫자와 시계크기는 공개적이어도 된다.(시계 연산에 대해서 어떻게 이렇게 똑같은 메시지로 돌아올수 있는가에 대해서 궁금증이 풀리지 않아서 찾아봐야함!!!!!) 앞에서 얘기 했듯이 이 공개적인 내용들은 신뢰할수있는 기관에 맡긴다. 긴 메시지에 서명하려면 어떻게 해야하는가? 시계크기가 소수라면 시계크기보다 작은 모든 양의 값은 자물쇠로 작동할 수있다 그러나 자물쇠를 선택하고도 자물쇠를 열 키를 선택해야한다 이 방법은 유클리드 알고리즘으로 이에 대응하는 키값을 알 수가 있다. 그러나 이 방법으로 행하는 것은 역으로도 작동이 되어서 디지털 서명을 위조가 가능하다 지수 자물쇠로 서명하기 - 우리는 곱셈시스템을 실제로 이용하는 RSA라는 디지털 서명 체계로 업그레이드한다. 메시지를 자물쇠의 크기로 제곱을한 후 시계연산을 해 서명을 한다 이 서명을한 값은 자물쇠에 대응하는 키 값으로 다시 제곱을하고 시계연산을 하면 동일한 메시지를 다시 얻게 된다.(그럼 이 메시지가 동일한지 여부는 어떻게 확인하는가????) 이 방법은 다른 사람이 이용하는 키와 시계크기를 안다고해서 이에 대응하는 자물쇠값을 계산할수가없다. RSA가 안전하다는 질문은고대부터 풀리지 않는 소인수분해와 양자컴퓨팅에 의존한다. RSA에서 시계크기보다 작은 자물쇠의 크기를 사용하는데 이는 하나하나 대입을 해보면 풀수는있다 하지만 실제에서는 엄청 큰 크기의 시계크기를 사용하고 이를 다 계산하는데 현존하는 컴퓨터로는 수조년이 걸린다고한다. A는 두 소수를 선택해 주 시계 크기를 만든다 그리고 각 소수에서 1씩을 빼 보조 시계크기를 만든다. 이 보조 시계크기를 활용해 곱셈 시스템을 활용해 빠르게 검증이 가능하다. 그리고 빠르게 RSA 지수 시스템으로 넘어갈수있다. 양자컴퓨팅 - 고전물리학의 결정론적 법칙과 달리 양자 역학에서 대상의 움직음은 확률이 지배한다 따라서 양자역학의 효과에 반응하도록 컴퓨터를 구축할 경우 컴퓨터가 계산하는값은 일반적인 0과 1의 절대적인 배열이 아니라 확률에 따라 결정된다 양자컴퓨터가 다양한값을 동시에 저장한다는 사실이다 모든값은 각기다른확률을 갖지만 컴퓨터애ㅔ게 가요해 최종답을 산출하게 할때까지 이다양한값은 동시에존재한다 이는 양자컴퓨터가 서로 다른 가능한 답을동시에 계산할 가능성을 초래한다. 그래서 브루트 포스를 이용할수있다 이는 소인수분해를 훨씬더 효율적으로 수행할수있다 실제디지털서명- 최종 사용자가 디지털 서명을 할필요가 없다는사실을 알았다 그래서 서명 대부분은 다운로드한 내용을 검증할때 주로 사용한다 소프트웨어를 다운로드할때 컴퓨터가 서명자의 공개키를 이용해 이서명을 열고 서명자의 메시지(보안 해시라는 작은 메시지로 압축된다)와 계산결과를 비교한다 열린 서명이 소프트웨어와 일치할경우 실행을 권하는 메시지를 보게되고 일치하지않을경우 경고 메시지를 보게 된다. 여기에서 중요한 점은 신뢰할수있는 기관인데 이를 어떻게 검증하는가? 인증기관을 인증하는 다른 기관을 찾으면 되는데 이 연쇄의 끝에 최상위 연쇄기관을 디지털 서명에 대한 신뢰할만한 출발점에 닻을 내리게 되는 방식이다. 디지털 서명은 정교하고 아름다운 알고리즘이기도 하지만 엄청난 실용적 중요성도 지닌다, 데이터의 암호화를 이용해 안전하게 교환할수도있겠지만 데이터의 추러를 검증하기는 어려웠을것이다

10. 계산 가능성과 결정 불가능성:컴퓨터로 모든 문제를 해결할 수 있을까?

컴퓨터가 해결할수없는 문제는 앞에 알고리즘들이 이뤄낸 업적에 대한 흥미로운 전환점을 제시한다. 그리고 이런 문제가 나온것은 최초의 계산기가 탄생하기전에 밝혀졌다. 버그 충돌 소프트웨어의 신뢰성 - 자동 소프트웨어 검삳 ㅗ구는 모든 컴퓨터 프로그램에 있는 잠정적 문제를 모두 검찰할수있는 수준에 도달할게 될까? 그러나 이런 소프트웨어 해탈의 경지에 절대 이룰 수없다. 불가능한것을 증명한다 는 표현의 뜻에 관해 좀 알아보자 어떤 명제가 참이 아님을 증명하기 수학자들은 귀류법이라 부르는 기법으로 충돌검출프로그램이 불가능하다는 증명을 해보겠다. 미국 남북전쟁은 1860년대에 일어났다 링컹은 남북전쟁중에 대통령이었다 여기서 링컨은 1520년에 태어났다는 진술은 참인가 거짓인가? 여기에서 아무도 150년 이사 살수없다 따라서 링컨이 1520년에 태어났다면 아무리 오래살았더라도 1670년 에는 사망했어야한다 링컨은 남북전쟁 중 대통령이었다 따라서 남북전쟁은 그가 죽기 이전 즉 1670년 이전에 일어났어야한다 그러나 남북전쟁이 1860년대에 일어났다는 사실에 모두 동의했으므로 1670년 이전에 남북전쟁이 일어나는일은 불가능하다 그러므로 링컨은 1520년에 태어났을리가 없다 이 논증을 더 주의 깊게 검토해보자 왜 위에 나온 처음 진술이 거짓이라는 결론이 타당한가? 이는 이 주장이 참이라고 알려진 다른 사실과 모순된다는 것을 증명했디 때문이다 구체적으로 처음 진술에서 남북전쟁이 1670년 이전에 일어났다는 점을 내포하고 있고 이는 남북전쟁이 1860년대 일어났다는 사실과 모순된다는 사실을 증명했다 귀류법을 추상젇ㄱ인 용어를 이용해 귀류법을 요약해보자. 진술 S가 거짓이라는 의심읋 하고 있어 이것이 의심의 여지없이 거짓임을 증명하고자 한다 S가 참이라고 가정한다. 이로부터 논증을해 예컨대 T라는 다른 진술도 참이어야 한다는 결론에 도달한다 그러나 T가 거짓임이 알려져있다면 모순에 도달한 셈이다 수학자는 이를 S는 T를 내포하지만 T는 거짓임으로 S도 거짓이다.라고 간략히 진술한다.

다소 이상한 세가지 개념에 익숙해져야한다 첫쨰 어떤 파일이나 입력을이용해서 어떤 프로그램이라도 실행할수있다는 개념 그러나 입력파일이 이를 실행한 프로그램의 목적에 맞는 파일이 아닌경우 결과는 쓰레기가 출력된다. 둘째 컴퓨터 프로그램도 컴퓨터 디스크에 파일로 저장되므로 아무 프로그램이나 입력으로 이용해 어떤프로그램이라도 실행할수있다는 사실 셋째 한 컴퓨터 프로그램은 자기 자신을 입력으로 이요해 실행할수있다 존재할수없는 프로그램 단순한 예아니오 프로그램 - 그저 단순하게 예나 아니오만 출력한다 이를 바탕으로 사이즈 체커란 프로그램을 만들얶ㅆ다 이프로그램은 한파일의 크기가 10kb가 넘어가면 예를 그게아니라면 아니오를 출력한다, 이와는 약간 다른 네임사이즈 프로그램을 만든다 파일 이름이 한글자이상이면 예를 그렇지 않으면 아니오를 출력한다 정의상 모든 프로그램의 이름은 한글자이상이므로 이프로그램은 항상 예를 출력한다 항상예스 프로그램 이파일이 항상 예를 출력하는 파일이면 예를 그렇지 않으면 아니오를 출력한다, 프리즈 라는 프로그램은 실행되면 입력에 상관없이 프리즈 되어버린다. 즉 프로그램이 잠겨 어떤 응답도 거부하는 상태이다.이는 교착상태와 같은 다양한 이유때문이기도하다. 예스온셀프 프로그램은 자신을 입력으로 실행할때 예를 출력하고 나머지는 아니오를 출력한다. 만약 여기서 예스온 셀프가 자기 자신을 입력으로 받지만 그 입력으로 받은 예스온 셀프에서 아니오가 출력된다면? 예스온 셀프에 정의에 따라 예를 출력한다 항상예스라는 프로그램을 작성했다고 가정하면 예스온셀프 프로그램을 만들기란 쉽다. 예스온셀프는 항상예스의 더 단순한 형태이기때문이다 이는 모든 가능한 입력이 아닌 하나의 가능한 입력만을 검포해야한다

안티예스온셀프, 예스온 셀프의 정반대예스온 셀프에서 예라고 나오면 아니오를 출력하고 아니오가 나오면 예를 출력한다. 예스,온 셀프는 자신을 대상으로 실행될때 예를 출력하는 입력에만 예를 출력하고 그렇지 않을경우 아니오를 출력한다. 여기에서 안티예스온 셀프에 자기 자신인 안티예스온 셀프를 넣으면 어떻게되는가?(해당 그림에서 출력표에 오류가있어 마지막행이 antiyesonself.exe가 아닌 selfonself.exe로 표기되어 이해를 하는데 난항이있었다.) 여기에서 해당 질문은 모순을 발견했다는것을 발견했다. 이는 첫 가정이 틀렸음을 내포한다. yesonself.exe프로그램이 존재하면 antiyesontself.exe프로그램을 만들기 쉽다. 따라서 충돌을 찾는 프로그램이 존재할수없음을 증명하는 최종목표에 이르는 디딤돌이라는 사실을 기억하라

충돌찾기의불가능성 cancrush.exe - 입력이 충돌 하면 예, 아니라면 아니오 cancrashweired.exe - ㅇ비력이 충돌할수있으면 충돌 , 충돌하지 않으면 아니요 출력 crashonself.exe - 입력이 자신을 대상으로 실행될때 충돌하면 충돌, 입력이 자신을 대상으로 실행될때 충돌하지않으면 아니오 anticrashonself.exe - 입력이 자신을 대상으로 실행될때 충돌하면 아니오, 입력이 자신을 대상으로 실행될때 충돌하지 않으면 충돌 자 그럼 여기서 마지막에 모순을 발견한다 충돌하지 않았는데 충돌을하게 된다는 모순이 발생. 따라서 cancruash가 존재한다는 가정은 거짓임이 틀림없다

정지문제와 결정불가능성 - 컴퓨터과학에서 가장 난해하고 심오한 결론중하나를향한여행의 결론이났다 cancrash.exe같은 프로그램은 절대 불가능함을 증명했다. 앨런 튜링은 이를 최초로 증명했을때 버그나 충돌을 전혀신경쓰지않았다 튜링은 컴퓨터 프로그램이 결국답을 산출할지에 고나심이있었다 이와 밀접히 연관된질문은 컴퓨터 프로그램은 계산을 끝내고 멈출수있을까 아니면 영원히 계속해서 계산할수있을까 하는 정지(halt)에 관한 질문인 정지문제(Halting problem)으로 알려져있다. 튜링의 위대한업적은 결정불가능성이라고 부르는 다양하게 변형된 형태의 정지문제를 증명해냈다 따라서 alwatshalts.exe 입력이 늘정지하면 예를 출력하고 그렇지않으면 아니오를 출력하는 프로그램은 작성할수없다. 이렇게 컴퓨터과학에는 결정할수없는문제가 많다.

불가능한 프로그램이 주는 함의 결정 불가능한문제가 현실에서 우리의 컴퓨터 사용방식에 영향을 줄까? 인간이 머리로하는 계산은 어떨ㄹ까? 결정 불가능성은컴퓨터의 일상적 사용에 별 영향을 주지않는다 결정불가능성은 컴퓨터가 답을 산출할수있는지애ㅔ만 고나심이았고 답을하는데 걸리는 시간은 고려하지않는다 그러나 실생활에서 이 답을하는데 걸리는시간은 중요하다 또한 별영향을 주지않는 이유로 대체로 결정불가능한문제를 잘해결할수있다.우리는 버그를 찾는 프로그램을 만들수없는 결론에 도달했지만 실생활에서는 대부분의 버그를 찾아내는 충돌검색프로그램을 작성하기 위해 노력할수있다. 그러므로 결정 불가능한 문제에 매우 유용한 부분적 해결책을 만드는일은 얼마든지 가능하다 결정불가능성과 인간의 뇌 결정불가능한 문제의 존재가 인간사고과정에 함의를 줄까? 이는 의식의 정의나 정신과 뇌의 구분 같은 고전적인 철학문제의 심연까지 들어가야한다 모든 컴퓨터가 인간의 사고과정을 모방할수도있다는 개념은 처치-튜링명제로 알려져있다 이명제를 지지하는 가장 강력한 입장을 취하면 컴퓨터만이 결정불가능성이란 한계에 부딪히는 것이 아니라고 말할수있다. 결정불가능성의 한계는 우리앞에 놓인 천재뿐 아니라 우리안의 천재 즉 정신에도 적용될수있다고 한다.

11. 마치면서: 미래의 알고리즘과 진화하는 컴퓨터

컴퓨터 과학의 위대한 알고리즘의 미래에 대해 생각하기를 멈춰서는 안된다. 우리가 탐구한 위대한 알고리즘이 영원히 위대한 상태로 남아있을까? 이런 질문을 다루기 위해 역사할자 처럼 생각한다. 인간은 과거에 했던 대로 반복한다라는 인용을 따라넓은 범위의 역사를 받아들이자. 알고리즘은 20세기에 출현한 사고나과 발명으로 등장했고 21세기에도 이와 비슷한 속도로 이삼십년마다 주요 알고리즘들이 등장했다. 이것처럼 앞으로도 주요 알고리즘들은 계속 등장할 것이다. 그러나 새로운 테크놀로지가 출현한다고 반드시 새로운 알고리즘이 생겨나는것은 암에 주의하라. 노트북 컴퓨터가 등장은 했지만 그 어떤 위대한 알고리즘을 불러오지는 않았다. 그럼으로 맹렬히 성장하는 테크놀로지의 발전이 위대한 알고리즘의 출현을 보장하지는 않는다. 그러나 최신 테크놀로지가 제공하는 새로운 틈새로 인해 새로운 알고리즘에 대한 시야가 넓어지지만, 이 분야가 성숙함에 따라 기회의 폭이 좁아진다. 이 둘을 모두 감안할때 앞으로 이 두효과가 서로 상쇄하면서 새로운 알고리즘은 천천히 그리고 꾸준히 출현할것이다.

잠재력 있는 위대한 알고리즘 후보군 우리는 일상생활에서 인공지능 특히 패턴인식을 점점 많이 사용한다 이분야는 놀랍도록 참신한 알고리즘이 출현할지 관망해보는것도 흥미롭다 또하나는 영지식 프로토콜이라는 알고리즘 부류다 두개 이상의 개체에 단하나의 정보도 노출하지 않고 정보를 결합할수있게하는 방법이다. 그리고 분산해시 테이블로 중앙서버가 없는 p2p 서버에서 정보를 저장하는 기발한 방식이다. 비잔틴 장애허용이라는 기법도 같은 범웨 속한다 어떤 유형의오류도 이겨낼수있다. 오늘날 위대한 알고리즘들은 언젠가 중요성을 잃게 될 것이다. MD5로 알려진 해시 함수는 인터넷 표준이고 이전부터 널리 이용됐다 그러나 심각한 보안의 문제를 발견하고 그 이후로는 함수의 이용을 권하지 않게됐다 앞에서 말한 RSA 디지털 서명 체계는 적절한 크기의 양자 컴퓨터가 만들어 진다면 쉽게 무너질것이다. 이 책에서 얻은 교휸 - 저자가 매우 놀랐던 부분은 컴퓨터 과학에 관한 사전 지식 없이도 해당 알고리즘들을 모두 설명할 수 있다는 것이었다. 전문적 내용을 분명히 많이 생략했지만 모든 알고리즘의 핵심 작동 기제를 전문적이지 않은 개념을 이용해 설명이 가능했다. 그리고 또 다른 중요한 주제는 컴퓨터과학의 분야는 프로그래밍을 훌 쩍넘어선다는 사실이다. 컴퓨터 과학은 프로그래밍, 소프트웨어 공학을 넘어서는 것을 이해했기를 바란다고 한다. 컴퓨터 과학자에게 프로그래밍 언어네 관한 지식은 필수다 그러나 이는 기본요건에 불과하고 가장 큰 도전은 알고리즘을 개발하고 적용하며 이해하는것이다. 저자가 이 책을 쓴 이유는 알고리즘에 고나한 지식을 얻음으로써 컴퓨터가 하는 일상적인 작업에 경외감을 갖게하는 아무추어 천문학자가 밤하늘을 재미있게 볼 수있는 상황처럼 되는 것에 목적이라고한다,.