Thuật toán – theo nghĩa thông thường là cách thức thực hiện một công việc hay giải quyết một bài toán nào đó – hiện diện khắp nơi trong ngành công nghiệp điện toán. Những thuật toán xác định cách thức người dùng liên lạc, làm việc và cả giải trí. Những thuật toán làm thay đổi thế giới đôi khi không phát sinh từ công việc nghiên cứu mà chính từ yêu cầu thực tiễn.
Có những thuật toán nổi tiếng hơn những thuật toán khác. Có thể kể một số thuật toán nổi tiếng nhất như TCP/IP xác định cách thức truyền dữ liệu trên Internet; Cơ chế tìm kiếm Google xác định cách thức hàng triệu người tìm thông tin trực tuyến; HTTP, nền tảng của World Wide Web và đóng vai trò to lớn trong cuộc cách mạng Internet vào giữa thập niên 1990. Một số thuật toán khác ít nổi tiếng hơn nhưng có vai trò quan trọng không kém, ví dụ thuật toán đồng bộ tất cả đồng hồ trên Internet của Dave Mills thuộc đại học Delaware.
Truyền thông
Một trong những thuật toán quan trọng nhất là TCP/IP – Transmission Control Protocol/Internet Protocol – được phát kiến vào lúc mà đa phần máy tính là những cỗ máy kềnh càng đặt trong phòng lạnh. Vào những năm 1960, cơ quan nghiên cứu của bộ quốc phòng Mỹ (ARPA) phối hợp với nhiều trường đại học thành lập nhóm nghiên cứu tạo hệ thống kết nối các mạng khác nhau dựa trên các chuẩn mở.
Năm 1969 – cùng năm Nicklaus Wirth (tác giả của phát biểu nổi tiếng: “Thuật toán + cấu trúc dữ liệu = Chương trình”) viết trình biên dịch Pascal – nhóm nghiên cứu đã phát triển mạng chuyển mạch gói gồm 4 nút được đặt tên là ARPANET. Năm năm sau, Vinton Cerf và Robert Kahn đưa ra thuật toán mới, sau này được biết đến với tên gọi TCP/IP.
Năm 1980, ARPA bắt đầu chuyển các máy tính của mình sang dùng TCP/IP, và 3 năm sau tổ chức này bắt buộc tất cả máy tính kết nối với ARPANET đều phải dùng thuật toán này. TCP/IP đã thực sự trở thành chuẩn nền tảng của Internet ngày nay, với hàng trăm triệu người dùng trên khắp thế giới.
Bảo mật
Các thuật toán làm thay đổi thế giới đôi khi không phát sinh từ công việc nghiên cứu mà từ yêu cầu thực tiễn. Một ví dụ của trường hợp này là thuật toán mã hoá, được tạo ra để chống lại những chuyên gia “bẻ khoá” nhằm lấy cắp hay xem trộm dữ liệu quan trọng.
Thuật toán mã hoá RSA được phát triển tại học viện kỹ thuật Massachusetts (MIT) vào năm 1977, đặt theo tên các tác giả Ronal Rivest, Adi Shamir và Leonard Adleman. Thực ra trước đó vài năm, Clifford Cox, chuyên gia mã hoá người Anh, đã phát triển riêng một biến thể RSA. Tuy nhiên, chính phủ Anh xem đây là vấn đề mật và đã không công bố.
Thuật toán RSA gần như gặp chung số phận. Khi Rivest, Shamir và Adleman công bố RSA trong ấn phẩm Scientific American tháng 9/1977, họ tự nguyện cung cấp toàn bộ thông tin cho bất kỳ ai gửi đến một phong bì có dán tem và ghi sẵn địa chỉ (người nhận). Cơ quan an ninh quốc gia Mỹ (NSA) đã không đồng ý về việc phổ biến rộng rãi RSA và ra lệnh cấm – tuy nhiên lệnh cấm này không có cơ sở pháp lý. Năm 1978, các tác giả đã công bố thuật toán trong ấn phẩm nổi tiếng Communications of the Association for Computing Machinery (ACM). Và thế là RSA sổ lồng.
Trong môi trường Internet hiện nay, các thuật toán bảo mật như RSA và các hậu duệ của nó có vai trò rất quan trọng. Các thuật toán này tạo nên cơ sở cho thương mại điện tử an toàn bằng cách cho phép thực hiện các giao dịch trực tuyến trong định dạng mã hoá.
Nén
Cũng vậy, trong thế giới thông tin trao đổi nhanh hiện nay, các thuật toán nén dữ liệu, âm thanh và hình ảnh ngày càng có vai trò quan trọng trong đời sống. Thuật toán nén âm thanh và video đã giúp cho VoIP và truyền hình IP trở nên hiện thực.
Nhằm mục đích này, các nhà nghiên cứu đã phát triển nhiều thuật toán dùng để nén và truyền dữ liệu. Chẳng hạn, năm 1991, Steve Casner và Van Jacobsen của Cisco Systems đồng phát triển Compressed Real-Time Protocol (CRTP).
Trong khi đó, ở Đức, một thuật toán được khai sinh đã làm thay đổi cả ngành công nghiệp âm nhạc. Năm 1987, nhóm nghiên cứu tại đại học Erlangen dưới sự hướng dẫn của giáo sư Dieter Seitzer và nhóm nghiên cứu của Fraunhofer Gesellschaft tại học viện Institut Integrierte Schaltungen cùng phát triển thuật toán cho phép nén âm thanh lưu trữ và truyền dẫn. Kết quả là MP3 ra đời, cho phép giảm 12 lần dung lượng gốc trên CD mà vẫn giữ được chất lượng âm thanh. Từ đó, thế giới không còn như trước nữa.
Thuật toán ở mọi nơi
Các thuật toán được giới thiệu ở đây chỉ là một vài điển hình. Bạn có thể tìm thấy thuật toán ở mọi nơi – trong các phần mềm máy tính, trong động cơ ô tô và trong guồng máy của thị trường chứng khoán. Thực tế, nếu câu hỏi là “nó làm việc như thế nào?” thì câu trả lời hầu như liên quan đến thuật toán.
Dù với mục đích nén, bảo mật, truyền thông, tốc độ, truy cập hay cái gì đó hoàn toàn khác (mà hiện chúng ta chưa hình dung được) – không nghi ngờ gì các thuật toán sẽ tiếp tục chi phối cuộc sống của chúng ta.
TOP 10 THUẬT TOÁN CỦA MỌI THỜI ĐẠI | |
| “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. | 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. |
Phương Uyên
Nguồn: Ecommerce Times
FPT Aptech – Hệ Thống Đào Tạo Lập Trình Viên Quốc Tế
| FPT Aptech trực thuộc Tổ chức Giáo dục FPT có hơn 25 năm kinh nghiệm đào tạo lập trình viên quốc tế tại Việt Nam, và luôn là sự lựa chọn ưu tiên của các sinh viên và nhà tuyển dụng. |
