linhxinh_sweetcandy
New Member
Link tải luận văn miễn phí cho ae
MỤC LỤC
PHẦN 1. BÀI TOÁN LIỆT KÊ . 1
§1. NHẮC LẠI MỘT SỐKIẾN THỨC ĐẠI SỐTỔHỢP .2
1.1. CHỈNH HỢP LẶP .2
1.2. CHỈNH HỢP KHÔNG LẶP.2
1.3. HOÁN VỊ.2
1.4. TỔHỢP.3
§2. PHƯƠNG PHÁP SINH (GENERATION) .4
2.1. SINH CÁC DÃY NHỊPHÂN ĐỘDÀI N .5
2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ.6
2.3. LIỆT KÊ CÁC HOÁN VỊ.8
§3. THUẬT TOÁN QUAY LUI .12
3.1. LIỆT KÊ CÁC DÃY NHỊPHÂN ĐỘDÀI N.12
3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ.13
3.3. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K .15
3.4. BÀI TOÁN PHÂN TÍCH SỐ.16
3.5. BÀI TOÁN XẾP HẬU .18
§4. KỸTHUẬT NHÁNH CẬN .24
4.1. BÀI TOÁN TỐI ƯU.24
4.2. SỰBÙNG NỔTỔHỢP .24
4.3. MÔ HÌNH KỸTHUẬT NHÁNH CẬN.24
4.4. BÀI TOÁN NGƯỜI DU LỊCH .25
4.5. DÃY ABC .28
PHẦN 2. CẤU TRÚC DỮLIỆU VÀ GIẢI THUẬT . 33
§1. CÁC BƯỚC CƠBẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC.34
1.1. XÁC ĐỊNH BÀI TOÁN.34
1.2. TÌM CẤU TRÚC DỮLIỆU BIỂU DIỄN BÀI TOÁN .34
1.3. TÌM THUẬT TOÁN .35
1.4. LẬP TRÌNH .37
1.5. KIỂM THỬ.37
1.6. TỐI ƯU CHƯƠNG TRÌNH .38
§2. PHÂN TÍCH THỜI GIAN THỰC HIỆN GIẢI THUẬT .40
2.1. ĐỘPHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT .40
2.2. XÁC ĐỊNH ĐỘPHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT .40
2.3. ĐỘPHỨC TẠP TÍNH TOÁN VỚI TÌNH TRẠNG DỮLIỆU VÀO.43
2.4. CHI PHÍ THỰC HIỆN THUẬT TOÁN.43
§3. ĐỆQUY VÀ GIẢI THUẬT ĐỆQUY . 45
3.1. KHÁI NIỆM VỀ ĐỆQUY . 45
3.2. GIẢI THUẬT ĐỆQUY . 45
3.3. VÍ DỤVỀGIẢI THUẬT ĐỆQUY . 46
3.4. HIỆU LỰC CỦA ĐỆQUY . 50
§4. CẤU TRÚC DỮLIỆU BIỂU DIỄN DANH SÁCH. 52
4.1. KHÁI NIỆM DANH SÁCH . 52
4.2. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH . 52
§5. NGĂN XẾP VÀ HÀNG ĐỢI . 58
5.1. NGĂN XẾP (STACK). 58
5.2. HÀNG ĐỢI (QUEUE). 60
§6. CÂY (TREE). 64
6.1. ĐỊNH NGHĨA . 64
6.2. CÂY NHỊPHÂN (BINARY TREE) . 65
6.3. BIỂU DIỄN CÂY NHỊPHÂN . 67
6.4. PHÉP DUYỆT CÂY NHỊPHÂN. 69
6.5. CÂY K_PHÂN . 70
6.6. CÂY TỔNG QUÁT. 71
§7. KÝ PHÁP TIỀN TỐ, TRUNG TỐVÀ HẬU TỐ. 74
7.1. BIỂU THỨC DƯỚI DẠNG CÂY NHỊPHÂN . 74
7.2. CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC. 74
7.3. CÁCH TÍNH GIÁ TRỊBIỂU THỨC . 75
7.4. CHUYỂN TỪDẠNG TRUNG TỐSANG DẠNG HẬU TỐ. 78
7.5. XÂY DỰNG CÂY NHỊPHÂN BIỂU DIỄN BIỂU THỨC. 80
§8. SẮP XẾP (SORTING) . 82
8.1. BÀI TOÁN SẮP XẾP. 82
8.2. THUẬT TOÁN SẮP XẾP KIỂU CHỌN (SELECTIONSORT) . 84
8.3. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLESORT). 85
8.4. THUẬT TOÁN SẮP XẾP KIỂU CHÈN. 85
8.5. SHELLSORT. 87
8.6. THUẬT TOÁN SẮP XẾP KIỂU PHÂN ĐOẠN (QUICKSORT) . 88
8.7. THUẬT TOÁN SẮP XẾP KIỂU VUN ĐỐNG (HEAPSORT) . 92
8.8. SẮP XẾP BẰNG PHÉP ĐẾM PHÂN PHỐI (DISTRIBUTION COUNTING) . 95
8.9. TÍNH ỔN ĐỊNH CỦA THUẬT TOÁN SẮP XẾP (STABILITY) . 96
8.10. THUẬT TOÁN SẮP XẾP BẰNG CƠSỐ(RADIXSORT). 97
8.11. THUẬT TOÁN SẮP XẾP TRỘN (MERGESORT). 102
8.12. CÀI ĐẶT . 105
8.13. ĐÁNH GIÁ, NHẬN XÉT. 112
§9. TÌM KIẾM (SEARCHING) . 116
9.1. BÀI TOÁN TÌM KIẾM.116
9.2. TÌM KIẾM TUẦN TỰ(SEQUENTIAL SEARCH) .116
9.3. TÌM KIẾM NHỊPHÂN (BINARY SEARCH) .116
9.4. CÂY NHỊPHÂN TÌM KIẾM (BINARY SEARCH TREE - BST) .117
9.5. PHÉP BĂM (HASH).122
9.6. KHOÁ SỐVỚI BÀI TOÁN TÌM KIẾM .122
9.7. CÂY TÌM KIẾM SỐHỌC (DIGITAL SEARCH TREE - DST).123
9.8. CÂY TÌM KIẾM CƠSỐ(RADIX SEARCH TREE - RST) .126
9.9. NHỮNG NHẬN XÉT CUỐI CÙNG .131
PHẦN 3. QUY HOẠCH ĐỘNG . 133
§1. CÔNG THỨC TRUY HỒI.134
1.1. VÍ DỤ.134
1.2. CẢI TIẾN THỨNHẤT.135
1.3. CẢI TIẾN THỨHAI.137
1.4. CÀI ĐẶT ĐỆQUY .137
§2. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG .139
2.1. BÀI TOÁN QUY HOẠCH .139
2.2. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG .139
§3. MỘT SỐBÀI TOÁN QUY HOẠCH ĐỘNG .143
3.1. DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT.143
3.2. BÀI TOÁN CÁI TÚI.148
3.3. BIẾN ĐỔI XÂU .150
3.4. DÃY CON CÓ TỔNG CHIA HẾT CHO K.154
3.5. PHÉP NHÂN TỔHỢP DÃY MA TRẬN.159
3.6. BÀI TẬP LUYỆN TẬP.163
PHẦN 4. CÁC THUẬT TOÁN TRÊN ĐỒTHỊ. 169
§1. CÁC KHÁI NIỆM CƠBẢN .170
1.1. ĐỊNH NGHĨA ĐỒTHỊ(GRAPH).170
1.2. CÁC KHÁI NIỆM.171
§2. BIỂU DIỄN ĐỒTHỊTRÊN MÁY TÍNH.173
2.1. MA TRẬN LIỀN KỀ(MA TRẬN KỀ) .173
2.2. DANH SÁCH CẠNH.174
2.3. DANH SÁCH KỀ.175
2.4. NHẬN XÉT.176
§3. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒTHỊ.177
3.1. BÀI TOÁN .177
3.2. THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DEPTH FIRST SEARCH).178
3.3. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (BREADTH FIRST SEARCH) .184
3.4. ĐỘPHỨC TẠP TÍNH TOÁN CỦA BFS VÀ DFS . 189
§4. TÍNH LIÊN THÔNG CỦA ĐỒTHỊ. 190
4.1. ĐỊNH NGHĨA . 190
4.2. TÍNH LIÊN THÔNG TRONG ĐỒTHỊVÔ HƯỚNG. 191
4.3. ĐỒTHỊ ĐẦY ĐỦVÀ THUẬT TOÁN WARSHALL . 191
4.4. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH . 195
§5. VÀI ỨNG DỤNG CỦA CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒTHỊ. 205
5.1. XÂY DỰNG CÂY KHUNG CỦA ĐỒTHỊ. 205
5.2. TẬP CÁC CHU TRÌNH CƠBẢN CỦA ĐỒTHỊ. 208
5.3. ĐỊNH CHIỀU ĐỒTHỊVÀ BÀI TOÁN LIỆT KÊ CẦU . 208
5.4. LIỆT KÊ KHỚP . 214
§6. CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒTHỊEULER . 218
6.1. BÀI TOÁN 7 CÁI CẦU . 218
6.2. ĐỊNH NGHĨA . 218
6.3. ĐỊNH LÝ . 218
6.4. THUẬT TOÁN FLEURY TÌM CHU TRÌNH EULER. 219
6.5. CÀI ĐẶT . 220
6.6. THUẬT TOÁN TỐT HƠN . 222
§7. CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒTHỊHAMILTON . 225
7.1. ĐỊNH NGHĨA . 225
7.2. ĐỊNH LÝ . 225
7.3. CÀI ĐẶT . 226
§8. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT . 230
8.1. ĐỒTHỊCÓ TRỌNG SỐ.230
8.2. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT . 230
8.3. TRƯỜNG HỢP ĐỒTHỊKHÔNG CÓ CHU TRÌNH ÂM - THUẬT TOÁN FORD BELLMAN . 232
8.4. TRƯỜNG HỢP TRỌNG SỐTRÊN CÁC CUNG KHÔNG ÂM - THUẬT TOÁN DIJKSTRA. 234
8.5. THUẬT TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP . 237
8.6. TRƯỜNG HỢP ĐỒTHỊKHÔNG CÓ CHU TRÌNH - THỨTỰTÔ PÔ . 240
8.7. ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH - THUẬT TOÁN FLOYD. 242
8.8. NHẬN XÉT . 245
§9. BÀI TOÁN CÂY KHUNG NHỎNHẤT . 247
9.1. BÀI TOÁN CÂY KHUNG NHỎNHẤT . 247
9.2. THUẬT TOÁN KRUSKAL (JOSEPH KRUSKAL - 1956) . 247
9.3. THUẬT TOÁN PRIM (ROBERT PRIM - 1957). 252
§10. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG. 256
10.1. BÀI TOÁN . 256
10.2. LÁT CẮT, ĐƯỜNG TĂNG LUỒNG, ĐỊNH LÝ FORD - FULKERSON. 256
10.3. CÀI ĐẶT . 258
10.4. THUẬT TOÁN FORD - FULKERSON (L.R.FORD & D.R.FULKERSON - 1962).262
§11. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI TRÊN ĐỒTHỊHAI PHÍA .266
11.1. ĐỒTHỊHAI PHÍA (BIPARTITE GRAPH) .266
11.2. BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG VÀ CÁC KHÁI NIỆM.266
11.3. THUẬT TOÁN ĐƯỜNG MỞ.267
11.4. CÀI ĐẶT .268
§12. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI VỚI TRỌNG SỐCỰC TIỂU TRÊN ĐỒTHỊHAI
PHÍA - THUẬT TOÁN HUNGARI .273
12.1. BÀI TOÁN PHÂN CÔNG .273
12.2. PHÂN TÍCH .273
12.3. THUẬT TOÁN .274
12.4. CÀI ĐẶT .278
12.5. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI VỚI TRỌNG SỐCỰC ĐẠI TRÊN ĐỒTHỊHAI PHÍA .284
12.6. NÂNG CẤP.284
§13. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI TRÊN ĐỒTHỊ.290
13.1. CÁC KHÁI NIỆM.290
13.2. THUẬT TOÁN EDMONDS (1965) .291
13.3. PHƯƠNG PHÁP LAWLER (1973) .293
13.4. CÀI ĐẶT .295
13.5. ĐỘPHỨC TẠP TÍNH TOÁN .299
TÀI LIỆU ĐỌC THÊM . 301
PHẦN 1. BÀI TOÁN LIỆT KÊ
Có một số bài toán trên thực tế yêu cầu chỉ rõ: trong một tập các đối
tượng cho trước có bao nhiêu đối tượng thoả mãn những điều kiện
nhất định. Bài toán đó gọi là bài toán đếm.
Trong lớp các bài toán đếm, có những bài toán còn yêu cầu chỉ rõ
những cấu hình tìm được thoả mãn điều kiện đã đánh giá là những cấu hình
nào. Bài toán yêu cầu đưa ra danh sách các cấu hình có thể có gọi là
bài toán liệt kê.
Để giải bài toán liệt kê, cần xác định được một thuật toán để có
thể theo đó lần lượt xây dựng được tất cả các cấu hình đang quan tâm.
Có nhiều phương pháp liệt kê, nhưng chúng cần đáp ứng được
hai yêu cầu dưới đây:
• Không được lặp lại một cấu hình
• Không được bỏ sót một cấu hình
Có thể nói rằng, phương pháp liệt kê là phương kế cuối cùng để giải
được một số bài toán tổ hợp hiện nay. Khó khăn chính của phương
pháp này chính là sự bùng nổ tổ hợp dẫn tới sự đòi hỏi lớn về không
gian và thời gian thực hiện chương trình. Tuy nhiên cùng với sự phát
triển của máy tính điện tử, bằng phương pháp liệt kê, nhiều bài toán tổ
hợp đã tìm thấy lời giải. Qua đó, ta cũng nên biết rằng chỉ nên dùng
phương pháp liệt kê khi không còn một phương pháp nào khác
tìm ra lời giải. Chính những nỗ lực giải quyết các bài toán thực tế
không dùng phương pháp liệt kê đã thúc đẩy sự phát triển của nhiều
ngành toán học.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
PHẦN 1. BÀI TOÁN LIỆT KÊ . 1
§1. NHẮC LẠI MỘT SỐKIẾN THỨC ĐẠI SỐTỔHỢP .2
1.1. CHỈNH HỢP LẶP .2
1.2. CHỈNH HỢP KHÔNG LẶP.2
1.3. HOÁN VỊ.2
1.4. TỔHỢP.3
§2. PHƯƠNG PHÁP SINH (GENERATION) .4
2.1. SINH CÁC DÃY NHỊPHÂN ĐỘDÀI N .5
2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ.6
2.3. LIỆT KÊ CÁC HOÁN VỊ.8
§3. THUẬT TOÁN QUAY LUI .12
3.1. LIỆT KÊ CÁC DÃY NHỊPHÂN ĐỘDÀI N.12
3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ.13
3.3. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K .15
3.4. BÀI TOÁN PHÂN TÍCH SỐ.16
3.5. BÀI TOÁN XẾP HẬU .18
§4. KỸTHUẬT NHÁNH CẬN .24
4.1. BÀI TOÁN TỐI ƯU.24
4.2. SỰBÙNG NỔTỔHỢP .24
4.3. MÔ HÌNH KỸTHUẬT NHÁNH CẬN.24
4.4. BÀI TOÁN NGƯỜI DU LỊCH .25
4.5. DÃY ABC .28
PHẦN 2. CẤU TRÚC DỮLIỆU VÀ GIẢI THUẬT . 33
§1. CÁC BƯỚC CƠBẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC.34
1.1. XÁC ĐỊNH BÀI TOÁN.34
1.2. TÌM CẤU TRÚC DỮLIỆU BIỂU DIỄN BÀI TOÁN .34
1.3. TÌM THUẬT TOÁN .35
1.4. LẬP TRÌNH .37
1.5. KIỂM THỬ.37
1.6. TỐI ƯU CHƯƠNG TRÌNH .38
§2. PHÂN TÍCH THỜI GIAN THỰC HIỆN GIẢI THUẬT .40
2.1. ĐỘPHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT .40
2.2. XÁC ĐỊNH ĐỘPHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT .40
2.3. ĐỘPHỨC TẠP TÍNH TOÁN VỚI TÌNH TRẠNG DỮLIỆU VÀO.43
2.4. CHI PHÍ THỰC HIỆN THUẬT TOÁN.43
§3. ĐỆQUY VÀ GIẢI THUẬT ĐỆQUY . 45
3.1. KHÁI NIỆM VỀ ĐỆQUY . 45
3.2. GIẢI THUẬT ĐỆQUY . 45
3.3. VÍ DỤVỀGIẢI THUẬT ĐỆQUY . 46
3.4. HIỆU LỰC CỦA ĐỆQUY . 50
§4. CẤU TRÚC DỮLIỆU BIỂU DIỄN DANH SÁCH. 52
4.1. KHÁI NIỆM DANH SÁCH . 52
4.2. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH . 52
§5. NGĂN XẾP VÀ HÀNG ĐỢI . 58
5.1. NGĂN XẾP (STACK). 58
5.2. HÀNG ĐỢI (QUEUE). 60
§6. CÂY (TREE). 64
6.1. ĐỊNH NGHĨA . 64
6.2. CÂY NHỊPHÂN (BINARY TREE) . 65
6.3. BIỂU DIỄN CÂY NHỊPHÂN . 67
6.4. PHÉP DUYỆT CÂY NHỊPHÂN. 69
6.5. CÂY K_PHÂN . 70
6.6. CÂY TỔNG QUÁT. 71
§7. KÝ PHÁP TIỀN TỐ, TRUNG TỐVÀ HẬU TỐ. 74
7.1. BIỂU THỨC DƯỚI DẠNG CÂY NHỊPHÂN . 74
7.2. CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC. 74
7.3. CÁCH TÍNH GIÁ TRỊBIỂU THỨC . 75
7.4. CHUYỂN TỪDẠNG TRUNG TỐSANG DẠNG HẬU TỐ. 78
7.5. XÂY DỰNG CÂY NHỊPHÂN BIỂU DIỄN BIỂU THỨC. 80
§8. SẮP XẾP (SORTING) . 82
8.1. BÀI TOÁN SẮP XẾP. 82
8.2. THUẬT TOÁN SẮP XẾP KIỂU CHỌN (SELECTIONSORT) . 84
8.3. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLESORT). 85
8.4. THUẬT TOÁN SẮP XẾP KIỂU CHÈN. 85
8.5. SHELLSORT. 87
8.6. THUẬT TOÁN SẮP XẾP KIỂU PHÂN ĐOẠN (QUICKSORT) . 88
8.7. THUẬT TOÁN SẮP XẾP KIỂU VUN ĐỐNG (HEAPSORT) . 92
8.8. SẮP XẾP BẰNG PHÉP ĐẾM PHÂN PHỐI (DISTRIBUTION COUNTING) . 95
8.9. TÍNH ỔN ĐỊNH CỦA THUẬT TOÁN SẮP XẾP (STABILITY) . 96
8.10. THUẬT TOÁN SẮP XẾP BẰNG CƠSỐ(RADIXSORT). 97
8.11. THUẬT TOÁN SẮP XẾP TRỘN (MERGESORT). 102
8.12. CÀI ĐẶT . 105
8.13. ĐÁNH GIÁ, NHẬN XÉT. 112
§9. TÌM KIẾM (SEARCHING) . 116
9.1. BÀI TOÁN TÌM KIẾM.116
9.2. TÌM KIẾM TUẦN TỰ(SEQUENTIAL SEARCH) .116
9.3. TÌM KIẾM NHỊPHÂN (BINARY SEARCH) .116
9.4. CÂY NHỊPHÂN TÌM KIẾM (BINARY SEARCH TREE - BST) .117
9.5. PHÉP BĂM (HASH).122
9.6. KHOÁ SỐVỚI BÀI TOÁN TÌM KIẾM .122
9.7. CÂY TÌM KIẾM SỐHỌC (DIGITAL SEARCH TREE - DST).123
9.8. CÂY TÌM KIẾM CƠSỐ(RADIX SEARCH TREE - RST) .126
9.9. NHỮNG NHẬN XÉT CUỐI CÙNG .131
PHẦN 3. QUY HOẠCH ĐỘNG . 133
§1. CÔNG THỨC TRUY HỒI.134
1.1. VÍ DỤ.134
1.2. CẢI TIẾN THỨNHẤT.135
1.3. CẢI TIẾN THỨHAI.137
1.4. CÀI ĐẶT ĐỆQUY .137
§2. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG .139
2.1. BÀI TOÁN QUY HOẠCH .139
2.2. PHƯƠNG PHÁP QUY HOẠCH ĐỘNG .139
§3. MỘT SỐBÀI TOÁN QUY HOẠCH ĐỘNG .143
3.1. DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT.143
3.2. BÀI TOÁN CÁI TÚI.148
3.3. BIẾN ĐỔI XÂU .150
3.4. DÃY CON CÓ TỔNG CHIA HẾT CHO K.154
3.5. PHÉP NHÂN TỔHỢP DÃY MA TRẬN.159
3.6. BÀI TẬP LUYỆN TẬP.163
PHẦN 4. CÁC THUẬT TOÁN TRÊN ĐỒTHỊ. 169
§1. CÁC KHÁI NIỆM CƠBẢN .170
1.1. ĐỊNH NGHĨA ĐỒTHỊ(GRAPH).170
1.2. CÁC KHÁI NIỆM.171
§2. BIỂU DIỄN ĐỒTHỊTRÊN MÁY TÍNH.173
2.1. MA TRẬN LIỀN KỀ(MA TRẬN KỀ) .173
2.2. DANH SÁCH CẠNH.174
2.3. DANH SÁCH KỀ.175
2.4. NHẬN XÉT.176
§3. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒTHỊ.177
3.1. BÀI TOÁN .177
3.2. THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DEPTH FIRST SEARCH).178
3.3. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (BREADTH FIRST SEARCH) .184
3.4. ĐỘPHỨC TẠP TÍNH TOÁN CỦA BFS VÀ DFS . 189
§4. TÍNH LIÊN THÔNG CỦA ĐỒTHỊ. 190
4.1. ĐỊNH NGHĨA . 190
4.2. TÍNH LIÊN THÔNG TRONG ĐỒTHỊVÔ HƯỚNG. 191
4.3. ĐỒTHỊ ĐẦY ĐỦVÀ THUẬT TOÁN WARSHALL . 191
4.4. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH . 195
§5. VÀI ỨNG DỤNG CỦA CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒTHỊ. 205
5.1. XÂY DỰNG CÂY KHUNG CỦA ĐỒTHỊ. 205
5.2. TẬP CÁC CHU TRÌNH CƠBẢN CỦA ĐỒTHỊ. 208
5.3. ĐỊNH CHIỀU ĐỒTHỊVÀ BÀI TOÁN LIỆT KÊ CẦU . 208
5.4. LIỆT KÊ KHỚP . 214
§6. CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒTHỊEULER . 218
6.1. BÀI TOÁN 7 CÁI CẦU . 218
6.2. ĐỊNH NGHĨA . 218
6.3. ĐỊNH LÝ . 218
6.4. THUẬT TOÁN FLEURY TÌM CHU TRÌNH EULER. 219
6.5. CÀI ĐẶT . 220
6.6. THUẬT TOÁN TỐT HƠN . 222
§7. CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒTHỊHAMILTON . 225
7.1. ĐỊNH NGHĨA . 225
7.2. ĐỊNH LÝ . 225
7.3. CÀI ĐẶT . 226
§8. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT . 230
8.1. ĐỒTHỊCÓ TRỌNG SỐ.230
8.2. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT . 230
8.3. TRƯỜNG HỢP ĐỒTHỊKHÔNG CÓ CHU TRÌNH ÂM - THUẬT TOÁN FORD BELLMAN . 232
8.4. TRƯỜNG HỢP TRỌNG SỐTRÊN CÁC CUNG KHÔNG ÂM - THUẬT TOÁN DIJKSTRA. 234
8.5. THUẬT TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP . 237
8.6. TRƯỜNG HỢP ĐỒTHỊKHÔNG CÓ CHU TRÌNH - THỨTỰTÔ PÔ . 240
8.7. ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH - THUẬT TOÁN FLOYD. 242
8.8. NHẬN XÉT . 245
§9. BÀI TOÁN CÂY KHUNG NHỎNHẤT . 247
9.1. BÀI TOÁN CÂY KHUNG NHỎNHẤT . 247
9.2. THUẬT TOÁN KRUSKAL (JOSEPH KRUSKAL - 1956) . 247
9.3. THUẬT TOÁN PRIM (ROBERT PRIM - 1957). 252
§10. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG. 256
10.1. BÀI TOÁN . 256
10.2. LÁT CẮT, ĐƯỜNG TĂNG LUỒNG, ĐỊNH LÝ FORD - FULKERSON. 256
10.3. CÀI ĐẶT . 258
10.4. THUẬT TOÁN FORD - FULKERSON (L.R.FORD & D.R.FULKERSON - 1962).262
§11. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI TRÊN ĐỒTHỊHAI PHÍA .266
11.1. ĐỒTHỊHAI PHÍA (BIPARTITE GRAPH) .266
11.2. BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG VÀ CÁC KHÁI NIỆM.266
11.3. THUẬT TOÁN ĐƯỜNG MỞ.267
11.4. CÀI ĐẶT .268
§12. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI VỚI TRỌNG SỐCỰC TIỂU TRÊN ĐỒTHỊHAI
PHÍA - THUẬT TOÁN HUNGARI .273
12.1. BÀI TOÁN PHÂN CÔNG .273
12.2. PHÂN TÍCH .273
12.3. THUẬT TOÁN .274
12.4. CÀI ĐẶT .278
12.5. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI VỚI TRỌNG SỐCỰC ĐẠI TRÊN ĐỒTHỊHAI PHÍA .284
12.6. NÂNG CẤP.284
§13. BÀI TOÁN TÌM BỘGHÉP CỰC ĐẠI TRÊN ĐỒTHỊ.290
13.1. CÁC KHÁI NIỆM.290
13.2. THUẬT TOÁN EDMONDS (1965) .291
13.3. PHƯƠNG PHÁP LAWLER (1973) .293
13.4. CÀI ĐẶT .295
13.5. ĐỘPHỨC TẠP TÍNH TOÁN .299
TÀI LIỆU ĐỌC THÊM . 301
PHẦN 1. BÀI TOÁN LIỆT KÊ
Có một số bài toán trên thực tế yêu cầu chỉ rõ: trong một tập các đối
tượng cho trước có bao nhiêu đối tượng thoả mãn những điều kiện
nhất định. Bài toán đó gọi là bài toán đếm.
Trong lớp các bài toán đếm, có những bài toán còn yêu cầu chỉ rõ
những cấu hình tìm được thoả mãn điều kiện đã đánh giá là những cấu hình
nào. Bài toán yêu cầu đưa ra danh sách các cấu hình có thể có gọi là
bài toán liệt kê.
Để giải bài toán liệt kê, cần xác định được một thuật toán để có
thể theo đó lần lượt xây dựng được tất cả các cấu hình đang quan tâm.
Có nhiều phương pháp liệt kê, nhưng chúng cần đáp ứng được
hai yêu cầu dưới đây:
• Không được lặp lại một cấu hình
• Không được bỏ sót một cấu hình
Có thể nói rằng, phương pháp liệt kê là phương kế cuối cùng để giải
được một số bài toán tổ hợp hiện nay. Khó khăn chính của phương
pháp này chính là sự bùng nổ tổ hợp dẫn tới sự đòi hỏi lớn về không
gian và thời gian thực hiện chương trình. Tuy nhiên cùng với sự phát
triển của máy tính điện tử, bằng phương pháp liệt kê, nhiều bài toán tổ
hợp đã tìm thấy lời giải. Qua đó, ta cũng nên biết rằng chỉ nên dùng
phương pháp liệt kê khi không còn một phương pháp nào khác
tìm ra lời giải. Chính những nỗ lực giải quyết các bài toán thực tế
không dùng phương pháp liệt kê đã thúc đẩy sự phát triển của nhiều
ngành toán học.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: