Donald Knuth là một nhà khoa học máy tính quan tâm rất nhiều đến tính chính xác của các cuốn sách của mình đến mức ông gợi ý một đô la hex ($2,56, 0x$1,00) cho bất kỳ "lỗi" nào được tìm thấy, trong đó lỗi được xác định là bất kỳ điều gì "không chính xác về mặt kỹ thuật, lịch sử, kiểu chữ hoặc về mặt chính trị". Tôi thực sự muốn nhận được séc từ Knuth, vì vậy tôi quyết định tìm kiếm lỗi trong kiệt tác của anh ấy "Nghệ thuật lập trình" (TAOCP). Chúng tôi đã tìm được ba. Đúng như lời hứa, Knut đã gửi một tấm séc cho 0x$3,00.
Như bạn có thể thấy, đây không phải là một séc thực sự. Knuth từng gửi séc thật nhưng đã ngừng hoạt động vào năm 2008 do . Bây giờ anh ta gửi “chứng chỉ tiền gửi cá nhân” tới (Ông chủ). Anh ấy nói rằng anh ấy sẵn sàng gửi tiền thật nếu cần thiết, nhưng có vẻ như việc đó quá rắc rối.
Tôi tìm thấy hai lỗi chính tả và một lỗi lịch sử. Tôi sẽ liệt kê chúng theo thứ tự mức độ tầm thường giảm dần.
Lỗi đánh máy số 1
Lỗi đánh máy đầu tiên ở trang 392 của tập thứ ba “Sắp xếp và tìm kiếm”, dòng thứ tám từ dưới lên: “Sau khi tìm kiếm không thành công, đôi khi (đôi khi) nên nhập một bản ghi mới vào bảng chứa K; phương pháp thực hiện điều này được gọi là thuật toán tìm kiếm và chèn. Sai lầm là thay vào đó thỉnh thoảng nên là đôi khi.
Tất nhiên, một sai lầm như vậy không có gì đáng ngạc nhiên. Chỉ riêng bài viết này chắc chắn sẽ có một vài lỗi chính tả (không có phần thưởng cho việc tìm ra chúng). Điều thực sự đáng ngạc nhiên là nó đã không được chú ý trong một thời gian dài. Trang 392 không đào sâu vào phần toán mà là trang đầu tiên Chương 6 "Tìm kiếm"! Có thể là một trong những phần được đọc nhiều nhất của cuốn sách. Về lý thuyết thì nên có ít lỗi chính tả nhất, nhưng không.
Nhân tiện, nếu bạn đã từng nghĩ đến việc đọc TAOCP, hãy thử xem. Nhiều người sẽ nói rằng đây là thư mục, không nhằm mục đích đọc trực tiếp, nhưng điều này không đúng. Tác giả có quan điểm rõ ràng và phong cách riêng. Điều duy nhất cản trở khả năng đọc là sự phức tạp của toán học. Tuy nhiên, có một giải pháp đơn giản: đọc cho đến khi đến phần toán không hiểu, hãy bỏ qua và chuyển sang phần tiếp theo mà bạn có thể hiểu được. Đọc thế này thì mình bỏ sót ít nhất 80% nội dung cuốn sách, còn 20% còn lại thì tuyệt vời!
Người ta cũng nói rằng TAOCP không liên quan, đã lỗi thời hoặc không thể áp dụng cho "lập trình thực". Điêu nay cung không đung. Ví dụ: phần đầu tiên sau phần giới thiệu sẽ xem xét việc tìm một phần tử trong một mảng chưa được sắp xếp. Thuật toán đơn giản nhất quen thuộc với tất cả các lập trình viên. Bắt đầu con trỏ ở đầu mảng, sau đó thực hiện các thao tác sau trong vòng lặp:
- Kiểm tra xem phần tử hiện tại có phải là phần tử mong muốn không. Nếu vậy, chúng tôi sẽ trả lại nó; nếu không thì
- Kiểm tra xem con trỏ có nằm ngoài ranh giới mảng hay không. Nếu vậy, hãy trả về lỗi; nếu không thì
- Phóng to và tiếp tục.
Bây giờ hãy xem xét: trung bình thuật toán này yêu cầu bao nhiêu lần kiểm tra giới hạn? Trong trường hợp xấu nhất, khi mảng không chứa một phần tử, mỗi phần tử trong danh sách sẽ yêu cầu một lần kiểm tra và trung bình nó sẽ giống như 
. Thuật toán tìm kiếm thông minh hơn có thể thoát khỏi chỉ bằng một lần kiểm tra giới hạn. Đính kèm phần tử mong muốn vào cuối mảng, sau đó bắt đầu con trỏ ở đầu mảng và thực hiện các thao tác sau trong một vòng lặp:
- Kiểm tra xem phần tử hiện tại có phải là phần tử mong muốn không. Nếu vậy, chúng tôi trả về phản hồi nếu con trỏ nằm trong mảng hoặc trả về lỗi nếu không nằm trong mảng. Nếu không thì
- Phóng to và tiếp tục.
Bằng cách này hay cách khác, phần tử được đảm bảo được tìm thấy và việc kiểm tra giới hạn chỉ được thực hiện một lần khi điều này xảy ra. Đây là một ý tưởng sâu sắc nhưng nó đủ đơn giản ngay cả đối với một lập trình viên mới vào nghề. Có lẽ tôi không thể nói về mức độ liên quan của công việc với người khác, nhưng tôi ngay lập tức có thể áp dụng sự hiểu biết này cho cả mã cá nhân và nghề nghiệp. Cuốn sách TAOCP chứa đầy những viên ngọc quý như vậy (công bằng mà nói, trong đó cũng có rất nhiều điều kỳ lạ, chẳng hạn như ).
"Tìm kiếm
Lâu quá
Tìm kiếm
Tôi chỉ muốn nhảy"
- Luther Vandross, “Việc tìm kiếm” (1980)
Lỗi đánh máy số 2
Lỗi đánh máy thứ hai nằm trong Tập 4A, Thuật toán tổ hợp, Phần 1. Trang 60 mô tả một vấn đề liên quan đến việc sắp xếp lịch trình cho các diễn viên hài biểu diễn tại nhiều sòng bạc khác nhau. Một số diễn viên hài ngoài đời thực được lấy làm ví dụ, bao gồm Lily Tomlin, Weird Al Yankovic và Robin Williams, những người vẫn còn sống khi cuốn sách được xuất bản. Knuth luôn liệt kê tên đầy đủ trong chỉ mục, vì vậy Williams được liệt kê ở trang 882 với tên "Williams, Robin McLorim." Nhưng tên đệm của anh ấy kết thúc bằng “n” chứ không phải “m”, tức là McLaurin.
McLaurin là tên thời con gái của mẹ anh. Cô là chắt gái của Anselm Joseph McLaurin, Thống đốc thứ 34 của Mississippi. Rõ ràng triều đại của ông không được ghi nhớ vì điều gì tốt đẹp. Từ cuốn sách :
“Sự kiện quan trọng nhất dưới thời chính quyền McLaurin là việc Hoa Kỳ tuyên chiến với Tây Ban Nha vào mùa xuân năm 1898... Thật không may, chiến tranh có thể đã tạo cơ hội cho một số quan chức chính phủ tham gia hối lộ. McLaurin bị buộc tội về nhiều hành vi đáng nghi vấn, bao gồm cả chủ nghĩa gia đình trị và sử dụng quá mức quyền ân xá. Trong phong trào ôn hòa, những người chỉ trích đã cáo buộc thống đốc là một kẻ say rượu, điều mà ông đã công khai thừa nhận ”.
Sai lầm lịch sử
Hãy xem xét thuật toán nhân truyền thống từ chương trình giảng dạy của trường. Cần bao nhiêu phép nhân có một chữ số? Giả sử bạn nhân 
-số có chữ số 
trên 
-chút 
. Đầu tiên nhân chữ số đầu tiên 
cho mỗi chữ số 
từng cái một. Sau đó nhân chữ số thứ hai 
cho mỗi chữ số 
từng con số một và cứ như vậy cho đến khi bạn xem hết tất cả các con số 
. Vì vậy phép nhân truyền thống đòi hỏi 
phép nhân nguyên thủy. Cụ thể là nhân hai số với 
yêu cầu cấp bậc 
phép nhân có một chữ số.
Điều này thật tệ, nhưng có thể tối ưu hóa quy trình bằng phương pháp do nhà toán học Liên Xô Anatoly Alekseevich Karatsuba phát triển. Hãy giả vờ như vậy 
и 
- số thập phân có hai chữ số; tức là có những con số 
, 
, 
, 
như vậy mà 
и 
(Việc khái quát hóa thuật toán này thành số lớn hơn cần một số thao tác; tuy không quá khó nhưng để không mắc sai sót trong các chi tiết, tốt hơn tôi nên lấy một ví dụ đơn giản). Sau đó 
, 
, 
. Nhân các nhị thức cho 
. Hiện tại chúng tôi vẫn có 
phép nhân có một chữ số: 
, 
, 
, 
. Bây giờ hãy cộng và trừ 
. Sau một vài lần sắp xếp lại mà tôi sẽ để lại như một bài tập cho người đọc, hóa ra 
- chỉ có ba phép nhân có một chữ số! (Có một số hệ số không đổi nhưng chỉ có thể tính được bằng cách cộng và dịch chuyển các chữ số).
Đừng yêu cầu bằng chứng, nhưng Thuật toán Karatsuba (được khái quát hóa đệ quy từ ví dụ trên) cải thiện phương pháp nhân truyền thống với 
hoạt động trước 
. Xin lưu ý rằng đây là một cải tiến thực sự đối với thuật toán chứ không phải là sự tối ưu hóa cho việc tính toán trong đầu. Thật vậy, thuật toán này không phù hợp với số học trí tuệ vì nó đòi hỏi chi phí lớn cho các phép toán đệ quy. Ngoài ra, hiệu ứng sẽ không thể hiện đầy đủ cho đến khi số lượng đủ lớn (may mắn thay, thuật toán của Karatsuba đã được thay thế bằng các phương pháp thậm chí còn nhanh hơn: vào tháng 2019 năm XNUMX, một thuật toán đã được xuất bản chỉ yêu cầu phép nhân; gia tốc chỉ áp dụng cho những con số lớn không thể tưởng tượng được).
Thuật toán này được mô tả ở trang 295 của Tập XNUMX, Thuật toán bán số. Ở đó Knuth viết: “Thật tò mò rằng ý tưởng này chỉ được phát hiện ở 1962 năm,” khi một bài báo mô tả thuật toán Karatsuba được xuất bản. Nhưng! Năm 1995, Karatsuba xuất bản một bài báo "Độ phức tạp tính toán", trong đó nói lên một số điều: 1) khoảng năm 1956, Kolmogorov cho rằng phép nhân không thể được thực hiện trong ít hơn 
bước; 2 trong 1960 Năm Karatsuba tham dự hội thảo nơi Kolmogorov trình bày giả thuyết của mình n². 3) “Trong đúng một tuần,” Karatsuba đã phát triển thuật toán “chia để trị”; 4) vào năm 1962 Kolmogorov đã viết và xuất bản một bài báo thay mặt Karatsuba kèm theo mô tả thuật toán. “Tôi chỉ biết đến bài viết này sau khi nó được xuất bản lại.”
Vì vậy, lỗi là ở chỗ thay vì 1962 phải được chỉ định 1960 năm. Đó là tất cả.
Phân tích
Việc tìm lỗi không đòi hỏi kỹ năng đặc biệt.
- Lỗi đầu tiên càng nhỏ càng tốt và nằm ở một vị trí tương đối dễ thấy (phần đầu của chương). Bất kỳ tên ngốc nào cũng có thể tìm thấy nó; Hoá ra tôi chính là tên ngốc đó.
- Việc tìm ra lỗi đánh máy thứ hai đòi hỏi sự may mắn và siêng năng chứ không phải kỹ năng. Mục lục cho cuốn “Williams” nằm ở trang áp chót của tập sách, một phần khá nổi bật của cuốn sách. Tôi chỉ đang lật qua mục lục (nghe có vẻ không thảm hại lắm vì có những quả trứng Phục sinh ẩn trong mục mục của Knuth. Ví dụ, có những mục bằng tiếng Ả Rập và tiếng Do Thái, cả hai đều trỏ đến trang 66. Nhưng trang đó không đề cập đến một trong hai ngôn ngữ; thay vào đó nó đề cập đến “các ngôn ngữ được đọc từ phải sang trái”). Và cái tên thứ hai khiến tôi chú ý. Vì tôi thường đọc Wikipedia nên tôi đã kiểm tra Robin Williams và nhận thấy có sự khác biệt.
- Tôi ước gì có thể nói rằng tôi đã nghiên cứu nghiêm túc để tìm ra lỗi lịch sử, nhưng thực sự tôi chỉ xem xét . Ngay những dòng đầu tiên đã nói: “Thuật toán Karatsuba là một thuật toán nhân nhanh. Được phát hiện bởi Anatoly Karatsuba vào năm 1960 và xuất bản năm 1962." Sau đó tất cả những gì còn lại là cộng hai và hai.
Trong tương lai tôi muốn tìm ra một lỗi nghiêm trọng hơn, đặc biệt là trong mã của Knuth. Tôi cũng muốn tìm một lỗi trong tập đầu tiên của Thuật toán cơ bản. Có lẽ tôi đã tìm được nó, nhưng không hiểu sao thư viện địa phương chỉ có tập 2, 3 và 4A.
Sự kiện tài chính:
- Tổng cộng, đóng góp của tôi cho TAOCP chỉ bao gồm ba nhân vật: một sự bổ sung s, thay thế m trên n и 2 trên 0. Với mức giá 2,56 USD, đây là một số biểu tượng khá sinh lợi; Nếu bạn được trả số tiền đó, một bài viết 1000 từ (trung bình bốn ký tự) sẽ giúp bạn kiếm được XNUMX nghìn đô la.
- Với ba đô la thập lục phân, tôi cùng với 29 công dân khác được xếp ở vị trí thứ 69 trong danh sách những người gửi tiền giàu nhất của Ngân hàng San Serriff (tính đến ngày 1 tháng 2019 năm XNUMX).
Các cuộc thảo luận khác về séc từ Knuth
Khuyến nghị chung để tìm lỗi trong sách của Knuth. Hầu hết họ liên quan đến các lỗi kỹ thuật mà tôi không mắc phải. Có một đề nghị mà tôi đã thực hiện một cách nghiêm túc:
Tốt nhất là đợi cho đến khi bạn thu thập được một loạt lỗi rồi mới gửi. Bằng cách kết hợp một số lỗi thực tế nhưng không có giá trị lắm, bạn sẽ tăng khả năng một trong số chúng thực sự bị coi là một sai lầm hoặc một lời khuyên. Nếu bạn gửi từng lỗi một thì mỗi lỗi có thể bị từ chối.
Tôi không muốn chỉ gửi những lỗi đánh máy vô nghĩa mà đã nghe theo lời khuyên và chỉ gửi thư khi tôi tìm thấy một lỗi lịch sử có vẻ đủ nghiêm trọng.
Ashutosh Mehra là nhà đầu tư giàu thứ ba ở San Serriff với tài sản ròng khổng lồ là 0x$207,f0 trong BoSS.
- Khác:
Nguồn: www.habr.com
