Bài giảng Toán rời rạc 2 - Chương mở đầu: Giới thiệu - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Giới thiệu
Ngô Xuân Bách
Vai trò của toán rời rạc trong CNTT
Là lĩnh vực nghiên cứu cơ bản, đóng vai trò quan trọng trong
nhiều lĩnh vực khác của CNTT
o Trí tuệ nhân tạo
o Thuật toán
o Lý thuyết tối ưu
o Học máy
o …
Là môn học cơ sở trong ngành CNTT, nền tảng của nhiều môn
học khác
o Các môn học lập trình
o Cấu trúc dữ liệu và giải thuật
o Nhập môn trí tuệ nhân tạo
o Cơ sở dữ liệu
o …
2
Nội dung môn học (1/7)
Phần 1: Các khái niệm cơ bản của lý thuyết đồ thị
o Định nghĩa đồ thị
o Một số thuật ngữ cơ bản trên đồ thị vô hướng
o Một số thuật ngữ cơ bản trên đồ thị có hướng
o Một số dạng đồ thị đặc biệt
3
Nội dung môn học (2/7)
Phần 2: Biểu diễn đồ thị trên máy tính
o Biểu diễn đồ thị bằng ma trận kề
o Biểu diễn đồ thị bằng ma trận liên thuộc
o Biểu diễn đồ thị bằng danh sách cạnh
o Biểu diễn đồ thị bằng danh sách kề
4
Nội dung môn học (3/7)
Phần 3: Tìm kiếm trên đồ thị
o Thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS)
o Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS)
o Một số ứng dụng của DFS và BFS
5
Nội dung môn học (4/7)
Phần 4: Đồ thị Euler và Đồ thị Hamilton
o Đồ thị Euler
o Đồ thị Hamilton
6
Nội dung môn học (5/7)
Phần 5: Cây và Cây khung của đồ thị
o Cây và các tính chất của cây
o Cây khung của đồ thị
o Bài toán cây khung nhỏ nhất
7
Nội dung môn học (6/7)
Phần 6: Bài toán tìm đường đi ngắn nhất
o Phát biểu bài toán
o Thuật toán Dijkstra
o Thuật toán Bellman-Ford
o Thuật toán Floyd
8
Nội dung môn học (7/7)
Phần 7: Bài toán luồng cực đại trong mạng
o Phát biểu bài toán
o Thuật toán Ford-Fulkerson
9
Thông tin môn học
Giảng viên
o TS. Ngô Xuân Bách, Bộ môn KHMT, Khoa CNTT 1
Tài liệu tham khảo
o Nguyễn Duy Phương. Bài giảng Toán rời rạc 2. Học viện Công nghệ
Bưu chính Viễn Thông, 2013.
o Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán rời rạc. Nhà xuất bản
Giáo dục, 2005.
o Đỗ Đức Giáo. Toán rời rạc. Nhà xuất bản ĐHQG Hà Nội, 2003.
Đánh giá
o Chuyên cần (10%)
o Bài tập (10%)
o Kiểm tra giữa kỳ (10%)
o Thi cuối kỳ (70%)
Thiếu điểm thành phần hoặc
nghỉ quá 20% số buổi sẽ
không được thi hết môn!!!
10
10 trang
21780
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc 2 - Chương mở đầu: Giới thiệu - Ngô Xuân Bách", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_2_chuong_mo_dau_gioi_thieu_ngo_xuan_b.pdf
