The Art of Computer Programming

The Art of Computer Programming (tạm dịch Nghệ thuật lập trình máy tính) là một chuyên khảo toàn diện của Donald Knuth bao trùm rất nhiều chủng loại giải thuật lập trình và những phân tích về chúng. Knuth bắt đầu dự án, với kế hoạch ban đầu là chỉ viết một cuốn sách, vào năm 1962. Ba tập đầu tiên được phát hành với thời gian gần nhau, bắt đầu bằng tập 1 năm 1968, tập 2 năm 1969, và tập 3 năm 1973. Phần đầu của tập 4 đã được in vào tháng 2 năm 2005. Các phần sau dự kiến in hai lần mỗi năm với một khoảng dừng trước tập sách số 5 để hoàn thành loạt "Các bài báo chọn lọc".

Lịch sử
Được xem là chuyên gia về viết trình biên dịch, Knuth bắt đầu viết một cuốn sách về thiết kế trình biên dịch vào năm 1962. Ông nhanh chóng nhận ra rằng phạm vi của cuốn sách cần phải lớn hơn nhiều. Vào tháng 6 năm 1965, Knuth hoàn thành bản nháp đầu tiên của những gì ban đầu dự tính là một cuốn sách duy nhất gồm mười hai chương. Bản thảo viết tay này dài 3.000 trang. Knuth đã cho rằng khoảng năm trang viết tay sẽ được chuyển sang một trang in. Nhà xuất bản nói rằng thực ra khoảng 1½ trang viết tay là đã chuyển được thành một trang in: do đó cuốn sách sẽ lên đến 2.000 trang.

Vào năm 1976, Knuth chuẩn bị lần tái bản thứ hai của Tập 2, đòi hỏi phải sắp chữ một lần nữa. Nhưng kiểu sắp chữ (được gọi là kiểu nóng) được dùng trong ấn bản thứ nhất đã không còn sử dụng nữa. Vì vậy vào năm 1977 ông quyết định bỏ ra vài tháng để làm ra một thứ gì đó thích hợp hơn. Tám năm sau, ông quay trở lại với TeX, cách sắp chữ hiện được sử dụng cho tất cả các tập.

Lời đề nghị nổi tiếng về một tấm séc phần thưởng trị giá "một đô la thập lục phân) (0x100 cent, theo Cơ số 16, là 2,56 dollar Mỹ) cho bất kỳ lỗi nào được tìm thấy, và sửa những lỗi đó trong những lần in kế tiếp, đã đóng góp vào bản chất chính xác được chăm chút và tiếp tục cao của tác phẩm, một thời gian dài sau lần xuất bản đầu tiên. Độ khó được xếp từ những bài tập "khởi động" đến những bài toán nghiên cứu chưa bao giờ được giải, khiến cho bất kỳ người đọc nào cũng cảm thấy thách thức. Câu đề tặng của Knuth cũng nổi tiếng: "This series of books is affectionately dedicated / to the Type 650 computer once installed at / Case Institute of Technology, / in remembrance of many pleasant evenings." (tạm dịch: "Loạt sách này được âu yếm dành cho / chiếc máy tính Kiểu 650 đã từng đặt tại / Viện
Công nghệ Case, / để ghi nhớ những buổi tối dễ chịu").

Ngôn ngữ assembly trong cuốn sách

Tất cả các ví dụ trong quyển sách đều sử dụng một ngôn ngữ có tên "ngôn ngữ assembly MIX", chạy trên máy tính giả tưởng MIX. (Hiện nay, máy tính MIX đã được thay bằng máy tính MMIX, là một phiên bản RISC). Những phần mềm như GNU MDK tồn tại để cung cấp sự mô phỏng kiến trúc MIX.

Một số độc giả gặp khó khăn khi sử dụng ngôn ngữ assembly, nhưng Knuth cho rằng điều này là cần thiết vì những giải thuật cần được đặt trong phạm vi sử dụng để đánh giá tốc độ và mức sử dụng bộ nhớ của chúng. Tuy nhiên, nó thực sự hạn chế khả năng tiếp cận với sách của nhiều độc giả, và giới hạn sự hữu ích của nó theo kiểu "sách nấu ăn" dành cho những lập trình viên đang chập chững, nhiều người trong số họ không quen thuộc với assembly, và thậm chí nếu có quen thuộc, họ cũng không thực sự mong muốn phải chuyển những đoạn mã assembly thành ngôn ngữ cấp cao.

Đánh giá
American Scientist đã chọn tác phẩm này là một trong một trăm chuyên khảo về khoa học hay nhất thế kỷ hai mươi, và trong cộng đồng khoa học máy tính nó được xem là sách nghiên cứu toàn diện đầu tiên và vẫn là hay nhất về chủ đề mà nó đề cập. Trang bìa của lần ấn bản thứ ba của Tập 1 trích lại lời Bill Gates, "Nếu bạn nghĩ là thật sự là một lập trình viên giỏi […] hãy đọc Nghệ thuật lập trình máy tính (của Knuth) […] Bạn nên ngay lập tức gửi cho tôi lý lịch nếu bạn có thể đọc được toàn bộ mọi thứ." (Theo folklore, Steve Jobs mới là người tuyên bố câu này.)

Sơ lược các chương
Tập 1 - Những giải thuật cơ bản
Chương 1 - Các khái niệm cơ bản
Chương 2 - Cấu trúc thông tin
Tập 2 - Những giải thuật nửa số
Chương 3 - Số ngẫu nhiên
Chương 4 - Số học
Tập 3 - Sắp xếp và tìm kiếm
Chương 5 - Sắp xếp
Chương 6 - Tìm kiếm
Tập 4 - Các giải thuật tổ hợp Algorithms, đang chuẩn bị (ba tập sách đã được ấn bản đến tháng 2 năm 2006, và phiên bản kiểm thử alpha của những tập sách khác có thể tải về được từ trang của Knuth ở dưới).
Tập 4A - Đếm và Backtracking
Chương 7 - Tìm kiếm tổ hợp
Tập 4B - Những giải thuật đồ thị và Mạng
Chương 7 tiếp
Tập 4C và có thể 4D - Tối ưu hóa và Đệ quy
Chương 7 tiếp
Chương 8 - Đệ quy
Tập 5 - Những giải thuật cú pháp, đã có kế hoạch (vào tháng 8 năm 2006, dự tính vào năm 2015).
Chương 9 - Quét từ vựng
Chương 10 - Kỹ thuật phân tích cú pháp
Tập 6 - Lý thuyết Ngôn ngữ phi ngữ cảnh, đã có kế hoạch.
Tập 7 - Các kỹ thuật Trình biên dịch, đã lên kế hoạch.

Phiên bản tiếng Anh
Ấn bản hiện tại
Theo thứ tự số Tập:

Tập 1: Fundamental Algorithms. Ấn bản thứ ba (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
Tập 1, Cuốn 1: MMIX -- A RISC Computer for the New Millennium. (Addison-Wesley, ngày 14 tháng 2 năm 2005) ISBN 0-201-85392-2 (sẽ trong ấn bản thứ tư của Tập 1)
Tập 2: Seminumerical Algorithms. Ấn bản thứ ba (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
Tập 3: Sorting và Searching. Ấn bản thứ hai (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
Tập 4, Cuốn 0: Introduction to Combinatorial Algorithms và Boolean Functions, (Addison-Wesley Professional, ngày 28 tháng 4 năm 2008) vi+240pp, ISBN 0-321-53496-4
Tập 4, Cuốn 1: Bitwise tricks and techniques and Binary Decision Diagrams (partial preview available, publication est: 2009)
Tập 4, Cuốn 2: Generating All Tuples and Permutations, (Addison-Wesley, ngày 14 tháng 2 năm 2005) v+127pp, ISBN 0-201-85393-0
Tập 4, Cuốn 3: Generating All Combinations and Partitions. (Addison-Wesley, ngày 26 tháng 7 năm 2005) vi+150pp, ISBN 0-201-85394-9
Tập 4, Cuốn 4: Generating all Trees -- History of Combinatorial Generation, (Addison-Wesley, ngày 6 tháng 2 năm 2006) vi+120pp, ISBN 0-321-33570-8

Tham khảo




Liên kết ngoài
Overview of topics (Knuth's personal homepage)
Computer programming as an art (pdf) Turing Award talk given by Donald Knuth
"Robert W Floyd, In Memoriam", by Donald E. Knuth -(on the influence of Bob Floyd)
Injokes in the books
Who is Bill Gosper? (on the influence of Bill Gosper on the 2nd Edition of Tập 2.)
TAoCP and its Influence of Computer Science(Softpanorama)