Với sự nổ lực hết mình của bản thân, chúng tôi thiết nghĩ đây sẽ là tài liệu tham khảo tốt cho các giáo viên giảng dạy học phần toán rời rạc, các học viên cao học ngành Phương pháp giảng dạy Toán, các thí sinh thi vào cao học ngành công nghệ thông tin, | BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NÔNG NGHIỆP HÀ NỘI VŨ KIM THÀNH TOÁN RỜI RẠC Giáo trình dành cho sinh viên ngành công nghệ thông tin Hà nội 2008 Trường Đại học Nông nghiệp Hà Nội - Giáo trình Giáo trình Toán Rời rạc. 0 MỤC LỤC 5 Lời nói đâu Chương 1. THUẬT TOÁN 7 1. Định nghĩa 7 2. Mô tả thuật toán bằng lưu đồ 8 3. Mô tả thuật toán bằng ngôn ngữ phỏng Pascal 9 4. Độ phức tạp của thuật toán 14 5. Thuật toán tìm kiếm 18 6. Thuật toán đệ quy 19 7. Một số thuật toán về số nguyên 23 BÀI TẬP CHƯƠNG 1 28 Chương 2. BÀI TOÁN ĐẾM 32 1. Nguyên lý cộng và nguyên lý nhân 32 2. Chỉnh hợp. Hoán vị. Tổ hợp. 35 3. Nguyên lý bù trừ 42 4. Giải các hệ thức truy hồi 44 5. Bài toán liệt kê. 51 6. Bài toán tồn tại 61 BÀI TẬP CHƯƠNG 2 64 Chương 3. CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ 69 1. Các định nghĩa về đồ thi và biểu diễn hình học của đồ thị 69 2. Biểu diễn đồ thị bằng đại s ố 79 3. Sự đẳng cấu của các đồ thị 82 4. Tính liên thông trong đồ thị 84 5. Số ổn định trong số ổn định ngoài và nhân của đồ thị 88 6. Sắc số của đồ thị 91 BÀI TẬP CHƯƠNG 3 93 Chương 4. ĐỒ THỊ EULER ĐỒ THỊ HAMILTON ĐỒ THỊ PHẲNG 98 1. Đồ thị Euler 98 2. Đồ thị Hamilton 103 3. Đồ thi phẳng 108 BÀI TẬP CHƯƠNG 4 113 Chương 5. CÂY VÀ MỘT SỐ ỨNG DỤNG CỦA CÂY 117 1. Cây . các tính chất cơ bản của cây 118 2. Cây nhị phân và phép duyệt cây 122 3. Một vài ứng dụng của cây 126 Trường Đại học Nông nghiệp Hà Nội - Giáo trình Giáo trình Toán Rời 4. Cây khung cây bao trùm của đồ thị 131 5. Hệ chu trình độc lập 134 6. Cây khung nhỏ nhất 136 BÀI TẬP CHƯƠNG 5 142 Chương 6. MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ 147 1. Bài toán đường đi ngắn nhất trong đồ thị 147 2. Tâm Bán kính Đường kính của đồ thị 152 3. Mạng và Luồng 153 4. Bài toán du lịch 160 BÀI TẬP CHƯƠNG 6 166 Chương 7. ĐẠI SỐ BOOLE 172 1. Hàm Boole 172 2. Biểu thức Boole 174 3. Định nghĩa đại số Boole theo tiên đề 176 4. Biểu diễn các hàm Boole 177 5. Các cổng logic 183 6 Tối thiểu hoá hàm Boole 185 BÀI TẬP CHƯƠNG 7
