Thuật toán

Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.

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ụ: 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

Lưu ý

Khi một thuật toán đã hình thành thì ta không xét đến việc chứng minh thuật toán đó mà chỉ chú trọng đến việc áp dụng các bước theo sự hướng dẫn sẽ có kết quả đúng. Việc chứng minh tính đầy đủ và tính đúng của các thuật toán phải được tiến hành xong trước khi có thuật toán. Nói rõ hơn, thuật toán có thể chỉ là việc áp dụng các công thức hay quy tắc, quy trình đã được công nhận là đúng hay đã được chứng minh về mặt toán học.

"Thuật toán" hiện nay thường được dùng để chỉ thuật toán giải quyết các vấn đề tin học. Hầu hết các thuật toán tin học đều có thể viết thành các chương trình máy tính mặc dù chúng thường có một vài hạn chế (vì khả năng của máy tính và khả năng của người lập trình). Trong nhiều trường hợp, một chương trình khi thiết kế bị thất bại là do lỗi ở các thuật toán mà người lập trình đưa vào là không chính xác, không đầy đủ, hay không ước định được trọn vẹn lời giải của vấn đề. Tuy nhiên cũng có một số bài toán mà hiện nay người ta chưa tìm được lời giải triệt để, những bài toán ấy gọi là những bài toán NP-không đầy đủ.
Như trên,thuật toán ngoài ra còn chỉ những phương pháp đem lại được kết quả một cách tối ưu,giảm lượng tài nguyên bỏ ra để đạt được.Những phương pháp này có thể được rút ra từ thực nghiệm và có thể giải được bằng toán học hoặc không,tuy nhiên mọi thuật toán đáp ứng tính logic tối hậu của tự nhiên mà là nguyên do của nhiều loại logic mờ.
vd:logic mờ tồn tại trong trạng thái chỉnh lưu của transistor mà trở nên chuẩn xác trong việc tính toán nhờ sự tái chuẩn hoá mà làm các đặc tính trung gian vi mô của transistor không còn quan yếu ở thang lớn hơn.

Tính chất của thuật toán

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.

Ý nghĩa đặc biệt

Trong ngành khoa học máy tính, thì thuật toán là được thể hiện thông qua một chương trình máy tính (hay một tập hợp các chương trình máy tính) được thiết kế để giải quyết một số loại vấn đề một cách có hệ thống. Một thí dụ kinh điển trong ngành khoa học máy tính là thuật toán đệ quy dùng để giải bài toán tháp Hà Nội.

Đọc thêm

• Độ phức tạp thuật toán
• Máy truy tìm dữ liệu
• Thuật toán sắp xếp

Bản mẫu:Khoa học Máy tính

Liên kết đến đây

• Olympic Tin học Quốc tế
• Giải thuật vẽ đoạn thẳng Bresenham
• Alan Turing
• Đại số
• Lý thuyết số
• Pi
• Số học
• Phần mềm
• Máy tính lượng tử
• Khoa học máy tính