The Art of Computer Programming 4(양장본 Hardcover)

이 책이 제시하는 핵심 내용

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



이 책의 특징과 장점

? 도널드 커누스 교수의 필생에 걸친 역작, 『The Art of Computer Programming』 시리즈 제4권의 첫 번째(A권) 책.

? 4A는 여러 조합적 알고리즘들의 기초를 닦는 책이다. 조합적 알고리즘들 전반을 간단히 소개한 후에는 부울 논리와 비트 단위 연산들을 설명하고, 그 다음으로는 열거를 설명한다. 열거는 어떠한 집합이나 대상(문제에 대한 해 공간 등)에서 얻을 수 있는 순열이나 조합 등을 체계적으로 '나열'하는 것인데 이는 4B, 4C에서 다룰 역추적(모든 문제를 풀 수 있다고 하는 강력한 기법)이나 그래프 같은 좀 더 구체적인 기법들의 기초가 된다.

? 이 책의 최신 정보 및 도서 인터넷 페이지

http://www-cs-faculty.stanford.edu/~knuth/taocp.html



? 이 책과 시리즈의 다른 책들에 대한 좀 더 자세한 정보는 커누스 교수의 개인 홈페이지에서 볼 수 있다.

www.cs-faculty.stanford.edu/~knuth



어떤 독자를 위한 책인가?

-. 알고리즘 관련 전공 학부생, 대학원생, 연구원

-. 『The Art of Computer Programming 1 ~3권』 독자



도서 특징(책 표지 글)



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



이 시리즈는 전통적인 전산학에 대한 궁극의 설명서로 널리 받아들여지고 있다. 처음 세 권은 수십 년간 프로그래밍 이론에 대한 매우 귀중한 자료이자 학생, 연구자, 실무자 모두를 위한 실습서 역할을 해왔다.

셀 수 없이 많은 독자들이 커누스의 저서가 자신에게 미친 영향력을 밝혔다. 과학자들은 그의 분석의 아름다움과 우아함에 경탄했으며, 보통의 프로그래머들은 그의 "요리책" 해법들을 자신의 현실 업무에 성공적으로 적용했다. 그들 모두는 이 책들에서 볼 수 있는 너비, 명확함, 정확함, 그리고 명랑한 유머 때문에 커누스를 존경한다.

이 책들은 기본적으로는 참고서로 저술된 것이지만, 각 권을 처음부터 끝까지 차례로 읽는 것이 가능하고 재미있다는 점을 발견한 사람들도 있다. 중국의 한 프로그래머는 시를 읽는 경험에 비교했을 정도이다.

독자의 경력이 어떠하든, 컴퓨터 프로그래밍으로 뭔가 진지한 일을 하는 사람이라면 이 시리즈의 각 권을 언제라도 뽑아볼 수 있도록 독자의 학술 또는 전문 라이브러리에 포함시킬 만한 좋은 이유를 찾을 수 있을 것이다.



20년 이상이 지나서 처음으로 도널드 커누스 교수는 1, 2, 3권을 이 분야의 최근 발전을 반영해서 갱신했다. 그의 갱신은 특히 마지막 판의 출판 이후 지식이 통합된 분야와 풀린 문제들, 그리고 변한 문제들에 집중되어 있다. 이 책들의 권위적 특징을 유지함과 동시에, 이전 성과에 대한 모든 역사적 정보도 필요에 따라 갱신되었다. 공들인 완벽함에 대한 저자의 명성에 걸맞게, 명민하고 적극적인 독자들이 발견한 드문 기술적 오류들도 모두 정정되었다. 학습 욕구를 더욱 높일 수 있도록 수백 개의 새로운 연습문제들이 추가되었다.



제4권은 조합적 알고리즘이라는 방대하고도 중요한 분야를 다룬다. 제4권의 첫 번째 책인 제4A권에서 저자는 부울 연산과 필수적인 비트 조작 기법들을 설명한 후 조합적 생성(순열, 분할, 트리 같은 근본적인 조합적 대상들을 모두 나열하는 것)의 세계로 독자를 인도한다. 한 권에 담지 못할 정도로 많은 주제와 결과 중 가장 중심적이고 중요한 것을 세심히 선택해서 직관적이고도 간명하게 제시하는 이 책에는 역사적 참고사항과 다른 책에서는 찾을 수 없는 수백 개의 유용한 사실들도 수록되어 있다. 이 제4A권이 모든 진지한 프로그래머의 서재에서 이전의 세 권과 어깨를 나란히 할 것은 명백한 일이다.



추천사



모든 기본적 알고리즘들의 바이블. 오늘날의 수많은 소프트웨어 개발자들은 컴퓨터 프로그래밍의 대부분을 이 책에서 배웠다. ＿Byte, 1995년 9월



이들 작품들이 나에게 얼마나 많은 시간 동안 연구와 재창조의 기쁨의 여유를 주었는지, 말로는 표현할 수 없다! 차 속에서 식당에서 근무 중에 집에서... 심지어는 내 아들이 라인-업에 들지 않았던 리틀 리그게임에서조차도 이들 작품에 몰두하였다. ＿Charles Long



여러분이 정말로 훌륭한 프로그래머라고 생각한다면... 『The Art of Computer Programming』을 읽으세요... 만일 전체를 다 읽을 수 있다면 꼭 저에게 이력서를 보내시길. ＿Bill Gates



책장에서 커누스의 책들을 뽑아야 할 만큼 어려운 문제를 만나는 것은 언제라도 즐거운 일이다. 그냥 책을 펼치기만 해도 컴퓨터가 지레 겁을 먹고 굴복하는 효과를 본 적도 있다. ＿Jonathan Laventhol



[한국 독자에게]

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



관련도서

-. 『The Art of Computer Programming 1 컴퓨터 프로그래밍의 예술: 기초 알고리즘』(2006)

-. 『The Art of Computer Programming 2 컴퓨터 프로그래밍의 예술: 준수차적 알고리즘(개정 3판)』(2007)

-. 『The Art of Computer Programming 3 컴퓨터 프로그래밍의 예술: 정렬과 검색(개정 2판)』(2008)

제 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 - 조합 문제 찾아보기

__찾아보기 및 용어집

도널드 커누스 저자 도널드 커누스는 알고리즘 및 프로그래밍 기법에 대한 선구자적 성과로, 컴퓨터 조판을 위한 TEX 및 시스템의 고안으로, 그리고 영향력 큰 다작으로(책 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를 받았다. 그는 아내 질과 함께 Stanford 교정에서 살고 있다.