tailieunhanh - Bài giảng Toán rời rạc - ĐH Lâm Nghiệp

Nội dung của Bài giảng Toán rời rạc này được bố trí trong 4 phần, không kể lời nói đầu, mục lục, tài liệu tham khảo và phần phụ lục: Phần 1 được dành cho Chương I đề cập đến Thuật toán; Phần 2 được dành cho Chương II nói đến bài toán đếm; Phần 3 đây là phần chiếm nhiều trang nhất trong giáo trình, bàn về Lý thuyết đồ thị và các ứng dụng gồm 5 chương: Đồ thị, Đồ thị Euler và đồ thị Hamilton, Một số bài toán tối ưu trên đồ thị, Cây, Đồ thị phẳng và tô màu đồ thị; Phần 4 được dành cho Chương 8, chương cuối cùng, đề cập đến Đại số Boole. | ThS. KHƯƠNG THỊ QUỲNH TO N RêI R C TRƯỜNG ĐẠI HỌC LÂM NGHIỆP - 2019 ThS. KHƢƠNG THỊ QUỲNH BÀI GIẢNG TOÁN RỜI RẠC TRƢỜNG ĐẠI HỌC LÂM NGHIỆP - 2019 MỤC LỤC MỤC LỤC . i LỜI NÓI ĐẦU . 1 Chƣơng 1. THUẬT TOÁN . 3 . Khái niệm thuật toán . 3 . Định nghĩa . 3 . Các đặc trưng của thuật toán . 4 . Thuật toán tìm kiếm . 5 . Bài toán tìm kiếm . 5 . Thuật toán tìm kiếm tuyến tính . 5 . Thuật toán tìm kiếm nhị phân . 6 . Độ phức tạp của thuật toán . 7 . Khái niệm về độ phức tạp của một thuật toán . 7 . So sánh độ phức tạp của các thuật toán . 9 . Đánh giá độ phức tạp của một thuật toán. 11 . Số nguyên và thuật toán . 13 . Thuật toán Euclide . 13 . Biểu diễn các số nguyên . 15 . Thuật toán cho các phép tính số nguyên . 16 . Thuật toán đệ quy . 19 . Khái niệm đệ quy . 19 . Đệ quy và lặp . 20 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1. 23 Chƣơng 2. BÀI TOÁN ĐẾM . 25 . Cơ sở của phép đếm . 25 . Những nguyên lý đếm cơ bản . 25 . Nguyên lý bù trừ . 27 . Nguyên lý dirichlet . 29 . Mở đầu. 29 . Nguyên lý Dirichlet tổng quát . 29 . Một số ứng dụng của nguyên lý Dirichlet . 30 . Chỉnh hợp va tổ hợp suy rộng. 32 . Chỉnh hợp có lặp . 32 i . Tổ hợp lặp . 32 . Hoán vị của tập hợp có các phần tử giống nhau . 33 . Sự phân bố các đồ vật vào trong hộp . 33 . Sinh các hoán vị và tổ hợp . 34 . Sinh các hoán vị. 34 . Sinh các tổ hợp . 35 . Hệ thức truy hồi . 36 . Khái niệm mở đầu và mô hình hóa bằng hệ thức truy hồi . 36 . Giải các hệ thức truy hồi . 37 . Quan hệ chia để trị . 38 . Mở đầu . 38 . Hệ thức chia để trị . 39 BÀI TẬP CHƢƠNG 2 . 41 Chƣơng 3. ĐỒ THỊ . 43 . Định nghĩa và thí dụ . 43 . Định nghĩa . 44 . Định nghĩa . 44 . Định nghĩa . 44 . Định nghĩa . 44 . Định nghĩa . 45 . Bậc của đỉnh . 46 . Định nghĩa . 46 . Định nghĩa . 46 . Mệnh đề . 46 . Hệ quả. 46 . Mệnh đề . 47 . Định .