Vai trò của thuật toán

Nguồn: [You must be registered and logged in to see this link.]
Thuật toán là gì? Vì sao cần học thuật toán? Vai trò của thuật toán so với các lĩnh vực công nghệ khác sử dụng trong máy tính?

1.1. Thuật toán

Nói nôm na, thuật toán là bất kỳ một thủ tục tính toán nào nhận vào một tập dữ liệu, hay input, và sinh ra một tập kết quả, hay output. Thuật toán do đó là một chuỗi các bước tính toán để sinh ra kết quả từ dữ liệu đầu vào.

Ta cũng có thể xem thuật toán như một công cụ để giải các bài toán tính toán nhất định. Yêu cầu của bài toán chỉ ra mối quan hệ giữa dữ liệu đầu vào và kết quả mong muốn. Thuật toán sẽ mô tả một dãy các thủ tục tính toán để đạt được mối quan hệ đó.

Chẳng hạn ta cần sắp xếp một dãy các số theo thứ tự không giảm. Bài toán này nảy sinh thường xuyên trên thực tế và là một ví dụ tốt để giới thiệu các kỹ thuật thiết kế và phân tích thuật toán căn bản. Ta định nghĩa bài toán sắp xếp như sau:

Input: Một dãy gồm n số (a1, a2,..., an)

Output: Một hoán vị (a'1, a'2,..., a'n) của dãy đã cho sao cho a'1 ≤ a'2 ≤ ... ≤ a'n

Ví dụ, cho dãy (31, 41, 59, 26, 41, 58), một thuật toán sắp xếp sẽ trả về dãy (26, 31, 41, 41, 58, 59). Một dãy đầu vào như vậy gọi là một trường hợp riêng của bài toán. Tổng quát, trường hợp riêng của một bài toán sẽ gồm dữ liệu vào thỏa mãn các điều kiện đề bài nêu, và cần để tính toán kết quả.

Sắp xếp là một thao tác cơ bản trong khoa học máy tính. Do đó, nhiều thuật toán hiệu quả cho bài toán sắp xếp đã được xây dựng. Thuật toán nào tốt nhất với một ứng dụng cụ thể phụ thuộc vào nhiều yếu tố, số phần tử cần sắp xếp, mức độ các phần tử đã được sắp xếp, các giới hạn về giá trị phần tử và loại thiết bị lưu trữ: bộ nhớ, đĩa cứng hay băng từ.

Một thuật toán là đúng đắn nếu, với mọi trường hợp riêng,thuật toán dừng với kết quả đúng. Ta nói một thuật toán đúng đắn giải quyết được một bài toán tính toán. Một thuật toán không đúng đắn có thể không dừng lại hoặc cho ra kết quả sai với một trường hợp riêng nào đó. Trái với những gì ta nghĩ, đôi khi những thuật toán không đúng đắn có thể mang lại hiệu quả, nếu có thể điều khiển được hiệu suất lỗi.

Một thuật toán có thể được chỉ ra bằng tiếng Anh, tiếng Việt, một chương trình máy tính hoặc thậm chí một thiết kế phần cứng. Điều ràng buộc duy nhất là phải nêu rõ ràng, chính xác các bước tính toán cần thiết.

Thuật toán có thể giải những loại bài toán nào?

Sắp xếp chắc chắn không phải là bài toán duy nhất đã được xây dựng về thuật toán. Các ứng dụng thực tiễn của thuật toán có mặt ở khắp mọi nơi, bao gồm các ví dụ sau:

Dự án bản đồ Genes người với mục tiêu xác định tất cả 100000 genes trong DNA của loài người, xác định dãy 3 tỷ các cặp hóa chất cơ bản cấu tạo nên DNA của loài người, lưu trữ vào cơ sở dữ liệu, và thiết kế các công cụ phân tích dữ liệu. Mỗi bước đều đòi hỏi các thuật toán phức tạp. Mặc dù lời giải nằm ngoài phạm vi của quyển sách nhưng những ý tưởng trong nhiều chương của quyển sách này được áp dụng vào lời giải của các bài toán sinh học, giúp các nhà khoa học đạt được mục tiêu bằng cách sử dụng hiệu quả dữ liệu. Chúng giúp tiết kiệm về thời gian, của cả người và máy, và tiền bạc, vì nhiều thông tin hơn giờ đây có thể thu được từ các phương pháp thí nghiệm.
Internet giúp mọi người trên thế giới nhanh chóng truy cập và đón nhận một khối lượng thông tin khổng lồ. Để làm được điều đó, các thuật toán thông minh đã được sử dụng để quản lý khối lượng dữ liệu này. Các bài toán phải giải chẳng hạn như tìm hành trình tốt nhất cho dữ liệu di chuyển, dùng một máy tìm kiếm để nhanh chóng tìm các trang web chứa thông tin cần thiết,...