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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - ĐH Lâm Nghiệp 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 1.1. Khái niệm thuật toán ................................................................................... 3 1.1.1. Định nghĩa ............................................................................................ 3 1.1.2. Các đặc trưng của thuật toán ............................................................... 4 1.2. Thuật toán tìm kiếm .................................................................................... 5 1.2.1. Bài toán tìm kiếm .................................................................................. 5 1.2.2. Thuật toán tìm kiếm tuyến tính ............................................................. 5 1.2.3. Thuật toán tìm kiếm nhị phân ............................................................... 6 1.3. Độ phức tạp của thuật toán ......................................................................... 7 1.3.1. Khái niệm về độ phức tạp của một thuật toán ..................................... 7 1.3.2. So sánh độ phức tạp của các thuật toán .............................................. 9 1.3.3. Đánh giá độ phức tạp của một thuật toán.......................................... 11 1.4. Số nguyên và thuật toán ............................................................................ 13 1.4.1. Thuật toán Euclide ............................................................................. 13 1.4.2. Biểu diễn các số nguyên ..................................................................... 15 1.4.3. Thuật toán cho các phép tính số nguyên ............................................ 16 1.5. Thuật toán đệ quy ..................................................................................... 19 1.5.1. Khái niệm đệ quy ................................................................................ 19 1.5.2. Đệ 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 2.1. Cơ sở của phép đếm .................................................................................. 25 2.1.1. Những nguyên lý đếm cơ bản ............................................................. 25 2.1.2. Nguyên lý bù trừ ................................................................................. 27 2.2. Nguyên lý dirichlet ................................................................................... 29 2.2.1. Mở đầu................................................................................................ 29 2.2.2. Nguyên lý Dirichlet tổng quát ............................................................ 29 2.2.3. Một số ứng dụng của nguyên lý Dirichlet .......................................... 30 2.3. Chỉnh hợp va tổ hợp suy rộng................................................................... 32 2.3.1. Chỉnh hợp có lặp ................................................................................ 32 i 2.3.2. Tổ hợp lặp ........................................................................................... 32 2.3.3. Hoán vị của tập hợp có các phần tử giống nhau ............................... 33 2.3.4. Sự phân bố các đồ vật vào trong hộp ................................................. 33 2.4. Sinh các hoán vị và tổ hợp ........................................................................ 34 2.4.1. Sinh các hoán vị.................................................................................. 34 2.4.2. Sinh các tổ hợp ................................................................................... 35 2.5. Hệ thức truy hồi ........................................................................................ 36 2.5.1. Khái niệm mở đầu và mô hình hóa bằng hệ thức truy hồi ................. 36 2.5.2. Giải các hệ thức truy hồi .................................................................... 37 2.6. Quan hệ chia để trị .................................................................................... 38 2.6.1. Mở đầu .............................................................................................. ...