TAILIEUCHUNG - 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 mở đầu - Phạm Xuân Cường được biên soạn nhằm giúp học viên hiểu biết rõ về các cơ sở toán học, cơ sở thuật toán và lý thuyết khoa học máy tính để có thể thiết kế một hệ thống hay mô hình tính toán trên máy tính; có khả năng phân tích vấn đề và xác định các thành phần cần thiết để có thể giải quyết vấn đề đó trên máy tính; . 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 Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Tổng quan môn học Mục tiêu môn học Trang bị cho học viên những hiểu biết cũng như kĩ năng về nền tảng tính toán trong tin học bao gồm - Hiểu biết rõ về các cơ sở toán học cơ sở thuật toán và lý thuyết khoa học máy tính để có thể thiết kế một hệ thống hay mô hình tính toán trên máy tính - Có khả năng phân tích vấn đề và xác định các thành phần cần thiết để có thể giải quyết vấn đề đó trên máy tính - Có kiến thức nền tảng về một số mô hình tính toán phổ biến - Có khả năng thực hiện một số thuật toán tính toán cơ bản Trang web môn học http 1 Tổng quan môn học Giáo trình - Nhập môn Lý thuyết tính toán Khoa CNTT ĐH Thủy Lợi 2009 - Introduction to the theory of computation 2nd Michael Sipser MIT 2004 2 Đánh giá môn học Điểm môn học - Điểm quá trình 40 Kiểm tra giữa kỳ 90 Chuyên cần 10 - Thi cuối kỳ 60 Thời gian thi Kiểm tra 60 phút và thi 90 phút Hình thức Viết Không sử dụng tài liệu 3 Điều kiện thi cuối kỳ Môn học 30 tiết lý thuyết LT 15 tiết thực hành TH 15 buổi - 15 buổi LT 2 tiết bắt đầu từ tuần 1 - 5 buổi TH 3 tiết bắt đầu từ tuần 3 Điều kiện Không nghỉ quá 2 buổi Thực hành Thi đạt bài kiểm tra giữa kỳ 4 điểm thang điểm 10 4 Nội dung môn học Bài giảng Lý thuyết Thực hành 1 Kiến thức nền tảng 2 Ôtômat hữu hạn 3 Ôtômat hữu hạn không đơn định Bài TH 1 4 Biểu thức chính quy 5 Ngôn ngữ không chính quy Bài TH 2 6 Văn phạm phi ngữ cảnh 7 Ôtômat đẩy xuống Bài TH 3 8 Ngôn ngữ không phi ngữ cảnh 9 Máy Turing Bài TH 4 10 Các biến thể của máy Turing 11 Định nghĩa giải thuật Bài TH 5 12 Các ngôn ngữ quyết định được 13 Bài toán dừng 14 Quy dẫn 15 Thi giữa kỳ 5 Questions 5

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• 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
• 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ữ
• 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
• Đị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