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à:
Đị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:
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ế:
Họ ngôn ngữ ML và các dẫn xuất.
Trong ngôn ngữ ML chuẩn, OCaml và Scala