TAILIEUCHUNG - 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 10 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về định nghĩa giải thuật; khái niệm định nghĩa giải thuật; bài toán của Hilbert; luận đề Church-Turing; . 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 10 Định nghĩa giải thuật Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Khái niệm 2. Bài toán của Hilbert 3. Luận đề Church-Turing 1 Khái niệm Khái niệm Một giải thuật là tập các lời chỉ dẫn đơn giản để thực hiện một vài nhiệm vụ nào đó Giải thuật thủ tục công thức Giải thuật đóng vai trò quan trọng cho rất nhiều nhiệm vụ khác nhau Ví dụ tìm số nguyên tố tìm ước số chung lớn nhất . . . Trước thế kỉ XX chưa tồn tại khái niệm giải thuật các khái niệm mang tính trực giác về giải thuật 2 Bài toán của Hilbert Bài toán của Hilbert Năm 1900 nhà toán học David Hilbert đưa ra một bài toán có liên quan đến giải thuật Xét bài toán đa thức Ví dụ 6x 3 yz 2 3xy 2 x 3 10 Một nghiệm của đa thức là bộ các giá trị x y z sao cho đa thức có giá trị bằng 0 x 5 y 3 z 0 Bài toán của Hilbert là hãy đưa ra 1 giải thuật để kiểm tra 1 đa thức có nghiệm nguyên hay không 3 Bài toán của Hilbert Cần phải có định nghĩa về giải thuật mới có thể giải quyết được bài toán trên Alonzo Church và Alan Turing đã đưa ra một phép tính Lamda λ để định nghĩa các giải thuật tương đương Mối liên hệ giữa khái niệm không hình thức của giải thuật và định nghĩa chính xác Luận đề Church-Turing 4 Luận đề Church-Turing Luận đề Church-Turing Giải thuật Máy Turing Các cách để mô tả giải thuật Đặc tả hình thức - Mô tả các trạng thái bộ chữ hàm chuyển dịch Là mô tả mức thấp nhất đầy đủ nhất Đặc tả thực thi Implementation-level specification Sử dụng văn xuôi để mô tả - Nội dung của băng nhớ - Cách thức biểu diễn dữ liệu - Cách hoạt động của đầu đọc Đặc tả mức cao High-level specification Sử dụng văn xuôi để mô tả Bỏ qua các chi tiết thực thi - Mã giả Pseudo-code 5 Ví dụ Bài toán Cho đồ thị G V E hãy cho biết đồ thị có liên thông hay không 1 2 3 4 Ta đưa về bài toán đoán nhận ngôn ngữ A G là một đồ thị liên thông Ta cần đưa ra một máy Turing đoán nhận A 6 Ví dụ 2 Biểu diễn đồ thị G thành một ngôn ngữ Ví dụ G 1 2 3 4 1 2 1 3 1 4 2 3 1 2 3 4 1 2 1 3 1 4 2 3 Σ 1 2 3

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Định nghĩa giải thuật
• Bài toán của Hilbert
• Luận đề Church Turing
• 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
• 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ạ
• Ô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
• 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