"Thuật toán" được dịch từ chữ "Algorithm" (tiếng Anh) có nguồn gốc từ chữ Al-Khwarizmi, tên của một học giả A-rập sống vào thế kỷ 9, tác giả của quyển sách al-jabr wa'l muqabalah khởi nguồn của các sách giảng dạy về đại số hiện nay. Al-Khwarizmi đã nhấn mạnh đến tầm quan trọng của các phương pháp thủ tục dùng để giải quyết các bài toán. Phương pháp được đặt theo tên Al-Khwarizmi - algorithm, hay thuật toán - đã có những bước tiến đầy ấn tượng cùng với ngành công nghệ thông tin trong thế kỷ qua. Dưới đây là 10 thuật toán có "ảnh hưởng lớn nhất đến sự phát triển của khoa học và công nghệ", theo Computing in Science & Enginering (ấn phẩm hợp tác của học viện Vật Lý Mỹ và IEEE Computer Society).
1 1946: John von Neumann, Stan Ulam và Nick Metropolis, cả ba đều thuộc viện nghiên cứu Los Alamos Scientific Lab., xây dựng thuật toán Metropolis, còn được biết đến với tên là phương pháp Monte Carlo. Mặc dù sử dụng các quá trình ngẫu nhiên, thuật toán này đưa ra một cách thức hiệu quả để đi "đến gần" lời giải cho các bài toán quá phức tạp, khó có thể giải một cách chính xác.
2 1947: George Dantzig thuộc công ty RAND tạo thuật toán đơn hình cho quy hoạch tuyến tính (Simplex Method for Linear Programming). Một giải pháp hay cho bài toán phổ biến trong hoạch định và ra quyết định.
3 1950: Magnus Hestenes, Eduard Stiefel và Cornelius Lanczos, cả ba đều thuộc học viện Numerical Analysis, phát triển thuật toán lặp không gian con Krylov. Thuật toán này cho phép giải nhanh các phương trình tuyến tính rất phổ biến trong tính toán khoa học.
4 1951: Alston Householder thuộc viện nghiên cứu Oak Ridge National Lab. xây dựng phương pháp phân rã tính toán ma trận, gồm các kỹ thuật dùng cho đại số tuyến tính.
5 1957: John Backus phụ trách một nhóm nghiên cứu tại IBM phát triển trình biên dịch tối ưu Fortran cho phép chuyển mã lệnh cấp cao thành mã máy một cách hiệu quả. Đây là một trong những sự kiện quan trọng nhất trong lịch sử lập trình máy tính.
6 1959: J.G.F.Francis thuộc công ty Ferranti giới thiệu thuật toán QR, một trong những phép tính ma trận quan trọng nhất.
7 1962: Tony Hoare thuộc công ty Elliott Brothers giới thiệu thuật toán Quicksort, cho phép xử lý hiệu quả cơ sở dữ liệu lớn.
8 1965: James Cooley thuộc trung tâm nghiên cứu T.J. Watson của IBM và John Turkey thuộc đại học Princeton và viện nghiên cứu AT&T Bell Lab công bố thuật toán biến hình Fourier nhanh (Fast Fourier Transform). Đây có lẽ là thuật toán phổ biến nhất hiện nay, nó cho phép phân tích các dạng sóng bất kỳ (như âm thanh) thành các thành phần tuần hoàn.
9 1977: Helaman Ferguson và Rodney Forcade thuộc đại học Brigham Young đưa ra thuật toán phát hiện quan hệ số nguyên. Đây là phương pháp tìm lời giải nhanh cho các phương trình đơn giản ràng buộc bởi tập hợp các số dường như không có liên quan với nhau. Thuật toán này rất hữu ích trong việc làm đơn giản các phép tính lược đồ Feynman theo lý thuyết lượng tử.
10 1987: Leslie Greengard và Vladimir Rokhlin của đại học Yale (Mỹ) đưa ra thuật toán đa cực nhanh (Fast Multipole Method). Đây là bước đột phá trong việc giải quyết độ phức tạp của các phép tính bậc N, ứng dụng từ các bài toán thiên văn đến phân tử.
Cả 10 thuật toán trên đều ra đời trong thế kỷ 20. Những thuật toán nào của thể kỷ 21 sẽ gia nhập danh sách này? Câu trả lời có lẽ phải đợi hàng chục hoặc cả trăm năm nữa.
2. The real 10 algorithms that dominate our world
In Vietnamese translation:
http://www.baigiangtoanhoc.com/cau-chuyen-toan-hoc/10-thuat-toan-co-ban-thong-tri-khoa-hoc-the-gioi.html
No comments:
Post a Comment