다운로드 

프로그래밍의 예술. "프로그래밍의 예술" - 전설적인 책 시리즈에 대한 리뷰

2011년 12월 27일 오후 01:32

프로그래밍의 예술?

  • 프로그램 작성

나는 코드 한 줄도 없는 프로그래밍에 관한 기사를 읽는 것을 좋아합니다. 이러한 기사는 "심층적으로" 발전하는 데 적합하며 종종 오랫동안 확립된 내용을 다른 각도에서 볼 이유를 제공합니다. 따라서 이미 성장이 둔화된 나의 카르마에 대해 대중의 특정 부분의 분노를 불러일으킬 위험을 무릅쓰고 그럼에도 불구하고 나는 이 기사를 출판하기로 결정했습니다. 이 기사가 누군가에게 생각할 거리를 제공할 뿐만 아니라 그들의 활동을 새롭게 살펴보세요.

시작

현재 직장에서 프로그래머는 자신의 장치에 맡겨져 있습니다. 즉, 물론 그들은 기업의 이익을 위해 코딩하지만 평범한 테스터가 없을 정도로 완전히 통제할 수 없습니다. "무거운" 프로그램의 경우에도 참조 조건은 A4 용지 3장을 초과하는 경우가 거의 없습니다(그 중 하나는 관련된 모든 사람의 서명입니다).

소프트웨어 문제에 관한 전화는 프로그래머에게 직접 전송됩니다. 이 모든 것이 시작된 이래로.

나는 내 동료(나보다 몇 년 동안 자신의 전문 분야에서 이 특정 위치에서 일해 온 사람)에게 전화한 전화 수가 내 소프트웨어에 대한 전화 수보다 (과장 없이) 훨씬 더 많다는 것을 알았습니다. . 동시에 통화는 일반적으로 더 "무거워"집니다. 우리 제품의 보급률과 노동 강도는 거의 같습니다.

소통하는 과정에서 프로그래밍에 대한 동료들의 견해에 관심을 가지게 되었고, 그 후 일부 프로그램의 소스 코드를 살펴보니 모든 것이 정리되었습니다.

창의적인 성격에 관한 Opus

개인적, 사업적 이유로 저는 창의적인 사람들과 소통합니다. 이들은 주로 다양한 장르의 음악가와 예술가입니다. 나는 서식지부터 상점, 카페까지 다양한 환경에서 그들을 자주 방문합니다.

집에서 그러한 사람들은 일반적으로 페인트로 얼룩진 소파와 허름한 벽부터 끔찍해 보이는 가전 제품과 접시에 이르기까지 혼란과 창의적 장애를 가지고 있습니다.

그러한 사람들의 행동에는 특정 벡터가 있지만 그 매개 변수는 부동 소수점 숫자가 아니라 "남남서" 방향으로 지정됩니다. 이는 상점에 가는 것뿐만 아니라(그런 사람들과 함께 목록에서 무언가를 구입하는 것은 단순히 비현실적임) 창의성을 포함한 일반적인 모든 것에 적용됩니다.

작품 작업을 할 때 아티스트/음악가는 일반적으로 바로 이 "남남서 벡터", 즉 특정 분위기, 컨셉(내부적으로 탄생했거나 고객이 발행한 것, 이 경우에는 그다지 중요하지 않음)에서 시작합니다. 대부분의 경우 최종 결과는 매우 모호해 보입니다. 공평하게 말하면, 이것이 창의성의 즐거움 중 가장 큰 몫이라는 점에 주목합니다. 즉, 완료된 대로 수행하는 것입니다. 이것은 본질적으로 "자신을 표현"하려는 시도입니다.

창의적인 프로그래머

프로그래머에 대한 대화로 돌아가 보겠습니다. 대화 중에 일부 동료는 자부심 없이는 자신을 "창의적인 직업"의 대표자라고 말하는 것이 분명해졌습니다. 동시에 그들은 거의 완전한 속성 세트를 갖춘 창의적인 접근 방식(“남남서 벡터”)을 실제로 사용합니다. 결과적으로 완전히 이상한 연결의 모듈이 나타나고, 계층 구조가 있는 클래스가 "여기서 이런 그림을 만들겠습니다", 메소드는 마술처럼 "흥미로운"(잘 설계되고 명확한 오류 처리와 함께 구현)로 나누어집니다. 암호화 및 네트워크 프로토콜) 및 "흥미롭지 않음"(데이터를 내보내는 킬로미터 길이의 목록, 많은 복사-붙여넣기 포함).

오류 처리는 결과에 따라 수행됩니다. 여기서는 반환 값을 확인하고 다음 파일에는 예외 처리 메커니즘이 있습니다. 여기서는 스마트 포인터를 사용하고, 여기서는 직접 작업합니다. 그리고 이와 같은 다른 것들도 많이 있습니다.

이러한 작업의 결과는 동작이 완전히 예측할 수 없는 제품입니다. 우리 개발자 중 한 사람의 주요 문제는 새 버전에서 오류를 수정하면 이미 디버깅된 것처럼 보이는 모듈에 새로운 오류가 지속적으로 나타나며 모든 것을 완전히 다시 작성하지 않고 이를 방지하는 것은 이미 비현실적이라는 것입니다. 이러한 제품을 유지 관리하는 것은 매우 어렵습니다. 가장 기본적인 사항을 개선하려면 모든 것이 무너지지 않도록 수행하는 방법을 이해하기 위해 코드에 대한 장기적인 명상이 필요하며 가급적이면 기존 "창의력을 복사하여 붙여 넣지 않고" ".

이 이야기의 교훈

프로그래밍은 연애를 좋아하는 후배들이 아무리 주장해도 자신의 표현이 아닙니다. 좋은 코드는 명확하게 설계되고 특정 규칙을 따르는 문서입니다. 어떤 사람들에게는 슬프지만 프로그래머는 자신에게 입력된 명령의 품질에 따라 다양한 효율성으로 이러한 단백질 덩어리가 그에게 원하는 것이 무엇인지 다른 로봇에게 설명하는 로봇입니다. 파일 및 변수 이름 지정부터 패턴에 이르기까지 모든 것이 명확한 논리에 따라 최대 효율성을 갖습니다. 결과적으로 이러한 효율성을 위해 프로그래머는 고용주의 돈뿐만 아니라 제품을 유지할 때 마음의 평화를 얻고 프로그램에 문제가 발생할 경우 상황을 통제할 수 있다는 느낌을 받습니다.

프로그래머에게 잘 작성된 기술 사양이 제공되지 않더라도 결국 어떤 일이 일어날지 스스로 명확하게 이해해야 합니다. 작성된 내용을 크게 수정해야 할 가능성이 있다면 훨씬 더 좋습니다. 강력한 수정 가능성이 있는 소프트웨어를 작성하는 작업은 매우 흥미롭고 결코 간단하지 않습니다.

결론적으로 Steve McConnell의 문구는 "당신이 사는 곳을 아는 폭력적인 정신병자가 동행하는 것처럼 코드를 작성하십시오."입니다. 그리고 정신병자는 논리와 질서가 부족하여 머리가 부러지면 아마도 매우 화를 낼 것입니다.

글로벌 컴퓨터 문헌 시장에는 기본 알고리즘을 가르치고 프로그래밍에 사용되도록 고안된 책이 많이 있습니다. 그 수가 꽤 많고 서로 크게 경쟁합니다. 그런데 그 중에 특별한 책이 있다. 이 책은 D. E. Knuth의 3권짜리 "프로그래밍 기술"로, 어떤 경쟁에서도 우위를 점하고 컴퓨터 과학에 관한 세계 문학의 황금 기금에 포함되어 있으며 프로그래밍과 관련된 거의 모든 사람을 위한 참고서입니다.

출판사로서 우리는 이 책이 프로그래밍 기술을 가르치는 것이 아니라 가능하다면 프로그래밍의 "예술"을 가르치고 프로그램을 개선하기 위한 많은 방법을 제공한다는 사실에서 이 책의 가치를 봅니다. , 가장 중요한 것은 이러한 요리법을 직접 찾는 방법을 가르쳐줍니다.

우리 프로그래머가 세계에서 가장 높은 자격을 갖춘 전문가라는 것은 비밀이 아닙니다. 그들은 컴퓨터 과학의 기본 기반 형성에 지대한 공헌을 한 국내 프로그래밍 및 컴퓨터 과학 학교를 해외에서 대표합니다. 이 수준을 유지하고 앞으로 나아가려면 이 분야의 주요 세계 성과를 반영하는 러시아어 서적을 시기적절하게 출판해야 합니다. D. E. Knuth가 쓴 3권짜리 "The Art of 프로그래밍"이 그러한 책 중 하나입니다.

우리는 이 고전 책이 프로그래머, 교사, 학생, 고등학생 및 기타 많은 사람들의 도서관에 추가될 것이며 이를 통해 컴퓨터 과학의 기초에 대한 더 깊은 이해에 기여할 것이라는 점을 자랑스럽게 생각합니다. 우리는 D. E. Knuth가 쓴 "The Art of 프로그래밍"이라는 책이 사람을 완벽에 더 가깝게 만들 수 있다고 깊이 확신합니다. 우리는 이 훌륭한 책을 러시아어로 출판함으로써 진정한 가치가 수년이 지나도 구식이 되지 않는다는 점을 다시 한 번 확인하게 되기를 바랍니다.

- Victor Shtonda, Gennady Petrikovets, Alexey Orlovich, 출판사

"프로그래밍의 예술"이라는 책에 대해

각 책에는 고유한 운명이 있습니다. 일부는 눈에 띄지 않게 나타나고 시간이 지남에 따라 눈에 띄지 않게 사라져 도서관 선반의 먼지로 뒤덮입니다. 다른 사람들은 새로운 참고 도서로 대체될 때까지 좁은 범위의 전문가들 사이에서 일정 기간 동안 수요가 있습니다. 또 다른 것들은 시간을 초월하여 사회의 기술 발전에 강력한 영향을 미칩니다. 후자의 범주에 속하는 책은 그리 많지 않습니다. 세상에 그들의 모습은 항상 휴일입니다. 몇 년이 지나고 기술은 변하지만 새로운 세대는 끊임없는 관심을 가지고 자신의 페이지를 다시 읽습니다. 유명한 미국 과학자 도널드 어윈 크누스(Donald Erwin Knuth)가 독자들에게 제공한 여러 권의 작품인 "프로그래밍의 예술"을 포함하는 것이 바로 이 책들입니다.

이 책이 1972년 미국에서 처음 출판된 지 거의 30년이 지났습니다. 러시아어를 포함한 세계 대부분의 언어로 번역되었습니다. 현재까지 CIS 국가에서는 D. E. Knuth의 3권짜리 작품이 서지적으로 희귀해졌습니다. 1998년에 "The Art of 프로그래밍"의 세 번째 판이 미국에서 출판되었습니다. 이 판은 이전 버전의 자료 제시 순서를 유지하지만 최신의 가장 중요한 결과를 포함하는 참고 문헌 목록이 크게 확장되었습니다. , 새로운 연습과 설명이 추가되었으며 부정확한 내용이 제거되었습니다. 전 세계적으로 "프로그래밍의 기술"의 인기를 고려할 때, 우리는 여러분이 손에 쥐고 있는 새로운 러시아어 번역판의 등장을 오랫동안 기대했어야 했습니다.

D. E. Knuth의 "프로그래밍의 기술"의 성공은 무엇입니까?

첫째, 이 책은 컴퓨터 알고리즘의 설계와 분석에 관한 훌륭한 교과서입니다. 해당 섹션은 프로그래밍 기술, 알고리즘 이론 및 이산 수학에 대한 많은 대학 과정에 포함될 수 있습니다. 이 책은 프로그래밍의 기초에 익숙한 고등학생도 읽을 수 있습니다. 저자는 가상의 MIX 범용 컴퓨터의 기계 명령 언어를 녹음 알고리즘의 주요 언어로 선택했습니다. 이를 통해 컴퓨터의 특성을 고려한 최적의 프로그램을 구축할 수 있습니다. MIX 프로그램을 실제 컴퓨터로 전송하거나 고급 언어로 다시 작성하는 것은 특별히 어렵지 않습니다. 프로그램의 논리는 거의 항상 간단한 블록 다이어그램을 사용하여 설명됩니다.

둘째, 이 책에 포함된 엄선된 자료에는 어떤 형태로든 프로그래밍 실습에서 가장 자주 발견되는 알고리즘의 기본 기본 클래스가 포함되어 있습니다.

셋째, D. E. Knuth 책의 성공에 중요한 요소는 표현의 백과사전적 성격이다. 크누스 교수는 문제의 역사적 배경부터 현재 상태까지 추적하는 독특한 능력을 갖고 있습니다. 현대적 맥락에 배치된 옛 거장(고대까지)의 작품에 대한 수많은 참조는 독자에게 과학적 아이디어와 방법의 역사적 발전에 대한 특별한 참여감을 불러일으킵니다.

넷째, 프리젠테이션의 숙달에 주목해야 한다. 이 책은 초보 학생부터 전문 프로그래머까지 광범위한 독자를 대상으로 작성되었습니다. 누구나 자신의 수준에 맞게 컴퓨터 알고리즘을 배우는 데 관심이 있을 것입니다. 재료는 자급 자족합니다. 방법의 본질을 이해하는 데에는 수학의 특별한 분야나 특별한 프로그래밍 기술에 대한 지식이 필요하지 않습니다. 줄거리의 특정 "음악적" 구성을 추적할 수 있습니다(D. E. Knuth는 집에 그가 연주하는 작은 오르간을 가지고 있습니다).

프로그래밍 기술의 성공 요소 목록은 쉽게 계속될 수 있습니다.

이 줄의 저자는 1976년부터 1977년까지 스탠포드 대학에서 인턴십을 하는 동안 Knuth 교수가 강의한 "프로그래밍 기술" 과정을 수강했습니다. 그런 다음 프로그래밍 기술의 알고리즘 기반이 형성되었으며 그 기원은 D. E. Knuth였습니다. 많은 토론과 세미나, 창의적인 아이디어가 있었습니다.

중요한 책은 항상 저자의 운명과 연결되어 있습니다. Donald Erwin Knuth는 1962년에 The Art of 프로그래밍 작업을 시작했습니다. 그것은 오늘날까지 계속됩니다. 그는 많은 계획을 가지고 있습니다. 독자들이 간절히 기다리고 있는 "프로그래밍 기술"의 새로운 권이 곧 출간됩니다.

- 아나톨리 아니시모프 교수

번역 편집기에서

D. E. Knuth가 쓴 "프로그래밍의 기술"이라는 책의 초판이 나온 지 약 25년이 지났습니다. 그럼에도 불구하고 이 책은 구식일 뿐만 아니라 여전히 프로그래밍 기술에 대한 주요 가이드로 남아 있으며, 이 책을 통해 이 기술의 본질과 특징을 이해하는 방법을 배울 수 있습니다.

수년에 걸쳐 1권과 2권의 세 번째 판과 3권의 두 번째 판이 영어로 출판되었습니다. 저자는 여기에 중요한 변경 사항과 중요한 추가 사항을 적용했습니다. 연습 문제의 수가 거의 두 배로 늘었고 이전 버전에 포함된 연습 문제 중 많은 것(특히 그에 대한 답변)이 수정되었다고만 말하면 충분합니다. 많은 장과 섹션이 크게 보완되고 다시 작성되었으며 부정확성과 오타가 수정되었으며 문헌에 대한 수많은 새로운 참고 자료가 추가되었으며 최근 몇 년간의 이론적 결과가 사용되었습니다.

3장은 크게 변형되었으며, 특히 섹션 3.5, 3.6, 섹션 4.5.2, 4.7, 5.1.4, 5.3, 5.4.9, 6.2.2, 6.4, 6.5 등이 크게 변경되었습니다.

당연히 이 책의 새 판이 필요하게 되었습니다.

번역은 1권, 2권 3판과 3권 2판을 바탕으로 작성되었습니다. 또한 저자가 친절하게 제공한 추가 및 수정 사항이 고려되었습니다.

번역할 때 우리는 저자의 스타일, 표기법, 자료 표현 방식을 유지하려고 노력했습니다. 대부분의 경우 러시아어 과학 문헌에 채택된 용어가 사용되었습니다. 필요한 경우 영어로 동등한 내용이 제공되었습니다. 일부 섹션의 복잡성을 포함하여 여러 가지 이유로 The Art of 프로그래밍은 읽기 어려운 책입니다. 책을 이해하기 어렵게 만드는 이유 중 하나는 저자의 표현 스타일입니다. 익숙해지면 훨씬 쉽게 읽을 수 있습니다.

자료가 풍부하기 때문에(상호 연결이 거의 없음) 다양한 개념과 정의가 처음 언급되는 즉시 소개되는 방식으로 책을 구성하는 것은 불가능합니다. 따라서 1장에서는 3권에서 엄격한 정의가 제공되는 개념을 참조 없이 논의할 수 있습니다. 그렇기 때문에 주제 색인의 역할이 매우 중요하며, 이것이 없으면 책을 이해하기가 상당히 어려울 것입니다. 우리는 독자가 제안된 세 권의 장에 포함되지 않은 7장, 8장 및 후속 장에 대한 참조를 발견하더라도 놀라지 않기를 바랍니다. 우리는 저자와 함께 이 책이 곧 출판되기를 바라며, 물론 이 출판물의 연속으로 러시아어 번역에도 즉시 나타날 것입니다.

또한 저자가 항상 사용하는 표준 표기법이 아니라는 점에도 주의를 기울여야 합니다. 정의와 마찬가지로 이러한 명칭은 1권에 나타날 수 있으며 2권에 소개됩니다. 따라서 기호 색인이 없으면 책을 사용하기가 매우 어려울 것입니다. 나는 또한 A가 특정 진술인 항목 [A]에 주목하고 싶습니다. 이 항목은 공식, 때로는 텍스트에서 발견되며 표시기 A와 동일한 값을 나타냅니다.

- V. Kozachenko 교수

머리말

친애하는 독자 여러분! 당신은 손에 책을 들고 있고,

당신이 우리에게 수천 통의 편지로 요청한 것을 출판하기 위해. 우리는 끝없는 수의 요리법을 신중하게 확인하고 다시 확인하고 가장 좋고, 가장 흥미롭고, 가장 완벽한 것을 선택하는 데 수년을 소비해야 했습니다.

이제 의심의 여지 없이 지침을 따르면 이전에 요리한 적이 없더라도 모든 요리가 우리가 했던 것과 동일하게 나올 것이라고 말할 수 있습니다.
- 맥콜의 요리책(1963)

디지털 컴퓨터용 프로그램을 준비하는 과정은 매우 흥미로운 활동입니다. 그리고 요점은 경제적, 과학적 관점에서 그 자체를 정당화한다는 것뿐만 아니라; 또한 창의적인 개인이 음악이나 시를 쓸 때 경험하는 것과 유사한 미적 경험을 불러일으킬 수도 있습니다. 당신은 프로그래머의 기술을 구성하는 다양한 지식과 기술을 독자에게 제공하는 것이 목적인 여러 권으로 구성된 출판물의 첫 번째 볼륨을 손에 쥐고 있습니다.

다음 장에서는 컴퓨터 프로그래밍에 대한 소개가 아닙니다. 귀하는 이미 이 분야에 대한 경험이 있다고 가정합니다. 실제로 독자의 요구 사항은 매우 간단합니다. 그러나 초보 프로그래머가 디지털 컴퓨터가 무엇인지 이해하려면 시간과 연습이 필요합니다. 따라서 독자는 다음을 갖추어야 합니다.

a) 디지털 저장 프로그램 컴퓨터가 작동하는 방식에 대한 어느 정도의 이해 이 경우 전자 장치를 이해할 필요는 없습니다. 가장 중요한 것은 명령이 컴퓨터 메모리에 저장되고 순차적으로 실행되는 방법을 이해하는 것입니다.

b) 컴퓨터가 이해할 수 있는 명확하고 정의된 용어로 문제를 진술할 수 있는 능력(컴퓨터에는 인간 지능이 없으므로 지시받은 대로만 수행하며 그 이상도 그 이하도 아닙니다. 이는 일반적으로 컴퓨터에게 가장 어려운 사실입니다. 초보 사용자가 파악해야 함) ;

c) 루핑(특정 명령어 세트의 반복 실행), 서브루틴 및 인덱스 변수의 사용과 같은 가장 간단한 컴퓨터 기술에 대한 지식

d) "메모리", "레지스터", "비트", "부동 소수점", "오버플로", "소프트웨어"와 같은 일반적인 컴퓨터 용어에 대한 지식 본문에 정의되지 않은 대부분의 용어는 각 권 끝에 있는 색인에 설명되어 있습니다.

이 네 가지 조건은 아마도 하나의 요구 사항으로 결합될 수 있습니다. 독자는 최소한 한 대의 컴퓨터에 대해 최소한 네 가지 프로그램을 작성하고 디버깅한 경험이 있어야 합니다.

나는 이 책들이 여러 가지 다른 목적에 봉사할 수 있는 방식으로 쓰려고 노력했습니다. 첫째, 과학의 여러 중요한 분야의 지식을 한데 모아 놓은 참고 매뉴얼입니다. 둘째, 대학의 프로그래밍이나 컴퓨터 과학에 대한 독학 보조 자료 및 교과서로 사용할 수 있습니다. 이와 관련하여 나는 본문에 많은 연습 문제를 포함시켰고 대부분에 대한 답변을 제공했습니다. 또한, '물을 붓는' 식의 일반적인 추론보다는 사실에 집중하려고 노력했습니다.

3권으로 구성된 이 책은 전문가뿐만 아니라 컴퓨터에 진지한 관심을 갖고 있는 모든 사람을 대상으로 합니다. 본질적으로 나의 주요 목표 중 하나는 다른 분야의 사람들이 프로그래밍 기술에 더 쉽게 접근할 수 있도록 하는 것이었습니다. 일반적으로 이러한 전문가는 컴퓨터를 사용하여 큰 이점을 얻지만 필요한 정보를 검색하는 데 시간을 낭비할 여유가 없습니다. 그 정보의 일부는 여러 기술 저널에 분산되어 있습니다.

이 책의 주제는 '비수치적 분석'으로 정리할 수 있다. 컴퓨터는 일반적으로 방정식의 근 찾기, 수치 보간, 적분 등과 같은 수치 문제를 해결하는 데 사용됩니다. 그러나 3권으로 구성된 이 책에서는 그러한 주제를 다루지 않습니다(과정에서 필요한 경우 제외). 프레젠테이션의). 수치 컴퓨터 프로그래밍은 매우 흥미롭고 빠르게 발전하는 분야입니다.

이 주제에 관해 많은 좋은 책이 저술되었습니다. 그러나 1960년대부터 숫자가 부차적인 역할을 하는 문제를 해결하는 데 컴퓨터가 점점 더 많이 사용되었습니다. 이제 단순히 산술 연산을 수행하는 것이 아니라 결정을 내리는 컴퓨터의 능력이 주목을 받고 있습니다. 숫자가 아닌 문제를 풀 때 덧셈과 뺄셈이 필요할 때도 있지만 곱셈과 나눗셈이 필요한 경우는 거의 없습니다. 그러나 물론, 수치 컴퓨터 프로그래밍에 주로 관여하는 사람이라도 수치 프로그램의 기초를 형성하는 비수치 방법을 배우면 도움이 될 것입니다.

비수치해석 분야의 연구 결과는 여러 기술 저널에 분산되어 있습니다. 나의 목표는 이 방대한 양의 정보로부터 다양한 프로그래밍 상황에 적용할 수 있는 기본적인 기술만을 추출하는 것이었습니다. 나는 선택된 정보를 요약하여 "이론"이라고 부를 수 있는 것에 도달하고 또한 이 이론을 다양한 실제 문제에 적용하는 방법을 보여 주려고 노력했습니다.

물론 '비수치해석'이라는 말은 이 과학 분야에 있어서는 극히 불행한 이름이다. 그것은 주로 다른 개념에 대한 부정만을 포함하고 있기 때문에 성공하지 못합니다. "not"이라는 접두사가 없는 좀 더 의미 있는 용어를 선택하는 것이 훨씬 낫습니다. "정보 처리"라는 이름은 여기에서 논의된 내용보다 더 넓은 영역을 포괄하고 "프로그래밍 방법"은 더 좁은 영역을 포괄합니다. 나는 이 책에서 다루는 주제에 대해 가장 적절한 이름이 알고리즘 분석이라고 생각하며, 이는 "특정 컴퓨터 알고리즘의 속성 이론"으로 해석될 수 있습니다.

The Art of 프로그래밍이라는 제목의 전체 책 세트는 다음과 같은 기본 구조를 가지고 있습니다.

1권. 기본 알고리즘

1장. 기본 개념 2장. 정보 구조

2권. 파생 알고리즘

3장. 난수 4장. 산술

3권. 정렬 및 검색

5장. 정렬 6장. 검색

4권. 조합 알고리즘

7장. 조합 검색 8장. 재귀

5권. 구문 알고리즘

9장. 사전식 검색 10장. 구문 분석

4권은 매우 광범위한 주제를 다루므로 실제로는 세 권의 별도 책(4A권, 4B권, 4C권)으로 구성됩니다. 보다 전문적인 주제에 대한 두 권의 추가 권도 계획되어 있습니다: 6권, 언어 이론(11장) 및 7권, 컴파일러(12장).

나는 나열된 모든 장을 포함하는 한 권의 책을 집필하려는 의도로 1962년에 이 작업을 시작했지만 곧 선택한 주제를 단지 표면만 훑어보는 것이 아니라 깊이 있게 고려하는 것이 필요하다는 것을 깨달았습니다. 그 결과 각 장의 자료가 대학 한 학기 동안 공부하기에 충분할 정도로 긴 텍스트가 탄생했습니다. 그리고 자료를 여러 권으로 나누어야 한다는 것이 분명해졌습니다. 한두 장만 포함된 책이 다소 이상해 보인다는 것을 알고 있지만, 상호 참조를 더 쉽게 하기 위해 원래 장 번호 매기기를 유지하기로 결정했습니다. 1~5권의 요약본은 학생들을 위한 보다 일반적인 참고 자료 및/또는 교과서로 사용될 계획입니다. 여기에는 이 책의 대부분의 자료가 포함되며 더 전문적인 정보는 생략됩니다. 요약판은 전체판과 동일한 장 번호를 유지합니다.

제1권은 다른 모든 책에서 사용되는 기본 정보를 담고 있다는 점에서 전체 장 세트의 "교차"로 간주될 수 있습니다. 반면에 2~5권은 서로 독립적으로 읽을 수 있습니다. 1권은 다른 권을 읽을 때 참고용으로만 사용되는 참고서가 아닙니다. 또한 데이터 구조(2장에 중점) 또는 이산 수학(1.1, 1.2, 1.3.3 및 2.3.4에 중점) 또는 기계 명령 언어 프로그래밍 주제에 대한 대학 교과서 또는 독학 가이드 역할을 할 수도 있습니다. (섹션 1.3 및 1.4에 중점을 둡니다).

이 장들은 대부분의 최신 프로그래밍 서적과는 다른 관점에서 작성되었습니다. 즉, 독자에게 다른 사람의 소프트웨어를 사용하는 방법을 가르치려고 노력하지 않았습니다. 대신에 나는 독자들에게 자신만의 고품질 프로그램을 작성하는 방법을 가르치는 것을 목표로 삼았습니다.

나의 초기 목표는 독자들에게 다루는 각 지식 분야의 최첨단 과학 연구를 소개하는 것이었습니다. 그러나 경제적으로 수익성이 있는 산업에서 최신 정보를 유지하는 것은 매우 어렵습니다. 컴퓨터 과학의 급속한 성장으로 인해 내 꿈을 실현하는 것이 불가능해졌습니다. 비유적으로 말하면, 나는 전 세계 수만 명의 재능 있는 사람들이 얻은 수만 개의 작은 결과가 담긴 광활한 바다의 해안에 있었습니다. 그래서 저는 새로운 목표를 설정해야 했습니다. 수십 년 동안 관련성이 유지될 "고전적인" 방법에 집중하고 이를 최선을 다해 설명하는 것입니다. 특히, 각 주제의 역사를 추적하고 향후 발전을 위한 탄탄한 기반을 마련하려고 노력했습니다. 나는 현대 출판물에서 사용되는 것과 일치하는 정확한 용어를 사용하려고 노력했으며, 형식의 단순성과 우아함으로 구별되는 모든 알려진 순차 프로그래밍 아이디어를 보고하려고 시도했습니다.

이제 이 여러 권으로 구성된 출판물의 수학적 내용에 대해 몇 마디 하겠습니다. 자료는 중등 교육을 받은 사람도 쉽게 접근할 수 있는 방식으로 제공됩니다. 더 복잡한 조각을 훑어보거나 간단히 건너뛸 수 있습니다. 동시에 수학에 관심이 있는 사람들은 이산수학과 관련된 흥미로운 수학적 기법을 배울 수 있습니다. 정보 표시의 이러한 이중성은 한편으로는 각 연습에 등급을 지정함으로써 달성되었으며(독자가 수학적으로 복잡한 연습을 간단한 연습과 구별할 수 있도록) 다른 한편으로는 이러한 섹션 구성 덕분에 달성되었습니다. 여기서 주요 수학적 결과는 증명 전에 공식화됩니다. 연습으로 직접 증명을 수행하거나(답변은 별도 섹션에 제공됨) 섹션 끝에서 찾는 것이 좋습니다.

수학보다는 프로그래밍에 주로 관심이 있는 독자는 수학 자료가 이해하기 너무 어려워지면 해당 섹션 읽기를 중단할 수도 있습니다. 반면에, 수학 독자는 스스로 많은 흥미로운 사실을 발견하게 될 것입니다. 프로그래밍 주제에 관한 많은 수학 출판물에는 오류가 있었습니다. 따라서 이 책의 목표 중 하나는 독자에게 해당 주제에 대한 올바른 수학적 정당성을 제공하는 것입니다. 그리고 나는 나 자신을 수학자라고 생각하기 때문에, 나의 직접적인 책임은 (가능한 한) 수학적 관점에서 자료를 정확하게 제시하는 것입니다.

대부분의 수학적 자료를 읽으려면 이론의 거의 모든 부분이 여기에서 개발되었으므로 초등 수학에 대한 지식이면 충분합니다. 하지만 때로는 복소변수 이론, 확률론, 수론 등의 더 깊은 정리가 필요할 때도 있습니다. 그런 경우에는 이러한 주제에 대한 자세한 설명이 포함된 책을 참조합니다.

이 책을 준비하면서 제가 내린 가장 어려운 결정은 다양한 방법을 어떻게 제시할 것인가였습니다. 순서도의 이점과 알고리즘의 단계별 설명은 잘 알려져 있습니다. 이러한 문제는 ACM Communications, Vol. 6(1963년 9월), 555-563페이지. 컴퓨터 알고리즘을 설명하려면 형식적이고 정확한 언어도 필요합니다. 그래서 나는 ALGOL이나 FORTRAN과 같은 대수학 언어를 사용할지 아니면 기계 지향 언어를 사용할지 결정해야 했습니다. 오늘날의 많은 컴퓨터 과학자들은 아마도 기계 지향 언어를 사용하기로 한 나의 결정에 동의하지 않을 것입니다. 그러나 나는 그것이 올바른 선택이었다고 확신합니다. 여기에는 다음과 같은 이유가 있습니다.

a) 프로그래머는 프로그램이 작성된 언어에 큰 영향을 받습니다. 현재 컴퓨터에 가장 적합한 언어 구성보다는 가장 단순한 언어 구성을 선택하는 것이 일반적인 경향입니다. 그리고 기계 지향 언어를 아는 프로그래머는 보다 효율적인 방법을 사용하여 더 나은 프로그램을 만드는 경향이 있습니다.

b) 기계 지향 언어로 작성해야 하는 모든 프로그램은 드문 경우를 제외하고는 크기가 작습니다. 이는 처리 능력이 최소인 컴퓨터가 있으면 그러한 프로그램을 사용하는 데 문제가 없음을 의미합니다.

c) 고급 언어는 코루틴 통신, 난수 생성, 고정밀 연산 및 효율적인 메모리 사용과 관련된 기타 여러 문제와 같은 중요한 하위 수준 세부 사항을 논의하는 데 적합하지 않습니다.

d) 컴퓨터에 진지하게 관심이 있는 사람이라면 컴퓨터 작동의 기초가 되는 기계어에 대한 지식이 있어야 합니다.

e) 많은 예제에 제시된 프로그램의 출력을 이해하려면 어떤 경우에도 기계어에 대한 어느 정도의 지식이 필요합니다.

f) 5년 정도마다 새로운 대수학 언어가 유행하고 사라지는 동안 나는 "영원한 진리"에 대해 이야기하려고 합니다.

반면에 고급 언어로 프로그램을 작성하고 이러한 프로그램을 디버깅하는 것이 훨씬 쉽다는 것을 인정합니다. 사실, 1970년 이후 나 자신은 내 프로그램에 저수준 기계어를 거의 사용하지 않았습니다. 현대 컴퓨터는 대용량 메모리와 빠른 속도를 갖추고 있기 때문입니다. 그러나 이 책에서 논의된 많은 문제를 해결하려면 프로그래밍 기술이 가장 중요합니다. 예를 들어 일부 조합 계산은 수조 번 반복해야 하며 내부 루프의 계산 시간을 단 1마이크로초만 줄여 약 11.6일의 작업 시간을 절약할 수 있습니다. 마찬가지로, 특히 프로그램은 한 번만 작성하면 되므로 많은 컴퓨터에서 매일 여러 번 사용되는 프로그램을 작성하는 데 추가적인 노력을 기울이는 것이 합리적입니다.

그리고 기계 지향 언어를 사용하기로 결정했다면 어떤 언어를 선택해야 할까요? 특정 컴퓨터 X에 대한 언어를 선택할 수 있지만 다른 컴퓨터를 사용하는 사람들은 이 책이 컴퓨터 X만을 염두에 두고 작성되었다고 생각할 것입니다. 또한 컴퓨터 X에는 이 책의 내용을 완전히 적용할 수 없는 많은 고유한 기능이 있을 것입니다. , 하지만 여전히 제시해야 합니다. 그리고 마지막으로 2년 안에 기계 X의 제조업체는 기계 X+1이나 10X를 출시할 것이고 누구도 더 이상 컴퓨터 X에 관심을 갖지 않을 것입니다.

이 문제를 해결하기 위해 나는 매우 간단한 작동 규칙(예를 들어 단 한 시간 안에 배울 수 있음)을 갖고 실제 기계와 매우 유사한 "이상적인" 컴퓨터를 개발하려고 노력했습니다. 학생들이 다양한 컴퓨터의 특성을 배우지 않을 이유가 없습니다. 한 언어를 배우고 나면 다른 모든 언어도 훨씬 쉽게 배울 수 있습니다. 또한, 진지한 프로그래머는 작업 과정에서 다양한 기계어를 다룰 준비가 되어 있어야 합니다. 따라서 가상의 기계를 사용하는 데에는 단 하나의 단점이 있습니다. 즉, 해당 기계를 위해 작성된 프로그램을 실행하는 것이 어렵다는 것입니다. 운 좋게도 많은 자원봉사자들이 가상 기계의 시뮬레이터를 작성하기 위해 자원 봉사를 했기 때문에 이것은 실제로 문제가 되지 않습니다. 이러한 시뮬레이터는 교육 목적에 이상적이며 실제 컴퓨터로 작업하는 것보다 작업이 훨씬 쉽습니다.

나는 각 주제에 대한 가장 오래된 논문에 대한 링크를 제공하고 새로운 작업을 언급하려고 노력했습니다. 문헌 출처를 언급할 때, 나는 가장 자주 인용되는 저널을 제외하고는 정기 간행물 제목에 표준 약어를 사용했으며 다음 약어가 사용되었습니다.

CACM - 컴퓨팅 기계 협회 커뮤니케이션

JACM - 컴퓨팅 기계 협회 저널

Sotr. J. - 컴퓨터 저널(영국 컴퓨터 학회)

수학. Sotr. - 계산수학

AMM - 미국 수학 월간

SICOMP - 컴퓨팅에 관한 SIAM 저널

FOCS - 컴퓨터 과학 기초에 관한 IEEE 심포지엄

SODA - 이산 알고리즘에 관한 ACM-SIAM 심포지엄

STOC - 컴퓨팅 이론에 관한 ACM 심포지엄

Crelle - Journal fur die reine und angewandte Mathematik

예를 들어, "CASM 6 (1963), 555-563"은 이 서문의 앞부분에서 참조된 저널을 나타냅니다. 나는 또한 섹션 1.2의 서문에서 언급된 콘크리트 수학(Concrete Mathematics) 책을 참조하기 위해 약어 "CMatA"를 사용했습니다.

이 책에 있는 기술 자료의 대부분은 연습 문제에서 나온 것입니다. 사소한 운동에 대한 아이디어가 내 것이 아니라면 그 저자를 언급하려고했습니다. 문헌에 대한 참조는 일반적으로 해당 섹션의 텍스트나 연습 문제의 답변에 제공됩니다. 그러나 많은 경우 연습은 참조할 수 없는 미출판 자료를 기반으로 합니다.

이 책을 집필하는 동안 많은 분들이 저를 도와주셨고, 진심으로 감사드립니다. 우선, 끝없이 인내심을 갖고 삽화를 준비하며 모든 일에 끊임없는 도움을 준 아내 Jill에게 감사의 마음을 전하고 싶습니다. 또한 1960년대에 이 자료를 개선하고 심화하는 데 많은 시간을 할애한 Floyd Robert W.에게도 감사드립니다. 다른 수천 명의 사람들도 나에게 귀중한 도움을 주었습니다. 단지 그들의 이름을 나열하려면 또 다른 책이 필요할 것입니다! 그들 중 많은 사람들이 친절하게도 그들의 오래되고 출판되지 않은 저작물을 사용할 수 있도록 허락해 주었습니다. Caltech와 Stanford University에서 제가 진행한 연구는 국립과학재단(National Science Foundation)과 해군연구소(Office of Naval Research)의 넉넉한 자금 지원을 받았습니다. Addison-Wesley는 내가 1962년에 프로젝트 작업을 시작한 이래로 매우 도움이 되고 지원을 해왔습니다. 이 모든 사람들에게 최고의 감사는 이 출판물인 것 같습니다. 이는 그들의 기여로 인해 그들이 기대했던 것을 내가 쓸 수 있었던 책이 탄생했음을 보여줍니다.

세 번째 판의 서문

METAFONT 및 TEX 컴퓨터 타이핑 시스템을 개발하는 데 10년을 보냈으며 이제 이러한 시스템을 사용하여 책을 타이핑하려는 꿈을 실현할 수 있습니다. 프로그래밍의 예술. 마침내 나는 이 책의 전문을 개인용 컴퓨터에 입력하여 전자 버전을 얻을 수 있었고, 이를 통해 향후 인쇄 및 화면 디스플레이 기술에 어떤 변경도 가할 수 있게 되었습니다. 이러한 작업 방식을 통해 저는 말 그대로 수천 가지의 개선을 이룰 수 있었습니다. 오랫동안 꿈꿔왔던 것을 이루었습니다.

이 새 판에서 나는 원래 연구의 젊은 열정을 유지하는 동시에 더 성숙한 판단력을 도입하려고 노력하면서 텍스트의 모든 단어를 검토할 수 있었습니다. 수십 개의 새로운 연습이 추가되었으며, 수십 개의 기존 연습에 새롭거나 향상된 답변이 제공되었습니다.

따라서 "The Art of 프로그래밍"이라는 책에 대한 작업이 계속됩니다. 이것이 바로 이 책의 일부 부분이 "공사중" 아이콘으로 시작하는 이유입니다(제공된 데이터가 최신이 아니라는 사실에 대한 일종의 사과입니다). 내 폴더에는 1권의 영광스러운 마지막 4판에 포함할 중요한 자료가 넘쳐납니다. 아마 15년 안에 나올 거예요. 하지만 먼저 4권과 5권을 마무리해야 합니다. 출판할 준비가 되는 대로 출판되기를 바랍니다.

이 새 판을 준비하는 데 있어 많은 노력은 두 번째 판의 텍스트를 전문적으로 입력하고 편집한 Phyllis Winkler와 Silvio Levy, 그리고 거의 모든 원본 삽화를 METAP0ST 형식으로 변환한 Jeffrey Oldham이 수행했습니다. 나는 경고 독자(Barry)가 제2판에서 발견한 모든 오류(아쉽게도 아무도 알아차리지 못한 오류도 포함)를 모두 수정했으며 새 자료에 새로운 오류가 발생하지 않도록 노력했습니다. 그럼에도 불구하고 아직 부족한 부분이 남아 있다는 점을 인정하며, 빠른 시일 내에 이를 수정하고 싶습니다. 따라서 제시된 자료의 본질이나 제공된 역사적 정보와 관련된 오류뿐만 아니라 모든 오타*에 대해 그것을 발견한 첫 번째 사람에게 기꺼이 $2.56를 지불하겠습니다. 제목 페이지 뒷면에 있는 웹 페이지에는 나에게 보고된 모든 오류의 현재 목록이 포함되어 있습니다**.

* 본 출판물의 원본을 참고합니다. - 대략. 에드.
** 러시아어판 준비 당시 알려진 오류가 수정되었습니다. -대략. 에드.

D.E.K.
캘리포니아주 스탠포드
1997년 4월

지난 20년 동안 세상은 변했습니다.
- 빌 게이츠(1995)


1장. 기본 개념.................................................................. ....... ... 27
1.1. 알고리즘................................................................. .. ...... 27
1.2. 수학적 소개................................................................ .... 37
1.2.1. 수학적 귀납법........................................... 38
1.2.2. 숫자, 거듭제곱, 로그................................................................ 49
1.2.3. 합계와 곱.................................................................. .... 56
1.2.4. 정수 함수와 기본 정수론......................... 68
1.2.5. 순열 및 계승........................................... 75
1.2.6. 이항 계수........................................................... 82
1.2.7. 고조파 수.......................................................... ... 105
1.2.8. 피보나치 수열.......................................................... .... 109
1.2.9. 함수 생성........................................................... 118
1.2.10. 알고리즘 분석........................................................... 127
*1.2.11. 점근적 표현.................................. 138
*1.2.11.1. 상징 에 대한 .......................................... 138
*1.2.11.2. 오일러의 합 공식..................................................... 143
*1.2.11.3. 점근식 적용................................................. 148
1.3. 믹스 ................................................. ....................... 156
1.3.1. MIX 설명................................................. 156
1.3.2. MIX 컴퓨터 어셈블리 언어 ............................................. 178
1.3.3. 순열에 적용................................................. 198
1.4. 몇 가지 기본 프로그래밍 기술.................................................................. 221
1.4.1. 서브루틴........................................................... .......221
1.4.2. 코루틴........................................................... ........229
1.4.3. 통역사 프로그램................................................................. ... 237
1.4.3.1. 믹스 시뮬레이터 ........................................... 239
*1.4.3.2. 추적 프로그램.................................................. 248
1.4.4. 입력과 출력............................................... ......... 251
1.4.5. 역사 및 참고문헌.................................................. 266

2장. 정보 구조.................................................................. ....... 271
2.1. 소개................................................. ....... ....271
2.2. 선형 목록.......................................................... .... 277
2.2.1. 스택, 대기열 및 데크.................................................. ......277
2.2.2. 순차적 배포........................................... 283
2.2.3. 연계 배포...........................................295
2.2.4. 순환 목록........................................................... 315
2.2.5. 이중 연결 목록.................................................. 322
2.2.6. 배열 및 직교 목록.................................................................. 341
2.3. 나무................................................. ..... 352
2.3.1. 이진 트리 순회................................................. 362
2.3.2. 트리를 이진 트리로 표현........................ 380
2.3.3. 나무의 다른 표현................................. 395
2.3.4. 나무의 기본 수학적 속성.................................. 410
2.3.4.1. 무료 나무........................................... 410
2.3.4.2. 지향성 트리...........................420
*2.3.4.3. 무한 트리의 보조정리................................................................ 431
*2.3.4.4. 나무 열거............................ 435
2.3.4.5. 경로 길이...........................................449
*2.3.4.6. 역사 및 참고문헌.................................. 456
2.3.5. 목록 및 가비지 컬렉션 ............................................. 459
2.4. 다중 연결 구조.................................................................. ......476
2.5. 동적 메모리 할당.................................................................. 488
2.6. 역사와 참고문헌................................................................................ 512

연습에 대한 답변................................................................................ ..... ......521

부록 A. 일부 상수의 값 표........................................................... 683
일체 포함. 기본상수(십진수) .............................................. ..... 683
A.2. 기본 상수(8진수) .............................................. 684
A.Z. 조화수, 베르누이 수, 피보나치 수의 의미...... 685

부록 B. 기본 표기법.................................................................. .......687

주제 색인.................................................. .............692

컴퓨터 과학 분야의 기본 저작인 Donald Knuth의 전설적인 논문 "프로그래밍의 예술"에 대한 간략한 개요입니다.

1권. 기본 알고리즘

첫 번째 볼륨은 기본 알고리즘과 데이터 구조를 소개하고 기본 프로그래밍 개념과 기술을 설명합니다. 컴퓨터 메모리에 데이터를 표현하고 효과적으로 작업하는 주제도 여기에서 논의됩니다.

이 책은 기호 계산, 수치 방법, 시뮬레이션 방법 등에 대한 예제로 가득 차 있습니다.

예제 프로그램은 가상의 "MIX 컴퓨터"에서 실행되도록 설계된 언어인 "MIX 어셈블러"로 작성되었습니다. 세 번째 버전은 레거시 MIX를 에뮬레이트하기 위한 소프트웨어가 있는 MMIX로 대체되었습니다.

저급 언어의 사용은 많은 독자들을 낙담하게 하지만, 저자 자신은 그럴 만한 이유를 가지고 자신의 선택을 정당화합니다. 아키텍처에 연결하면 속도 및 복잡성(예: 메모리 사용)과 같은 알고리즘의 특성을 판단할 수 있습니다.

2권. 파생 알고리즘

두 번째 책은 반수치 알고리즘에 대한 소개입니다. 별도의 섹션에서는 생성을 위한 산술, 난수 및 알고리즘을 다룹니다. 반수치 알고리즘 이론의 기본이 제공되며 수많은 예가 뒷받침됩니다.

이번 판에서 Knuth가 제안한 난수 생성기의 새로운 해석과 형식 거듭제곱을 사용한 계산 방법에 대한 고려는 특별히 언급할 가치가 있습니다.

3권. 정렬 및 검색

3권에서는 기존 정렬 및 검색 알고리즘에 대한 포괄적인 개요를 제공합니다. 이 자료는 첫 번째 부분에 제시된 데이터 구조에 대한 정보를 보완하여 첫 번째 볼륨의 일종의 논리적 연속이 됩니다.

여기서 저자는 내부 및 외부 메모리, 크고 작은 데이터베이스 구축 및 작업에 대해 이야기합니다. 책에서 논의된 모든 알고리즘에 대해 효율성에 대한 비교 분석이 제공됩니다. 특별 섹션에서는 최적의 정렬 방법과 새로운 순열 이론 및 범용 해싱에 대한 설명을 다룹니다.

4권. 결합 알고리즘

네 번째 권은 그 자체가 여러 권으로 구성된 세트입니다. 조합 검색은 풍부하고 중요한 주제이며 Knuth는 한두 권(또는 세 권)의 책에 담기에는 너무 많은 새롭고 흥미롭고 유용한 자료를 제공합니다. 이 책에는 독립적인 작업에 대한 답변이 포함된 약 1,500개의 연습 문제와 다른 출판물에서는 찾을 수 없는 수백 가지 유용한 사실이 포함되어 있습니다.

이름:프로그래밍의 예술 - 1권.

책 시리즈 The Art of 프로그래밍의 첫 번째 권은 프로그래밍의 기본 개념과 방법에 대한 설명으로 시작됩니다. 그런 다음 저자는 정보 구조, 컴퓨터 내 정보 표현, 데이터 요소 간의 구조적 관계 및 이를 효과적으로 사용하는 방법을 조사합니다. 시뮬레이션 방법, 기호 계산, 수치 방법 및 소프트웨어 개발 방법에 대한 기본 응용 사례가 제공됩니다. 이전 버전에 비해 수십 가지 간단하지만 동시에 매우 중요한 알고리즘이 추가되었습니다. 현대적인 연구 방향에 따라 수학적 소개 섹션이 크게 수정되었습니다.

각 책에는 고유한 운명이 있습니다. 일부는 눈에 띄지 않게 나타나고 시간이 지남에 따라 눈에 띄지 않게 사라져 도서관 선반의 먼지로 뒤덮입니다. 다른 사람들은 새로운 참고 도서로 대체될 때까지 좁은 범위의 전문가들 사이에서 일정 기간 동안 수요가 있습니다. 또 다른 것들은 시간을 초월하여 사회의 기술 발전에 강력한 영향을 미칩니다. 후자의 범주에 속하는 책은 그리 많지 않습니다. 세상에 그들의 모습은 항상 휴일입니다. 몇 년이 지나고 기술은 변하지만 새로운 세대는 끊임없는 관심을 가지고 자신의 페이지를 다시 읽습니다. 유명한 미국 과학자 Donald Erwin Knuth가 독자에게 제공하는 여러 권의 작품 "The Art of 프로그래밍"이 바로 그러한 책에 속합니다.
D. E. Knuth의 프로그래밍 기술의 성공은 무엇입니까?
첫째, 이 책은 컴퓨터 알고리즘의 설계와 분석에 관한 훌륭한 교과서입니다. 해당 섹션은 프로그래밍 기술, 알고리즘 이론 및 이산 수학에 대한 많은 대학 과정에 포함될 수 있습니다. 이 책은 프로그래밍의 기초에 익숙한 고등학생도 읽을 수 있습니다. 저자는 가상의 MIX 범용 컴퓨터의 기계 명령 언어를 녹음 알고리즘의 주요 언어로 선택했습니다. 이를 통해 컴퓨터의 특성을 고려한 최적의 프로그램을 구축할 수 있습니다. MIX 프로그램을 실제 컴퓨터로 전송하거나 고급 언어로 다시 작성하는 것은 특별히 어렵지 않습니다. 프로그램의 논리는 거의 항상 간단한 블록 다이어그램을 사용하여 설명됩니다.
둘째, 이 책에 포함된 엄선된 자료에는 어떤 형태로든 프로그래밍 실습에서 가장 자주 발견되는 알고리즘의 기본 기본 클래스가 포함되어 있습니다.
셋째, D. E. Knuth 책의 성공에 중요한 요소는 표현의 백과사전적 성격이다. 크누스 교수는 문제의 역사적 배경부터 현재 상태까지 추적하는 독특한 능력을 갖고 있습니다. 현대적 맥락에 배치된 옛 거장(고대까지)의 작품에 대한 수많은 참조는 독자에게 과학적 아이디어와 방법의 역사적 발전에 대한 특별한 참여감을 불러일으킵니다.

편리한 형식으로 전자책을 무료로 다운로드하고 시청하고 읽으세요.
프로그래밍의 기술 - 1권 - Knut D. E. - fileskachat.com 책을 빠르고 무료로 다운로드하세요.

DJVU 다운로드
아래에서 러시아 전역으로 배송되는 할인 혜택으로 이 책을 최고의 가격에 구입할 수 있습니다.

책 쓰기 프로젝트는 에서 저자에 의해 시작되었습니다. 처음에는 1권으로 발매하려고 했으나, 분량이 너무 많아서 7권으로 늘렸습니다. 처음 3권은 상당히 빨리 출판되었습니다. 1권은 1968년, 2권은 1969년, 3권은 1973년에 출판되었으며, 이후 2005년 2월까지 중단되어 저자는 4권의 첫 번째 부분을 출판했습니다. 4권의 나머지 부분은 1년에 약 2번씩 별도의 호로 발행하기로 결정되었으며, 그 후에는 4권 전체가 공식적으로 출판될 것입니다. 2005~2009년에는 0호, 1호, 2호, 3호, 4호가 출판되었고, 2011년에는 이들 호에 대한 정보가 포함된 4A권이 출판되었습니다. 또한 2005년에는 제1호 "MMIX - 새천년을 위한 RISC 컴퓨터"가 출시되었으며, 이 정보는 새로운 제1권 제4판에 포함될 예정입니다. 6호는 2015년에 발행되었습니다. 만족도, 곧 출간될 4B권의 중간 1/3을 나타냅니다.

Knuth는 항상 프로그래밍의 기술을 자신의 인생의 주요 프로젝트로 여겼기 때문에 누락된 부분을 작성하고 기존 부분을 정리하는 데 전적으로 집중할 의도로 1993년에 은퇴했습니다. 그는 이 작업을 완료하는 데 20년이 걸릴 것이라고 믿었습니다.

백과사전 유튜브

  • 1 / 5

    컴파일러 설계 분야에서 인정받는 전문가인 Knuth는 1962년에 컴파일러 설계에 관한 책을 쓰기 시작했습니다. 그는 곧 자료의 범위가 훨씬 더 넓어져야 한다는 것을 깨달았습니다. 1965년 6월, 그는 원래 출판하고 싶었던 내용의 첫 번째 버전을 12개 섹션으로 구성된 한 권의 책으로 완성했습니다. 손으로 쓴 글의 분량은 3000페이지였다. Knuth의 계산에 따르면 이 책은 인쇄된 텍스트의 600페이지에 적합해야 했지만 출판사가 그에게 알려준 대로 실제 책은 2,000페이지였을 것입니다. 이와 관련하여 책의 구조는 각각 1~2섹션으로 구성된 여러 권으로 수정되었습니다. 그 이후로 자료의 지속적인 증가로 인해 네 번째 권도 별도의 책(4A, 4B, 4C 및 4D)으로 나누기로 결정되었습니다. 그러나 섹션 7.1과 7.2.1이 이미 총 650페이지 이상을 차지하고 있기 때문에 이 구분이 최종적인 것은 아닐 것 같습니다.

    1976년에 Knuth는 제2권의 제2판을 준비했는데, 이를 위해서는 재타자가 필요했습니다. 그러나 초판에 사용된 인쇄 디자인(모노타이프)은 당시 더 이상 사용할 수 없었습니다. 미래에 비슷한 실망을 피하기 위해 Knuth는 1977년에 자신만의 컴퓨터 타이포그래피 시스템을 개발하기 시작했습니다. 그의 계산에 따르면 작업은 6개월도 채 걸리지 않았어야 했는데, 완성되기까지 약 10년이 걸렸다. 이 시스템은 TeX라고 불리며 현재 The Art of 프로그래밍의 모든 권의 레이아웃에 사용됩니다. 게다가 TeX은 이후 자연과학 분야의 기사와 논문 작성을 위한 사실상의 표준이 되었습니다.

    Knuth의 다른 책과 마찬가지로 The Art of 프로그래밍에는 그의 "상표"가 표시되어 있습니다. 즉, 텍스트에서 발견된 각 오류에 대해 저자는 16진수 1달러, 즉 $2.56(0x100센트, 16진법)을 지불합니다. 이 책의 또 다른 특징은 단순한 "준비" 문제부터 개방형 문제에 이르기까지 다양한 난이도의 독립적인 실행을 위한 풍부한 연습 문제입니다. 각 연습의 난이도는 0에서 50까지의 숫자 척도로 평가됩니다. 따라서 초기 판에서 페르마의 마지막 정리는 50점으로 평가되었지만, 제3판에서는 이 점수가 45점으로 "평가 절하"되었습니다. 그 때까지 그 증명이 중단되었기 때문입니다. 공개적인 문제가 될 것입니다.

    1978년 3권 "정렬 및 검색"에 대한 범례 요약(왼쪽 - 평가, 오른쪽 - 간략한 설명)

    • 블랙 트라이앵글 - 권장
    • M - 수학적 편견이 있음
    • VM - "고등 수학"에 대한 지식이 필요합니다.
    • 00 - 즉각적인 응답 필요
    • 10 - 단순(1분 동안)
    • 20 - 중간 난이도(15분 동안)
    • 30 - 난이도 증가
    • 40 - "수학 워크샵"을 위해
    • 50 - 연구 문제

    책을 집필하기 위한 원래 계획에는 다음과 같은 자료 분석이 포함되었습니다.

    • 볼륨 1. 기본 알고리즘.
      • 1장. 기본 개념.
      • 제 2 장. 정보 구조.
    • 2권. 반수치 알고리즘.
      • 3장. 난수.
      • 4장. 산술.
    • 3권. 정렬 및 검색.
      • 5장. 정렬.
      • 6장. 검색.
    • 4권. 조합 알고리즘.
      • 7장. 조합 검색.
      • 8장. 재귀.
    • 5권. 구문 알고리즘.
      • 9장. 사전식 검색.
      • 10장. 구문 검색.
    • 6권. 언어이론.
    • 7권. 컴파일러.

    실제로 이 계획은 3권까지 구현됐다.

    현재 7장의 첫 번째 섹션을 포함하는 4A권이 출판되었습니다. 새로운 섹션은 처음에는 별도의 호(약 128페이지)로 발행될 예정이며, 대략 연간 2호입니다(0, 1, 2, 3, 4호는 4A권 발행 이전에 비슷한 방식으로 발행되었습니다).

    기계 지향 예제 언어

    책에 제시된 예제 프로그램은 가상의 MIX 컴퓨터에서 실행되도록 설계된 "MIX 어셈블러"를 사용합니다. 세 번째 버전에서는 더 이상 사용되지 않는 MIX가 완전한 RISC 아키텍처를 갖춘 MMIX로 대체되었습니다. 표준 IBM 호환 컴퓨터에서 (M)MIX 시스템 에뮬레이션을 제공하는 소프트웨어가 있습니다. GNU Compiler Collection에는 대상 MMIX 아키텍처에서 C/C++ 코드를 컴파일하는 기능이 있습니다.

    많은 독자들은 저수준 언어를 사용한다는 사실 때문에 거부감을 느끼지만 Knuth는 자신의 선택이 정당하다고 생각합니다. 속도, 메모리 소비 등과 같은 알고리즘의 특성을 정확하게 판단하려면 아키텍처에 대한 링크가 필요하기 때문입니다. 그러나 이 선택으로 인해 타겟층이 크게 좁아졌습니다. 또한 실무 프로그래머를 위한 "레시피 북"으로 사용하는 범위가 제한적이며, 이들 중 다수는 어셈블리 언어를 모르고, 알고 있더라도 이 책의 하위 수준 알고리즘을 어셈블리 언어로 번역하려는 욕구가 없습니다. 고급 언어. 동일한 자료를 보다 대중적인 방식으로 제시하는 많은 실용적인 안내서가 바로 이러한 이유로 출판되었습니다.

    비판

    Knuth의 논문은 프로그래밍에 관한 다른 책들과 확실히 구별되는 주요 특징은 매우 높은 수준의 자료와 학문적 발표뿐 아니라 고려 중인 문제에 대한 깊이 있는 분석입니다. 덕분에 진정한 베스트셀러이자 모든 전문 프로그래머의 참고서가 되었습니다. American Scientist 잡지는 20세기 최고의 물리 및 수학 논문 12개 목록에 The Art of 프로그래밍을 포함시켰으며, 양자역학에 관한 Dirac의 저작, 상대성이론에 관한 Einstein, 수학의 기초에 관한 Russell과 Whitehead의 저작, 그리고 다른 몇 가지.

    이 책의 제1권 제3판 표지에는 빌 게이츠의 인용문이 들어 있습니다. "당신이 정말 훌륭한 프로그래머라고 생각한다면... Knuth의 The Art of Programme을 읽어보세요. 모든 내용을 읽을 수 있다면 꼭 이력서를 보내주세요.".

    에디션

    원래의

    세 번째 (현재)

    볼륨 번호의 오름차순:

    • 1권: 기본 알고리즘. 제3판(리딩, 매사추세츠: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
    • 1권, Fascicle 1: MMIX - 새천년을 위한 RISC 컴퓨터. (Addison-Wesley, 2005년 2월 14일) ISBN 0-201-85392-2 (1권 4판에 게재 예정)
    • 2권: 반수치 알고리즘. 제3판(리딩, 매사추세츠: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
    • 3권: 정렬 및 검색. 제2판(Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
    • 4A권: 조합 알고리즘, 1부(뉴저지주 어퍼 새들 리버: Addison-Wesley, 2011), xvi+883pp. ISBN 0-201-03804-8
    • 4권 6권: 만족감. (Addison-Wesley Professional, 2015), xiii+310pp. ISBN 978-0-13-439760-3

    이전의

    출판일 기준:

    • 1권, 초판, 1968. 634pp. ISBN 0-201-03801-3 .
    • 2권, 초판, 1969, xi+624pp, ISBN 0-201-03802-1.
    • 3권, 초판, 1973, xi+723pp+centerfold, ISBN 0-201-03803-X
    • 1권, 제2판, 1973, xiii+634pp, ISBN 0-201-03809-9.
    • 2권, 제2판, 1981, xiii+ 688pp. ISBN 0-201-03822-6 .
    • 4권, Fascicle 2: 모든 튜플과 순열 생성, (Addison-Wesley, 2005년 2월 14일) v+127pp, ISBN 0-201-85393-0
    • 4권, Fascicle 3: 모든 조합 및 파티션 생성. (Addison-Wesley, 2005년 7월 26일) vi+150pp, ISBN 0-201-85394-9
    • 4권, Fascicle 4: 모든 트리 생성 - 조합 생성의 역사, (Addison-Wesley, 2006년 2월 6일) vi+120pp, ISBN 0-321-33570-8
    • 4권, Fascicle 0: 조합 알고리즘 및 부울 함수 소개, (Addison-Wesley Professional, 2008년 4월 28일) vi+240pp, ISBN 0-321-53496-4
    • 4권, Fascicle 1: 비트별 트릭 및 기술; 바이너리 결정 다이어그램(Addison-Wesley Professional, 2009년 3월 27일) viii+260pp,


질문이 있으신가요?

오타 신고

편집자에게 전송될 텍스트:

보내다