tailieunhanh - Bài giảng Lý thuyết tính toán: Bài 14 - Phạm Xuân Cường

Bài giảng Lý thuyết tính toán: Bài 14 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về quy dẫn; các bài toán không quyết định được, bài toán kiểm tra rỗng; quy dẫn thông qua lịch sử tính toán; bài toán PCP; quy dẫn ánh xạ; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LÝ THUYẾT TÍNH TOÁN BÀI 14 Quy dẫn Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Giới thiệu 2. Các bài toán không quyết định được 3. Quy dẫn thông qua lịch sử tính toán 4. Bài toán PCP 5. Quy dẫn ánh xạ 1 Giới thiệu Giới thiệu Quy dẫn là một kỹ thuật chứng minh sự không quyết định được của một ngôn ngữ Một quy dẫn là cách chuyển 1 bài toán khó thành bài toán khác dễ hơn có thể giải được Có thể sử dụng lời giải của bài toán dễ để áp dụng cho bài toán khó Quy dẫn thường hay xuất hiện trong các bài toán về toán học Ví dụ - Bài toán tìm đường đi trong một thành phố mới đến khó Bài toán tìm bản đồ của thành phố đó từ bản đồ đường đi - Bài toán tính diện tích hình chữ nhật Bài toán đo chiều dài chiều rộng 2 Logic ngược Quy dẫn đưa một bài toán khó về một bài toán dễ hơn Nếu bài toán khó là không thể giải được Bài toán dễ phải chắc chắn là không giải được Ví dụ - Bài toán A Sống mãi mãi - Bài toán B Trẻ mãi Nếu ta tìm được lời giải cho bài toán B Có thể giải được bài toán A Nhưng bài toán A là không thể xảy ra Bài toán B cũng không thể xảy ra Tương tự trong LTTT bài toán A là không quyết định được bài toán B cũng không quyết định được 3 Logic Ta biết rằng ATM là không quyết định được Xét bài toán P P có quyết định được hay không Định lý 1 P là không quyết định được Chứng minh Giả sử P là quyết định được Quy dẫn ATM Bài toán khó về P Bài toán dễ hơn Sử dụng thuật toán quyết định P để giải ATM Nhưng ta biết rằng không tồn tại bộ quyết định cho ATM Mâu thuẫn P là không quyết định được 4 Các bài toán không quyết định được Các bài toán không quyết định được Bài toán dừng Kiểm tra xem một máy Turing có dừng trên một đầu vào w đã cho hay không HALTTM M là một máy Turing và M dừng với đầu vào w Vậy HALTTM là quyết định được hay không Không 5 Bài toán dừng Định lý 2 HALTTM là không quyết định được Chứng minh Ý TƯỞNG Giả sử HALTTM là quyết định được Quy dẫn ATM về HALTTM ATM quyết định được Mâu thuẫn với định lý trong bài trước Điều giả sử là .