목차
1. 서문 = 1
1.1 소개 = 1
1.2 알고리즘이란? = 2
1.3 프로그램을 위한 표기법 = 6
1.4 수학적 표기법 = 8
1.4.1 제안된 계산 = 8
1.4.2 집합론 = 8
1.4.3 정수 실수와 간격 = 9
1.4.4 함수와 관계 = 10
1.4.5 기호 = 11
1.4.6 합과 곱 = 12
1.4.7 기타 = 13
1.5 증명 방법 1 - 반증법 = 14
1.6 증명 방법 2 - 수학적 귀납법 = 18
1.6.1 수학적 귀납법의 원리 = 21
1.6.2 다른 색깔의 말 = 26
1.6.3 정규화된 수학적 귀납법 = 28
1.6.4 구조적 귀납법 = 31
1.7 그 외의 것들 = 35
1.7.1 극한 = 36
1.7.2 등차, 등비 급수 = 39
1.7.3 기본 조합론 = 45
1.7.4 기초 확률 = 48
1.8 연습문제 = 57
2. 기본적 알고리즘 = 67
2.1 소개 = 67
2.2 문제와 사례 = 68
2.3 알고리즘의 효율성 = 69
2.4 평균과 최악의 경우 분석 = 72
2.5 기본적인 연산이란 무엇인가? = 75
2.6 왜 효율성을 구해야 하는가? = 78
2.7 예제 = 80
2.7.1 행렬식 계산 = 80
2.7.2 정렬 = 81
2.7.3 큰 정수의 곱셈 = 83
2.7.4 최대 공약수 계산 = 84
2.7.5 Fibonacci 수열 계산 = 85
2.7.6 Fourier 변형 = 87
2.8 알고리즘은 언제 상술되는가 = 88
2.9 연습문제 = 89
3. 점근 표기법 = 95
3.1 소개 = 95
3.2 "순서" 표기법 = 96
3.3 다른 점근 표기법 = 102
3.4 조건 점근 표기법 = 106
3.5 여러 매개변수들의 점근 표기법 = 109
3.6 점근 표기법의 연산 = 110
3.7 연습문제 = 112
4. 알고리즘 분석 = 119
4.1 소개 = 119
4.2 제어구조 분석 = 119
4.2.1 순차 = 120
4.2.2 "For" 루프 = 120
4.2.3 재귀적 호출 = 123
4.2.4 "while"과 "repeat" 루프 = 124
4.3 바로미터(barometer) 사용하기 = 126
4.4 보충 예제 = 129
4.5 평균 분석 = 134
4.6 양도 분석 = 136
4.7 재귀함수 계산법 = 141
4.7.1 지능적인 추측 계산 = 141
4.7.2 동차 재귀함수 계산 = 144
4.7.3 동차수가 아닌 재귀함수 계산 = 150
4.7.4 변수 변경 = 158
4.7.5 범위 전환 계산 = 166
4.7.6 점근적 재귀함수 계산 = 168
4.8 연습문제 = 171
5 자료 구조 = 181
5.1 배열, 스택과 큐 = 181
5.2 레코드와 포인터 = 185
5.3 리스트 = 186
5.4 그래프 = 187
5.5 트리 = 189
5.6 조합 테이블 = 195
5.7 힙(Heap) 구조 = 198
5.8 이항 힙 = 207
5.9 분리된 집합 구조 = 212
5.10 연습문제 = 220
6. Greedy 알고리즘 = 227
6.1 구성 변화(1) = 227
6.2 Greedy 알고리즘의 일반적인 특성 = 228
6.3 그래프 : 최소 신장 트리 = 230
6.3.1 Kruskal 알고리즘 = 233
6.3.2 Prim 알고리즘 = 236
6.4 그래프 : 최단 경로 = 261
6.5 Knapsack 문제(1) = 239
6.6 스케줄링 = 243
6.6.1 시스템내의 최소시간 = 246
6.6.2 제한된 시간을 갖는 스케줄링 = 249
6.7 연습문제 = 257
7. 분할 해결법 = 261
7.1 소개 : 큰 정수의 곱셈 = 261
7.2 일반적 형태 = 265
7.3 이진 탐색 = 269
7.4 정렬 = 271
7.4.1 합병에 의한 정렬 = 271
7.4.2 퀵 정렬 = 274
7.5 중간값 찾기 = 280
7.6 행렬 곱셈 = 285
7.7 지수화 = 287
7.8 모든 방법의 적용 : 암호법의 소개 = 292
7.9 연습문제 = 295
8. 동적 프로그래밍 = 305
8.1 두 개의 간단한 예 = 306
8.1.1 이항계수 계산 = 306
8.1.2 월드 시리즈 = 307
8.2 잔돈바꾸기(2) = 309
8.3 최적의 원리 = 312
8.4 배낭문제(2) = 313
8.5 최단경로 = 316
8.6 행렬 곱셈 연결 = 319
8.7 재귀적 호출을 사용한 접근 = 324
8.8 메모리 함수 = 326
8.9 연습문제 = 328
9. 탐색 그래프 = 337
9.1 그래프와 게임 소개 = 337
9.2 방문 트리 = 344
9.2.1 선행조건 = 345
9.3 깊이 우선 검색 : 무방향 그래프 = 347
9.3.1 관절점 = 350
9.4 깊이 우선 검색 : 방향 그래프 = 353
9.4.1 비순환 그래프 : 위상 정렬 = 354
9.5 너비 우선 검색 = 356
9.6 역추적 = 361
9.6.1 배낭문제(3) = 362
9.6.2 8 여왕 문제 = 364
9.6.3 일반적인 형태 = 368
9.7 분기-경계 방법 = 368
9.7.1 할당 문제 = 369
9.7.2 배낭문제(4) = 373
9.7.3 일반적인 고려사항 = 374
9.8 minmax 원리 = 374
9.9 연습문제 = 378
10. 확률적 알고리즘 = 387
10.1 소개 = 387
10.2 불확실성을 함축하지 않는 확률 = 388
10.3 기대 시간과 평균 시간 = 390
10.4 Pseudorandom 발생기 = 391
10.5 수치 확률적 알고리즘 = 393
10.5.1 버펀의 바늘 = 393
10.5.2 수치 적분법 = 397
10.5.3 확률 계산 = 399
10.6 Monte Carlo 알고리즘 = 401
10.6.1 행렬 곱셈의 증명 = 402
10.6.2 Primality 검사 = 405
10.6.3 한 임의의 수가 솟수일 확률은 = 410
10.6.4 확률적 잇점의 증대 = 412
10.7 Las Vegas 알고리즘 = 416
10.7.1 재방문되는 8 여왕 문제 = 419
10.7.2 확률적 선택 정렬 = 423
10.7.3 범용 해싱 = 425
10.7.4 큰 정수의 인수분해 = 427
10.8 연습문제 = 433
11. 병렬 알고리즘 = 443
11.1 병렬 연산을 위한 모델 = 444
11.2 기본 기법들 = 446
11.2.1 완전한 이진 트리 연산 = 446
11.2.2 포인터 더블링 = 448
11.3 작업과 효율 = 452
11.4 그래프 이론에서의 두 가지 예 = 455
11.4.1 최단 경로 = 455
11.4.2 연결 요소 = 456
11.5 병렬 표현의 계산 = 462
11.6 병렬 정렬 네트워크 = 467
11.6.1 제로-원 법칙 = 469
11.6.2 병렬 병합 네트워크 = 470
11.6.3 향상된 정렬 네트워크 = 472
11.7 병렬 정렬 = 473
11.7.1 예비 단계 = 474
11.7.2 주요 개념 = 475
11.7.3 알고리즘 = 476
11.7.4 상세한 기술 = 477
11.8 EREW와 CREW p-ram의 관점 = 478
11.9 분산 계산법 = 479
11.10 연습문제 = 481
12. 계산 복잡도 = 485
12.1 소개 : 간단한 예 = 486
12.2 정보-이론 논의 = 487
12.2.1 정렬 복잡도 = 491
12.2.2 알고리즘 재사용에 관한 복잡도 = 494
12.3 반대 논의 = 497
12.3.1 배열의 최대값 발견 = 498
12.3.2 그래프 연결성 검사 = 499
12.3.3 중위 재방문 = 500
12.4 선형 귀납법 = 502
12.4.1 일반적인 정의 = 505
12.4.2 행렬 문제에 따른 감소 = 508
12.4.3 최소 경로 문제에 따른 감소 = 514
12.5 NP-완전에 관한 개요 = 518
12.5.1 P와 NP 분류 = 519
12.5.2 다항식 감소 = 523
12.5.3 NP-완전 문제 = 529
12.5.4 NP-완전성 증명 = 533
12.5.5 NP-hard 문제 = 538
12.5.6 비결정 알고리즘 = 539
12.6 복잡도 분류 집합 = 542
12.7 연습문제 = 547
13. 경험적 근사 알고리즘 = 557
13.1 경험적 알고리즘 = 558
13.1.1 그래프 색칠 문제 = 558
13.1.2 방문판매원 순회 문제 = 561
13.2 근사 알고리즘 = 562
13.2.1 미터법 방문판매원 순회 문제 = 562
13.2.2 Knapsack 문제(5) = 565
13.2.3 Bin packing = 567
13.3 NP.hard 근사 알고리즘 = 570
13.3.1 어려운 절대적 근사 문제 = 571
13.3.2 어려운 연관적 근사 문제 = 573
13.4 같은점과 다른점 = 575
13.5 근사 스키마 = 580
13.5.1 Bin packing 재방문 = 580
13.5.2 Knapsack 문제(6) = 581
13.6 연습문제 = 585
참고문헌 = 591
