Tài liệu Toán rời rạc

Toán rời rạc (146 trang)
Được sự động viên mạnh mẽ của các đồng nghiệp trong các Khoa Toán-Cơ-Tin học, Công nghệ Thông tin và Vật lý (Trường Đại học Khoa học-Đại học Huế), các Khoa Toán và Tin học (Trường Đại học Sư phạm-Đại học Huế) và đặc biệt do nhu cầu học tập của các sinhv.v.v

MỤC LỤC
Lời nói đầu 1
Mục lục 2
Chương I: Thuật toán 4
1.1. Khái niệm thuật toán .4
1.2. Thuật toán tìm kiếm .5
1.3. Độ phức tạp của thuật toán 7
1.4. Số nguyên và thuật toán .12
1.5. Thuật toán đệ quy .17
Bài tập Chương I .19
Chương II: Bài toán đếm 22
2.1. Cơ sở của phép đếm .22
2.2. Nguyên lý Dirichlet 25
2.3. Chỉnh hợp và tổ hợp suy rộng 28
2.4. Sinh các hoán vị và tổ hợp 30
2.5. Hệ thức truy hồi 32
2.6. Quan hệ chia để trị 34
Bài tập Chương II 35
Chương III: Đồ thị .37
3.1. Định nghĩa và thí dụ .37
3.2. Bậc của đỉnh .39
3.3. Những đơn đồ thị đặc biệt 41
3.4. Biểu diễn đồ thị bằng ma trận và sự đẳng cấu đồ thị .44
3.5. Các đồ thị mới từ đồ thị cũ .46
3.6. Tính liên thông .47
Bài tập Chương III .51
Chương IV: Đồ thị Euler và Đồ thị Hamilton 54
4.1. Đường đi Euler và đồ thị Euler 54
4.2. Đường đi Hamilton và đồ thị Hamilton 58
Bài tập Chương IV .64
Chương V: Một số bài toán tối ưu trên đồ thị 67
5.1. Đồ thị có trọng số và bài toán đường đi ngắn nhất 67
5.2. Bài toán luồng cực đại 72
5.3. Bài toán du lịch .79
Bài tập Chương V 84
Chương VI: Cây .87
6.1. Định nghĩa và các tính chất cơ bản .87
6.2. Cây khung và bài toán tìm cây khung nhỏ nhất .88
6.3. Cây có gốc 93
6.4. Duyệt cây nhị phân .94
Bài tập Chương VI .101
Chương VII: Đồ thị phẳng và tô màu đồ thị .104
7.1. Đồ thị phẳng .104
7.2. Đồ thị không phẳng 106
7.3. Tô màu đồ thị 107
Bài tập Chương VII .112
Chương VIII: Đại số Boole .114
8.1. Khái niệm đại số Boole 114
8.2. Hàm Boole 117
8.3. Mạch lôgic 120
8.4. Cực tiểu hoá các mạch lôgic .125
Bài tập Chương VIII 132
Tài liệu tham khảo .134
Phần phụ lục 135
Phụ lục 1 .135
Phụ lục 2 .158