Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Bài giảng Lý thuyết tính toán: Bài 14 - Phạm Xuân Cường
Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Lý thuyết tính toán: Bài 14 - Phạm Xuân Cường
Tùng Châu
92
35
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuố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@tlu.edu.vn 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à .
TÀI LIỆU LIÊN QUAN
Bài giảng Lý thuyết tính toán: Bài 14 - Phạm Xuân Cường
lý thuyết tính toán
Bài giảng Lý thuyết tính toán: Bài 01 - Nguyễn Ngọc Tú
Bài giảng Lý thuyết tính toán: Bài mở đầu - Phạm Xuân Cường
Bài giảng Lý thuyết tính toán: Bài 3 - Phạm Xuân Cường
Bài giảng Lý thuyết tính toán: Bài 10 - Phạm Xuân Cường
Bài giảng Lý thuyết tính toán: Bài 11 - Phạm Xuân Cường
Bài giảng Lý thuyết tính toán: Bài 13 - Phạm Xuân Cường
Bài giảng Lý thuyết tính toán: Bài 7 - Phạm Xuân Cường
Bài giảng Lý thuyết tính toán: Bài 2 - Phạm Xuân Cường
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.