Thông tin
Tên ebooks: Giáo
trình Toán rời rạc
Nguồn: Đại học khoa
học - Đại học Huế
Thể loại: Toán, Tin, CNTT
Định Dạng: doc, zip
Giới
thiệu
Nội dung của tài liệu 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 giúp bạn làm
quen với môn toán rời rạc này một cách hiệu quả hơn.
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
4.1. Đường đi Euler và
đồ thị Euler....................................................................................... 54
4.2. Đường đi Hamilton
và đồ thị Hamilton
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
Post a Comment