Khoa Cong Nghe Thong Tin - DH Nong Lam TP.HCM

 

       Bộ Giáo Dục và Đào Tạo                                   CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

TRƯỜNG ĐẠI HỌC NÔNG LÂM TP.HCM                        Độc Lập – Tự Do – Hạnh Phúc

 

 

CHƯƠNG TRÌNH TRÌNH ĐỘ (ĐẠI HỌC, CAO ĐẲNG)

NGÀNH ĐÀO TẠO:

 

 

ĐỀ CƯƠNG CHI TIẾT HỌC PHẦ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

 

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

-         Dụng cụ học tập

-         Khác

  1. Tiêu chuẩn đánh giá sinh viên:

-         Dự lớp

-         Thảo luận

-         Bản thu hoạch

-         Thuyết trình

-         Thi cuối học phần

-         Khác

  1. Thang điểm:

 

 

Ngày           tháng          năm

     Duyệt của                                                          Ý kiến                                Người biên soạn

Trưởng Khoa/BM                                            Trưởng Bộ Môn

 

           

 

 

 

 

 

Số lần xem trang: 2165
Điều chỉnh lần cuối:

Trang liên kết

Chào bạn !
X

Xin mời bạn đặt câu hỏi !

Họ tên
 
Email /Fb/Điện thoại:

Nội dung:

Số xác nhận : ba năm chín bảy bốn

Xem trả lời của bạn !