서적소개 – THE ART OF COMPUTER PROGRAMMING : 컴퓨터 프로그래밍의 예술 전4권 (도널드 커누스 / 한빛미디어 / 2008~13)

서적소개

THE ART OF COMPUTER PROGRAMMING : 컴퓨터 프로그래밍의 예술 (전4권)

도널드 커누스 / 한빛미디어 / 2008~13

• 수십년 동안 중요하게 남을 만한 고전적 기법들의 정수

컴퓨터 프로그래밍을 사랑하는 한국의 모든 이에게 진심으로 인사드립니다! 전산학이 끊임없이 사람들을 맺어주는 전 세계적인 분야라는 점을 행복하게 생각합니다. 이 시리즈에 남아 있는 오류를 제거하는 데 수년간 많은 한국 독자들이 저를 도와주었습니다. 새 번역서가 더 많은 사람들을 신비에 싸인 이 분야에 발을 들여놓게 하는 데, 그리고 이 분야를 더욱 발전시키는 데 도움이 되길 희망합니다. — 도널드 커누스 Donald E. Knuth, 高德納

여러분이 정말로 훌륭한 프로그래머라고 생각한다면 … 커누스의 『The art of computer programming (컴퓨터 프로그래밍의 예술)』을 읽으세요 … 만일 전체를 다 읽을 수 있다면 꼭 저에게 이력서를 보내시길. — 빌 게이츠 (Bill Gates)

○ 목차

• The art of computer programming 1: 기초 알고리즘

제 1 장 – 기본 개념
1.1. 알고리즘
1.2. 수학적 기초
1.2.1. 수학적 귀납법
1.2.2. 수, 거듭제곱, 로그
1.2.3. 합과 곱
1.2.4. 정수 함수와 초등 수론
1.2.5. 순열과 계승
1.2.6. 이항계수
1.2.7. 조화수
1.2.8. 피보나치 수
1.2.9. 생성함수
1.2.10. 알고리즘 분석
*1.2.11. 점근적 표현
*1.2.11.1. 표기법
*1.2.11.2. 오일러의 합 공식
*1.2.11.3. 몇 가지 점근 계산
1.3. MIX
1.3.1. MIX 설명
1.3.2. MIX 어셈블리 언어
1.3.3. 순열 응용
1.4. 몇 가지 기본적인 프로그래밍 기법들
1.4.1. 서브루틴
1.4.2. 코루틴
1.4.3. 해석 루틴
1.4.3.1. MIX 시뮬레이터
*1.4.3.2. 추적 루틴
1.4.4. 입력과 출력
1.4.5. 역사 및 문헌 정보

제 2 장 – 정보 구조
2.1. 소개
2.2. 선형 목록
2.2.1. 스택, 대기열, 큐
2.2.2. 순차 할당
2.2.3. 연결된 할당
2.2.4. 순환 목록
2.2.5. 이중으로 연결된 목록
2.2.6. 배열과 직교 목록
2.3. 트리
2.3.1. 이진트리의 운행
2.3.2. 트리의 이진트리 표현
2.3.3. 트리의 다른 표현들
2.3.4. 트리의 기본적인 수학적 성질들
2.3.4.1. 자유 트리
2.3.4.2. 유향 트리
*2.3.4.3. 무한대 보조정리
*2.3.4.4. 트리 열거하기
2.3.4.5. 경로 길이
*2.3.4.6. 역사 및 문헌정보
2.3.5. 리스트와 쓰레기 수거
2.4. 다중연결 구조
2.5. 동적인 저장소 할당
2.6. 역사 및 문헌정보

연습문제 해답

부록 A – 수량표
1 동적인 저장소 할당
2 동적인 저장소 할당
3 동적인 저장소 할당

부록 B – 표기법 일람

찾아보기

• The art of computer programming 2: 준수치적 알고리즘

제 3 장 – 난수
3.1. 소개
3.2. 균등 난수 생성
3.2.1. 선형합동법
3.2.1.1. 법의 선택
3.2.1.2. 곱수의 선택
3.2.1.3. 농도
3.2.2. 다른 방법들
3.3. 통계적 검정
3.3.1. 무작위 자료의 연구를 위한 일반적인 검정 절차
3.3.2. 경험적 검정
*3.3.3. 이론적 검정
3.3.4. 스펙트럼 검정
3.4. 다른 종류의 무작위 수량들
3.4.1. 수치분포
3.4.2. 무작위 표본추출 및 뒤섞기
*3.5. 난수열이란?
3.6. 요약

제 4 장 – 산술
4.1. 위수치체계
4.2. 부동소수점 산술
4.2.1. 단정도 계산
4.2.2. 부동소수점 산술의 정확도
*4.2.3. 배정도 계산
4.2.4. 부동소수점 수의 분포
4.3. 다중 정밀도 산술
4.3.1. 고전적 알고리즘
*4.3.2. 나머지식 산술
*4.3.3. 곱셈을 어느 정도까지 빠르게 할 수 있을까?
4.4. 기수 변환
4.5. 유리수 산술
4.5.1. 분수
4.5.2. 최대공약수
*4.5.3. 유클리드 알고리즘의 분석
4.5.4. 소인수분해
4.6. 다항식 산술
4.6.1. 다항식 나눗셈
*4.6.2. 다항식의 인수분해
4.6.3. 거듭제곱의 평가
4.6.4. 다항식의 평가
*4.7. 멱급수 다루기

연습문제 해답
부록 A – 수량표
1 기본적인 상수들(10진)
2 기본적인 상수들(8진)
3 조화수, 베르누이수, 피보나치수 값들
부록 B – 표기법 일람
찾아보기 및 용어집

• The art of computer programming 3: 정렬과 검색

제 5 장 – 정렬
5.1. 순열의 조합 성질
5.1.1. 반전
5.1.2. 중복집합의 순열
5.1.3. 연속열
5.1.4. 타블로와 대합
5.2. 내부 정렬
5.2.1. 삽입을 이용한 정렬
5.2.2. 교환에 의한 정렬
5.2.3. 선택에 의한 정렬
5.2.4. 병합에 의한 정렬
5.2.5. 배분에 의한 정렬
5.3. 최적 정렬
5.3.1. 최소비교 정렬
5.3.2. 최소비교 병합
5.3.3. 최소비교 선택
5.3.4. 정렬을 위한 회로망
5.4. 외부 정렬
5.4.1. 다중 병합과 치환 선택
5.4.2. 다중페이즈 병합
5.4.3. 중첩 병합
5.4.4. 테이프 거꾸로 읽기
5.4.5. 진동 정렬
5.4.6. 테이프 병합에 대한 현실적인 고려사항들
5.4.7. 외부 기수 정렬
5.4.8. 2테이프 정렬
5.4.9. 디스크와 드럼
5.5. 요약, 역사, 문헌정보

제 6 장 – 검색
6.1. 순차 검색
6.2. 키 비교에 의한 검색
6.2.1. 정렬된 표의 검색
6.2.2. 이진트리 검색
6.2.3. 균형 트리
6.2.4. 다중 트리
6.3. 숫자별 검색
6.4. 해싱
6.5. 2차키에 의한 조회

연습문제 해답

부록 A – 수량표

1. 기본적인 상수들(10진)
2. 기본적인 상수들(8진)
3. 조화수, 베르누이수, 피보나치수 값들
   부록 B – 표기법 일람
   찾아보기 및 용어집

• The Art of Computer Programming 4 : 조합적 알고리즘 1부 – 알고리즘의 고전을 읽는다

제 7 장 – 조합적 검색
7.1. 0과 1
7.1.1. 부울 연산의 기초
7.1.2. 부울 함수의 평가
7.1.3. 비트별 요령과 기법
7.1.4. 이진 결정도
7.2. 모든 가능성의 생성
7.2.1. 기본적인 조합 패턴 생성
7.2.1.1. 모든 ?짝의 생성
7.2.1.2. 모든 순열의 생성
7.2.1.3. 모든 조합의 생성
7.2.1.4. 모든 분할의 생성
7.2.1.5. 모든 집합 분할의 생성
7.2.1.6. 모든 트리의 생성
7.2.1.7. 역사 및 추가 참고문헌
연습문제 해답
부록 A – 수량표

1. 기본적인 상수들(십진)
2. 기본적인 상수들(16진)
3. 조화수. 베르누이 수, 피보나치 수 값들
   부록 B – 표기법 일람
   부록 C – 알고리즘 및 정리 찾아보기
   부록 D – 조합 문제 찾아보기
   찾아보기 및 용어집

○ 저자소개 : 도널드 커누스

도널드 커누스 (Donald E. Knuth)는 알고리즘 및 프로그래밍 기법에 대한 선구자적 성과로, 컴퓨터 조판을 위한 TeX 및 METAFONT 시스템의 고안으로, 그리고 영향력 큰 다작으로 (책 19권, 논문 160편) 전 세계적으로 유명한 학자이다.

Stanford University의 컴퓨터 프로그래밍의 예술 명예 교수 (Emeritus of The Art of Computer Programming)인 그는, California Institute of Technology의 대학원생이었던 1962년에 시작한 전통적 전산학에 대한 독창적인 7권짜리 이 시리즈의 완성에 현재 그의 모든 시간을 투여하고 있다.

커누스 교수는 ACM Turing Award, 카터 전 미대통령이 수여한 Medal of Science, AMS Steele Prize 해설문 부문 등 수많은 상과 표창을 수상했다.

최근 1996년 11월에는 고등 기술에 대한 권위있는 Kyoto Prize를 받았다.

그는 아내 질 (Jill)과 함께 Stanford 교정에서 살고 있다.

– 역자: 류광

옮긴이 류광은 1996년부터 활동해온 프로그래밍 서적 전문 번역가이다.
『Game Programming Gems』 시리즈를 비롯한 게임 프로그래밍 서적 다수와 『Code Reading : 오픈 소스 관점에서 본 코드 읽기』,『일반적 프로그래밍과 STL』,『서브버전을 이용한 실용적인 버전 관리』등 다양한 분야의 프로그래밍 서적 다수를 번역했으며 Bjarne Stroustrup의 고전『The C++ Programming Language』의 한국어판 (곽용재 역) 감수 작업에도 참여했다.

2006년부터 2008년까지 Knuth 교수의 역작 『The Art of Computer Programming』 시리즈 전권 (1, 2, 3, 4A)을 번역했다.
번역과 프로그래밍 외에 소프트웨어 문서화에도 많은 관심을 가지고 있으며, 수많은 오픈소스 프로젝트들의 표준 문서화 형식으로 쓰이는 DocBook의 국내 사용자 모임인 닥북 한국 (http://docbook.or.kr/)의 일원이다.

현재 번역서 정보 사이트 “occam’s Razor” (http://occam.com.ne.kr/)와 Game Programming Gems 스터디 사이트 “GPGstudy.com” (http://gpgstudy.com/)을 운영하고 있다.

○ 책 속으로

• The art of computer programming 1: 기초 알고리즘 – 수십년 동안 중요하게 남을 만한 고전적 기법들의 정수

시리즈의 첫 권인 이 책은 기본적인 프로그래밍 개념과 기법으로 시작해서 정보 구조, 다시 말해서 컴퓨터 안에서의 정보 표현, 자료 요소들 사이의 구조적 관계, 그리고 그것들의 효율적인 처리에 초점을 둔다. 시뮬레이션, 수치적 방법, 기호 처리, 소프트웨어 및 시스템 설계에 대한 기본적인 응용들도 제공한다. 이전 판에 비해 수십 개의 간단하고도 중요한 알고리즘 및 기법들이 추가되었다. 기본적인 수학에 대한 섹션은 최근 연구 동향에 맞도록 크게 개정되었다.

• The art of computer programming 2: 준수치적 알고리즘 – 컴퓨터가 ‘수’를 다루는 최상의 방법

이 책은 알고리즘을 좀더 깊게 파고들 필요가 있는 독자를 위해 여러 권으로 이루어진 시리즈 도서 중 두번째 책이다. 2권에서는 컴퓨터가 수를 다루는 최상의 방법을 어떻게 찾는지를 다루고 있다. 1권처럼 대학 교재뿐만 아니라 독학도 가능하도록 충분한 연습문제를 제공하고 있어 배운 내용을 빠짐없이 복습하고 응용해볼 수 있다.

• The art of computer programming 3: 정렬과 검색 – 정렬과 검색을 통한 이상적인 알고리즘의 발견

이 책은 다른 기본적인 구조적 착안들에 선형 순서 자료의 개념을 더하는 것이므로, 제1권 제2장의 정보 과학 내용과 관련해서, 그 자연스러운 속편에 해당한다. “정렬과 검색”이라는 제목 때문에, 이 책을 범용 정렬 루틴이나 정보 조회를 위한 응용프로그램에 관계되는 시스템 프로그래머들만을 위한 책으로 오해할 수도 있으나 사실 이 책에서 다루는 내용은 다음과 같은 다양한 종류의 주요 주제들에 대한 이상적인 틀을 제공한다.
좋은 알고리즘은 어떻게 발견되는가? 알고리즘과 프로그램을 개선하려면?
알고리즘의 효율을 수학적으로 분석하려면? 같은 과제를 위한 서로 다른 알고리즘들 중 적절한 것을 합리적으로 선택하려면?
어떤 의미 하에서 알고리즘이 “가능한 최고”임을 증명할 수 있는가? 컴퓨팅 이론이 현실의 고려사항들과 어떻게 연동되는가?
_커다란 데이터베이스를 위해 테이프, 드럼, 디스크 같은 외부 기억장치들을 효율적으로 사용하려면?

• The Art of Computer Programming 4 : 조합적 알고리즘 1부 – 알고리즘의 고전을 읽는다

4A에서는 조합적 알고리즘을 다룬다. 조합적 알고리즘은 서로 구분되는 항목들의 일부를 선택해서 조합하거나 특정 순서로 나열하는 것에 관련된 것으로, 2권의 수치 알고리즘이나 3권의 정렬, 검색과 함께 수많은 자료구조와 개별 알고리즘들 (문자열 관련 등등)의 기반에 해당한다.

○ 출판사 서평

“알고리즘 도서 중 최고의 고전 The Art of Computer Programming 전권 출간 기념 이벤트!
The Art of Computer Programming : 컴퓨터 프로그래밍의 예술 특별판 (전3권) 300권 한정 판매”

• The art of computer programming 1: 기초 알고리즘

이 책은 알고리즘을 좀더 깊게 파고들 필요가 있는 독자를 위해 여러 권으로 이루어진 시리즈 도서 중 첫번째 책이다. 그렇기 때문에 모든 알고리즘의 수학적 원리를 아주 상세하게 기술하고 있다.
또한, 대학 교재뿐만 아니라 독학도 가능하도록 충분한 연습문제를 제공하고 있어 배운 내용을 빠짐없이 복습하고 응용해볼 수 있다.

• The art of computer programming 2: 준수치적 알고리즘

이 책은 알고리즘을 좀더 깊게 파고들 필요가 있는 독자를 위해 여러 권으로 이루어진 시리즈 도서 중 두번째 책이다. 2권에서는 컴퓨터가 수를 다루는 최상의 방법을 어떻게 찾는지를 다루고 있다. 1권처럼 대학 교재뿐만 아니라 독학도 가능하도록 충분한 연습문제를 제공하고 있어 배운 내용을 빠짐없이 복습하고 응용해볼 수 있다.

• The art of computer programming 3: 정렬과 검색

이 책은 알고리즘을 좀더 깊게 파고들 필요가 있는 독자를 위해 여러 권으로 이루어진 시리즈 도서 중 세번째 책이다. 3권에서는 정렬과 검색이라는 특정 분야의 알고리즘을 다루지만 독자는 이를 통해서 좋은 알고리즘을 어떻게 발견하고 프로그램을 개선하며 효율을 수학적으로 어떻게 분석할 수 있는지 등에 대해 배울 수 있다.

• The Art of Computer Programming 4 : 조합적 알고리즘 1부 – 알고리즘의 고전을 읽는다

4A에서는 조합적 알고리즘을 다룬다. 조합적 알고리즘은 서로 구분되는 항목들의 일부를 선택해서 조합하거나 특정 순서로 나열하는 것에 관련된 것으로, 2권의 수치 알고리즘이나 3권의 정렬, 검색과 함께 수많은 자료구조와 개별 알고리즘들 (문자열 관련 등등)의 기반에 해당한다.

크리스천라이프 편집부