Các vấn đề liên quan đến thuật toán

Để giải một bài toán trên máy tính điện tử (MTĐT), điều trước tiên là chúng ta phải có thuật toán. Một câu hỏi đặt ra là làm thế nào để tìm ra được thuật toán cho một bài toán đã đặt ra? Lớp các bài toán được đặt ra từ các ngành khoa học kỹ thuật, từ các lĩnh vực hoạt động của con người là hết sức phong phú và đa dạng. Các thuật toán giải các lớp bài toán khác nhau cũng rất khác nhau. Tuy nhiên, có một số kỹ thuật thiết kế thuật toán chung như: Chia để trị (divide-and-conque), phương pháp tham ăn (greedy method), qui hoạch động (dynamic programming)... Việc nắm được các chiến lược thiết kế thuật toán này là hết sức quan trọng và cần thiết, nó giúp cho ta dễ tìm ra các thuật toán mới cho các bài toán mới được đưa ra.

Khi một thuật toán được làm ra, ta cần phải chứng minh rằng, thuật toán khi được thực hiện sẽ cho ta kết quả đúng với mọi dữ liệu vào hợp lệ. Điều này gọi là chứng minh tính đúng đắn của thuật toán. Việc chứng minh tính đúng đắn của thuật toán là một công việc không dễ dàng. Trong nhiều trường hợp, nó đòi hỏi ta phải có trình độ và khả năng tư duy toán học tốt.

Sau đây ta sẽ chỉ ra rằng, khi thực hiện thuật toán Euclid, g sẽ là ước chung lớn nhất của hai số nguyên dương bất kỳ m, n. Thật vậy, khi thực hiện bước 1, ta có m = qn + r ,trong đó q là số nguyên nào đó . Nếu r = 0 thì n là ước của m và hiển nhiên n (do đó g) là ước chung lớn nhất của m và n. Nếu r ≠ 0 thì một ước chung bất kỳ của m và n cũng là ước chung của n và r (vì r=m-qn). Ngược lại một ước chung bất kỳ của n và r cũng là ước chung của m và n (vì m = qn + r). Do đó ước chung lớn nhất của n và r cũng là ước chung lớn nhất của ma và n. Vì vậy, khi thực hiện lặp lại bước 1, với sự thay đổi giá trị của m bởi n, và sự thay đổi giá trị của n bởi r, cho tới khi r=0 ta nhận được giá trị của g là ước chung lớn nhất của các giá trị m và n ban đầu.

Giả sử, với một số bài toán nào đó chúng ta có một số thuật toán giải . Một câu hỏi mới xuất hiện là, chúng ta cần chọn thuật toán nào trong số các thuật toán đó để áp dụng. Việc phân tích thuật toán, đánh giá độ phức tạp của thuật toán là nội dung của phần dưới đây sẽ giải quyết vấn đề này.

Khi giải một vấn đề, chúng ta cần chọn trong số các thuật toán, một thuật toán mà chúng ta cho là “tốt” nhất .Vậy ta cần lựa chọn thuật toán dựa trên cơ sở nào? Thông thường ta dựa trên hai tiêu chuẩn sau đây:

Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)

Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy tính, và đặc biệt chạy nhanh nhất có thể được.

Khi ta viết một chương trình chỉ để sử dụng một số ít lần,và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chương trình thì tiêu chuẩn (1) là quan trọng nhất. Nhưng có trường hợp ta cần viết các chương trình (hoặc thủ tục, hàm) để sử dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp xếp, tìm kiếm được sử dụng rất nhiều lần, bởi rất nhiều người trong các bài toán khác nhau . Trong trường hợp này ta cần dựa trên tiêu chuẩn (2). Ta sẽ cài đặt thuật toán có thể sẽ rất phức tạp, miễn là chương trình nhận được chạy nhanh hơn so với các chương trình khác.

Tiêu chuẩn (2) được xem là tính hiệu quả của thuật toán. Tính hiệu quả của thuật toán bao gồm hai nhân tố cơ bản:

Dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, các kết quả tính toán trung gian và các kết quả của thuật toán .

Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy). Chúng ta chỉ quan tâm đến thời gian thực hiện thuậ toán, có nghĩa là ta nói đến đánh giá thời gian thực hiện. Một thuật toán có hiệu quả được xem là thuật toán có thời gian chạy ít hơn so với các thuật toán khác.