컴퓨팅의 정수

옮긴이 머리말 ix
베타리더 후기 xii
추천사 I xiv
추천사 II xviii
시작하며 xxi
이 책에 대하여 xxix

CHAPTER 0 컴퓨팅의 본질: 기계 운동에서 전자 운동으로 1
0.1 컴퓨터란 무엇인가? 1
0.2 기계식 컴퓨터, 불 대수와 스위칭 회로 4
0.3 튜링 기계, 컴퓨팅의 본질은 기계 운동 12
0.4 인공지능의 한계 17
0.5 마무리 20

CHAPTER 1 작지만 큰 차이: Big O 개념 21
1.1 알고리즘의 정규화와 정량화 21
1.2 컴퓨팅에서의 차수적 차이 25
1.3 최적의 알고리즘을 찾는 방법 30
1.4 정렬에 관한 논의 40
__1.4.1 직관적인 정렬 알고리즘은 어디에서 시간을 낭비할까? 41
__1.4.2 효과적인 정렬 알고리즘 효율성은 어디에서 올까? 43
__1.4.3 특정한 경우에서 더 나은 알고리즘이 있을까? 48
1.5 마무리 51
부록: 정렬 알고리즘 복잡도가 O(NlogN)보다 작아질 수 없는 이유 52

CHAPTER 2 역방향 사고: 순환에서 재귀로 53
2.1 재귀: 컴퓨팅 사고의 핵심 53
__2.1.1 간단해 보이는 순환적 사고 공식 55
__2.1.2 하노이의 탑과 구련환: 재귀로 표현되는 문제 57
__2.1.3 가우스조차 해결하지 못한 여덟 개 퀸 문제 61
2.2 순회: 재귀적 사고의 전형적 응용 63
__2.2.1 이진 트리와 그 순회 65
__2.2.2 재귀를 사용한 이진 트리 순회 구현 68
2.3 스택과 큐: 순회의 데이터 구조 71
2.4 중첩: 자연어의 구조적 특징 76
2.5 마무리 81
부록1: 피보나치 수열의 재귀 공식 유도 82
부록2: 여덟 퀸 문제 알고리즘의 의사 코드 84
부록3: 임의의 트리를 이진 트리로 변환하기 85

CHAPTER 3 모든 것이 코드다: 추상화와 표현 86
3.1 인간과 컴퓨터 사이의 정보 인코딩의 차이점 87
3.2 황금 분할 문제와 실험 쥐 문제 91
3.3 데이터 표현: 정밀도와 범위 96
3.4 비선형 코딩과 차등 코딩 100
3.5 허프먼 코드 102
3.6 행렬의 효과적인 표현 107
3.7 마무리 114
부록1: 100층 건물에서 두 개의 유리 공으로 파손 높이를 테스트하는 최적의 방법 115
부록2: 허프먼 코딩의 유효성 증명 115

CHAPTER 4 지능의 본질: 분류와 조합 116
4.1 문제는 선택 분류 116
4.2 정보의 구성: 집합과 판단 120
__4.2.1 의사결정 트리 121
__4.2.2 해시 테이블 124
4.3 B+ 트리, B* 트리: 데이터베이스의 데이터를 구성하는 방식 127
4.4 카탈랑 수 132
4.5 마무리 139
부록1: 집합의 열 가지 공리 140
부록2: 카탈랑 수의 재귀 공식 도출 141

CHAPTER 5 도구와 알고리즘: 그래프 이론 및 응용 142
5.1 그래프 본질: 점과 선 143
5.2 그래프 접근: 순회와 연결성 148
5.3 웹 크롤러 구축의 개발자 문제 151
5.4 동적 계획법: 최단 경로를 찾는 효과적인 방법 154
5.5 최대 흐름: 트래픽 문제 해결 방법 161
5.6 최대 매칭: 흐름 문제의 확장 169
5.7 마무리 173
부록1: 그래프의 깊이 우선 순회 알고리즘 173
부록2: 그래프의 너비 우선 순회 알고리즘 174
부록3: 동적 계획법을 사용한 최단 거리를 계산하는 의사 코드 174
부록4: 최대 흐름 알고리즘 의사 코드 175

CHAPTER 6 복잡함의 단순화: 분할 정복법 응용 176
6.1 분할 정복: O(N2)에서 O(NlogN)으로 177
6.2 분할 알고리즘: 퀵 정렬과 중앙값 문제 186
6.3 병렬에 대한 토론: 행렬 곱셈과 맵리듀스 197
6.4 머신러닝에서 딥러닝까지: 구글 브레인 203
6.5 마무리 209

CHAPTER 7 공간과 시간의 균형: 스토리지의 이해 211
7.1 액세스: 순차 vs. 임의 213
7.2 메모리 계층: 용량 vs. 속도 225
__7.2.1 CPU 캐시에서 클라우드 스토리지까지 226
__7.2.2 두 가지 실제 사례 231
7.3 인덱스: 주소 vs. 내용 234
7.4 마무리 237
부록: x&(x?1)를 사용하여 x에 포함된 1의 수를 세는 방법 238

CHAPTER 8 병렬과 직렬: 파이프라인과 분산 컴퓨팅 239
8.1 파이프라이닝: 논리적 직렬 및 물리적 병렬 처리 239
8.2 무어의 법칙의 두 분수령 242
8.3 클라우드 컴퓨팅 이해하기: GFS와 맵리듀스 244
8.4 마무리 252

CHAPTER 9 상태와 과정: 등가성과 인과관계 254
9.1 문제에서 상태로 255
9.2 등가성: 상태를 추상화하는 도구 261
9.3 인과관계: 상태 간의 연결 설정 266
9.4 마무리 272

CHAPTER 10 결정론적 알고리즘과 확률: 확률론적 알고리즘과 응용 273
10.1 데이터 지문: 무작위성으로 확정한다 274
10.2 무작위성과 양자 통신 278
10.3 신뢰수준: 비용과 효과의 균형 282
10.4 마무리 288

CHAPTER 11 이론과 실습: 전형적인 문제 풀이 289
11.1 가장 긴 연속 부분 수열 문제 289
11.2 구간 병합 문제 294
11.3 열두 개의 공 문제 296
11.4 스카이라인 문제 302
11.5 가장 긴 회문 문제 307
11.6 계산기 문제 314
11.7 검색 결과 요약 문제 317
11.8 합이 k인 부분 수열을 찾는 문제 324
11.9 마무리 327

찾아보기 329

역사를 보면 때때로 사유가 시공을 초월하는 천재, 예를 들어 뉴턴과 아인슈타인 같은 인물이 등장한다. 컴퓨터 분야도 마찬가지인데, 바로 ‘컴퓨터 과학의 아버지’라고 불리는 튜링이다. 튜링은 컴퓨터를 연구하는 사람들에게 신과 같은 존재다. 전 세계에서 지능으로 아인슈타인과 동등하게 위치할 수 있는 사람은 튜링과 폰 노이만뿐일 것이다(폰 노이만의 지능은 아인슈타인을 능가한다고 여겨진다).

동일한 문제에 다른 알고리즘을 사용할 때 알고리즘 간의 효율성 차이는 매우 클 수 있다. IT 업계 종사자의 작업 중 많은 부분은 프로그래밍에서 더욱 효율적인 알고리즘을 찾는 것이다. 물론 다양한 알고리즘이 다양한 규모의 문제를 처리할 때 효율성은 각각 다르다. 알고리즘의 효율성을 측정할 때는 문제 규모가 매우 크고 거의 무한하다고 가정한다. 그리고 계산량과 문제 크기 N 사이의 상관관계를 찾는다. 컴퓨터 과학에서 관심을 가져야 하는 것은 구체적인 계산 함수가 아니라 상한선이다. 이 상한선은 수학에서 함수의 상한 개념, 즉 Big O의 개념이다.