Đại học Ngoại ngữ - Tin học TP. Hồ Chí MinhKHOA CÔNG NGHỆ THÔNG TIN

Học phần: Lý thuyết đồ thị

01_koenigsberg

Thời gian/địa điểm:

Nhóm Thời gian Địa điểm
TH1503 Thứ hai (từ 4/9/2017), 06g45 – 09g15 Phòng B37
TH1504 Thứ hai (từ 4/9/2017), 09g30 – 12g00 Phòng B34

 

Giảng viên: Tôn Quang Toại

 

Liên lạc:

 

Nội dung

  • Mô tả nội dung học phần: Học phần này giới thiệu các khái niệm cơ bản về đồ thị (Graph) và một số thuật toán cơ bản trong lý thuyết đồ thị. Qua đó, người học có một công cụ để mô hình hóa các bài toán lập trình thành các bài toán đồ thị, rồi sử dụng các thuật toán trong lý thuyết đồ thị để giải quyết các bài toán lập trình.
  • Môn học trước: Cấu trúc dữ liệu và giải thuật
  • Giáo trình:

[1] Toán rời rạc, Nguyễn Đức Nghĩa và Nguyễn Tô Thành, NXB Giáo dục, 2006

Slides

  • Tài liệu tham khảo:

[1] Graph Algorithms, Shimon Even, Cambridge University Press, 2011

[2] Graph Theory and Applications: With Exercises and Problems, Jean-Claude Fournier, Wiley, 2009

[3] Discrete Mathematics and Its Applications Seventh Edition, Kenneth H. Rosen, McGraw-Hill, 2011

 

Bài tập thực hành:

 

Kiểm tra:

  • Giữa kỳ (30%): làm bài thực hành tại phòng máy
  • Cuối kỳ (70%): làm bài tự luận

 

Lịch học:

STT

Ngày Nội dung

Slides

1 Thứ hai, 28/08/2017 Một số khái niệm cơ bản về đồ thị Giới thiệu
Chương 1
2 Thứ hai, 04/09/2017 Biểu diễn đồ thị trên máy tính: ma trân kề, ma trận trọng số Chương 2
3 Thứ hai, 11/09/2017 Biểu diễn đồ thị trên máy tính: Danh sách kề, danh sách cạnh  
4 Thứ hai, 18/09/2017 Tìm kiếm trên đồ thị – DFS  Chương 3
5 Thứ hai, 25/09/2017 Tìm kiếm trên đồ thị – BFS  
6 Thứ hai, 02/10/2017 Đồ thị Euler  Chương 4
7 Thứ hai, 09/10/2017 Đồ thị Hamilton  
8 Thứ hai, 16/10/2017 Đường đi ngắn nhất trên đồ thị: thuật toán Dijkstra  Chương 5
9 Thứ hai, 23/10/2017 Đường đi ngắn nhất trên đồ thị: thuật toán Ford – Bellman, thuật toán Floyd  
10 Thứ hai, 06/11/2017 Cây: thuật toán xây dựng cây  Chương 6
11 Thứ hai, 13/11/2017 Cây: thuật toán Kruskal, thuật toán Prim  
12 Thứ hai, 20/11/2017 Luồng cực đại trong mạng: khái niệm  Chương 7
13 Thứ hai, 27/11/2017 Luồng cực đại trong mạng: thuật toán Ford – Fulkerson  
14 Thứ hai, 04/12/2017 Tô màu đồ thị  Chương 8
15 Thứ hai, 04/12/2017 Ôn tập