Đang chuẩn bị liên kết để tải về tài liệu:
CÁC BÀI TOÁN NP – KHÓ VÀ NP - ĐẦY ĐỦ

Tham khảo tài liệu các bài toán np – khó và np - đầy đủ , công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Các thuật toán không đơn định được thực hiện như thế nào? Để thực hiện thuật toán không đơn định, chúng ta cần thực hiện các tính toán theo dòng điều khiển được quy định bởi các câu lệnh như khi ta thực hiện thuật toán đơn định, chỉ có một điều khác biệt so với thuật toán đơn định là, khi gặp hàm lựa chọn choice(S) thì sự tính toán được phân thành nhiều nhánh, mỗi nhánh tương ứng với một giá trị được chọn ra từ tập S, tất cả các nhánh này sẽ làm việc đồng thời và độc lập với nhau. Mỗi nhánh tính toán đó khi gặp một hàm lựa chọn khác choice(S’) lại được phân thành nhiều nhánh tính toán khác. Và như vậy, khi thực hiện thuật toán không đơn định, chúng ta cần phải thực hiện đồng thời và độc lập nhiều đường tính toán (được tạo thành từ các nhánh tương ứng với các lựa chọn). Do đó, ta có thể quan niệm rằng, thuật toán không đơn định mô tả sự tính toán song song không hạn chế. Khi mà một đường tính toán gặp lệnh success, thì có nghĩa là đường tính toán đó đã được tạo thành từ các lựa chọn đúng đắn và đã thành công cho ra nghiệm của bài toán, khi đó tất cả các đường tính toán đều dừng làm việc. Còn nếu một đường tính toán gặp lệnh failure, thì có nghĩa là đường tính toán này đã thất bại, không cho ra nghiệm của bài toán, và chỉ riêng đường này dừng làm việc. Máy có khả năng thực hiện thuật toán không đơn định sẽ được gọi là