Thuật toán

TÔ QUANG HIỆP

tháng 8 24, 2017

0

Thuật toán (Algorithm), còn gọi lài giải thuật, là một dãy các thao tác xác định trên một đối tượng, sao cho sau khi thực hiện một số hữu hạn các bước thì đạt được mục tiêu.

Nói cách khác, thuật toán là một bộ các quy tắc hay quy trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào.

Ví dụ 1.1: Thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là các số thực), trong tập hợp các số thực có thể là một bộ các bước sau đây:

1.      Nếu a = 0

b = c thì P(x) có nghiệm bất kì

b ≠ c thì P(c) vô nghiệm

2.      Nếu a ≠ 0

P(x) có duy nhất một nghiệm x = (c - b)/a

Một thuật toán có các tính chất sau:

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