Bắt đầu giải quyết bài toán tin học

Một bài toán tin học (Problem - vấn đề) yêu cầu chúng ta tìm ra giải pháp để đạt được một mục đích xác định từ những điều kiện ban đầu (Dữ liệu đầu vào).
Trước khi bước vào giải quyết một bài toán bằng tin học, điều đầu tiên cần có là: một Thuật giải (Thuật toán) để giải quyết một bài toán. Nhưng, chúng là gì?
Khi dịch ra tiếng Anh, cả Thuật toán và Thuật giải đều là Algorithm. Nhưng, một số nguồn tài liệu tách riêng hai định nghĩa này. Ở đây, tui sẽ trình bày hai định nghĩa trên bằng cách tổng hợp các tài liệu.
Thuật giải (thuật toán) đều được hiểu là: "Một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết vấn đề" (1). Nói chính xác hơn, thuật giải (thuật toán) được định nghĩa là: "Một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn" (2).
 Tính chất thuật toán:

• Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác.
• Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định.
• Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau.
• Tính phổ dụng: Thuật toán 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.
• Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán.

Một số tính chất khác:

• Đầu vào và đầu ra: mọi thuật giải (thuật toán) đều có dữ liệu đầu vào, xử lý nó, và cho kết quả.
• Tính hiệu quả: dựa trên khối lượng tính toán, không gian và thời gian thi hành thuật toán.

Bài toán ví dụ: tính giai thừa, tính phương trình bậc nhất, bậc hai.
Tuy nhiên, trong quá trình nguyên cứu giải quyết bài toán, người ta đã đưa ra những nhận xét (3):

• Có nhiều bài toán chưa tìm ra được cách giải kiểu thuật toán, và cũng chưa biết có tồn tại thuật toán giải quyết hay không.
• Có nhiều bài toán đã có thuật toán giải quyết, nhưng thời gian tính toán quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng.
• Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận (Thường gặp nhất là ở tính chính xác và tính khách quan: kết quả sau khi tính có thể chưa được tối ưu, nhưng phải nằm trong khoảng chấp nhận).

Từ đây, ta có thể gọi các phương pháp như vậy là thuật giải. Một số thuật giải: thuật giải Heuristic, thuật giải Di truyền. Bài toán ví dụ: tìm đường đi ngắn nhất (A*) cho một đối tượng trong game (warcraft, starcraft).

Mô tả thuật giải (thuật toán):
Cách đơn giản nhất là đưa ra từng bước một, ở mỗi bước, hãy suy nghĩ: ta cần làm gì?
Ví dụ: xuất một mảng a (A[0], A[1], ..., A[n - 1]) cho trước có n phần tử.

1. Gán i là 0 (i := 0).
2. Nếu i vẫn còn nhỏ hơn n: chuyển tới bước 3, ngược lại chuyển tới bước 4.
3. Xuất a[i] và tăng i thêm một đơn vị (i := i + 1).
4. Kết thúc chương trình.

Cách thứ hai: dùng sơ đồ khối.
Ưu điểm: Giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý (4).
Nhược điểm: Cồng kềnh, dùng một không gian rất lớn để mô tả một bài toán. Ngoài ra chỉ phân biệt được hai thao tác: rẽ nhánh và xử lý. Trong thực tế, các thuật giải (thuật toán) còn có thêm thao tác lặp.
Sử dụng:

• Thao tác rẽ nhánh (chọn lựa): Mô tả bằng hình thoi, bên trong hình ghi nội dung điều kiện.
• Thao tác xử lý: Mô tả bằng hình chữ nhật, bên trong hình ghi nội dung cần xử lý.

Cách thứ ba: dùng mã giả (mượn cú pháp của một ngôn ngữ lập trình để mô tả các bước tính toán).
Ưu điểm: Diễn đạt được nội dung bài toán một cách trọn vẹn mà không tốn nhiều không gian.
Ví dụ: Cũng bài toán trên, nhưng được viết bằng mã giả theo kiểu ngôn ngữ Pascal:

For i := 0 to n -1 do
xuất a[i]

Tài liệu tham khảo:
(1), (2), (4): Hoàng Kiếm. GIẢI MỘT BÀI TOÁN TRÊN MÁY TÍNH NHƯ THẾ NÀO?. NXB Giáo dục.
(3): Hoàng Kiếm. THUẬT TOÁN THUẬT GIẢI.
Wikipedia: Algorithm - http://en.wikipedia.org/wiki/Algorithm.