Phải thành thật, mình là fanboy của Donald Knuth. Có thể có rất nhiều giáo sư có tầm ảnh hưởng lớn đến các hướng mà mình quan tâm (khoa học máy tính/ trí tuệ nhân tạo hay thị giác máy tính) như Hinton, Li Fei-Fei, Zisserman, Pascal Fua. Nhưng có rất ít nhà khoa học mà mình dành trọn thời gian để có thể tìm hiểu và “cuồng” như Donald Knuth. Và mong ước của mình từ khi bước chân vào giảng đường đại học, theo đuổi đam mê với Khoa Học Máy Tính, rằng mình sẽ chinh phục cuốn “Kinh Thánh” này. Đó là một cuộc hành trình, và còn thử thách hơn cả tất cả những hành trình mình từng trải nghiệm.

Ngày sinh nhật vào năm đầu tiên đi làm, mình đã tự thưởng cho bản thân bản full set của bộ sách . Trước giờ mình chỉ dùng với mục đích tham khảo là chính. Nhưng vừa sau đợt sinh nhật 24 của mình, mình quyết định phải “chinh phục” bằng được cuốn sách. Mà theo plan của mình Volume 1 sẽ tốn tầm … 1-2 năm. Và có lẽ, mình sẽ mất chừng chục năm để chinh phục Volume 4A 😆. Chưa kể, phần 4B cực kì khó nhằn vì có cả Satistiability trong đó. Có lẽ riêng Volume 4 không thôi thì đã trở thành tượng đài mất rồi.

TAoCP liệu có khó đọc?

Theo mình thì không. Nhiều người khi nhìn vào cuốn sách với hàng đống công thức toán và những bài tập khó nhằng cũng như code mã máy MIX khiến họ nghĩ đây là một cuốn sách rất khó đọc. Nhưng ngay từ đoạn giới thiệu, Don Knuth đã hướng dẫn cách đọc và ông đã chỉ rõ những vấn đề mà người đọc thắc mắc.

1. Với MIX - mình đồng ý quan điểm của Don Knuth, nếu ông viết chương trình theo C/C++ hay Java hay Python, một thời gian sau chắc chắn nó sẽ có vấn đề. Kể cả những ngôn ngữ bậc cao càng khiến ta khó phân tích chính xác số lượng tính toán trong thuật toán đó. Mà theo phân tích của Knuth, đó phải là những phân tích chính xác. Ngôn ngữ của MIX cũng rất dễ đọc, không đến nối rắc rối như mọi người tưởng. Đồng thời, việc đọc code bằng mã máy khuyến khích người đọc “vọc” với thuật toán được ghi. Thêm nữa, “ngôn ngữ bậc cao” mà Knuth dùng chính là tiếng Anh.

2. Trong biểu đồ sử dụng sách của mình, Knuth có nói rằng nếu các công thức toán “is all Greek to you” ta chỉ cần xem qua và nắm được kết quả cơ bản mà phần đó đề cập, và hầu như các kết quả đó được nói ở đầu mục hoặc cuối mục.

3. Với bài tập của TAoCP, Knuth đề xuất hệ thống phân loại. Hơn hết, hệ thống này nhằm giúp cho người đọc, với thời lượng cho phép của mình, lựa chọn và làm những bài bản thân nghĩ là phù hợp. Bởi thật sự những bài với độ khó lớn hơn 45, dù là không dính đến toán, M hay HM đều cần rất nhiều thời gian nghiên cứu. Bản thân mình nghĩ nếu giải được những bài đó thì có thể hoàn thành được PhD của Computer Science rồi. Nhưng mình vẫn nghĩ người đọc nên xem qua các câu hỏi này,  vì nó chính là biên giới tri thức trong khoa học máy tính.

4. Knuth nêu rõ trong cuốn sách của mình, mục đích của cuốn sách phục vụ: (1) là tài liệu tham khảo chính xác và chi tiết về phân tích thuật toán, (2) là một sách giáo khoa  tự học  dành cho những người đam mê về thuật toán cũng như Khoa Học Máy Tính. Nếu bạn mua TAoCP chỉ với giá trị tham khảo thì đó hoàn toàn là mục đích chính xác của bộ sách: mình đặc biệt thích phần tra khảo về lịch sử. Đúng ra, Don Knuth rất quan tâm đến lịch sử của Khoa Học Máy Tính, đó là lí do vì sao trong sách đề cập các thông tin lịch sử lại chi tiết đến như vậy. Nhưng ngoài ra, phần bài tập lẫn lời giải, mà thường chiếm đến ¹⁄₃ cuốn sách, nói lên rằng Knuth mong mỏi cuốn sách này sẽ là một tài liệu học tốt dành cho mọi người.

Kế hoạch của mình rất đơn giản: Chinh phục TAoCP đồng thời giúp mọi người dễ dàng tiếp cận với tài liệu quý giá này. Quá nhiều bạn đọc dường như sợ tiếp cận cuốn sách bởi những “myth” vừa nêu, đồng thời, chinh phục TAoCP là một hành trình thực sự thú vị. Mình đã học được rất nhiều điều thông qua cuốn sách. Những ngày đầu đại học khi lần đầu cầm trong tay Volume 1, mình mới thực sự hiểu “computer science” là một khoa học đầy hấp dẫn, và nó cũng rất “art”.

Mình đồng ý với quan điểm của Knuth, người làm về phân tích thuật toán hạnh phúc gấp đôi những ngành khác: họ chiêm nghiệm được những công thức toán phức tạp để tính toán độ phức tạp, phân tích thuật toán, đồng thời họ cảm nhận được tính hiệu quả của thuật toán đó trong thực tế. Ta chắc chắn không cần bận tâm đến câu “học toán để làm gì”, bởi khi tiếp cận với phân tích thuật toán, ta cảm nhận ngay được ích lợi của toán học, thuật toán cũng như vẻ đẹp của thuật toán khi ta cài đặt và sử dụng trong thực tiễn.

---

Một chút về dự án này

Ngoài những chi tiết ở trên, một phần khiến TAoCP khó đọc ở chỗ thông tin được Knuth viết tương đối cô đặc. Chính vì lẽ đó mà đôi khi có những phần tương đối khó hiểu đối với những bạn tìm hiểu về khoa học máy tính và chưa có nhiều kiến thức trước đó. Mục tiêu của project này nhằm giúp các bạn dễ tiếp cận hơn với sách, đồng thời giải thích các phần bài tập, bởi mình thấy Knuth viết phần Solutions cực kì gọn, và đôi khi cũng không biết là từ đâu lại có những đáp số đó. Ngoài ra, tìm hiểu về TAoCP cũng chính là tìm hiểu các thuật toán kinh điển, các bài toán làm trên nền tảng của Khoa Học Máy Tính cũng như đây là nguồn tài liệu rất quý giá để mài dũa “algorithmic thinking”. Một lý do nữa khiến mình có hứng thú để làm đó là hiện nay tuy có khá nhiều blog, repo trên Github note lại TAoCP nhưng chưa có ai viết đầy đủ, hoặc chi tiết.

Loạt bài viết cùa mình yêu cầu người đọc đã đọc qua trước chương hoặc phần mình đề cập trong bài viết, trong các bài viết mình sẽ chú trọng đến các chi tiết sau:

• Các chi tiết tương đối khó hiểu.
• Phần bài tập.
• Các state-of-the-art hiện nay.
• Các thông tin lý thú liên quan đến chủ đề đó.

Mình có tích hợp plugin Hypothesis giúp các bạn có thể highlight, viết note trên blog của mình, đồng thời phần comment để mọi người thuận tiện trao đổi với nhau cũng như giúp mình update các lỗi có trong bài viết.

Kinh nghiệm cá nhân

Một số kinh nghiệm bản thân khi mình đọc TAoCP, thực ra đến tận bây giờ bản thân mình mới dành thời gian với cuốn sách, trước đây mình chủ yếu dùng tham khảo là chính:

• Luôn có giấy và bút bên cạnh để có thể:
  • Chạy “chay” các thuật toán.
  • Làm bài tập.
  • Hiểu công thức đang muốn nói điều gì.
• Có một sổ tay ghi chú. Một số chỗ Knuth viết rất cô đọng và mình nghĩ chỉ có cách ghi note lại mới thực sự nhớ và hiểu được.
• Thử implement thuật toán bằng một ngôn ngữ ưa thích. Quan điểm của mình thì C hoặc C++ là phù hợp nhất. C thì có thể gần với mục đích nhất, trong khi đó C++ sẽ tiện hơn.

Một chút về phần Preface (Volume I)

Tuy chỉ là phần lời nói đầu, nhưng tác giả đã đề cập đến khá nhiều câu chuyện hay ho mà mình có thể tóm lượt như sau:

• Thuở xa xưa khi Khoa học máy tính mới hình thành, có 3 ngành chính thịnh hành lúc bấy giờ: numerical analysis, artificial intelligent và language theory. Chính Knuth là người đã khai sinh ra nhánh “analysis of algorithms”. Trước đó đã có các công trình của Alan Turing, Jon von Neumann tuy nhiên đó là những nghiên cứu rời rạc và không có một hệ thống hoàn chỉnh.
• Trong phần preface, Knuth đề cập rằng những phân tích của mình “non-numerical” bởi vì nó quan tâm đến các đối tượng rời rạc nhiều hơn. Nếu chọn “nonnumerical analysis” thì lại hơi mang tính tiêu cực (có lẽ do tiền tố “non” trong đó). Trong khi đó “programming techniques” thì lại quá hẹp về 1 phần trong lĩnh vực. Đó là lí do mà ông chọn từ “analysis of algorithms”.
• Việc chọn mã máy MIX cũng được ông phân tích khá rõ trong phần này. Thực sự những lý do đó hoàn toàn thuyết phục. Mình nghĩ một ngôn ngữ gần nhất ông có thể dùng đó là C. Nhưng nếu như vậy ông phải định nghĩa số chỉ thị cho từng câu lệnh trong C, điều này mình nghĩ không đơn giản lắm.
• Người đồng hành với ông trong cuốn sách này là Robert W. Floyd , ông chính là tác giả thuật toán “Floyd-Warshall”, thuật toán phát hiện vòng trong danh sách liên kết cũng như những đóng góp tiêu biểu của ông trong “program verificaition”.

Ghi chú

• Một bài nói của Don Knuth về mối quan tâm của ông với lịch sử khoa học máy tính: [link]
• Phỏng vấn Don Knuth. Có khá nhiều chi tiết thú vị về suốt cuộc đời làm nghiên cứu của ông (Ông mất chỉ 1 giờ để hoàn thành luận án tiến sĩ của mình). [link]. Mình sẽ có một bài tóm tắt về cuộc phỏng vấn đầy hấp dẫn này.

Tài liệu

Một số tài liệu mình thấy là khá hay để có thể bắt đầu tìm hiểu công trình của Knuth. Dưới đây là danh sách các sách mình đang/ đã đọc. Không theo lối thông thường mà dân tình hay truyền nhau sách này hay sách kia hay mà chưa bao giờ đụng vô, mình chỉ review những sách mình đã tiếp xúc:

1. Algorithms - Sedgewick: cuốn sách lập trình mình tâm đắc nhất khi cung cấp cả code lẫn những phân tích chi tiết.
2. Introduction to Analysis of Algorithms - Sedgewick & Flajolet: dẫn nhập trực tiếp vào công trình của Knuth, mình nghĩ đây là bước đệm quan trọng, cuốn sách này thực sự rất hay.
3. Conrete Mathematics - Knuth: Không chỉ dần cho dân Toán, cuốn sách này đọc rất “đã” (Mình đang cố gắng đọc và làm nhiều bài tập nhất có thể)