10 thuật toán hàng đầu của thế kỷ 20

1. Thuật toán Monte Carlo(1946) do John von Neumann, Stan Ulaur và Nick Metropotis tất cả đều làm việc tại Los Alamos Scientific Laboratory. Đấy là một thuật toán cho phép xấp xỉ nghiệm của nhiều lớp bài toán tổng quát, dựa trên các phép thử ngẫu nhiên. Chính vì vậy mà thuật toán được mang tên một thành phố của Pháp nơi có nhiều sòng bạc nổi tiếng.

2. Thuật toán đơn hình giải quy hoạch tuyến tínhdo George Dantzig (Rand Corporation) công bố năm 1947. Đây là một trong những thuật toán được sử dụng rộng rãi và thành công nhất từ khi nó ra đời, do các bài toán quy hoạch tuyến tính xuất hiện trong mọi lĩnh vực của khoa học kỹ thuật, kinh tế... Thuật toán này tuy có độ phức tạp tính toán theo cấp mũ, tuy nhiên nó tỏ ra rất hiệu quả trong thực tế. Gần đây tuy đã có những thuật toán đa thức giải quy hoạch tuyến tính, nhưng phương pháp đơn hình vẫn được sử dụng nhiều hơn cả.

3. Thuật toán không gian con Krylovhoặc còn gọi là phương pháp Gradient liên hợp do Magnus Hestenes, Eduard Stiefel và Cornelias Lanczos (National Bureau of Standard) đề xuất năm 1950 Thuật toán này cho phép giải hệ phương trình A _x=b. Đây là một phương pháp lặp có dạng K _x1+t= K _xt+ b – Atrong đó K là một ma trận xấp xỉ A. Việc tìm K đưa đến việc nghiên cứu không gian con Krylov (tên nhà toán học Nga Nicolai Krylov). Lancos đã phát hiện ra một cách xây dựng một cơ sở trực giao cho một không gian con Krylov cho các ma trận đối xứng. Sau đó Hestenes và Stiefel đã đề nghị một phương pháp hướng gradient liên hợp cho những hệ với ma trận đối xứng và xác định dương. Các phương pháp hướng gradient liên hợp cũng đã được sử dụng giải các bài toán tối ưu, đặc biệt là quy hoạch toàn phương.

4. Phương pháp phân rã ma trậndo Alston Householder (Oak Ridge National Laboratory) đưa ra năm 1951. Kỹ thuật phân tích ma trận về các dạng đặc biệt như tam giác, dạng đường chéo, dạng khối v.v... tỏ ra rất hữu ích trong việc tính toán với các ma trận. Kỹ thuật này đã cho phép xây dựng những phần mềm máy tính rất hiệu quả để tính toán với các ma trận.

5. Ngôn ngữ FORTRANdo John Backus và cộng sự thuộc IBM đưa ra năm 1957 là một bước ngoặt trong sự phát triển ngôn ngữ dịch cho máy tính. Với FORTRAN con người có thể nói với máy tính tất cả những gì muốn máy tính thực hiện mà không cần can thiệp trực tiếp vào ngôn ngữ của máy.

6. Thuật toán QRdo J.G.F. Francis (Ferranti Ltd London) đưa ra trong những năm 1959-1961. Đây là một thuật toán ổn định cho phép tính các giá trị riêng. Thuật toán dựa trên một kỹ thuật lặp cho phép phân tích một ma trận thành tích của một ma trận trực giao và một ma trận tam giác trên, qua đó có thể tính các giá trị riêng rất hiệu quả. Ngày nay với thuật toán này người ta có thể tính được các giá trị riêng của các ma trận cỡ rất lớn.

7. Thuật toán sắp xếp nhanhdo Tony Heare (Elliott Brothers Ltd London) giới thiệu năm 1961. Xắp xếp n đối tượng theo một thứ tự nào đó là một bài toán quan trọng trong nhiều lĩnh vực, đặc biệt trong sự hoạt động của máy tính. Thuật toán thực hiện một cách rất trực giác và trực tiếp. Nó cũng đã góp phần rất lớn thúc đẩy việc nghiên cứu độ phức tạp tính toán.

8. Năm 1965 James Cooly (IBM) và John Tuckey (Đại học Princeton) phát minh phép biến đổi Fourier nhanh (FFT). Tư tưởng của FFT dựa theo phương pháp của Gauss khi ông tính toán một số quỹ đạo của các hành tinh. Tuy nhiên trong bài báo của mình Cooly và Tuckey đã giải thích rõ việc thực hiện phép biến đổi Fourier một cách nhanh chóng và dễ dàng. FFT cũng đã được áp dụng rất hiệu quả trong nhiều bài toán quan trọng, trong đó có việc tính toán với lược đồ Feynman trong lý thuyết lượng tử.

9. Thuật toán phát hiện quan hệ nguyên(IRD algorithm) do Helâmn Feguson và Rodney Forcade (Đại học Bringham Young) đưa ra năm 1977. Bài toán quen thuộc: cho nsố thực a ₁...a _n, hãy tìm các nghiệm nguyên x1,..., xn không phải tất cả là 0 sao cho a ₁x ₁+...+ a _nx _n= 0. Với n=2thuật toán Ơclit cho phép giải bài toán sau một số hữu hạn trước khi a ₁/a ₂hữu tỉ. Nếu thuật toán Ơclit không hữu hạn hoặc đơn giản là ta cấch dừng thuật toán lại, thì nó sẽ cho một cận của lời giải theo quan hệ nguyên nhỏ nhất. Sự tổng quát hoá của Ferguson và Forcade mặc dù rất phức tạp và khó hiểu nhưng đã tỏ ra rất hiệu quả. Thuật toán đã được dùng để tìm chính xác những hệ số của những đa thức thoả mãn bởi những điểm rẽ nhánh bậc 3 và 4 trong lý thuyết rẽ nhánh. Thuật toán này cũng làm cho việc tính toán với các lược đồ Feynman trong lý thuyết lượng tử trở nên đơn giản hơn nhiều.

10. Thuật đoán đa cực nhanh(fast multipole algorithm) do Leslie Greengard và Vladimir Rokhlin (Đại học Yale) phát minh năm 1987. Thuật toán này đã giải được bài toán mô phỏng N-vật thể, là một bài toán đau đầu nhất trong nhiều năm. Để tính toán chính xác lực tương tác giữa N vật thể (các hành tinh hoặc các nguyên tử trong phân tử) người ta đã phỏng đoán rằng cần đến 0(N ²) phép tính cho mỗi cặp vật thể. Thuật toán đa cực nhanh đã tính được với 0(N) phép tính. Thuật toán đa cực nhanh còn cho phép phân rã các vật thể theo từng nhóm để tính toán, do đó cho phép giải quyết bài toán với một số lớn các vật thể. Một ưu điểm nổi bật nữa của thuật toán đa cực nhanh là nó cho phép xử lý sai số dồn, là một vấn đề mà nhiều phương pháp khác không làm được.

Trên đây chỉ là những điều rất sơ lược về 10 thuật toán có ảnh hưởng lớn nhất của thế kỷ 20, đã được bình chọn bởi một nhóm các nhà khoa học. Việc tìm hiểu chi tiết về các thuật toán này sẽ cần đến nhiều bài báo. Nếu được đề nghị thêm 2 hoặc 5 thuật toán nữa thì bạn sẽ đề nghị những thuật toán nào? Hay bạn có thể dự đoán những điều mới lạ sẽ đến trong thế kỷ 21 trong việc phát minh các thuật toán. Câu hỏi này thật sự là khó trả lời cho một thời gian là một thế kỷ. Tuy nhiên điều chắc chắn rằng thế kỷ 21 sẽ không thể là một trăm năm bình lặng và cũng không thể là một thời kỳ mờ nhạt đối với khoa học.