Giáo trình Toán rời rạc
oán rời rạc là một lĩnh vực nghiên cứu và xử lý các đối tượng rời rạc dùng để đếm các đối
tượng, và nghiên cứu mối quan hệ giữa các tập rời rạc. Một trong những yếu tố làm Toán rời rạc
trở nên quan trọng là việc lưu trữ, xử lý thông tin trong các hệ thống máy tính về bản chất là rời
rạc. Chính vì lý do đó, Toán học rời rạc là một môn học bắt buộc mang tính chất kinh điển của các
ngành Công nghệ thông tin và Điện tử Viễn thông. Tài liệu hướng dẫn môn học Toán học rời rạc
được xây dựng cho hệ đào tạo từ xa Học viện Công nghệ Bưu chính Viễn thông được xây dựng
dựa trên cơ sở kinh nghiệm giảng dạy môn học và kế thừa từ giáo trình “Toán học rời rạc ứng
dụng trong tin học” của Kenneth Rossen. Tài liệu được trình bày thành hai phần:
Bạn đang xem trước 20 trang tài liệu Giáo trình Toán rời rạc, để xem tài liệu hoàn chỉnh bạn click vào nút TẢI VỀ ở trên
............... 2.7.1. Giới thiệu bài toán.................................................................................................................................. 197 Môc lôc 2.7.2. Phương pháp phản chứng....................................................................................................................... 2.7.3. Nguyên lý Dirichlet................................................................................................................................ NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 2 ........................................................................................................................................ CHƯƠNG III: BÀI TOÁN LIỆT KÊ.................................................................................................................... 3.1. GIỚI THIỆU BÀI TOÁN............................................................................................................................. 3.2. ĐỆ QUI......................................................................................................................................................... 3.2.1. Định nghĩa bằng đệ qui .......................................................................................................................... 3.2.2. Giải thuật đệ qui..................................................................................................................................... 3.3. PHƯƠNG PHÁP SINH................................................................................................................................ 3.4. THUẬT TOÁN QUAY LUI (BACK TRACK) ........................................................................................... NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 3 ........................................................................................................................................ CHƯƠNG IV: BÀI TOÁN TỐI ƯUU...................................................................................................................... 4.1. GIỚI THIỆU BÀI TOÁN............................................................................................................................. 4.2. DUYỆT TOÀN BỘ ...................................................................................................................................... 4.3. THUẬT TOÁN NHÁNH CẬN.................................................................................................................... 4.4. KỸ THUẬT RÚT GỌN GIẢI QUYẾT BÀI TOÁN NGƯỜI DU LỊCH..................................................... 4.4.1.Thủ tục rút gọn........................................................................................................................................ 4.4.2.Thủ tục chọn cạnh phân nhánh (r,c)........................................................................................................ 4.4.3.Thuật toán nhánh cận giải bài toán người du lịch ................................................................................... NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 4 ........................................................................................................................................ CHƯƠNG V: NHỮNG KHÁI NIỆM CƠ BẢN CỦA ĐỒ THỊ .......................................................................... 5.1. ĐỊNH NGHĨA VÀ KHÁI NIỆM ................................................................................................................. 5.2. CÁC THUẬT NGỮ CƠ BẢN...................................................................................................................... 5.3. ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG .................................................................................. 5.4. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH.................................................................................................... 5.4.1. Ma trận kề, ma trận trọng số .................................................................................................................. 5.4.2. Danh sách cạnh (cung ) .......................................................................................................................... 5.4.3. Danh sách kề .......................................................................................................................................... NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 5 ........................................................................................................................................ CHƯƠNG VI: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ .................................................................... 6.1. THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)............................................................................. 6.2. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)................................................ 6.3. DUYỆT CÁC THÀNH PHẦN LIÊN THÔNG CỦA ĐỒ THỊ .................................................................... 6.4. TÌM ĐƯỜNG ĐI GIỮA HAI ĐỈNH BẤT KỲ CỦA ĐỒ THỊ .................................................................... 198 Môc lôc 6.5. ĐƯỜNG ĐI VÀ CHU TRÌNH EULER ....................................................................................................... 6.6. ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON............................................................................................... NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 6 ........................................................................................................................................ CHƯƠNG 7. CÂY (TREE) .................................................................................................................................... 7.1. CÂY VÀ MỘT SỐ TÍNH CHẤT CƠ BẢN................................................................................................. 7.2. MỘT SỐ ỨNG DỤNG QUAN TRỌNG CỦA CÂY................................................................................... 7.2.1. Cây nhị phân tìm kiếm........................................................................................................................... 7.2.2. Cây quyết định ....................................................................................................................................... 7.2.3. Mã tiền tố ............................................................................................................................................... 7.2.4. Mã Huffman........................................................................................................................................... 7.3. CÂY BAO TRÙM........................................................................................................................................ 7.4. TÌM CÂY BAO TRÙM NGẮN NHẤT....................................................................................................... 7.5. THUẬT TOÁN KRUSKAL......................................................................................................................... 7.6. THUẬT TOÁN PRIM.................................................................................................................................. NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 7 ........................................................................................................................................ CHƯƠNG 8. MỘT SỐ BÀI TOÁN QUAN TRỌNG CỦA ĐỒ THỊ .................................................................. 8.1. BÀI TOÁN TÔ MÀU ĐỒ THỊ .................................................................................................................... 8.2. BÀI TOÁN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG .................................................................................. 8.3. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT.............................................................................................. 8.3.1. Thuật toán gán nhãn............................................................................................................................... 8.3.2. Thuật toán Dijkstra ................................................................................................................................ 8.3.3.Thuật toán Floy ....................................................................................................................................... NHỮNG NỘI DUNG CẦN GHI NHỚ............................................................................................................... BÀI TẬP CHƯƠNG 8 ........................................................................................................................................ TÀI LIỆU THAM KHẢO ...................................................................................................................................... 199 TOÁN RỜI RẠC Mã số: 492TNC211 và 492TNC212 Chịu trách nhiệm bản thảo TRUNG TÂM ÐÀO TẠO BƯU CHÍNH VIỄN THÔNG 1 (Tài liệu này được ban hành theo Quyết định số: 374/QĐ-TTĐT1 ngày 22/05/2006 của Giám đốc Học viện Công nghệ Bưu chính Viễn thông) In tại : Công ty cổ phần In Bưu điện Số lượng : 2000 cuốn, khổ 19 x 26 cm Ngày hoàn thành : 01/06/2006.
File đính kèm:
Toán rời rạc- HVBCVT.pdf
