The Art of Computer Programming
Bách khoa toàn thư mở Wikipedia
The Art of Computer Programming[1] (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".
Mục lục |
[sửa] 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").
[sửa] 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ần cần thiết vì những giải thuật cần một bối cảnh để đánh giá tốc độ và mức sử dụng bộ nhớ. Tuy nhiên, nó thực sự hạn chế khả năng tiếp cận của 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.
[sửa] Đánh giá
American Scientist đã chọn tác phẩm này là một trong mười hai chuyên khảo về khoa học-vật lý hay nhất thế kỷ hai mươi,[2] 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.[3])
[sửa] 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 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.
[sửa] Phiên bản tiếng Anh
[sửa] Ấ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, February 14, 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 and 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 and Boolean Functions, (Addison-Wesley Professional, April 28, 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, February 14, 2005) v+127pp, ISBN 0-201-85393-0
- Tập 4, Cuốn 3: Generating All Combinations and Partitions. (Addison-Wesley, July 26, 2005) vi+150pp, ISBN 0-201-85394-9
- Tập 4, Cuốn 4: Generating all Trees -- History of Combinatorial Generation, (Addison-Wesley, February 6, 2006) vi+120pp, ISBN 0-321-33570-8
[sửa] Tham khảo
- ^ The Art of Computer Programming
- ^ Morrison, Philip & Phylis Morrison (1999), "100 or so Books that shaped a Century of Science", American Scientist (no. 6). Bản trực tuyến truy cập được vào ngày 2008-01-11
- ^ Zito, Tom. "Close Encounters of the Steve Kind". folklore.org. Được truy cập ngày 2008-01-11.
- Slater, Robert (1987). Portraits in Silicon, MIT Press. ISBN 0-262-19262-4.
- Shasha, Dennis; Cathy Lazere (1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists, Copernicus. ISBN 0-387-97992-1.
[sửa] 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)
