Đề cương môn học Lý thuyết đồ thị

Nội dung text: Đề cương môn học Lý thuyết đồ thị

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 LÝ THUYẾT ĐỒ THỊ Mã môn: GTH32021 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 Đỗ 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ệ: Bộ môn 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. 2. 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. 3. Ths Nguyễn Thị Xuân Hương - 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: Công nghệ Phần mềm - Địa chỉ liên hệ: Bộ môn Công nghệ Phần mềm - Điện thoại: 01684892389, email: huong_ntxh@hpu.edu.vn - Các hướng nghiên cứu chính: Công nghệ phần mềm, Khai phá dữ liệu, Xử lý ngôn ngữ tự nhiên, Máy học
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: Toán cao cấp 1, Lập trình C - Các môn học kế tiếp: Ôtomát và Ngôn ngữ hình thức - Các yêu cầu đối với môn học (nếu có): Lập trình C, Kỹ năng Toán học - Thời gian phân bổ đối với các hoạt động: + Nghe giảng lý thuyết: 27 + Làm bài tập trên lớp: 15 + Thảo luận: + Thực hành, thực tập (ở PTN, nhà máy, điền dã, thực tập ): 15 + 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: Sinh viên nắm được các khái niệm cơ bản về cấu trúc đồ thị. Hiểu và giải được một số bài toán cơ bản của Lý thuyết đồ thị.Bước đầu thiết kế và lập trình để giải các bài toán liên quan - Kỹ năng;Giải toán lý thuyết, lập trình trên cấu trúc phức tạp của đồ thị - Thái độ: Chuyên cần, 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 : - Học phần này giúp sinh viên nắm được cấu trúc dữ liệu đồ thị, các khái niệm cơ bản và các bài toán trong tin học liên quan đến đồ thị. 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. [2].Đặng Huy Ruận, Lý thuyết đồ thị và ứng dụng, Nhà xuất bản Khoa học và Kỹ thuật - Hà Nội 2000. [3].Nguyễn Đức Nghĩa - Nguyễn Tô Thành, Toán rời rạc, Nhà xuất bản Giáo dục, 1997 Học liệu tham khảo: [4].Đỗ Đức Giáo, Cơ sở Toán trong lập trình, Nhà xuất bản Khoa học và Kỹ thuật, 1998.
4. [5].Bollobás, Béla, Modern Graph Theory, New York: Springer-Verlag. ISBN 0-387- 98488-7. [6].West, Douglas B, Introduction to Graph Theory (2ed), Upper Saddle River: Prentice Hall. 2001, ISBN 0-13-014400-2. 5. Nội dung và hình thức dạy - học: Hình thức dạy - học Nội dung Bà Kiểm Lý Th T Tổng (Ghi cụ thể theo từng chương, mục, i ả TH, TN, ự tra thuy o h c, t (tiết) tiểu mục) ế t n dã ọ ự t ậ lu n Điề NC p ậ Chương 1. Khái niệm cơ bản của 5 0 0 10 15 đồ thị 1.1 Các khái niệm cơ bản 1 0 1.2 Biểu diễn đồ thị 2 1.2.1 Biểu diễn đồ thị bằng hình học 1.2.2 Biểu diễn đồ thị trên máy tính 1.3 Tính liên thông của đồ thị 1 1.4 Phân loại đồ thị 1 Chương 2. Các thuật toán tìm 5 5 20 30 kiếm trên đồ thị 2.1 Tìm kiếm theo chiều sâu trên đồ 1 2 thị 2.2 Tìm kiếm theo chiều rộng trên 2 2 đồ thị 2.3 Tìm đường đi và kiểm tra tính 2 1 liên thông Chương 3. Đồ thị Euler và đồ thị 4 3 15 1 18 Hamilton Đồ thị Euler 2 2 Đồ thị Hamilton 2 1 Chương 4. Cây và cây khung của 9 5 30 1 45 đồ thị 4.1 Cây 1 4.2 Cây khung 2 4.3 Các thuật toán tìm cây khung và ứng dụng 4.3.1 Thuật toán tìm cây khung 2 2 trên đồ thị không có trọng số 4.3.2 Thuật toán tìm cây khung 2 1 trên đồ thị có trọng số - Thuật toán PRIM 4.3.3 Thuật toán tìm cây khung 2 2 trên đồ thị có trọng số - Thuật toán KRUSKAL
5. Chương 5. Bài toán tìm đường 4 2 15 1 22 đi ngắn nhất 5.1 Khái niệm 1 5.2 Ứng dụng 1 5.3 Thuật toán Dijstra 2 2 Tổng tiết 27 15 90 3 135 6. Lịch trình tổ chức dạy - học cụ thể: Chi ti t v hình N i dung yêu c u ế ề ộ ầ Ghi Tu n N i dung th c t ch c d y - sv ph i chu n b ầ ộ ứ ổ ứ ạ ả ẩ ị chú học trước Chương 1. Khái niệm cơ bản - Ngôn ngữ lập của đồ thị trình 1.1 Các khái niệm cơ bản - Nghe giảng - Thảo luận 1. 1.2 Biểu diễn đồ thị 1.2.1 Biểu diễn đồ thị bằng hình - Nghe giảng học - Làm ví dụ 1.2.2 Biểu diễn đồ thị trên máy Toán ma trận tính 1.3 Tính liên thông của đồ thị - Nghe giảng Toán ma trận Logic toán 1.4 Phân loại đồ thị - Nghe giảng 2. Chương 2. Các thuật toán tìm kiếm trên đồ thị 2.1 Tìm kiếm theo chiều sâu - Nghe giảng Đọc trước tài liệu trên đồ thị - Làm ví dụ Chuẩn bị các câu hỏi liên quan 2.1 Tìm kiếm theo chiều sâu -Làm BT trên đồ thị (tiếp-phần BT) 3. 2.2 Tìm kiếm theo chiều rộng - Nghe giảng trên đồ thị - Làm ví dụ 2.2 Tìm kiếm theo chiều rộng - Nghe giảng Đọc trước tài liệu trên đồ thị (tiếp) 4. - Làm ví dụ Chuẩn bị các câu - Làm BT hỏi liên quan 2.3 Tìm đường đi và kiểm tra - Nghe giảng Đọc trước tài liệu tính liên thông - Làm ví d Chu n b các câu 5. ụ ẩ ị - Làm BT hỏi liên quan
6. Chương 3. Đồ thị Euler và đồ - Nghe giảng Đọc trước tài liệu 6. thị Hamilton - Thảo luận 3.1 Đồ thị Euler 3.1 Đồ thị Euler (tiếp-BT) - Nghe giảng 7. 3.2 Đồ thị Hamilton - Làm ví dụ - Làm BT 3.2 Đồ thị Hamilton (tiếp) Đọc trước tài liệu Chương 4. Cây và cây khung - Nghe giảng 8. của đồ thị - Thảo luận 4.1 Cây 4.2 Cây khung 4.3 Các thuật toán tìm cây - Nghe giảng Đọc trước tài liệu khung và ứng dụng - Th o lu n 9. ả ậ 4.3.1 Thuật toán tìm cây - Nghe giảng Đọc trước tài liệu khung trên đồ thị không có - Thảo luận trọng số 4.3.1 Thuật toán tìm cây - Nghe giảng Đọc trước tài liệu khung trên đồ thị không có - Thảo luận Chuẩn bị các câu 10. trọng số - Làm bài tập áp hỏi xoay quanh dụng ứng dụng thực tiễn của thuật toán 4.3.2 Thuật toán tìm cây - Nghe giảng Đọc trước tài liệu khung trên đồ thị có trọng - Thảo luận Chuẩn bị các câu 11. số - Thuật toán PRIM - Làm bài tập áp hỏi xoay quanh dụng ứng dụng thực tiễn của thuật toán 4.3.2 Thuật toán tìm cây - Nghe giảng Đọc trước tài liệu khung trên đồ thị có trọng - Thảo luận Chuẩn bị các câu số - Thuật toán PRIM (tiếp- - Làm bài tập áp hỏi xoay quanh 12. BT) dụng ứng dụng thực tiễn c a thu t toán 4.3.3 Thuật toán tìm cây ủ ậ khung trên đồ thị có trọng số - Thuật toán KRUSKAL 4.3.3 Thuật toán tìm cây - Nghe giảng Đọc trước tài liệu khung trên đồ thị có trọng - Th o lu n 13. ả ậ số - Thuật toán KRUSKAL - Làm BT (tiếp –BT) Chương 5. Bài toán tìm đường đi ngắn nhất
7. 5.1 Khái niệm 5.2 Ứng dụng - Nghe giảng Đọc trước tài liệu - Thảo luận Chuẩn bị các câu hỏi xoay quanh ứng dụng thực tiễn 14. 5.3 Thuật toán Dijstra - Nghe giảng Đọc trước tài liệu - Thảo luận Chuẩn bị các câu - Làm bài tập áp hỏi xoay quanh dụng ứng dụng thực tiễn của thuật toán 5.3 Thuật toán Dijstra - Nghe giảng Đọc trước tài liệu - Thảo luận Chuẩn bị các câu 15. - Làm bài tập áp hỏi xoay quanh dụng ứng dụng thực tiễn của thuật toán 7. Tiêu chí đánh giá bài tập, nhiệm vụ giảng viên giao cho sinh viên: - Có đầy đủ tài liệu, giáo trình phục vụ học tập - Hoàn thành bài tập được giao 8. Phương pháp và hình thức kiểm tra đánh giá môn học: - Làm bài tập, kiểm tra định kỳ. - 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 về điều kiện để tổ chức giảng dạy môn học: Giảng đường, máy chiếu. - Yêu cầu đối với sinh viên: Đi học đầy đủ, đúng giờ, học bài trước khi đến lớp. 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. Đỗ Văn Chiểu