Thuật toán tất định

Trong khoa học máy tính, thuật toán tất định là một thuật toán có đầu ra (output) hoàn toàn có thể dự đoán được (xác định được) qua đầu vào (input), và máy chạy thuật toán đó luôn thực hiện các phép tính toán như nhau và có cùng một chuỗi trạng thái. Cho đến hiện tại, thuật toán tất định là loại thuật toán được nghiên cứu và được nhiều người quen thuộc nhất, cũng như là một trong các loại thuật toán thiết thực nhất, bởi lẽ loại thuật toán này có thể thực thi hiệu quả được trên các máy thực.

Nói ngắn gọn, tính tất định của thuật toán có nghĩa là:

• Nếu input giống nhau trên mỗi lần chạy, luôn có cùng một output
• Thời gian chạy, lượng bộ nhớ và tài nguyên cần thiết là như nhau trên mỗi lần chạy nếu input là giống nhau.

Định nghĩa chính thức

Thuật toán tất định có thể được định nghĩa theo máy trạng thái: một trạng thái mô tả đặc điểm của một máy đang hoạt động tại một thời điểm cụ thể trong thời gian chạy. Các máy trạng thái chuyển đổi rời rạc từ trạng thái này sang trạng thái khác. Ngay sau khi nhận đầu vào, máy nằm ở trạng thái ban đầu hay trạng thái khởi động. Nếu máy mang tính tất định, thì từ thời điểm này trở đi, trạng thái hiện tại của nó xác định trạng thái kế tiếp mà nằm trong tập trạng thái được định trước. Lưu ý rằng máy tất định vẫn có thể không dừng được hoặc kết thúc, do đó không có kết quả đầu ra.

Các ví dụ cụ thể của máy trừu tượng tất định gồm máy Turing mang tính xác định và máy tự động hữu hạn xác định.

Nguyên nhân làm cho thuật toán không xác định?

Một loạt các yếu tố khác nhau có thể khiến cho hành vi thuật toán không xác định được, hoặc bất định:

• Thuật toán sử dụng trạng thái bên ngoài mà không phải là đầu vào, như đầu vào của người dùng, biến toàn cục, giá trị bộ đếm thời gian phần cứng hoặc là giá trị ngẫu nhiên hoặc dữ liệu lưu trên ổ đĩa.
• Thuật toán nhạy cảm với thời gian, ví dụ nếu thuật toán có nhiều bộ xử lý ghi cùng lúc vào cùng một dữ liệu. Trong trường hợp này, thứ tự mà mỗi bộ xử lý ghi dữ liệu sẽ ảnh hưởng đến kết quả.
• Lỗi phần cứng làm cho trạng thái của thuật toán thay đổi theo cách không lường trước được.

Mặc dù các chương trình trong thực tế hiếm khi thực sự tất định, nhưng con người hoặc chương trình khác dễ dàng suy ra hơn về trạng thái của chương trình đó. Vì lý do này, hầu hết các ngôn ngữ lập trình và đặc biệt là các ngôn ngữ lập trình hàm nỗ lực ngăn chặn các sự kiện trên xảy ra hoặc xảy ra trong điều kiện kiểm soát.

Sự phổ biến của các bộ vi xử lý đa lõi đã dẫn đến sự quan tâm đến tính xác định trong lập trình song song và những thách thức của tính không xác định đã được tài liệu hóa một cách đầy đủ. Nhiều công cụ đã được phát triển để giúp đối phó với deadlocks và điều kiện đua.

Điểm bất lợi của sự tất định

Trong một số trường hợp, hành vi không xác định của chương trình là có lợi. Chẳng hạn như chương trình chia bài trong trò chơi blackjack phải khiến người chơi không thể dự đoán trước - ngay cả khi mã nguồn của chương trình là mở. Việc sử dụng một bộ tạo số giả ngẫu nhiên thường không đủ đảm bảo để người chơi không dự đoán được kết quả của việc chia bài. Một con bạc thông minh có thể đoán chính xác những con số bộ sinh tạo ra và do đó biết trước toàn bộ các lá bài trong canh bạc trước khi ván bài bắt đầu, cho phép hắn ăn gian. Những vấn đề này có thể được phòng tránh một phần nào đó thông qua việc sử dụng bộ sinh số giả ngẫu nhiên an toàn mật mã, nhưng việc sử dụng nguồn ngẫu nhiên không thể đoán trước để khởi động bộ sinh vẫn rất cần thiết, mà nguồn ngẫu nhiên này có thể được tạo bởi bộ sinh số ngẫu nhiên phần cứng.

Lưu ý rằng đáp án phủ định của bài toán P so với NP không ngụ ý về mặt lý thuyết rằng các chương trình với kết quả không xác định là hiệu quả hơn những chương trình có kết quả tất định. Lớp độ phức tạp NP có thể được định nghĩa mà không cần tham khảo đến tính không xác định qua việc sử dụng định nghĩa dựa trên xác minh.

Hạng mục tất định trong ngôn ngữ lập trình

Mercury

Ngôn ngữ lập trình hàm luận lý này tạo ra các phân loại tất định khác nhau cho các chế độ khác nhau.

Haskell

Haskell cung cấp một số cơ chế:

không xác định hoặc dấu hiệu Fail

• Kiểu dữ liệu Maybe và Either bao gồm dấu hiệu thành công trong kết quả.
• phương thức fail của lớp Monad, xem ngoại lệ là báo hiệu thất bại.
• Đơn nguyên Maybe và MaybeT có thể biến đổi cung cấp khi tính toán không thành công (ngừng tính toán và trả về Nothing).

xác định/không xác định với đa giải pháp

• Có thể truy xuất tất cả các kết quả có thể có của phép tính đa kết quả, bằng cách đóng gói kết quả trong đơn nguyên MonadPlus. (phương thức mzero làm cho một kết quả thất bại và phương thức mplus thu thập các kết quả thành công).

Họ ngôn ngữ ML và các dẫn xuất

Trong ngôn ngữ ML chuẩn, OCaml và Scala

• Kiểu option có chứa dấu hiệu thành công.

Java

• Giá trị tham chiếu null có thể biểu thị kết quả không thành công (ngoài miền giá trị).