Giải thuật là tập hợp hữu hạn các thao tác (các bước/các chỉ thị/câu lệnh) được thực hiện theo một trình tự chặt chẽ trên một đối tượng cụ thể, xuất phát từ một trạng thái ban đầu xác định để thu được kết quả mong muốn. Nói cách khác, GT cung cấp một bộ các qui tắc hay qui trình giải quyết một vấn đề nào đó sau một số bước hữu hạn xuất phát từ một tập hợp các dữ kiện cho trước. Trạng thái xuất phát (dữ liệu đầu vào) của GT thường được kí hiệu là INPUT, trạng thái đạt được (kết quả đầu ra) là OUTPUT.

Vd. dưới đây là giải thuật xác định số tự nhiên N cho trước là số chẵn hay số lẻ:

• Bước 1. INPUT: Nhập số tự nhiên N.

• Bước 2. Nếu N chia hết cho 2, chuyển tới bước 4.

• Bước 3. KQ = “N là số lẻ”. Chuyển tới bước 5.

• Bước 4. KQ = “N là số chẵn”.

• Bước 5. OUTPUT giá trị KQ. Kết thúc giải thuật.

Tính chất của giải thuật

• Tính rõ ràng: giải thuật được thể hiện bằng các thao tác tường minh được sắp xếp theo thứ tự xác định.

• Tính xác định: Mỗi thao tác của giải thuật có mục đích cụ thể và rõ ràng.

• Tính chính xác: Kết quả tính toán của từng thao tác hay từng giai đoạn của giải thuật luôn chính xác và đơn nhất.

• Tính dừng (tính kết thúc): Sau một số hữu hạn các thao tác thực hiện giải thuật phải kết thúc và cho kết quả mong muốn.

• Tính hiệu quả: Giải thuật có khả năng cho kết quả mong muốn trong điều kiện thời gian và tài nguyên cho phép.

• Tính khách quan: Giải thuật được thiết kế sao cho bất kì ai thực hiện cũng đều cho kết quả như nhau.

• Tính phổ dụng: Giải thuật không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.

• Dữ liệu đầu vào và kết quả đầu ra xác định: Dữ liệu đầu vào và kết quả đầu ra sau khi hoàn thành thực hiện giải thuật luôn là các yếu tố được xác định ngay trong quá trình thiết kế giải thuật (xt. thiết kế giải thuật).

Biểu diễn giải thuật

Người ta thường dùng 3 phương pháp chính để biểu diễn giải thuật:

1. Sử dụng ngôn ngữ tự nhiên: Đó là cách liệt kê các bước bằng ngôn ngữ tự nhiên (xem vd. giải thuật xác định số tự nhiên N cho trước là số chẵn hay số lẻ nêu trên). Khi dùng ngôn ngữ tự nhiên, quá trình thực hiện sẽ được mặc định hiểu là lần lượt đi từ bước trước đến bước sau, trừ khi có yêu cầu nhảy sang bước khác. Phương pháp biểu diễn này không yêu cầu người viết cũng như người đọc giải thuật phải nắm các qui tắc gì đặc biệt. Tuy nhiên, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của giải thuật, đôi khi khó hiểu cho người đọc.
2. Sử dụng sơ đồ/lưu đồ khối: Lưu đồ hay sơ đồ khối là một công cụ trực quan để biểu diễn giải thuật giúp theo dõi sự phân cấp các trường hợp và quá trình xử lý của giải thuật. Có hai loại thao tác chính trong các giải thuật: 1) Thao tác loại chọn lựa tùy theo một điều kiện nào đó được nêu dưới dạng “nếu A thì B” (lựa chọn không đầy đủ) hoặc “nếu A thì B, trong trường hợp ngược lại thì C” (lựa chọn đầy đủ); 2) Các thao tác không thuộc loại chọn lựa được gọi là thao tác loại hành động. Khi biểu diễn giải thuật bằng sơ đồ khối, thao tác loại chọn được biểu diễn bằng một khối hình thoi, thao tác loại hành động bằng khối hình chữ nhật. Để chỉ rõ điểm bắt đầu và kết thúc giải thuật người ta thường dùng các khối hình ô van và để phân biệt các thao tác nhập/xuất dữ liệu người ta dùng các khối hình bình hành. Trình tự thực hiện các thao tác được thể hiện bằng các cung nối có mũi tên theo nguyên tắc: 1) Mỗi khối hình chữ nhật và khối hình thoi tương ứng với lựa chọn không đầy đủ chỉ có đúng một cung ra; 2) Mỗi khối hình thoi tương ứng với lựa chọn đầy đủ chỉ có đúng hai cung ra tương ứng với các trường hợp điều kiện chọn lựa thỏa mãn hay không thỏa mãn. Dưới đây là vd. biểu diễn giải thuật xác định tính chẵn lẻ của một số tự nhiên N cho trước:
3. Sử dụng giả mã: Phương pháp biểu diễn giải thuật này sử dụng một phần ngôn ngữ tự nhiên kết hợp với cú pháp của một ngôn ngữ lập trình để thể hiện. Mặc dù cách biểu diễn giải thuật bằng giả mã sẽ bị phụ thuộc vào ngôn ngữ lập trình mà nó vay mượn cú pháp, song cách biểu diễn này, một mặt cho phép thể hiện đầy đủ các cấu trúc lập trình cơ bản, mặt khác nó cho phép tận dụng được các khái niệm trong ngôn ngữ lập trình, giúp người viết chương trình dễ dàng nắm bắt nội dung giải thuật (xt. Ngôn ngữ lập trình).

Phân loại giải thuật

Có hai cách tiếp cận chủ yếu để phân loại giải thuật:

• Theo phương pháp thực thi giải thuật: Theo cách phân loại này, các giải thuật được chia thành các nhóm như giải thuật hồi qui; giải thuật tuần tự, song song hay phân tán; giải thuật tất định hay không tất định; giải thuật chính xác hay gần đúng; giải thuật logic; giải thuật lượng tử…

• Theo phương pháp/mô hình thiết kế giải thuật: Theo cách phân loại này, các giải thuật được chia thành các nhóm như giải thuật vét cạn; giải thuật chia để trị; giải thuật tìm kiếm và liệt kê; giải thuật ngẫu nhiên; giải thuật truy hồi…

Tuy nhiên, phổ biến hơn vẫn là việc phân loại giải thuật trong từng lĩnh vực cụ thể như trong các lĩnh vực tối ưu hóa, học sâu, phân cụm dữ liệu v. v…

Độ phức tạp của giải thuật

Để đánh giá hiệu quả của một giải thuật người ta thường xét tới các đại lượng như số lượng các phép tính, thời gian tính toán hay dung lượng bộ nhớ cần dùng khi thực thi giải thuật. Các đại lượng đó nói chung là một hàm số R (n) > 0 đại diện cho những động thái của hệ thống phụ thuộc chủ yếu vào kích cỡ độ lớn của đầu vào n của bài toán. Việc ước lượng giá trị hàm số đó là một trong những vấn đề trọng tâm khi đánh giá giải thuật và được gọi là đánh giá độ phức tạp của giải thuật.

Trong thực tế, người ta thường dùng khái niệm bậc O-lớn để ước lượng độ phức tạp của giải thuật: Nếu như tìm được hằng số C > 0 không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R (n). g (n) đều dương và R (n) < C. g (n) thì ta nói giải thuật có độ phức tạp cỡ O (g (n)) hay độ phức tạp tương đương g (n) (xt. Lý thuyết độ phức tạp tính toán; Phân tích giải thuật).

Các độ phức tạp thường gặp đối với các giải thuật thông thường gồm có:

• Độ phức tạp hằng số, O (1): Số phép tính/thời gian chạy/dung lượng bộ nhớ để thực thi giải thuật không phụ thuộc vào độ lớn đầu vào.

• Độ phức tạp tuyến tính, O (n): Số phép tính/thời gian chạy/dung lượng bộ nhớ để thực thi giải thuật có xu hướng tỉ lệ thuận với độ lớn đầu vào.

• Độ phức tạp logarit, O (log n): giải thuật loại này hiệu quả hơn so với giải thuật có độ phức tạp tuyến tính.

• Độ phức tạp đa thức, O (P (n)): Trong đó P (n) là đa thức bậc cao (từ 2 trở lên). Bậc của đa thức P (n) càng cao giải thuật càng kém hiệu quả.

• Độ phức tạp hàm mũ, O (2n): Đây là trường hợp giải thuật kém hiệu quả nhất, việc sử dụng các giải thuật này nói chung khó khả thi với các tài nguyên tính toán truyền thống.

Từ tiếng Anh của giải thuật-Algorithm (là tên gọi Latin hóa của Al-Khwarizmi-nhà toán học vùng Vịnh Ba Tư nửa đầu thế kỉ thứ 9) ban đầu được sử dụng để chỉ các bộ qui tắc và kỹ thuật được Al-Khwarizmi sử dụng để giải các phương trình đại số, trước khi được khái quát hóa để chỉ bất kỳ bộ qui tắc hoặc kỹ thuật nào.

Các ý tưởng cơ bản liên quan đến khái niệm giải thuật gắn liền với tất cả các giai đoạn phát triển của toán học. Tuy nhiên, tới tận thế kỉ 20 giải thuật mới trở thành một chủ đề nghiên cứu độc lập, khởi đầu còn ở dạng khá mơ hồ trong một số công trình của những đại diện trường phái trực giác toán học như L. E. J. Brouwer và H. Weyl vào những năm 1920.

Sự phát triển của lý thuyết giải thuật bắt đầu bằng chứng minh của Kurt Gödel các định lý về tính không đầy đủ của các hệ thống tiên đề (định lý đầu tiên công bố vào năm 1931) đòi hỏi cần phải chuẩn hóa khái niệm giải thuật (xt. Định lý bất toàn Gödel). Các phiên bản chuẩn hóa đầu tiên của khái niệm này được phát triển vào những năm 1930 bởi Alan Turing, Emil Post và Alonzo Church. Sau đó, lý thuyết giải thuật đã nhận được sự phát triển hơn nữa trong các công trình của S. C. Kleene, E. L. Post, A. A. Markov và những người khác. A. A. Markov (1954) đề xuất tinh chỉnh khái niệm giải thuật bằng phương tiện mà ông gọi là giải thuật bình thường, theo đánh giá được coi là “một trong những phiên bản tiêu chuẩn hóa thành công nhất của giải thuật”. Cách tiếp cận chung nhất khái niệm giải thuật được đề xuất bởi A. N. Kolmogorov (1965). Trong những năm tiếp theo, Donald Knuth, Alfred Aho và Jeffrey Ullman đã đóng góp đáng kể cho lý thuyết giải thuật.

Giải thuật có thể được mô tả như một thủ tục hoặc công thức để giải quyết vấn đề. Chính vì vậy giải thuật được sử dụng rộng rãi trong các lĩnh vực khác nhau, đặc biệt trong toán học và khoa học máy tính, cũng như trong cuộc sống hàng ngày.

Riêng trong lĩnh vực toán học, ngoài các ứng dụng cụ thể trong đại số, giải tích, lý thuyết số, khái niệm giải thuật là cơ sở cho một trong những khái niệm trung tâm của logic toán học, cụ thể là khái niệm tính toán. Đó là lý do tại sao, định lý Gödel về tính không đầy đủ của các hệ thống tiên đề có thể được coi là hệ quả của các định lý của lý thuyết giải thuật. Lý thuyết giải thuật cũng có mối liên kết chặt chẽ với chính nền tảng của toán học, trong đó mối quan hệ giữa tính kiến thiết (constructive) và không kiến thiết (non-constructive) chiếm một vị trí trung tâm. Có thể nói, lý thuyết giải thuật cung cấp các công cụ cần thiết để phát triển xu hướng mang tính kiến thiết trong toán học.

Trong khoa học máy tính, năm 1965, A. N. Kolmogorov đã đề xuất sử dụng lý thuyết giải thuật làm cơ sở cho lý thuyết thông tin. Lý thuyết giải thuật cũng là nền tảng lý thuyết cho một số vấn đề của toán học tính toán và có liên quan chặt chẽ với điều khiển học, trong đó việc nghiên cứu các thuật toán điều khiển đóng vai trò quan trọng. Cuối cùng, cần phải nói, giải thuật là bước không thể thiếu trong quá trình giải quyết bất kì bài toán nào trên máy tính, do vậy, khái niệm giải thuật là một trong các khái niệm cơ bản cần biết đối với bất kì ai muốn lập trình cho máy tính.

Khi một GT đã hình thành, ta không xét đến việc chứng minh tính đầy đủ và tính đúng đắn của giải thuật đó mà chỉ chú trọng đến việc áp dụng các bước theo đúng trình tự qui định để thu được kết quả cần thiết. Việc chứng minh ấy phải được tiến hành trong quá trình thiết kế giải thuật (xt. Thiết kế giải thuật). Nói cách khác, giải thuật chỉ là việc áp dụng các công thức hay qui tắc, qui trình đã được công nhận là đúng hay đã được chứng minh về mặt toán học.

Mặc dù các giải thuật có thể được phân loại theo nhiều cách khác nhau, song nếu xét về mặt cấu trúc nội tại, thì chỉ có 3 loại cấu trúc điều khiển chính:

1. Cấu trúc tuần tự (tuyến tính): Loại cấu trúc này được đặc trưng với một loạt các bước được thực hiện lần lượt từ trên xuống dưới.
2. Cấu trúc rẽ nhánh: Loại cấu trúc này còn được gọi là "cấu trúc lựa chọn", khi mà trình tự thực hiện các bước phụ thuộc vào điều kiện dạng "nếu-thì", nếu điều kiện là đúng, thực hiện bước A, nếu điều kiện là sai, thực hiện bước B.
3. Cấu trúc lặp: Với cấu trúc loại này, các bước có thể được thực hiện lặp lại khi một điều kiện nhất định còn được thỏa mãn và quá trình lặp lại đó sẽ kết thúc sau một số vòng lặp khi điều kiện đó sai.

Trong khoa học máy tính, khi giải quyết một bài toán thực tế trên máy tính, nói chung cần phải quan tâm tới hai vấn đề cốt yếu liên quan mật thiết với nhau: các đối tượng dữ liệu và những yêu cầu xử lý trên những đối tượng đó. Nói cách khác, cần chú trọng:

1. Xây dựng cấu trúc dữ liệu thích hợp sao cho vừa biểu diễn chính xác các đối tượng thực tế cùng các mối quan hệ của chúng trong thực tế, vừa có thể dễ dàng xử lý trên máy tính.
2. Xây dựng các thao tác xử lý dữ liệu, tức là cần tìm ra giải thuật tương ứng để xác định trình tự các thao tác máy tính phải thi hành để thu được kết quả mong muốn.

Mối quan hệ nói tới ở đây chính là giải thuật đưa ra qui trình và thao tác xử lý, còn đối tượng xử lý của giải thuật lại là dữ liệu; dữ liệu chứa đựng các thông tin cần thiết để thực hiện giải thuật. Với một cấu trúc dữ liệu đã chọn, cần có những giải thuật tương ứng, phù hợp để tránh việc xử lý gượng ép, thiếu tự nhiên trên một cấu trúc không phù hợp. Một cấu trúc dữ liệu tốt sẽ giúp giải thuật xử lý trên đó vừa dễ hiễu và đơn giản, vừa có thể được thực thi một cách hiệu quả hơn.

Tài liệu tham khảo

• Chabert, Jean-Luc. A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. 1999. ISBN 978-3-540-63369-3.

• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms (3rd ed. ). MIT Press. ISBN 978-0-262-03384-8.

• Robert Sedgewick; Kevin Wayne (2011). Algorithms, 4th Edition. Addison-Wesley. ISBN-13: 978-0321573513.

• Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison–Wesley. ISBN 978-0-201-89683-1.

• Kosovsky, N. K. Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad, 1981

• A. Markov. Theory of algorithms. Academy of Sciences of the USSR, 1954.