Bài giảng Lý thuyết tính toán - Bài 00. Giới thiệu

GV: Nguyễn Ngọc Tú Tu.NguyenNgoc@hoasen.edu.vn Bài 00. Giới thiệu LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) TIN331 Mục tiêu môn học  Cung cấp những kiến thức cơ bản về ngôn ngữ, văn phạm và ôtômát.  Cung cấp các phương pháp phân tích từ vựng, phân tích cú pháp.  Cơ sở cho việc tìm hiểu các ngôn ngữ lập trình.  Rèn luyện kỹ năng lập trình cho sinh viên Cấu trúc môn học  Thời gian 60 tiết  30 tiết Lý thuyết + Bài tập  30 tiết Thực hành Nội dung học 1. Giới thiệu về lý thuyết tính toán 2. Ôtômát hữu hạn 3. Ngôn ngữ chính qui và văn phạm chính qui 4. Các tính chất của ngôn ngữ chính qui 5. Ngôn ngữ phi ngữ cảnh 6. Đơn giản hóa văn phạm phi ngữ cảnh và các dạng chuẩn 7. Ôtômát đẩy xuống 8. Các tính chất của ngôn ngữ phi ngữ cảnh 9. Máy Turing Các nội dung liên quan  Ngôn ngữ lập trình  Trình biên dịch (*)  Toán tin học  Kỹ thuật chứng minh Qui nạp  Phản chứng  Kỹ thuật mô phỏng Đánh giá  3 phần đánh giá  Cuối kỳ (Thi trắc nghiệm) 40%  Thời gian: 120 phút  Số lượng: 50 câu  Được phép xem tài liệu trong 4 tờ giấy A4  Project (Hiện thực công cụ) 30% + 10%  Bài tập định kỳ 20%  Cộng điểm 10% Tài liệu Tham khảo 1. Giáo trình lý thuyết Ngôn ngữ Hình thức và Automat - Hồ Văn Quân [2012]. 2. Introduction to Languages and The Theory of Computation, Fourth Edition. John C. Martin [2011] 3. Introduction to Theory of Computation. Anil Maheshwari , Michiel Smid, [2012].