컴퓨터 프로그래밍의 기술

The Art of Computer Programming
컴퓨터 프로그래밍의 기술
ArtOfComputerProgramming.svg
컴퓨터 프로그래밍의 기술, 제1권: 기본 알고리즘
작가.도널드 크누스
나라미국
언어영어
장르.논픽션
모노그래프
출판인애디슨 웨슬리
발행일자
1968 - (이 책은 아직 미완성)
미디어 타입인쇄(하드커버)
ISBN0-201-03801-3
519
LC ClassQA76.75

The Art of Computer Programming(TAOCP)은 프로그래밍 알고리즘과 그 분석을 컴퓨터 과학자인 Donald Knuth가 작성한 포괄적인 논문입니다.볼륨 1~5는 순차적 기계에 대한 컴퓨터 프로그래밍의 중심 코어를 나타내기 위한 것입니다.

Knuth는 원래 12장으로 구성된 하나의 책으로 구상된 이 프로젝트를 1962년에 시작했다.당시 7권 세트로 예상되었던 첫 세 권은 1968년, 1969년, 1973년에 출판되었다.1973년 제4권에서 본격적으로 작업이 시작되었지만, 1977년 제2권 제2판에 의해 조판 작업이 중단되었다.4A권 최종본은 2001년에 손으로 쓰기 시작했고 2001년 후반에 [1]첫 번째 온라인 프리 파시클인 2A가 등장했습니다.제4권의 첫 번째 출판물은 2005년에 페이퍼백에 파시클 2로 실렸다.제4권 파시클 0-4권을 결합한 하드백 제4A권은 2011년에 출판되었다.2015년 12월 제4권 파시클 6(만족도), 제4권 파시클 5(수학예비판 리덕스, 역추적, 댄싱 링크)가 2019년 11월 출시됐다.

4B권은 5장과 6장으로 구성될 것으로 예상된다.이 원고는 2022년 8월 1일에 출판사에 보내졌고, 출판은 2022년 10월에 있을 예정이다.[2] [3] 2022년 [4]8월 3일, 4C권으로 계획된 파시클 7이 크누스의 강연 주제였다.

역사

2005년 도널드 크누스

웨스팅하우스 탤런트 서치 장학금을 받은 후, Knuth는 Case Institute of Technology(현재의 Case Western Reserve University)에 등록했습니다.그곳에서 그의 업적은 매우 뛰어났기 때문에, Knuth는 학사 학위를 수료하면 그에게 이학 석사 학위를 수여하기로 투표했습니다.여름 방학 동안, Knuth는 Burroughs Corporation에 의해 컴파일러를 쓰기 위해 고용되었고, 그의 여름 몇 달 동안 전체 교수들이 1년 [5]동안 벌었던 것보다 더 많은 돈을 벌었다.이러한 업적은 리처드 S.를 포함한 수학과에서 크누스를 토론의 주제로 만들었다. 바르가

1962년 1월 칼텍 수학부 대학원생 때 애디슨 웨슬리로부터 컴파일러 설계에 관한 책을 써달라는 연락을 받고 더 넓은 범위를 제안했다.그는 같은 날 12개의 챕터 타이틀 목록을 작성했다.1962년 여름, 그는 UNIVAC용 FORTRAN 컴파일러에서 일했다.이 기간 동안, 그는 또한 선형 탐사에 대한 수학적 분석을 생각해 냈고, 이것은 그가 재료를 정량적 접근으로 제시하도록 설득했습니다.1963년 6월에 박사학위를 받은 후, 그는 원고를 쓰기 시작했고, 1965년 6월에 그의 첫 번째 초고를 3000장의 손으로 쓴 페이지에 [6]완성했다.그는 손으로 쓴 약 5페이지가 인쇄된 한 페이지로 번역될 것이라고 생각했지만, 그의 출판사는 대신 그것에 대해 말했다.1+1⁄2의 손으로 쓴 페이지를 1매의 인쇄 페이지로 변환.이것은 그가 약 2000장의 인쇄된 자료를 가지고 있다는 것을 의미했고, 이것은 처음 출판된 세 권의 크기와 거의 일치했다.출판사는 대학원생으로부터 그런 프로젝트를 받아들이는 것에 대해 긴장했다.이때 크누스는 리처드 S.의 지원을 받았다.Varga, 그는 출판사의 과학 고문이었다.Varga는 Caltech에 있는 Olga Taussky-Todd와 John Todd를 방문하고 있었다.바르가의 열렬한 지지로 출판사는 크누스의 확장된 계획을 받아들였다.확대판에서는, 이 책은 7권으로 나누어 출판될 것이며, 각 권은 단지 한두 [7]장으로 구성되어 있다.1965년 원고의 100페이지 미만이었던 제7장의 성장으로 인해 제4권의 계획은 제4A권, 제4B권, 제4C권, 제4D권 등으로 확대되었다.

1976년 Knuth는 제2권 제2판을 준비하여 다시 조판할 것을 요구하였으나, 제1판 (핫 활자라 불림)에 사용된 활자 스타일은 더 이상 이용할 수 없었다.1977년, 그는 좀 더 적합한 무언가를 만드는데 시간을 보내기로 결심했다.8년 후, 그는 현재 모든 볼륨에 사용되고 있는 TX를 가지고E 돌아왔다.

발견된 오류에 대해 "1 16진수 달러"(100 base 16센트, 10진수로는 2.56달러)의HEX 보상 수표를 제안하고, 이후 인쇄에서 이러한 오류를 수정함으로써, 첫 번째 출판 이후 오랜 시간 동안 이 작품의 고도로 다듬어지고 여전히 권위 있는 성격에 기여했습니다.책의 또 다른 특징은 연습의 난이도의 변화이다.Knuth는 0부터 50까지 다양하며, 여기서 0은 사소한 것이고 50은 현대 [8]연구에서 열린 질문이다.

Knuth의 헌신은 다음과 같습니다.

이 일련의 책들은 애정 어린 헌정입니다
타입 650 컴퓨터에 접속할 수 있습니다.
케이스 인스티튜트 오브 테크놀로지
나는 그들과 많은 즐거운 [a]밤을 보냈다.

책의 어셈블리 언어

이 책의 모든 예는 가상의 MIX 컴퓨터에서 실행되는 "MIX 어셈블리 언어"라고 불리는 언어를 사용합니다.현재 MIX 컴퓨터는 RISC 버전인 MMIX 컴퓨터로 교체 중입니다.GNU MDK 등의 소프트웨어는 MIX 아키텍처의 에뮬레이션을 제공하기 위해 존재합니다.Knuth는 알고리즘의 속도와 메모리 사용량을 판단하기 위해 필요한 어셈블리 언어의 사용을 고려하고 있습니다.

비판적 대응

Knuth는 "알고리즘의 분석에 대한 그의 주요한 공헌, 특히 이 [9]제목으로 연속되는 그의 잘 알려진 책을 통해 '컴퓨터 프로그래밍의 예술'에 기여한 공로로 1974년 튜링상을 수상했다."American Scientist는 이 연구를 [10]20세기를 지칭하는 "과학의 세기를 형성한 100여 권의 책"에 포함시켰으며, 컴퓨터 과학계에서는 이 책이 그 [failed verification]주제에 대한 최초의 그리고 여전히 최고의 포괄적인 논문으로 여겨지고 있다.제1권 제3판 표지에는 빌 게이츠가 다음과 같이 인용하고 있습니다.만약 당신이 정말 훌륭한 프로그래머라고 생각한다면 컴퓨터 프로그래밍 기술을 읽어보세요.모든 [11]것을 읽을 수 있다면 이력서를 꼭 보내 주세요.뉴욕타임즈는 그것을 "직업이 정의하는 논문"[12]이라고 언급했다.

볼륨

완료된

  • 제1권 – 기본 알고리즘
    • 1장 – 기본 개념
    • 제2장 – 정보 구조
  • 제2권 – 세미컨슈머 알고리즘
  • 제3권 – 정렬 및 검색
  • Volume 4A – 조합 알고리즘
    • 7장 – 조합 검색 (파트 1)
  • Volume 4B – 조합 알고리즘
    • 7장 – 조합 검색 (파트 2)

계획된

이 장의 개요

완료된

제1권 – 기본 알고리즘

  • 1장 – 기본 개념
  • 제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진수 트리 표현
      • 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. 역사와 참고 문헌

제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.6 다항식 산술
      • 4.6.1 다항식의 나눗셈
      • 4.6.2 다항식의 인수분해
      • 4.6.3 파워의 평가(가산 사슬의 지수화)
      • 4.6.4 다항식의 평가
    • 4.7. 멱급수의 조작

제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 세컨더리 키에서의 취득

Volume 4A – 조합 알고리즘, 파트 1

  • 7장 – 조합 검색
    • 7.1. 0과 1
    • 7.2. 모든 가능성 창출
      • 7.2.1. 기본 조합 패턴 생성
        • 7.2.1.1. 모든 n개의 튜플 생성
        • 7.2.1.2.모든 순열 생성
        • 7.2.1.3.모든 조합 생성
        • 7.2.1.4.모든 파티션 생성
        • 7.2.1.5.설정된 모든 파티션 생성
        • 7.2.1.6. 모든 나무 생성
        • 7.2.1.7.이력 및 추가 참조

Volume 4B – 조합 알고리즘, 파트 2

  • 7장 - 조합 검색(계속)

계획된

Volume 4C, 4D – 조합 알고리즘

제5권 – 구문 알고리즘

제6권 – 문맥이 없는[13] 언어의 이론

7권 – 컴파일러 기술

영문판

최신판

볼륨 번호에 따른 최신 버전은 다음과 같습니다.

  • 컴퓨터 프로그래밍의 예술, 1-4A권 박스 세트.제3판 (매사추세츠 주, 레딩:Adison-Wesley, 2011), 3168pp.ISBN 978-0-321-75104-1, 0-321-75104-3
  • The Art of Computer Programming, Volume 1-4B 박스 세트 (매사추세츠, 읽기:애디슨-웨슬리, 2023년), 3904pp.ISBN978-0-13-793510-9, 0-13-793510-2(표시 예정)
  • 제1권, 패시클 1: MMIX – 새천년을 위한 RISC 컴퓨터. (Addison-Wesley, 2005-02-14) ISBN 0-201-85392-2.Errata: [11] (2020-03-16) (제4판 볼륨1에 수록 예정)
  • 제4권, 파시클5: 수학예비단축, 백트랙, 댄싱링크(Addison-Wesley, 2019-11-22) 13+382pp, ISBN 978-0-13-467179-6.에러타: [12] (2020-03-27) (볼륨 4B의 일부)
  • 제4권 파시클 6: 만족도 (Addison-Wesley, 2015-12-08) xii+310pp, ISBN 978-0-13-439760-3.에라타: [13] (2020-03-26) (볼륨 4B의 일부)

구판

전체 볼륨

이러한 볼륨은 새 버전으로 대체되었으며 날짜별로 정렬되어 있습니다.

파시클스

제4권의 제0-4권은 개정되어 제4A권으로 발행되었다.

  • 제4권 파시클 0: 조합 알고리즘과 부울 함수 소개 (Addison-Wesley Professional, 2008-04-28) vi+240pp, ISBN 0-321-53496-4.에라타: [17] (2011-01-01)
  • 제4권 패시클1: 비트의 요령과 테크닉; 2진 결정도 (Addison-Wesley Professional, 2009-03-27) vii+260pp, ISBN 0-321-58050-8.에라타: [18] (2011-01-01)
  • 제4권 파시클2: 모든 튜플과 순열의 생성(Addison-Wesley, 2005-02-14) v+127pp, ISBN 0-201-85393-0.에라타: [19](2011-01-01)
  • 제4권 파시클3: 모든 조합과 파티션 생성 (Addison-Wesley, 2005-07-26) vi+150pp, ISBN 0-201-85394-9.에라타: [20](2011-01-01)
  • 제4권 파시클 4: 모든 나무의 생성; 조합 생성의 역사. (Addison-Wesley, 2006-02-06) vi+120pp, ISBN 0-321-33570-8.에라타 : [21] (2011-01-01)

제4권의 제5-6절은 제4B권의 일부가 된다.

  • 제4권, 파시클5: 수학예비단축, 백트랙, 댄싱링크(Addison-Wesley, 2019-11-22) 13+382pp, ISBN 978-0-13-467179-6.에라타: [22] (2020-03-27)
  • 제4권 파시클 6: 만족도 (Addison-Wesley, 2015-12-08) xii+310pp, ISBN 978-0-13-439760-3.에라타: [23] (2020-03-26)

파시클 전

제4권의 파시클 5A, 5B 및 5C는 개정되어 파시클 5로 발행되었다.

제4권의 파시클 6A는 개정되어 파시클 6으로 출판되었다.

「 」를 참조해 주세요.

레퍼런스

메모들

  1. ^ 헌신은 초판에서는 약간 다르게 표현되었다.

인용문

  1. ^ "note for box 3, folder 1".
  2. ^ "Addison-Wesley Pearson webpage".
  3. ^ "Pearson InformIT webpage".
  4. ^ "CP 2022 All Questions Answered, July 31–August 5, 2022, Haifa, Israel".
  5. ^ Frana, Philip L. (2001-11-08). "An Interview with Donald E. Knuth". hdl:11299/107413.
  6. ^ 도날드 크누스, 금주의 인용 클래식, 현재 목차, 34번(1993년 8월 23일), 8페이지.
  7. ^ Albers, Donald J. (2008). "Donald Knuth". In Albers, Donald J.; Alexanderson, Gerald L. (eds.). Mathematical People: Profiles and Interviews (2 ed.). A K Peters. ISBN 978-1-56881-340-0.
  8. ^ "Reflections on a year of reading Knuth". infinitepartitions.com. Retrieved 2020-07-25. I worked, or at least attempted to work, every single problem in the first volume. In some cases I settled for just understanding what the question was trying to ask for. In some cases I failed even to accomplish that (don't judge me until you try it yourself). Each problem is assigned a difficulty rating from 0-50 where 0 is trivial and 50 is "unsolved research problem" (in the first edition, Fermat's last theorem was listed as a 50, but since Andrew Wiles proved it, it's bumped down to a 45 in the current edition). I think I was able to solve most of the problems rated < 20 — it was hit and miss beyond that. Most of the problems fell into the 20-30 difficulty range, but Knuth's idea of "difficult" is subjective, and problems that he considers to be of average difficulty ended up stretching my comparatively tiny brain painfully. I've never climbed Mount Everest, but I imagine the whole ordeal feels similar: painful while you're going through it, but triumphant when you reach the pinnacle.
  9. ^ "Donald E. Knuth – A. M. Turing Award Winner". AM Turing. Retrieved 2017-01-25.
  10. ^ Morrison, Philip; Morrison, Phylis (November–December 1999). "100 or so Books that shaped a Century of Science". American Scientist. Sigma Xi, The Scientific Research Society. 87 (6). Archived from the original on 2008-08-20. Retrieved 2008-01-11.
  11. ^ Weinberger, Matt. "Bill Gates once said 'definitely send me a résumé' if you finish this fiendishly difficult book". Business Insider. Retrieved 2016-06-13.
  12. ^ Lohr, Steve (2001-12-17). "Frances E. Holberton, 84, Early Computer Programmer". The New York Times. Retrieved 2010-05-17.
  13. ^ "TAOCP – Future plans".
  14. ^ a b Wells, Mark B. (1973). "Review: The Art of Computer Programming, Volume 1. Fundamental Algorithms and Volume 2. Seminumerical Algorithms by Donald E. Knuth" (PDF). Bulletin of the American Mathematical Society. 79 (3): 501–509. doi:10.1090/s0002-9904-1973-13173-8.

원천

외부 링크