Bài Giảng & Thực Hành Lý Thuyết Đồ Thị - Ths. Nguyễn Đức Thành

Discussion in 'Công Nghệ Thông Tin' started by admin, Nov 11, 2013.

  1. admin

    admin Thư Viện Sách Việt Staff Member Quản Trị Viên

    1. Tên học phần: Lý thuyết đồ thị
    Tên tiếng Anh: Graph Theory
    1. Mã học phần: 14258
    2. Số đơn vị học trình: 4
    3. Trình độ (cho sinh viên năm thứ 2)
    4. Phân bổ thời gian:
    - Lên lớp: 30 tiết
    - Thực tập phòng thí nghiệm, thực hành: 30 tiết
    1. Giảng viên phụ trách: ThS. Nguyễn Đức Thành
    2. Bộ môn: Mạng MT và truyền thông Khoa: Công Nghệ Thông Tin
    3. Mục tiêu của học phần:
    Sau khi hoàn tất học phần, sinh viên có khả năng :
    - Cung cấp cho sinh viên những kiến thức cần thiết về lý thuyết đồ thị và các ứng dụng trên máy tính.
    - Nâng cao kỹ năng lập trình thông qua các bài tập thực hành.
    1. Mô tả vắn tắt nội dung học phần:
    2. Các học phần tiên quyết hay có liên quan: Lập trình A2, Toán rời rạc
    3. Nội dung chi tiết phân bố theo chương trình và số tiết tương ứng của học phần:
    Phần 1: Giới thiệu (6 LT / 3 TH)
    + Lý thuyết (6 tiết)
    - Các khái niệm cơ bản về đồ thị, đỉnh, cạnh
    - Các loại đồ thị
    - Bậc của đỉnh, đồ thị cân bằng
    - Biểu diễn đồ thị
    - Hai đồ thị đẳng hình
    - Đường đi và chu trình
    - Miền liên thông, liên thông mạnh
    - Một số định lý và tính chất quan trọng
    - Giới thiệu một số khái niệm cơ bản về độ phức tạp của thuật toán
    + Thực hành (3tiết)
    - Biểu diễn đồ thị bằng ma trận kề và bằng danh sách liên kết
    - Viết chương trình tính bậc của một đỉnh, xác định đồ thị cân bằng

    Phần 2: Đường đi và chu trình (6 LT / 6 TH)
    + Lý thuyết (6 tiết)
    - Đường đi Euler và chu trình Euler
    - Điều kiện cần và đủ để xác định một chu trình, đường đi Euler
    - Thuật toán xác định chu trình, đường đi Euler
    - Đường đi Halmiton và chu trình Halmiton
    - Bài toán người du lịch
    - Các quy tắc xác định chu trình Halmiton
    - Một số định lý và tính chất quan trọng
    + Thực hành (6tiết)
    - Viết chương trình xác định đường đi, chu trình Euler
    - Viết chương trình xác định đường đi, chu trình Halmiton, khảo sát thời gian thực hiện thuật toán khi số đỉnh đồ thị tăng
    https://drive.google.com/drive/folders/1yLBzZ1rSQoNjmWeJTM6cEZ3WGQHg04L1
    Phần 3: Đồ thị phẳng và bài toán tô màu đồ thị (6 LT / 3 TH)
    + Lý thuyết (6 tiết)
    - Định nghĩa đồ thị phẳng, đồ thị phẳng tối đa
    - Công thức Euler
    - Bài toán 3 nhà – 3 giếng
    - Bất đẳng thức cạnh – đỉnh
    - Định lý Kuratowski
    - Bài toán tô màu bản đồ
    + Thực hành (3tiết)
    - Giải bài toán tô màu đồ thị, khảo sát thời gian thực hiện thuật toán khi số đỉnh của đồ thị tăng

    Phần 4: Cây (6 LT / 9 TH)
    + Lý thuyết (6 tiết)
    - Định nghĩa cây, cây có gốc
    - Định lý Daisy Chain
    - Cây bao trùm
    - Thuật toán xác định cây bao trùm theo chiều sâu – DFS
    - Thuận toán xác định cây bao trùm theo chiều rộng – BFS
    - Kiểm tra tính liên thông của một đồ thị
    - Cây bao trùm nhỏ nhất – thuật toán xác định cây bao trùm tối thiểu
    - Thuật toán Prim
    - Thuật toán Kruskal
    + Thực hành (9tiết)
    - Cài đặt thuật toán DFS, BFS (so sánh thời gian thực hiện DFS và BFS)
    - Cài đặt thuật toán Prim
    - Cài đặt thuật toán Kruskal
    - So sánh thời gian thực hiện Prim và Kruskal

    Phần 5: Đồ thị có hướng – Bài toán tìm đường đi ngắn nhất (6 LT / 9 TH)
    + Lý thuyết (6 tiết)
    - Thuật toán Dijsktra
    - Thuật toán Floyd
    - Bài toán xác định bao đóng bắc cầu – thuật toán Warshall
    + Thực hành (9tiết)
    - Cài đặt thuật toán Dijsktra
    - Cài đặt thuật toán Floy
    1. Tài liệu học tập, trang thiết bị phụ vụ thực hành thực tập, trợ huấn cụ
    Tài liệu tham khảo
    1. W W L Chen, Discrete mathematics, University of London.
    2. Nguyễn Cam, Chu Đức Khánh, Lý thuyết Đồ thị, 1998.
    3. S. Even, Graph Algorithms, 1979.
    4. Robert Sedgewick, Cẩm nang thuật toán – tập 2 (bản dịch Việt ngữ), 1995.
    5. L. Lovász and K. Vesztergombi, Discrete Mathematics, Lecture notes, Yale University, Spring 1999.
    6. Nguyễn Trung Trực, Cấu trúc Dữ liệu, Khoa CNTT – Đại học Bách Khoa TP.HCM, 1997.
    1. Nhiệm vụ của sinh viên:
    - Dự lớp
    - Bài tập
    1. Tiêu chuẩn đánh giá sinh viên:
    - Thi giữa kỳ
    - Thi cuối học phần
    - Bài tập cộng điểm
    1. Thang điểm: Thi giữa kỳ (30%) + thi cuối kỳ (50%) + bài tập cộng điểm (20%)
    Download Link:
    http://fit.hcmuaf.edu.vn/data/file/LTDT.rar
    eBook có trong tuyển tập DVD Tin Học
     

Share This Page