Đề cương Otomat và Ngôn ngữ hình thức

Nội dung text: Đề cương Otomat và Ngôn ngữ hình thức

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PH ÒNG ISO 9001:2008 ĐỀ CƯƠNG CHI TIẾT MÔN HỌC OTOMAT VÀ NGÔN NGỮ HÌNH THỨC Mã môn: FLO32021 Dùng cho các ngành CÔNG NGHỆ THÔNG TIN Bộ môn phụ trách MẠNG VÀ HỆ THỐNG THÔNG TIN
2. THÔNG TIN VỀ CÁC GIẢNG VIÊN CÓ THỂ THAM GIA GIẢNG DẠY MÔN HỌC 1. Ths. Đỗ Xuân Toàn – Giảng viên cơ hữu - Chức danh, học hàm, học vị: Thạc sỹ - Thuộc bộ môn: Mạng và hệ thống thông tin - Địa chỉ liên hệ: Bộ môn Mạng và hệ thống thông tin - Điện thoại: 031.3739878. Email: toandx@hpu.edu.vn - Các hướng nghiên cứu chính: Mạng máy tính, Quản trị mạng, bảo mật mạng, Lập trình C++, Lập trình hướng đối tượng. 2. Ths. Đỗ Văn Chiểu – Giảng viên cơ hữu - Chức danh, học hàm, học vị: Thạc sỹ - Thuộc bộ môn: Mạng và Hệ thống Thông tin - Địa chỉ liên hệ: Mạng và Hệ thống Thông tin - Điện thoại: 3739878 Email: chieudv@hpu.edu.vn - Các hướng nghiên cứu chính: Trí tuệ nhân tạo, Công nghệ phần mềm. 3. Thông tin về trợ giảng (nếu có): - Họ và tên: - Chức danh, học hàm, học vị: - Thuộc bộ môn/lớp: - Địa chỉ liên hệ: - Điện thoại: Email: - Các hướng nghiên cứu chính:
3. THÔNG TIN VỀ MÔN HỌC 1. Thông tin chung: - Số đơn vị học trình/ tín chỉ: 3/2 - Các môn học tiên quyết: Logic Toán, Lý thuyết đồ thị - Các môn học kế tiếp: Chương trình dịch - Các yêu cầu đối với môn học (nếu có): - Thời gian phân bổ đối với các hoạt động: + Nghe giảng lý thuyết: 22 tiết + Làm bài tập trên lớp: 20 tiết + Thảo luận: + Thực hành, thực tập (ở PTN, nhà máy, điền dó, ): 0 tiết + Hoạt động theo nhóm: + Tự học: 90 tiết + Kiểm tra: 3 tiết 2. Mục tiêu của môn học: - Kiến thức: Cung cấp cho sinh viên các khái niệm về ngôn ngữ, văn phạm, ôtômát hữ hạn, ôtômát đẩy xuống, biểu thức chính quy, làm cơ sở cho nghiên cứu tin học về mặt lý thuyết và cũng làm cơ sở để học tiếp môn Chương trình dịch - Kỹ năng: Giải các bài toán về văn phạm chính quy và otomat hữu hạn, phương pháp giải các bài toán lien quan tới văn phạm phi ngữ cảnh và otomat đẩy xuống. - Thái độ: Yêu thích môn học ,thấy được vai trò của môn học trong các ứng dụng thực tiễn và là nền tảng cho sự phát triển thêm của các môn học tiếp theo 3. Tóm tắt nội dung môn học: - Bài giảng giới thiệu bốn chương:Chương mở đầu trình bày các khái niệm cơ bản về ngôn ngữ và cách xác định ngôn ngữ. Chương 2 giới thiệu về ôtômát hữu hạn và biểu thức chính qui. Văn phạm phi ngữ cảnh và văn phạm chính qui thì được đề cập đến trong chương 3. Chương 4 trình bày ôtômát đẩy xuống. 4. Học liệu: Học liệu bắt buộc: [1].Đỗ Đức Giáo, Toán Rời rạc, Nhà xuất bản Giáo dục, 2005. Học liệu tham khảo [2].Nguyễn Văn Ba, Ngôn ngữ hình thức, NXB KHKT 2002 [3].Đoàn Văn Ban, Giáo trình Ôtômát và Ngôn ngữ hình thức, ĐHQG HN 2003 [4].Đặng Huy Ruận, Lý thuyết Ngôn ngữ h ình thức và Ôtômát, NXB ĐHQG HN 2002
4. 5. Nội dung và hình thức dạy – học: Hình thức dạy – học Nội dung TH, Tổng Lý Bài Thảo Tự học, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) TN, (tiết) thuyết tập luận tự NC tra điền dã Chương 1: Đại cương về ngôn ngữ hình 6 4 24 1 35 thức và cách xác định ngôn ngữ 1.1. Khái niệm chung về ngôn ngữ 1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm. 1.3. Phân loại văn phạm của Chomsky. 1.4. Một số thí dụ về văn phạm. 1.5. Một số tính chất của văn phạm 1.6. Hai bài toán điển hình Bài tập cuối chương Chương2:Ôtomathữu hạn và biểu thức 6 4 24 1 35 chính quy. 2.1. Ôtômat hữu hạn 2.2. Ngôn ngữ chính quy và biểu thức chính quy 2.3. Các tính chất đóng của lớp các ngôn ngữ chính quy 2.4. Bài tập cuối chương Kiểm tra Chương3:Văn phạm phi ngữ cảnh 6 5 24 35 3.1. Xuất xứ và định nghĩa văn phạm phi ngữ cảnh (VPPNC). 3.2. Cây suy dẫn và sự nhập nhằng trong VPPNC 3.3. Giản lược các VPPNC 3.4. Bài tập cuối chương
5. Hình thức dạy – học Nội dung TH, Tổng Lý Bài Thảo Tự học, Kiểm (Ghi cụ thể theo từng chương, mục, tiểu mục) TN, (tiết) thuyết tập luận tự NC tra điền dã Chương4:Ôtoomat đẩy xuống 4.1. Mô tả phi hình thức. 4.2. Định nghĩa Ôtômat đẩy xuống. 5 3 18 1 27 4.3. Mối liên quan giữa các dạng khác nhau của Ôtômat đẩy xuống 4.4. Sự tương đương giữa Ôtômat đẩy xuống và VPPNC 4.5. Bài tập cuối chương Ôn tập cuối kỳ 3 3 Tổng (tiết) 22 20 0 90 3 135 6. Lịch trình tổ chức dạy – học cụ thể: Chi tiết về hình thức Nội dung yêu cầu sv Ghi Tuần Nội dung tổ chức dạy – học phải chuẩn bị trước chú Chương 1: Đại cương về ngôn ngữ hình thức và cách xác định ngôn ngữ 1.1. Khái niệm chung về ngôn ngữ Ôn các kiến thức về 1 Giảng bài trên lớp. 3 tiết t 1.2. Văn phạm và ngôn ngữ sinh ập hợp bởi văn phạm. 1.3. Phân loại văn phạm của Chomsky. 1.4. Một số thí dụ về văn phạm. Giảng bài trên lớp, Nắm vững các kiến 2 Sinh viên làm bài 4 tiết 1.5. Một số tính chất của văn phạm thức của baig trước. trên l 1.6. Hai bài toán điển hình ớp Nắm vững cách vận Sinh viên làm bài dụng các kiến thức tập trên lớp bài trước để thực 3 Bài tập cuối chương 3 tiết Chữa bài tâp trên hiện bài tập. Sinh lớp viên cần thực hiện bài tập đã cho.
6. Kiểm tra lần 1 1tiết Chương 2: Ôtomat hưỡu hạn và 4 Giảng bài trên lớp biểu thức chính quy 2 tiết 2.1. Ôtômat hữu hạn 2.2. Ngôn ngữ chính quy và biểu thức chính quy 5 Giảng bài trên lớp 3 tiết 2.3. Các tính chất đóng của lớp các ngôn ngữ chính quy Hướng dẫn làm bài 6 2.4. Bài tập cuối chương 2 tiết tập trên lớp 2.4. Bài tập cuối chương Chữa bài tập trên 2 t 7 Làm trước bài tập Kiểm tra lần 2 lớp 1 t Chương 3: Văn phạm phi ngữ cảnh 3.1. Xuất xứ và định nghĩa văn 8 phạm phi ngữ cảnh (VPPNC). Giảng bài trên lớp 3.2. Cây suy dẫn và sự nhập nhằng 3 tiết trong VPPNC 9 3.3. Giản lược các VPPNC Giảng bài trên lớp 3 t Hướng dẫn làm bài 10 3.4. Bài tập cuối chương 3 tiết tập trên lớp 3.4. Bài tập cuối chương Chữa bài tập trên 2 tiết 11 Chương 4: Ôtomat đẩy xuống lớp Làm trước bài tập 1 tiết 4.1. Mô tả phi hình thức Giảng bài trên lớp 4.2. Định nghĩa Ôtômat đẩy xuống. 12 4.3. Mối liên quan giữa các dạng Giảng bài trên lớp 3 tiết khác nhau của Ôtômat đẩy xuống 4.4. Sự tương đương giữa Ôtômat Giảng bài trên lớp 1 tiết 13 đẩy xuống và VPPNC Hướng dẫn làm bài 2 tiết 4.5. Bài tập cuối chương tập trên lớp 4.5. Bài tập cuối chương Chữa bài tập trên 2 t 14 Làm trước bài tập Kiểm tra lần 3 lớp 1 t Ôn lại các kiến thức 15 Ôn tập cuối kỳ Giải đáp trên lớp 3 tiết đã học
7. 7. Tiêu chí đánh giá nhiệm vụ giảng viên giao cho sinh viên: - Dựa trên kết quả các bài kiểm tra điều kiện, lên chữa bài trên lớp. 8. Hình thức kiểm tra, đánh giá môn học: - Kiểm tra định kỳ - Làm bài tập - Thi hết môn – Thi tự luận 9. Các loại điểm kiểm tra và trọng số của từng loại điểm: - Điểm quá trình: 3/10 trong đó: + Chuyên cần: 40% + Kiểm tra thường xuyên: 60% - Thi hết môn: 7/10 10. Yêu cầu của giảng viên đối với môn học: - Yêu cầu của giảng viên về điều kiện để tổ chức giảng dạy môn học như: (giảng đường, phòng máy ): Phòng học bình thường trên lớp, có máy chiếu và kết nối Internet. - Yêu cầu của giảng viên đối với sinh viên như: (sự tham gia học tập trên lớp, quy định về thời hạn, chất lượng làm các bài tập về nhà vv ): + Tham gia đầy đủ trên lớp. + Làm bài tập đầy đủ, chất lượng tốt + Có đầy đủ các tài liệu học tập liên quan. Hải Phòng, ngày 22 tháng 6 năm 2011 Chủ nhiệm Bộ môn Người viết đề cương chi tiết Ths. Ngô Trường Giang Ths. Đỗ Xuân Toàn