컴퓨팅의 정수

옮긴이 머리말 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