Đề cương chi tiết học phần Lý thuyết đồ thị (Graph Theory)

"Đề cương chi tiết học phần Lý thuyết đồ thị (Graph Theory)" sẽ thông tin đến các bạn thông tin chung về môn học; mục tiêu môn học; tóm tắt nội dung chương trình học; một số yêu cầu của môn học, nhiệm vụ của sinh viên và cách thức đánh giá kết quả học tập của sinh viên.
Nội dung trích xuất từ tài liệu:
Đề cương chi tiết học phần Lý thuyết đồ thị (Graph Theory) BM01.QT02/ĐNT-ĐT TRƯỜNG ĐH NGOẠI NGỮ - TIN HỌC TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN Độc lập – Tự do – Hạnh Phúc ĐỀ CƯƠNG CHI TIẾT HỌC PHẦN 1. Thông tin chung về học phần - Tên học phần : Lý Thuyết Đồ Thị (Graph Theory) - Mã số học phần : 1221124 - Số tín chỉ học phần : 4 (3+1) tín chỉ - Thuộc chương trình đào tạo của bậc, ngành: Bậc Đại học, ngành Công nghệ thông tin - Số tiết học phần :  Nghe giảng lý thuyết : 45 tiết  Làm bài tập trên lớp : 0 tiết  Thảo luận : 0 tiết  Thực hành (ở phòng thực hành): 30 tiết  Hoạt động theo nhóm : 0 tiết  Thực tế: : 0 tiết  Tự học : 120 giờ - Đơn vị phụ trách học phần: Bộ môn Khoa học máy tính / Khoa Công nghệ thông tin 2. Học phần trước: Kỹ thuật lập trình 3. Mục tiêu của học phần: Sau khi hoàn tất các yêu cầu trong học phần, sinh viên có thể: - Nắm vững các khái niệm cơ bản về đồ thị (Graph). - Nắm vững một số phương pháp để giải một số bài toán bằng mô hình đồ thị. - Hiểu và cài đặt được các thuật toán được trình bày trong học phần lý thuyết đồ thị. 4. Chuẩn đầu ra: Nội dung Đáp ứng CĐR CTĐT Kiến thức 4.1.1. Nắm vững một số khái niệm, thuật ngữ, K1 các định lý, các thuật toán cơ bản trong lý thuyết đồ thị. 4.1.2. Hiểu được cách mô hình hóa bài toán K1 thực tế sang bài toán tin học bằng công cụ lý thuyết đồ thị. Kỹ năng 4.2.1. Có kỹ năng tổ chức cấu trúc dữ liệu để S1 lưu trữ đồ thị và cài đặt các thuật toán trong lý thuyết đồ thị. 1 4.2.2. Có kỹ năng nhận diện và giải các bài toán S1 cơ bản trong thực tế bằng cách áp dụng lý thuyết đồ thị trên máy tính. Thái độ 4.3.1. Tôn trọng nội quy lớp học, đi học đầy đủ A2 và lên lớp đúng giờ. 4.3.2. Chuẩn bị bài trước khi đến lớp. Tham gia A3 tích cực trong giờ học. 5. Mô tả tóm tắt nội dung học phần: Học phần Lý thuyết đồ thị cung cấp cho sinh viên các khái niệm cơ bản về đồ thị như đỉnh của đồ thị, cạnh của đồ thị, bậc của đỉnh, đường đi, chu trình, …, Sinh viên cũng được học một số định lý cơ bản trong lý thuyết đồ thị. Dựa trên các khái niệm, các định lý này, sinh viên sẽ được học các thuật toán để giải quyết các bài toán trên đồ thị như tìm đường đi giữa hai đỉnh, tìm đường đi giữa mọi cặp đỉnh, tìm đường đi ngắn nhất, tìm cây khung nhỏ nhất, … Bên cạnh đó, Lý thuyết đồ thị là học phần cung cấp cho sinh viên một mô hình toán học để mô hình hóa các đối tượng trong thực tế (bằng các đỉnh trong đồ thị), mô hình hóa các mối quan hệ giữa các đối tượng trong thực tế (bằng các canh hay cung trong đồ thị), rồi sau đó giải quyết các bài toán trong thực tế bằng cách áp dụng các thuật toán đã được xây dựng trong lý thuyết đồ thị và giải bài toán thực tế đó trên máy tính. 2 6. Nội dung và lịch trình giảng dạy: - Các học phần lý thuyết: Buổi/ Hoạt động của Hoạt động của Giáo trình Nội dung Tài liệu tham khảo Ghi chú Tiết giảng viên sinh viên chính 1 Chương 1. Một số khái niệm cơ - Giới thiệu đề cương - Nghe giảng, ghi chú Cuốn [1]: Phần Cuốn [2]: Chương 1, Giải quyết bản về đồ thị môn học (mô tả nội - Trả lời câu hỏi 2, Chương 1 mục 1.1 mục tiêu 1.1 Một số bài toán dẫn đến khái dung môn học, cách - Làm bài tập 4.1.1, 4.1.2 niệm đồ thị đánh giá môn học, giáo - Đặt câu hỏi Cuốn [3]: Chương 1 1.2 Định nghĩa và phân loại đồ thị trình, tài liệu tham khảo) 1.3 Các thuật ngữ cơ bản - Thuyết giảng Cuốn [4]: Chương 10: 1.4 Một số dạng đồ thị - Đặt câu hỏi mục 10.1, 10.2 - Cho làm bài tập - Giải đáp thắc mắc của sinh viên 2 Chương 2. Biểu diễn đồ thị trên - Thuyết giảng - Nghe giảng, ghi chú Cuốn [1]: Phần Cuốn [2]: Chương 1, Giải quyết máy tính - Hướng dẫn lập trình trên - Trả lời câu hỏi 2, Chương 2, mục 1.2 mục tiêu 2.1 Ma trận kề, ma trận trọng số máy tính - Làm bài tập mục 2.1, 2.2 Cuốn [4]: Chương 10, 4.1.2 2.1.1 Ma trận kề - Đặt câu hỏi - Đặt câu hỏi mục 10.3 4.2.1 2.1.2 Ma trận trọng số - Cho làm bài tập 2.1.3 Cài đặt - Giải đáp thắc mắc của 2.1.4 Giới thiệu Collections sinh viê ...