Trong toán học và khoa học máy tính, một thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính được sử dụng chỉ rõ việc thực hiện các phép tính, xử lý dữ liệu, suy luận tự động và các tác vụ khác. Ví dụ như thuật toán sắp xếp các số trong dãy số nguyên hay thuật toán tìm số nguyên tố.
Nói dễ hiểu hơn, mỗi một bài toán giống một chiếc rương kho báu (kết quả, đáp án), và thuật toán chính là chiếc chìa khoá để mở nó. Nếu dùng sai chìa khoá, bạn vẫn có thể mở được rương, nhưng sẽ mất nhiều thời gian, hoặc mở được thì kho báu ở bên trong bị méo mó, không toàn vẹn. Sử dụng đúng chìa khoá, sẽ giúp bạn lấy được kho báu 1 cách dễ dàng, nhanh chóng. Tất nhiên mỗi chiếc rương sẽ luôn cần loại chìa khoá khác nhau, giống như một bài toán luôn có những giải thuật xác định.
Thuật toán là gì?
Trong toán học và khoa học máy tính, một thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính được sử dụng chỉ rõ việc thực hiện các phép tính, xử lý dữ liệu, suy luận tự động và các tác vụ khác. Ví dụ như thuật toán sắp xếp các số trong dãy số nguyên hay thuật toán tìm số nguyên tố.
Nói dễ hiểu hơn, mỗi một bài toán giống một chiếc rương kho báu (kết quả, đáp án), và thuật toán chính là chiếc chìa khoá để mở nó. Nếu dùng sai chìa khoá, bạn vẫn có thể mở được rương, nhưng sẽ mất nhiều thời gian, hoặc mở được thì kho báu ở bên trong bị méo mó, không toàn vẹn. Sử dụng đúng chìa khoá, sẽ giúp bạn lấy được kho báu 1 cách dễ dàng, nhanh chóng. Tất nhiên mỗi chiếc rương sẽ luôn cần loại chìa khoá khác nhau, giống như một bài toán luôn có những giải thuật xác định.
Trong cuộc sống, bạn cũng có thể sẽ gặp các bài toán hay vấn đề nhỏ yêu cầu bạn phải chọn đúng giải thuật để giải, ví dụ như:
- Hãy tìm kiếm 1 cái máy tính có giá từ X->Y, đáp ứng tối đa các tiêu chí của người dùng chỉ trong 1 cái click chuột
- Hãy đưa ra các bài viết hoặc sản phẩm mà người dùng quan tâm dựa trên lịch sử truy cập của họ
- Hãy tính toán và sắp xếp thứ hạng của người dùng dựa trên lịch sử mua hàng/ làm bài tập/ chơi game…
- Đếm số lượng truy cập của người dùng trong 1 khoảng thời gian để dự đoán giờ đăng bài
- Đưa ra gợi ý các bài viết mà người dùng nên xem dựa vào lịch sử truy cập và thao tác của họ trên hệ thống
Tất nhiên những bài toán trên là không khó với tập dữ liệu và người dùng nhỏ. Nhưng hãy thử tưởng tượng, khi hệ thống có hàng nghìn hàng vạn người cùng truy cập và bạn phải trả về kết quả là cực kì nhanh, bạn sẽ làm như thế nào để đảm bảo điều đó? Câu trả lời chính là tìm đúng thuật toán, và đôi khi chúng ta cần phải tìm cách nâng cấp chúng nữa.
Các đặc trưng của thuật toán
– Tính xác định
Ta có thể tìm ở đâu một lời giải vấn đề – bài toán có vô số bước giải ? Tính “không mập mờ” và “có thể thực thi được” gọi chung là tính xác định.
Tính “thực thi được” cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong “thuật toán” tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là “thực thi được” xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói “lấy căn bậc hai của một số âm” là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác “lấy căn bậc hai của một số âm” là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được.
-Tính hữu hạn
Tính “dừng” hay hữu hạn là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng “thuật toán” bị lặp vô tận hoặc bị quẩn.
-Tính đúng
Tính “đúng” là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học sinh nhất định là có khả năng đưa ra lời giải đúng!
-Tính hiệu quả
Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán.
-Tính tổng quát
Thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó.
Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.
Một số thuật toán thường gặp
Ở đây, mình muốn giới thiệu với các bạn những thuật toán có tính ứng dụng khá lớn trong các sản phẩm/hệ thống phần mềm hiện tại nhé:
Đầu tiên là thuật toán tìm đường đi ngắn nhất. Hãy tưởng tượng bạn được cho một danh sách các đường đi giữa các địa điểm, hãy tìm đường đi ngắn nhất (về khoảng cách) hoặc chi phí tối thiểu khi đi từ điểm X đến điểm Y.
Bạn có phát hiện mình đã gặp thuật toán này ở đâu rồi chứ? Nó xuất hiện trong các phần mềm chỉ đường và ứng dụng liên quan tới ngành giao thông vận tải (ví dụ Google map, Grab, Uber, giao hàng nhanh, ….) Ngoài ra, trong các hệ thống mạng, viễn thông người ta cũng dùng thuật toán này để định hướng đường truyền và tín hiệu. Cuộc điện thoại từ 1 người ở thành phố Hà Nội gọi cho 1 người ở thành phố Hồ Chí Minh đi qua các cột thu phát sóng, dữ liệu internet từ máy tính của bạn đi tới máy chủ của nhà cung cấp mạng cũng phải sử dụng thuật toán này để đạt được tốc độ tối đa.
Tiếp theo, một thuật toán khá nổi tiếng khác là thuật toán tìm kiếm. Bạn có thể nhìn thấy nó ở khá nhiều sản phẩm phần mềm hiện tại, điển hình như Google. Bạn có thể nghĩ rằng, tìm kiếm khá là đơn giản, khi bạn lần lượt soi vào từng ô, từng dòng dữ liệu xem có thứ mà mình tìm kiếm hay không? Nhưng hãy đặt địa vị, bạn có hàng tỷ tỷ món đồ dùng được vứt lộn xộn trong 1 căn nhà, bạn sẽ mất bao nhiêu lâu để tìm được món đồ mà bạn mong muốn. Hãy biết chắc chắn rằng, việc Google trả ra được kết quả mà bạn yêu cầu tìm kiếm trong vòng 1 vài giây là vô cùng khó. Điều ấy yêu cầu 1 thuật toán cực mạnh, và vẫn liên tục cần cải tiến cho đến ngày hôm nay.
Thuật toán có thực sự cần thiết?
Nếu các bạn không làm những bài toán có độ phức tạp cao, có dữ liệu người dùng lớn, cần phải ra đáp án nhanh với độ chính xác cao, bạn vẫn có thể giải quyết được vấn đề với vốn thuật toán hạn chế. Hay ví dụ nếu bạn làm 1 website chủ yếu là nội dung, nếu bạn làm 1 ứng dụng điện thoại chỉ xử lý các logic thông thường, thuật toán không giúp ích nhiều cho bạn trong trường hợp ấy. Kể cả khi bạn làm những sản phẩm rất lớn, sử dụng những công nghệ rất mới và hot như AI, BigData hay Blockchain, dù không thành thạo thuật toán nào cả, bạn vẫn xây dựng được hệ thống. Tuy nhiên, trong trường hợp này, bạn chỉ cần hiểu rõ cách sử dụng và ứng dụng của công nghệ để bù đắp cho sự không hiểu rõ thuật toán bên trong công nghệ ấy.
Do đó, việc học thuật toán, sự quan trọng của thuật toán phụ thuộc vào sản phẩm, ứng dụng mà bạn làm. Dù có giỏi hay không giỏi thuật toán, bạn vẫn có thể thành công nếu vận dụng đúng kỹ năng, hiểu biết của mình vào lĩnh vực mà bạn làm. Còn nếu bạn cần lời khuyên, chúng mình thiết nghĩ việc học và rèn luyện thuật toán thì vẫn là điều rất nên làm và cần được đầu tư nỗ lực. Vì thuật toán giúp bạn rèn luyện tư duy giải quyết vấn đề, cùng với suy nghĩ về việc luôn tối ưu và làm sản phẩm một cách tối ưu và tổng quát.
—Hết—