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

Thể loại: Công Nghệ Thông Tin

Tải sách Bài Giảng & Thực Hành Lý Thuyết Đồ Thị - Ths. Nguyễn Đức Thành pdf miễn phí

tên học phần: lý thuyết đồ thị

tên tiếng anh: graph theory

mã học phần: 14258

số đơn vị học trình: 4

trình độ (cho sinh viên năm thứ 2)

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

giảng viên phụ trách: ths. nguyễn Đức thành

bộ môn: mạng mt và truyền thông khoa: công nghệ thông tin

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.

mô tả vắn tắt nội dung học phần:

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

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

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.

nhiệm vụ của sinh viên:

- dự lớp
- bài tập

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

thang điểm: thi giữa kỳ (30%) + thi cuối kỳ (50%) + bài tập cộng điểm (20%)

download link:

ebook có trong tuyển tập​
 

Tải xuống: