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

• Slater, Robert (1987). Portraits in Silicon. MIT Press. ISBN 0-262-19262-4.
• Shasha, Dennis (1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Cathy Lazere. Copernicus. ISBN 0-387-97992-1.

Liên kết ngoài

• Overview of topics Lưu trữ 2008-09-04 tại Wayback Machine (Knuth's personal homepage)
• Computer programming as an art Lưu trữ 2008-04-14 tại Wayback Machine (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)