Những bài báo có ảnh hưởng nhất trong lịch sử khoa học máy tính
(terriblesoftware.org)- 7 bài báo khoa học máy tính từ năm 1936 đến 1998 đã định hình các tầng cốt lõi của điện toán hiện đại: khả năng tính toán, lý thuyết thông tin, cơ sở dữ liệu, độ phức tạp, Internet, Web và tìm kiếm
- Bài báo năm 1936 của Alan Turing, với Turing Machine, đã phân biệt những gì máy móc về nguyên lý có thể và không thể tính toán, trở thành điểm khởi đầu của mô hình tính toán hiện đại
- Claude Shannon, Edgar F. Codd và Stephen A. Cook lần lượt tạo ra ngôn ngữ chung cho truyền thông, dữ liệu và độ khó của bài toán thông qua đo lường thông tin và sửa lỗi, mô hình dữ liệu quan hệ, NP-completeness và SAT
- Các bài báo của Vinton G. Cerf và Robert E. Kahn, Tim Berners-Lee, Sergey Brin và Larry Page đã định hình cấu trúc của kết nối mạng, liên kết tài liệu và tìm kiếm web bằng TCP/IP, World Wide Web và PageRank
- Nhìn cả danh sách bổ sung gồm Lisp, lập trình có cấu trúc, đồng hồ logic, độ phức tạp phần mềm và Transformer, việc hiểu khái niệm nền tảng trở thành lợi thế cạnh tranh bền lâu hơn so với các công cụ mới
Tiêu chí lựa chọn và dòng chảy tổng thể
- Danh sách này không phải một bảng xếp hạng tuyệt đối, mà là lựa chọn mang tính chủ quan dựa trên mức độ ảnh hưởng đến thế giới ngày nay
- 7 bài được sắp xếp theo thời gian, cho thấy dòng chảy nối tiếp từ tính toán, truyền thông, lưu trữ dữ liệu, độ khó tính toán, mạng, Web đến tìm kiếm
- Dù các ngôn ngữ mới, tiến bộ AI, bước nhảy lượng tử và framework JavaScript liên tục xuất hiện, nền tảng của điện toán hiện đại vẫn còn những khái niệm do các bài báo này tạo ra
1. “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936)
- Vào thập niên 1930, Alan Turing đặt nền móng cho việc máy tính về mặt lý thuyết có thể làm gì thông qua Turing Machine giả tưởng
- Mô hình cốt lõi gồm một băng, đầu đọc/ghi và một tập hữu hạn các trạng thái
- Mô hình này định nghĩa bài toán nào có thể giải được theo nghĩa cơ học, và bài toán nào thì không
- Mọi ngôn ngữ lập trình và mã nguồn đều vận hành trong các quy tắc mà Turing đã định nghĩa; ngay cả khi nói về điện toán lượng tử, người ta vẫn tham chiếu đến những ranh giới mà Turing nêu ra
- Đọc thêm:
2. “A Mathematical Theory of Communication” (1948)
- Claude Shannon đã xây dựng lý thuyết thông tin để xử lý thông tin một cách chặt chẽ, đồng thời hệ thống hóa các khái niệm như bit, entropy và noisy channel
- “Thông tin” trừu tượng trở thành một đối tượng có thể đo lường, đặt nền móng cho nén dữ liệu và mã sửa lỗi
- Từ việc gửi tín hiệu vào không gian cho đến streaming Netflix, những ý tưởng này được dùng để đóng gói dữ liệu hiệu quả và bảo vệ dữ liệu khỏi lỗi
- Các hình thức liên lạc hằng ngày như gửi tin nhắn, streaming video hay gọi FaceTime cũng vận hành trên các khái niệm của Shannon
- Đọc thêm:
3. “A Relational Model of Data for Large Shared Data Banks” (1970)
- Edgar F. Codd đề xuất mô hình quan hệ để lưu trữ và truy vấn dữ liệu quy mô lớn
- Ý tưởng cốt lõi là lưu dữ liệu trong các bảng và thao tác bằng các phép toán logic
- Thiết kế này dẫn đến SQL và họ cơ sở dữ liệu quan hệ, làm nền tảng cho ngân hàng, website bán lẻ và hệ thống doanh nghiệp
- Ngay cả trong thời đại NoSQL, các khái niệm tổ chức dữ liệu như bảng, schema và tính nhất quán vẫn gắn với mô hình của Codd
- Đọc thêm:
4. “The Complexity of Theorem-Proving Procedures” (1971)
- Bài báo của Stephen A. Cook bàn về việc một số bài toán tính toán cực kỳ khó, đồng thời giới thiệu khái niệm NP-completeness
- Cook chứng minh Boolean satisfiability problem, tức SAT, là NP-complete
- Một ngôn ngữ chung để nói về độ khó của bài toán đã ra đời: nếu có thể giải SAT thật nhanh, thì nhiều bài toán khó khác cũng có thể được giải theo
- Cách nói “NP-hard”, hay những tình huống tối ưu hóa đường đi khiến CPU vất vả, đều nối tiếp ảnh hưởng của bài báo này
- Khái niệm này tác động lớn đến thuật toán, mật mã học và việc tìm kiếm lời giải hiệu quả hoặc lời giải xấp xỉ
- Đọc thêm:
5. “A Protocol for Packet Network Intercommunication” (1974)
- Bài báo của Vinton G. Cerf và Robert E. Kahn đặt nền tảng cho TCP, nhằm kết nối các mạng riêng lẻ với nhau
- Một ngôn ngữ phổ quát để các mạng khác nhau có thể giao tiếp đã xuất hiện; dữ liệu được chia thành các gói nhỏ, đi qua nhiều tuyến đường rồi được lắp ráp lại ở phía bên kia
- Nhờ tính linh hoạt này, kết nối toàn cầu trở nên khả thi mà không cần một mạng đơn khổng lồ duy nhất
- Các hoạt động như duyệt web, gửi email hay đăng nhập website ngân hàng đều dựa vào việc TCP/IP di chuyển bit một cách đáng tin cậy
- Một số ứng dụng thời gian thực dùng UDP, nhưng ý tưởng cốt lõi về mạng dựa trên IP mà Cerf và Kahn đưa ra đã gắn kết các thiết bị dưới một mạng toàn cầu
- Đọc thêm:
6. “Information Management: A Proposal” (1989)
- Sau khi máy móc đã có thể giao tiếp dễ dàng hơn, Tim Berners-Lee đề xuất hướng đi cho World Wide Web để con người có thể sử dụng dễ dàng hơn
- Ý tưởng cốt lõi là một hệ thống siêu văn bản toàn cầu với hyperlink, URL và HTTP
- Khi các tài liệu trên khắp thế giới không còn bị cô lập mà được liên kết với nhau, Internet trở thành một hình thức mà không chỉ nhà khoa học mà cả người dùng phổ thông cũng có thể khám phá
- Hạt giống của các trải nghiệm web như mạng xã hội, mua sắm trực tuyến hay những bài blog đọc lúc 3 giờ sáng bắt nguồn từ đề xuất này
- Đọc thêm:
7. “The Anatomy of a Large-Scale Hypertextual Web Search Engine” (1998)
- Sergey Brin và Larry Page đã tạo ra cách tiếp cận dựa trên phân tích liên kết để xử lý web khi số lượng liên kết và trang tăng bùng nổ; điều này phát triển thành công cụ tìm kiếm Google
- PageRank, ý tưởng cốt lõi, xem liên kết không chỉ là yếu tố tính toán từ khóa mà còn là một phiếu bầu về mức độ tin cậy
- Cách làm này cải thiện mạnh mẽ mức độ liên quan của kết quả tìm kiếm, biến web thành một không gian có thể tìm kiếm được
- Trải nghiệm nhập câu hỏi vào Google và nhận câu trả lời ngay lập tức vận hành trên PageRank cùng nhiều đổi mới sau đó
- PageRank đã định nghĩa lại cách tìm kiếm thông tin trực tuyến và mở ra một kỷ nguyên mới của các công nghệ dựa trên dữ liệu như quảng cáo, phân tích và machine learning
- Đọc thêm:
5 bài suýt được đưa vào phần chính
- “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) – John McCarthy
- Đã giới thiệu Lisp và phong cách lập trình hàm, phong cách này vẫn còn hiện diện trong các ngôn ngữ và framework hiện đại
- “Go To Statement Considered Harmful” (1968) – Edsger Dijkstra
- Phê phán
gotovì tạo ra mã lộn xộn, thiếu cấu trúc, qua đó châm ngòi cho cuộc cách mạng lập trình có cấu trúc
- Phê phán
- “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) – Leslie Lamport
- Trong hệ phân tán, không thể đồng bộ hoàn hảo đồng hồ thực, vì vậy cần đồng hồ logic
- “No Silver Bullet—Essence and Accident in Software Engineering” (1986) – Fred Brooks
- Cho rằng không có một phương pháp kỳ diệu duy nhất nào có thể giải quyết độ phức tạp bản chất của phát triển phần mềm
- “Attention Is All You Need” (2017) – Vaswani et al.
- Trình bày kiến trúc Transformer đứng sau GPT và nhiều mô hình AI nổi tiếng
Ảnh hưởng còn lại của các khái niệm nền tảng
- Ngày nay, các ngôn ngữ mới, đột phá AI, bước nhảy lượng tử và những framework JavaScript xuất hiện hằng tuần vẫn liên tục tràn tới
- Nếu không hiểu các khái niệm cốt lõi như cấu trúc dữ liệu, thuật toán và web đến từ đâu, ta sẽ rơi vào tình trạng chỉ liên tục chất thêm công cụ mới
- 7 bài báo này cùng các bài bổ sung giúp nhìn lại những ý tưởng đã trở thành nền móng cốt lõi của điện toán hiện đại
1 bình luận
Ý kiến trên Hacker News
Cũng đáng đưa vào Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush), Can Programming Be Liberated from the von Neumann Style (Backus)
Và bài giảng này trông cũng hay: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
“Bài giảng này đề cập đến những bài báo mà mọi nhà khoa học máy tính đáng lẽ nên đọc, từ thập niên 1930 đến nay. Đây là một trải nghiệm tổng hợp giúp sinh viên nâng cao ngành khoa học máy tính có cái nhìn bao quát toàn bộ lĩnh vực; không chỉ là một phần tổng quan đơn thuần, mà là cách để họ trải nghiệm lại quá trình sáng tạo ra lĩnh vực đó. Mục tiêu là tái hiện với tốc độ nhanh toàn bộ quá trình tiến hóa của khoa học máy tính cho những sinh viên đã có nền tảng nhất định, qua đó xây dựng một góc nhìn thống nhất về lĩnh vực này”
Danh sách này tạo cảm giác là một tổ hợp hơi kỳ lạ. Không rõ là đang chọn các bài báo có ảnh hưởng đến khoa học máy tính, tức lý thuyết tính toán, hay các bài báo có ảnh hưởng đến công nghệ, hay chỉ đơn giản gọi “mọi thứ liên quan đến máy tính” là khoa học máy tính
Bài báo của Turing là nền tảng của khoa học máy tính, nhưng tôi không chắc công nghệ có phát triển khác đi nếu không có bài đó hay không. Phần lớn kỹ sư phần mềm thậm chí chưa từng đọc nó. Ngược lại, chuẩn IP là một nền móng kỹ thuật, nhưng gần như không có nội dung khoa học; nó giống một đặc tả giao thức tương đối đơn giản mà bạn cần biết nếu làm các việc quanh mạng
“On Computable Numbers, with an Application to the Entscheidungsproblem” đến nay đã gần 90 năm tuổi nhưng vẫn đúng và còn hiệu lực như hồi đó. Tôi không chắc PageRank hiện nay còn liên quan như năm 1998 hay không, chưa nói đến 50 năm nữa
Đây là một danh sách bài báo hay. Tôi đã đọc 5 trong 7 bài trong danh sách; những bài chưa đọc là của Cerf và Kahn, và của Berners-Lee
Bài báo về tính khả tính của Turing đặc biệt khó theo dõi, vì ông đặt tên đủ thứ bằng chữ hoa kiểu Gothic, mà các chữ đó trông đều na ná nhau. Tôi phải xem tài liệu bổ trợ mới đọc nổi bài báo; nếu là bây giờ, tôi khuyên nên đọc cùng sách chú giải của Charles Petzold https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
Bài báo về NP-đầy đủ của Cook cũng khó tương tự, và cũng cần tài liệu bổ trợ như bài của Turing. Nếu là bây giờ, tôi khuyên nên đọc trước một sách nhập môn độ phức tạp tính toán có trình bày theo chứng minh của Cook
Bài báo của Shannon rõ ràng và được viết đẹp như một tác phẩm nghệ thuật, nhưng hoàn toàn không phải thứ có thể đọc nhẹ nhàng
Theo trí nhớ của tôi thì bài của Brin và Page, và bài của Codd không quá khó, nhưng để hiểu công trình của Brin và Page thì cần một mức kiến thức đại số tuyến tính nhất định
“Thuật toán lặp đơn giản” là cách tìm điểm bất động của một ánh xạ co tùy ý, dù tuyến tính hay không. Việc nó cũng là eigenvector thực ra gần như gây nhiễu, và người hiểu rõ sẽ không dùng khử Gauss
.tex, việc nhờ GPT đổi tên biến cho dễ đọc hơn, thành các tên dài hơn một chữ cái, sẽ hữu íchNếu bạn nghĩ A Mathematical Theory of Communication của Shannon là đóng góp nền tảng nhất của ông cho khoa học máy tính, thì có lẽ bạn chưa xem luận văn thạc sĩ ông viết trước đó 10 năm
https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
Ông đã chỉ ra rằng có thể định nghĩa logic Boolean bằng các phần tử chuyển mạch của mạch điện, tức transistor
Tất nhiên tôi không có ý hạ thấp tầm quan trọng của công trình đặt nền móng cho toàn bộ lý thuyết thông tin
Mô tả “cho thấy nếu một thứ có thể tính được thì về nguyên tắc máy móc có thể xử lý nó, và phác họa một ‘Turing Machine’ giả tưởng” không phải là điều Turing đã chứng minh
Điều ông chứng minh trong bài báo đó là có những bài toán mà Turing Machine không thể giải, và do đó có lẽ không máy nào có thể giải. Entscheidungsproblem trong tiêu đề, tức bài toán quyết định, chính là bài toán đó
Điều văn bản gốc đang ám chỉ là cái gọi là Church-Turing Thesis, đúng nghĩa gần với một luận đề. Trên thực tế không thể chứng minh nó, nhưng việc trong gần 100 năm qua chưa tìm được hệ tính toán nào mạnh hơn Turing Machine là lý do rất mạnh để tin vào nó
Thay vì tạo ra một cỗ máy chứa mọi chân lý đã biết, việc tìm kiếm trí tuệ nhân tạo dựa trên máy móc hiện đại nhìn chung gần với việc lục lọi bình luận của con người để tạo ra một cỗ máy feuilleton đã được sắp xếp hơn, khác với cách tiếp cận tiên đề kiểu Leibniz
Làm tốt lắm. Tôi cũng đang tự làm một thứ tương tự nên xin đề xuất thêm vài bài
RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
MapReduce: MapReduce: simplified data processing on large clusters (2008)
Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
Lan truyền ngược: Learning representations by back-propagating errors (1986)
Logic Hoare: An Axiomatic Basis for Computer Programming (1969)
Bài Evolution of Unix time-sharing systems khét tiếng của Dennis Ritchie đâu rồi?
https://www.bell-labs.com/usr/dmr/www/cacm.pdf
https://web.archive.org/web/20070926212100/http://www.almade...
Vì mọi người đều đang bổ sung đề xuất của mình, tôi cũng thêm một bài: Cook là người đầu tiên giới thiệu tính NP-đầy đủ, nhưng bài báo của Karp trình bày 21 bài toán có thể được quy giảm trong thời gian đa thức về 3SAT cũng là một nền tảng lớn, khơi dậy sự quan tâm rộng rãi hơn đối với lý thuyết của Cook
https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...
New Directions in Cryptography (1976) của Diffie và Hellman bị bỏ sót à?
Không phải là bài báo học thuật, nhưng Why Software Is Eating the World của Marc Andreessen và thư gửi cổ đông đầu tiên năm 1997 của Amazon cũng đáng được nhắc riêng
“Các công ty trong mọi ngành phải giả định rằng cuộc cách mạng phần mềm đang đến. Điều này bao gồm cả những ngành hiện nay vốn đã dựa trên phần mềm”
https://a16z.com/why-software-is-eating-the-world/
“Nhưng hiện tại là Day 1 của Internet, và nếu chúng ta thực thi tốt, cũng là Day 1 đối với Amazon.com”
https://www.aboutamazon.com/news/company-news/amazons-origin...