TAILIEUCHUNG - 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à .

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Quy dẫn
• Bài toán không quyết định được
• Quy dẫn thông qua lịch sử tính toán
• Bài toán PCP
• Quy dẫn ánh xạ
• giáo trình lý thuyết tính toán
• tài liệu về lý thuyết tính toán
• học lý thuyết tính toán
• tự học lý thuyết tính toán
• Tổng quan lý thuyết tính toán
• Khái niệm ngôn ngữ
• Khái niệm văn phạm
• Các phép toán trên ngôn ngữ
• Cơ sở toán học
• Cơ sở thuật toán
• Lý thuyết khoa học máy tính
• Ôtômat hữu hạn
• Văn phạm phi ngữ cảnh
• Ôtômat đẩy xuống
• Mô hình tính toán
• Ngôn ngữ không phi ngữ cảnh
• Ngôn ngữ phi ngữ cảnh
• Định nghĩa giải thuật
• Bài toán của Hilbert
• Luận đề Church Turing
• Ngôn ngữ quyết định được
• Bài toán quyết định được
• Ngôn ngữ chính quy
• Bài toán dừng
• Máy Turing vạn năng
• Phương pháp chéo hóa
• Ngôn ngữ vạn năng
• Bài giảng Lý thuyết hạch toán kế toán
• Lý thuyết hạch toán kế toán
• Hệ thống phương pháp hạch toán kế toán
• Phương pháp chứng từ
• Phương pháp tính giá
• Phương pháp tổng hợp cân đối
• Quy hoạch tuyến tính
• Lý thuyết quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Quy hoạch tuyến tính tổng quát
• Quy hoạch tuyến tính chính tắc
• Bài toán vận tải
• Tính chất của ngôn ngữ chính quy
• Ngôn ngữ không chính quy
• Nhận biết ngôn ngữ không chính quy
• Thiết kế ôtômat hữu hạn
• Toán tử chính quy
• Ôtômat hữu hạn không đơn định
• Toán tử chính quy với NFA
• Nondeterministic Finite State Automaton (NFA)
• Biểu thức chính quy
• Ngôn ngữ của biểu thức chính quy
• Toán học cơ sở
• Máy trừu tượng
• Biểu diễn ngôn ngữ
• Cấu trúc rời rạc
• Văn phạm và ô tô mát
• Kiến thức cơ bản về ngôn ngữ
• Phương pháp phân tích từ vựng
• Phân tích cú pháp
• Automat hữu hạn
• Accepter hữu hạn đơn định
• Accepter hữu hạn không đơn định
• Rút gọn số trạng thái
• Văn phạm chính quy
• Quan hệ ngôn ngữ và biểu thức chính quy
• Ngôn ngữ lập trình
• Biến đổi văn phạm
• Dạng chuẩn quan trọng
• Giải thuật thành viên
• Tập hợp
• Đồ thị
• Boolean logic
• Quan hệ tương đương
• Độ dài dẫn xuất
• Bổ đề Bơm (Pumping Lemma)
• Văn phạm nhập nhằng
• Dạng chuẩn tắc Chomsky
• Quy tắc thay thế
• Máy Turing
• Ngôn ngữ của Turing Machine
• Cấu trúc dữ liệu Turing Machine
• Đoán nhận ngôn ngữ
• Các biến thể của máy Turing
• Máy Turing tùy chọn tại chỗ
• Máy Turing bán vô hạn
• Máy Turing đa băng
• Máy Turing không đơn định