Giải thuật

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à GT 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 GT.

Tính chất của GT

• Tính rõ ràng: GT đượ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 GT 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 GT 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 GT phải kết thúc và cho kết quả mong muốn.

• Tính hiệu quả: GT 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: GT đượ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: GT 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 GT luôn là các yếu tố được xác định ngay trong quá trình thiết kế GT (xt. thiết kế giải thuật).

Biểu diễn GT

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

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. GT 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 GT 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 GT, đô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 GT giúp theo dõi sự phân cấp các trường hợp và quá trình xử lý của GT. Có hai loại thao tác chính trong các GT: 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 GT 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 GT 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 GT 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 GT 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 GT 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 GT (xt. Ngôn ngữ lập trình).

Phân loại GT

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

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

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

Tuy nhiên, phổ biến hơn vẫn là việc phân loại GT 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 GT

Để đánh giá hiệu quả của một GT 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 GT. 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á GT và được gọi là đánh giá độ phức tạp của GT.

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 GT: 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 GT 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 GT 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 GT 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 GT có xu hướng tỉ lệ thuận với độ lớn đầu vào.

• Độ phức tạp logarit, O (log n): GT loại này hiệu quả hơn so với GT 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 GT càng kém hiệu quả.

• Độ phức tạp hàm mũ, O (2n): Đây là trường hợp GT kém hiệu quả nhất, việc sử dụng các GT 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 GT-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 GT 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 GT 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 GT 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 GT (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 GT đã 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 GT bằng phương tiện mà ông gọi là GT 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 GT đượ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 GT.

GT 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 GT đượ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 GT 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 GT. Lý thuyết GT 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 GT 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 GT làm cơ sở cho lý thuyết thông tin. Lý thuyết GT 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, GT 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 GT 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 GT đó 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ế GT (xt. Thiết kế giải thuật). Nói cách khác, GT 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 GT 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 GT 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à GT đưa ra qui trình và thao tác xử lý, còn đối tượng xử lý của GT 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 GT. Với một cấu trúc dữ liệu đã chọn, cần có những GT 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 GT 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.