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

1. 검색엔진

• 매칭과 랭킹

• 인덱싱

  • 인덱싱

  • 단어 위치 트릭

    • 위치(근접성) 과 랭킹

  • 메타워드 트릭

• 페이지 랭크

  • 하이퍼링크 트릭
  • 권위 트릭
  • 무작위 서퍼 트릭
  • 웹 스팸, 링크 기반 랭킹 알고리즘

2. 공개키 암호화

• 공유비밀

• 덧셈 트릭

• 디피-헬먼 키

  • 페인트 혼합 트릭

  • 공개키 알고리즘

    • 개인 수, 공개 수
    • 공개 - 개인수 (PPN)

3. 오류 정정 코드

• 검출과 정정

• 반복 트릭

• 리던던시 트릭

  • 심벌 - 코드워드 (해밍 코드)

• 체크섬 트릭

• 핀포인트 트릭 (이차원 패리티)

4. 패턴인식과 인공지능

• 인접이웃 트릭 (KNN)
• 스무고개 트릭 (의사결정 나무)
• 인공 신경망 (ANN)

5. 데이터 압축

• 무손실 압축과 손실 압축

• 무손실 압축

  • 런-렝스 인코딩
  • 전과 같음 트릭
  • 더 짧은 심벌 트릭

• 손실 압축

  • 생략 트릭

    • JPEG 생략 기법

6. 데이터베이스

• 트랜잭션과 할 일 목록 트릭

  • 미리쓰기 로그 (Write Ahead Log, WAL)
  • 일관성과 원자성
  • 잠금 (Lock)
  • 준비 후 커밋 트릭 (2단계 커밋 프로토콜)

• 관계형 데이터베이스

7. 디지털 서명

• 디지털 서명의 목적

• 종이 서명

• 좌물쇠 서명

• 곱셈 자물쇠로 서명하기

  • 메시지, 좌물쇠, 시계크기, 키

• 지수 좌물쇠로 서명하기

• RSA

  • 인수분해와의 관계
  • 양자 컴퓨터와의 관계

• 실제 디지털 서명

  • 인증 기관

8. 계산 가능성과 결정 불가능성

• 버그, 충돌, 소프트웨어의 신뢰성

• 존재할 수 없는 프로그램

  • 다른 프로그램을 분석하는 프로그램
  • 귀류법

• 충돌 찾기의 불가능성

• 정지 문제

• 불가능한 프로그램이 주는 함의

  • 컴퓨터 사용
  • 인간의 뇌

 

코멘트

굉장히 굉장히 잘 읽었다. 4학년이 되고, 취업할 때가 되니, 그래도 전공생으로서 유명한 알고리즘들 정도는 교양으로라도 알아야겠다는 생각이 들었다. 그래서 학과 사무실에서 자기 전에 침대 위에서 읽어볼 수 있을만한 책 하나를 골랐는데, 원래 후보로 두었던 책들보다, 이 책이 끌려서 읽게 되었다.

정말로 '교양' 수준 답게 너무 무겁지 않게 주제를 설명해주며, 무엇보다 전문적인 용어가 아닌 누구나 쉽게 이해할만한 단어들로 알고리즘들을 설명한게 놀랍다. 단지 전공생의 교양이 아닌, 비전공자도 충분히 읽히기 쉽게 쓰인 책이다.

컴퓨터과학이라는 학문은, 다른 공학 영역과보다 '논리' 로 시작해 '해결' 을 내기 때문에, 애초에 무언가를 '정의' 하는 것 자체가 굉장히 추상적이다. 그러면서도, 논리를 쌓아올리는 ,이를테면 수학이나 철학과는 다르게, 메모리와 수행시간이라는 물리적 조건을 고려해야하기 때문에, 굉장히 어려운 학문이다. 따라서 이런 문제해결에 앞서 설명해야할 기초 지식들이란 너무 많고, 그래서 비전공자들은 본격적인 알고리즘에 앞서, 초반 진입장벽이 높다고 느낄 수 있다.

그런데 이 책은, 그런 것을 최소화 하고, '문제'의 맥락부터 차근차근 설명해준다. 이를테면 디지털 세계에서 '공개키'가 왜 필요한지, 오류검출, 정정이 왜 필요한지부터 설명해준다. 그리고, 이 문제를 어떻게 해결해나갈 것인지, 가장 간단한 방법부터 설명한다. 이후, 이 방법의 문제점은 무엇인지, 그에 대한 해결책으로 그 다음 방법을 또 소개한다. 그런데 이 모든 설명이 충분히 이해되도록 재차 말해주고, 적절한 예시와 비유를 들어서 설명해준다는 것이다. 그런점이 참 마음에 들었다.

문제를 해결해나간다는 것은, 참 재미있다. 그것은 '아이디어' 에서 시작하여, 수학, 논리적으로 구상한 후, 실제 현실의 문제를 '해결' 한다. 그리고 이 해결이 단지 수학문제를 푸는 것으로 끝나는 것이 아닌, 사회의 다른 부분들에 엄청난 영향을 끼친다면, 그 보람과 자부심은 참 클 것 같다. 컴퓨터 사이언티스트들이 바로 그 역할을 하는 사람들이다.

이 쪽은 워낙 천재들의 영역이라고 들어, 내가 직업으로 삼을 영역은 아니지만, 그래도 이 천재들의 아이디어와 해결방법을 쉽게 이해할 수 있는 것, 그리고 재미를 느끼는 것은 또 다른 것이다. 컴퓨터 사이언스의 매력을 충분히 늘낄 수 있게 해주는 책이었다.