우연히 발견한 책이지만, 나름 재밌게 읽어서 정리함.

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

첫 챕터만 봐도 컴퓨터 전공자만을 위한 책이 아니라는 것을 알 수 있다. 좋은 책이라고 생각한다.

Chapter 1 - [컴퓨터를 움직이는 위대한 아이디어들]

컴퓨터과학자들은 자신들의 중요한 아이디어의 상당수를 ‘알고리즘(Algorithm)’ 이라고 표현한다.

• 알고리즘이란
  • 문제를 푸는 데 필요한 단계의 순서를 명확히 명시하는 구체적인 계산법.
• 이 책을 읽었다고 해서 매우 숙련된 컴퓨터 사용자가 될 수는 없겠지만, 컴퓨터 장치에서 여러분이 매일 끊임없이 이용하는 알고리즘의 아름다움을 훨씬 깊이 느낄 수 있게 될 것이다.
  • 그게 왜 좋을까? 비유를 들어 보겠다. 나는 천문학 전문가가 아니다. 사실 천문학에 대해 상당히 무지하고 더 많이 알고 싶어 한다. 그러나 내가 가진 매우 짧은 천문학 지식 덕분에 밤 하늘을 볼 때마다 즐거움이 배가된다. 내가 바라보는 대상에 관한 이해가 만족감과 경탄을 낳기 마련이다. 책을 읽은 뒤 컴퓨터를 사용하면서 이런 기쁨을 가끔은 느끼게 되길 진심으로 바란다.우리 시대에서 가장 편재하고 불가해한 블랙박스인 컴퓨터, 즉 여러분 앞에 놓인 천재의 진가를 알아보게 될 것이다.

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

검색엔진은 우리 삶에 엄청난 영향을 미쳤다. 우리 대부분은 하루에도 몇 번씩 검색 쿼리를 던지지만 이 탁월한 툴의 작동 원리를 그다지 궁금해 하지 않는다. 막대한 정보의 양도, 빠른 속도로 나오는 훌륭한 결과도 이제는 늘 있는 일이라, 몇 초 안에 질문에 대한 답을 얻지 못하면 짜증이 밀려온다.

• 매칭과 랭킹
  • 가장 좋은 소수의 검색결과를 적절한 순서로 선별하는 작업을 ‘랭킹’이라 부른다. 랭킹은 매칭이라는 첫 단계를 뒤따르는 중요한 두 번째 단계이다. 검색 산업이라는 치열한 경쟁 세계에서 검색엔진은 랭킹 시스템의 질에 따라 살거나 죽는다.
  • 2002년 미국 최고 검색엔진 시장은 구글,야후, MSN이 각각 30% 가량을 점유했다. (MSN -> Live Search -> Bing) 이후 몇 년간 구글이 시장 점유율에서 극적으로 성장하며 야후와 MSN을 각각 20%이하로 떨어뜨렸다.
  • 구글이 검색 산업의 강자로 부상하게 된 것은 랭킹 알고리즘 덕분이라 여겨진다.
  • 검색엔진은 랭킹 알고리즘의 질에 따라 살거나 죽는다는 말은 절대 과장이 아니다.
• 알타 비스타 : 최초의 웹 규모 매칭 알고리즘
  • 검색엔진 매칭 알고리즘에 대해 많은 사람들이 21세기 초에 일어난 위대한 기술 성공 신화인 구글이 태오라고 생각할 것이다.
  • 웹 검색이라는 발상은 수년 전부터 이미 존재했다. 웹 검색기법을 최초로 상용 도입한 기업은 인포시크와 라이코스, 그리고 1955년에 검색엔진을 출범시킨 알타비스타(AltaVista)였다.
  • 1990년대 중반 몇 년 동안 알타비스타는 검색엔진의 왕이었다.
  • 최초로 검색엔진은 웹의 모든 페이지에 있는 모든 텍스트를 완전히 인덱싱했다. (눈 깜빡할 사이에 결과가 떴다.)
  • 이 획기적 기술발전을 이해하려면 아주 오래된 개념인 인덱싱부터 살펴 봐야한다.
• 오래된 평범한 인덱싱
  • 인덱스(index)란 개념은 모든 검색엔진 이면에 있는 가장 근본적 발상이다.
  • 웹 검색엔진용 인덱스는 책의 인덱스와 같은 방식으로 작동한다.
  • 구문 쿼리(phrase query)처리 문제 때문에 단순한 인덱싱으로는 부족하다.
• 단어 위치 트릭
  • 구문 쿼리 문제의 해결책이 오늘날 검색엔진을 잘 작동하게 만든 첫 번째 기발한 발상이다.
  • 인덱스가 페이지 번호뿐 아니라 페이지 안의 위치도 저장해야 한다는 아이디어에서 출발한다.
• 랭킹과 근접성
  • 사용자에 보여 줄 소수의 상위 검색결과를 설변하는 단계가 ‘랭킹’이다.
  • 페이지의 ‘순위’는 실제로 무엇에 달려 있는가?
    • ‘이 페이지가 쿼리에 부합하는가?’가 아니라 ‘이 페이지가 쿼리에 적합한가?’ 이다.
    • 컴퓨터과학자는 ‘적합성’ 이란 용어를 주어진 페이지가 특정 쿼리에 적압하거나 유용한 정도를 기술하는 데 쓴다.
• 메타워드 트릭
  • 대부분 웹페이지는 제목, 표제, 링크, 이미지 등 구조가 꽤 복잡하다.
  • 메타워드 : 제목의 시작, 끝, 표제의 시작, 끝 등을 말함.
  • 보통 단어와 같은 방식으로 메타워드를 인덱싱하는 트릭을 메타워드 트릭 이라고 한다. 터무니 없이 간단해 보일 수도 있지만 메타워드 트릭은 검색엔진이 정확한 결과와 고품질의 랭킹을 내는 데 결정적인 역할을 한다.
• 인덱싱과 매칭 트릭이 전부는 아니다
  • 이 장에서 소개한 두 트릭만으로 효과적 검색엔진 인덱스를 구축하지는 못한다는 사실을 반드시 인식해야 한다. 그러나 단어 위치 트릭과 메타워드 트릭은 분명히 실제 검색엔진이 인덱스를 구축하고 이용하는 방식을 맛배기로 보여준다.
  • 알타비스타가 (다른 검색엔진은 실패했던) 전체 웹에서 딱 들어맛는 결과를 찾는 데 성공한 이유는 메타워드 트릭 덕분이었다는 것을 1999년 알타비스타가 제출한 **<인덱스 제한 검색(Constrained Searching of and Index)> 라는 미국 특허를 통해 볼수 있다.
  • 우리가 이미 알고 있듯 효율적 매칭은 효과적 검색엔진이 되는 데 딱 절반 정도의 역할을 할 뿐이다. 나머지 과제는 적절하게 매칭된 페이지의 순위를 매기는 일, 즉 랭킹이다. 다음 장에서 보겠지만 새로운 유형의 랭킹 알고리즘은 알타비스타를 몰락시키고 구글을 웹 검색 세계의 중심으로 올려 놓기에 충분했다.

Chapter 3 - [페이지 랭크: 구글을 출범시킨 기술]

구글이 검색결과의 순위를 매기는 데 이용한 혁신적 알고리즘은 페이지랭크 이다. 이는 웹페이지 순위를 매기는 알고리즘인 동시에 래리 페이지가 개발한 랭킹 알고리즘이기도 하다. 이 장에서는 검색 쿼리에 가장 적합한 결과를 상위 검색결과로 산출할 수 있는 방법과 요인을 살펴본다.

• 하이퍼링크 트릭
  • 하이퍼링크란 클릭했을 때 다른 웹페이지로 연결하는 웹페이지 구문이다. 대부분 웹브라우저에서는 눈에 쉽게 띄도록 파란색 밑줄이 표시되어 있다.
  • 페이지 랭크를 이해하는 첫 단계는 이 책에서 하이퍼링크 트릭 이라고 부를 간단한 발상이다.
  • 각 페이지에서 연결된 페이지 수를 세어 각 페이지에 있는 인커밍링크 (incoming link) 의 수에 따라 순위를 매기는 방법으로 접근했다. 물론 사람이 페이지 전체를 읽고 순위를 수동으로 결정하는 방법만큼 정확하지 않지만 유용한 기법이다.
  • 한 가지 명백한 점은 때론 링크가 좋은 페이지가 아닌 나쁜 페이지를 지칭하는 데 이용된다는 것이다.
• 권위 트릭
  • 페이지의 모든 인커밍 링크를 동등하게 취급하는 것은 좋은 방법이 아니다.
  • 전문가의 추천은 일반인의 추천보다 분명히 더 가치가 있다로 출발한 아이디어.
  • 사이클이 생길 수 있다. (단점)
• 무작위 서퍼 트릭
  • 사이퍼링크는 컴퓨터과학자가 ‘사이클’이라고 부르는 것을 형성할 가능성이 꽤있다.
  • 무작위 서퍼 트릭은 하이퍼링크와 권위 트릭의 순기능을 결합했지만 하이퍼링크 사이클이 있을 때도 작동한다.
  • 무작위로 인커밍 링크중 하나를 방문하는식으로하여 점수를 메긴다.
• 실제 페이지 링크
  • 페이지랭크의 핵심을 공격하는 웹 스팸(web spam) 때문에 많은 연구가 지속됨.
  • 상용 검색엔진이 페이지랭크 같은 링크 기반 랭킹 알고리즘 외에도 훨씬 더 많은 것을 이용해 순위를 결정한다.
  • 1998년 공개된 구글 설명에서조차 구글의 두 공동 창업자는 검색결과 랭킹을 기여하는 여러 다른 특징을 언급했다.
  • 구글의 웹사이트는 페이지 중요도 평가에 200개 이상의 신호를 이용한다고 한다.
  • 오늘날 검색엔진이 매우 복잡해지기는 했지만, ‘권위 있는 페이지는 하이퍼링크를 통해 다른 페이지에 권위를 부여한다.’는 페이지랭크의 핵심 아이디어는 여전히 유효한다.

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

인터넷상의 어떤 메시지든 라우터(router)라 불리는 수많은 컴퓨터를 거쳐 여행하기에 이 라우터에 접속하면 누구든지 메시지 내용을 볼 수 있다.

• 공유 비밀로 암호화
  • 128비트 암호화
    • 덧셈 트릭을 이용한 암호화 기법
    • 비트 수의 30%를 계산하면 키의 근사 자릿수를 알 수 있다. 그렇다면 128의 30%는 약 38 이므로 128비트 암호화는 38자리 숫자 키를 이용한다.!
    • 38자리 숫자는 매우 큰 수이고 현존하는 어떤 컴퓨터도 이 모든 가능성을 시도하는 데 수십억 년이 걸리므로 38자리 공유 비밀은 매우 안전하다고 할 수 있다.
  • 블록 암호(Block cipher)
    • 덧셈은 통계적으로 분석 가능한 결과를 낳고 이는 누군가가 암호화된 메시지 분석을 기반으로 키를 계산할 수도 있다.
    • 변형된 덧셈트릭인 ‘블록암호’를 이용한다.
    • 긴 메시지를 통상 10~15자로 이뤄진 고정된 크기의 작은 ‘블록’으로 쪼갠다.
    • 그냥 메시지를 한 블록과 키를 더하는 대신 각 블록을 덧셈과 유사하지만 메시지와 키를 더 공격적으로 섞는 고정된 규칙에 따라 수 차례 변형한다.
    • 오늘날의 블록 암호는 주로 10차례 혹은 그 이상 작업을 한다.
    • 키를 아는 사람은 모든 계산을 역으로 구동해 해독된 원래 메시지를 얻을 수 잇다.
  • AES(Advanced Encryption Standard)
    • 다양한 설정으로 이용 할 수 있지만 일반적으로 16자짜리 블록을 128비트 키와 함께 이용해 10차례의 혼합 계산을 하는 방식으로 사용한다.
• 공유 비밀을 공개적으로 설정하기
  • 페인트 혼합 트릭(디피-헬만 키 교환)
    • 휫필드 디피와 마틴 헬만이 1976년에 발표하였다.
    • 책에는 그림 예시와 설명을 통해 이방식을 설명하고 있다.
    • 암호 키를 교환하는 하나의 방법으로, 두 사람이 암호화되지 않은 통신망을 통해 공통의 비밀키를 공유 할 수 있도록 한다.
    • 이 방식은 기초적인 암호학적 통신 방법을 수립하였고, 이후 1977년 공개 키 암호 방식인 RSA 암호가 제안됨.
  • 숫자로 하는 페인트 혼합 트릭
    • 컴퓨터는 혼합 계산으로 이산 누승법(discrete exponentiation) 과 이산 로그(discrete logarithm)를 사용한다.
    • 컴퓨터는 이산로그를 효율적으로 계산할 방법이 없다! (이점을 이용하면 일방향 암호화가 된다.)
  • 공개 키 암호화의 실체
    • RSA와 디피-헬만을 비롯한 공개 키 암호 시스템은 단순히 기발한 알고리즘 수준을 넘어선다. 이는 기업과 개인에게 동일하게 매우 중요한 상업 기술과 인터넷 표준으로 발전했다. 우리가 대부분은 공개 키 암호화 없이 안전하게 완료될 수 없다.

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

오류 정정 코드란 컴퓨터 데이터에서 오류를 검출해 정정하는 마법 같은 알고리즘이다.

• 오류 검출과 정정의 필요성
  • 컴퓨터는 세 가지 근본적 작업을 수행한다. 가장 중요한 일은 계산수행이다. 그러나 컴퓨터가 수행하는 다른 두 가지 매우 중요한 일이 없다면 답을 계산하는 능력조차 거의 무용지물이 될 것이다. 이는 데이터 저장 과 전송 이다.
  • 데이터 전송과 저장과 관련된 큰 난관이 있다. 데이터는 정확해야 한다는 점이다. 많은 사소한 실수 하나조차 데이터를 무용지물로 만들 수 있기 때문이다.
• 반복 트릭
  • 같은 정보를 반복적으로 전송하여 가장 많이 전송된 값을 올바른 데이터라 판단하는 방법.
  • 안타깝게도 오늘날의 컴퓨터 시스템에 별로 알맞지 않다. 데이터의 크기가 커졌기때문!
• 리던던시 트릭
  • 신뢰도를 향상시키기 위한 잉여 정보를 보낸다. 이를 리던던시(redundancy)라고 한다.
  • 반복 트릭보다 더욱 선호한다. (상대적 비용(overhead)이 더 적다.)
• 체크섬 트릭
  • 오류 정정을 하지않고 검출하는데만 집중하는 방법!
  • 오류의 여부에 따라 재전송을 요청하도록 하는 방식이다.
• 핀포인트 트릭
  • 2차원 패리티(two-dimensional parity)라고 컴퓨터과학에서는 부른다.
  • 패리티란 컴퓨터가 통상 쓰는 이진수로 작동하는 단순 체크섬을 뜻한다. 그리고 메세지를 이차원 격자(grid)에 배열하기에 이차원 패리티라고 부른다.
  • 실제 컴퓨터에 이용했지만 이는 그 어떤 리던던시 트릭보다 비효율적이다. 하지만 시각화가 쉽고, 오늘날 컴퓨터 시스템에서 흔히 쓰는 코드 이면의 복잡한 수학을 요하지 않고도 오류를 찾고 정정하는 방법의 묘미를 전달하기에 적합하다.
• 실제 오류 정정과 검출
  • 일반적으로 체크섬은 오류 정정보다 오류 검출에 널리 사용된다.
    • 이더넷은 오늘날 지구에 있는 거의 모든 컴퓨터가 쓰는 네트워킹 프로토콜로서, CRC-32란 체크섬을 이용해 오류를 검출한다.
    • 가장 유명한 인터넷 프로콜인 TCP도 보내는 데이터의 각 청크 또는 패킷에 체크섬을 이용한다. 체크섬이 부정확한 패킷은 폐기된다. tcp는 필요한 경우 이를 나중에 자동으로 재전송 하도록 설계됐기 때문이다.
  • 인터넷 상에 배포되는 소프트웨어 패키지는 대개 검사 합계를 이용해 검증된다.
    • 자주 쓰는 체크섬은 MD5와 SHA-1 이다.
    • 둘다 암호학적 해시 함수로 고안돼 무작위 통신 오류뿐 아니라 소프트웨어의 악성 변형으로부터 보호 기능을 제공한다.

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

인간의 타고난 이점을 활용하는 분야 -> 패턴 인식(pattern recognition) 인접이웃 분류자(nearest-neighbor classifier),의사 결정나무(decision tree),인공 신경망(artificial neural network)에 대해서 알아본다.

• 인접이웃 트릭
  • 가장 단순한 형태의 인접이웃 트릭은 문자 그대로의 작업을 한다. 가장 근접한 이웃을 찾아 이 최근접 이웃의 클래스를 예측값으로 이용한다.
• 스무고개트릭: 의사결정나무
  • 스무고개와 같은 방식으로 동작한다.
  • 분류자의 학습 단계는 복잡할 수 있지만 이는 완전히 자동이고 사람은 이를 단 한 번만 하면 된다. 그러면 우리가 필요로 하는 의사 결정나무를 갖게 되고 분류 단계는 놀랍도록 간단하다.
• 인공 신경망
  • 뇌의 아주 작은 부분을 매우 단순하게 작동하도록 재현한 컴퓨터 모델이다.
• 패턴인식 :과거, 현재, 미래
  • 패턴인식은 인공지능의 하위 분야다.
  • 패턴인식은 소리, 사진, 영상 같은 데이터를 다루는 반면, 인공지능은 체스, 로봇 등 다양한 과제를 다룬다.
  • 인공지능과 패턴 인식은 서서히 범위를 확장하고 있으며 성능을 향상시키고있다.

Chapter 7 - [데이터 압축: 책 한 권을 종이 한 장에 담기]

압축은 컴퓨터시스템의 보이지 않는 곳에서 꽤 자주 이용된다. 예를 들어 인터넷을 거쳐 전송되는 많은 메시지는 사용자조차 모르는 사이에 압축되고 거의 모든 소프트웨어는 압축된 형태로 다운로드된다. 가장 보편적인 ZIP 파일 포맷은 이 장에서 설명할 기발한 압축 알고리즘을 이용한다.

• 무손실 압축: 최고의 공짜 점심
  • 런-렝스 인코딩(run-length encoding)
    • 특정 길이를 가진 반복의 런을 인코딩 하는 방법
    • ex) aaaabcbcbcaaaff -> 4a, 10bc,3a, 2fa1629715A
    • 안타깝게도 이 인코딩법은 매우 특정한 유형의 데이터에만 유용하다.
    • 실제로 이를 사용하기도 하지만 주로 다른 압축 알고리즘과 함께 쓴다. 허프만 코딩
    • 허프만 코딩과 함께 결합하여 팩스 기계에 사용한다. 팩스기계는 검색은이나 흰색의 수많은 점이기 때문에 가능하다.
• 전과 같음 트릭(same-as-earlier trick)
  • 이전에 나왔던 문자를 반복해서 말하지 않고 특정지점으로 돌아가서 복사하라는 식으로 하여 압축하는 방식.
• 더 짧은 심벌 트릭(shorter-symbol trick)
  • 심볼 테이블을 작성하여 압축하는 방식.
  • 짧은 내용을 압축할때는 효율이 적은거 같지만 사이즈가 커질수록 효율이 엄청나다.
• 요약: 공짜 점심은 어디서 올까?
  • 컴퓨터의 전형적인 ZIP 압축 파일 제작 배후에 있는 모둔 중요한 개념
    • 1. 압축되지 않은 원본 파일을 ‘전과 같음 트릭’ 을 이용해 변형해서 파일에 있는 반복 데이터 대부분을 돌아가서 데이터를 작성한다.
    • 1. 변형된 파일에서 어떤 심벌이 자주 등장하는지 검토한다.
    • 1. 2.에서 숫자 코드는 직접 번해해 다시 파일은 변형한다.
    • 1. 2단계에서 계산된 숫자 코드 테이블도 ZIP파일에 저장한다. (나중에 풀기위함)
  • 압축되지 않은 파일이 다르면 숫자 코드 테이블도 달라진다.
  • ZIP파일의 숫자 코드 테이블은 각각 다르다는 것 알 수 있다. (2단계로 인해서)
  • 이 모든 과정은 효율적이고 자동적으로 이뤄지고 많은 유형의 파일에서 훌륭한 압축을 달성한다.
• 손실 압축: 공짜 점심은 아니지만 매우 좋은 거래
  • 이미지나 오디오 데이터는 손실 압축을 한다. (사람은 컴퓨터보다 덜 민감하기 때문에 가능)
  • 생략 트릭
    • 단순 생략
      • 짝수번째 행과 열을 생략하여 데이터를 변형 (1/4로 줄일 수 있다)
      • 픽셀의 일부 행과 열을 삭제 했기 때문에 사라진 픽셀을 추측해서 압축을 해제해야한다. (감안할 점)
    • JPEG
      • 지나치게 전문전인 압축법이라 간단히 설명할 수 없다.
      • 기본적인 발상은 간단하다. 전체 이미지를 8x8픽셀 크기의 작은 정사각형으로 나눈다.
      • 각 정 사각형을 개별적으로 압축한다. 칼라일경우 세배가 된다 (r,g,b)
      • 정사각형이 약간의 차이만 있고 거의 동일한 색이라면 컴퓨터는 하나의 숫자로 대체할 수 있고, 압축을 해제했을 때 매우 작은 오류만이 드러나는 괜찮은 압축 결과를 낳는다.

Chapter 8 - [데이터베이스: 일관성을 향한 여정]

거의 모든 온라인 거래는 1970년대이래 개발된 정교한 데이터베이스 기법을 이용해 처리된다. 데이터 베이스는 두 가지 사안을 중요시 한다. 효율성 그리고 신뢰성 이 장에서는 데이터베이스 이면의 근본적 알고리즘 세 가지를 다루겠다. 이는 미리 쓰기 로그(write-ahead logging), 2단계 커밋(2-phase commit), 관계형 데이터베이스(relational database) 이다.

• 트랜잭션과 할 일 목록 트릭
  • 트랜잭션(transaction)
  • 데이터 불일치, 충돌들을 피하고자 만들었음.
  • 일관성 유지를 위해 트랜잭션 ‘복귀(rollback)’ 이란 개념도 존재한다.
  • 충돌이란, 컴퓨터의 기능을 멈춰 데이터 손실을 야기할 수 있는 모든 사고를 아우른다.
  • 할 일 목록 트릭
    • 모든 사람이 체계적이지는 않다. 하지만 체계적인지 여부와 상관없이 매우 체계적인 사람이 가진 훌륜한 무기 중 하나는 ‘할 일’ 목록이다.
    • 컴퓨터과학자들도 유사한 개념으로 미리 쓰기 로그 란 용어를 사용한다.
    • 기본 개념은 데이터베이스가 수행하려는 동작의 로그를 유지하는것이다. (하드 드라이브 등에 저장)
    • 로그에 있는 정보는 충돌과 재시작 후에도 살아남게 된다. 모든 트랜잭션이 성공적으로 완료되면 할 일 목록을 삭제해 디스크 공간도 줄인다.
    • 한 트랜잭션은 몇 번 수행 되더라도 상관없이 같은 효과를 내도록 고안되었다. 전문용어로 멱등(idempotent) 라고 한다.
  • 크고 작은 원자성
    • 트랜 잭션을 이해하는 또 다른 방법이있다. 데이터베이스 사용자의 관점에서 모든 트랜잭션은 원자성(atomicity)을 띤다.
    • 할 일 목록 트릭은 원자적 트랜잭션을 제공해 일관성을 보장한다.
    • 할 일 목록은 잠금(locking) 기법과 결합할 때 수천 개의 요청이 들어와도 일관성을 유지할 수 있다.
  • 할 일 목록 트릭은 데이터 오염을 사전에 차단하지만 데이터 손실을 제거하진 못한다.
• 중복 데이터베이스를 위한 준비 후 커밋 트릭
  • 중복 데이터 베이스
    • 하드웨어 이상으로 인한 영구적 데이터 손실은 할 일 목록 트릭으로는 도움이 되지 않는다.
    • 두개 이상의 데이터베이스 사본 유지가 명백한 해결책이다.
    • 백업(back up) 유지라는 친숙한 개념과는 조금 다르게 동작한다.
      • 백업은 특정 시점 데이터의 스냅샷이다.
      • 항상 최신 상태를 유지하진 않는다.
    • 백업과 다르게 중복 데이터 베이스는 모든 사본을 늘 동기화한다.
  • 트랙잰션 복귀
    • 트랜잭션은 데이터베이스의 일관성을 보장하기 위해 반드시 수반되어야 하는 데이터베이스에 대한 일련의 처리 동작이다.
    • 어떤 이유에서 트랙잭션을 완료 할 수 없을때도 있다. (디스크 공간부족 등)
    • 대표적인 트랜잭션을 완료 할 수 없는 상황은 잠금(lock)상태이다. (교착상태)
    • 교착상태 검사를 주기적으로 실행하여 트랜잭션 중 하나가 취소돼 나머지 트랜잭션을 진행 할 수 있도록 한다.
  • 준비 후 커밋
    • 2단계 커밋 프로토콜
      • 1단계: 준비 단계.
      • 2단계: 결정 또는 중단 단계.
    • 복제 본들이 트랜잭션을 완료할 수 있는지 없는지 여부를 보고 수행을 하도록 하는 것.
• 관계형 데이터베이스와 가상 테이블 트릭
  • 오늘날 데이터베이스 테크놀로지의 진짜 힘은 복수의 테이블을 가진 데이터베이스에서 촉발됐다.
  • 복수 테이블 접근의 이점은 저장해야 하는 정보의 양이 줄어든는 점이다.
  • 테이블을 정확히 설계한다면 데이터베이스에 쉽게 변화를 줄 수 있다는 점이다.
  • 키
    • 테이블에 있는 상세 정보를 ‘찾아보는’ 데 이용하는 열을 데이터베이스 용어로 키(key)라고 한다.
    • 사람이 사전에서 단어를 찾는 방식과 유사하다.
    • 빠르게 키를 찾고자 사전에 계산된 묶음의 집합을 컴퓨터과학에서는 B-트리(B-tree)라 한다. 이는 오늘날 데이터베이스를 뒷받침하는 또 하나의 중요하고 기발한 개념이다.
  • 가상 테이블 트릭
    • 기본 아이디어는 데이터베이스의 모든 정보는 고정된 테이블에 저장되지만 데이터베이스는 필요할 때마다 완전히 새로운 테이블을 일시적으로 생성할 수 있는데, 이 처럼 일시적으로 추가하는 테이블은 어디에도 실제로 저장되지 않는 가상 테이블 을 만드는 것이다.
    • join(조인)이라는 명령을 이용하여 가상 테이블을 생성한다.
  • 관계형 데이터베이스
    • 상호 연결된 테이블에 있는 모든 데이터를 저장하는 데이터베이스를 관계형 데이터베이스라 부른다.

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

디지털(digital)이라는 단어를 문자 그대로 해석하면 ‘숫자 열로 구성된’ 이란 뜻이다. 서명(signature)의 핵심은 서명한 사람 이외의 사람이 읽을 순 있지만 복사(위조) 할 수 없다는 데 있다.

• 디지털 서명의 실제 목적은?
  • 종이 서명에서는 여러분이 상대방에게 보낼 내용에 서명을 하지만, 디지털 서명에서는 상대방이 여러분에게 내용을 보내기 전에 서명한다.
  • 사람들이 잘 인식하지 못하는 이유는 컴퓨터가 디지털 서명을 자동으로 확인하기 때문이다.
• RSA의 보안
  • 모든 디지털 서명 체계의 보안 문제는 ‘적이 내 서명을 위조할 수 있는가?’ 라는 질문으로 압축된다.
  • RSA 체계는 엄청나게 큰 시계 크기를 쓴다는 데 있다. (수천자리에 이름) 현존하는 컴퓨터 중 가장 빠른 컴퓨터조차 모든 가능한 자물쇠 값을 시도해 보는 데 수조 년이 걸린다.
• 실제 디지털 서명
  • 일부 컴퓨터에 정통한 사용자는 이메일 메시지 같은 곳에 서명을 하지만 대부분은 다운로드한 내용을 검증할 때 디지털 서명을 주로 사용한다.
  • 서명은 다른 메세지로 전환될 수 없으므로, 이를 그냥 복사한다고 해서 위조할 수 있는것은 아니다.

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

미래에 아무리 많은 기발한 알고리즘이 개발되더라도 ‘컴퓨터로 해결할 수 없는’ 문제는 늘 존재 할 것이다. 이 장은 간단한 정리로 마무리한다. 책의 예시를 다 적을순 없으므로…

• 버그, 충돌, 소프트웨어의 신뢰성
  • 어떠한 소프트웨어 검사 도구라도 ‘모든’ 프로그램에 잠재해 있는 충돌을 ‘모두’ 검출하는 일은 불가능하다는 것을 증명할 수 있다.
  • 모든 충돌을 검출하는 프로그램은 존재할 수 없다는 사실을 귀류법으로 증명할 수 있다.