Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Giải thuật và lập trình (Lê Minh Hoàng) pot
Nội dung xem thử
Mô tả chi tiết
LÊ MINH HOÀNG
¦¦¦ı}}}
(A.K.A DSAP Textbook)
A衣i h丑c S逢 ph衣m Hà N瓜i, 1999-2006
Try not to become a man of success
but rather to become a man of value.
Albert Einstein
¦ 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 A萎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 A浦 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 A浦 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渦.................................................................................................................... 17
3.5. BÀI TOÁN X蔭P H一U .............................................................................................................................. 19
§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 ................................................................................................................................................. 27
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 A卯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. GI閏I THI烏U.............................................................................................................................................. 40
2.2. CÁC KÝ PHÁP A韻 AÁNH GIÁ A浦 PH永C T萎P TÍNH TOÁN............................................................. 40
2.3. XÁC A卯NH A浦 PH永C T萎P TÍNH TOÁN C曳A GI謂I THU一T ............................................................ 42
2.4. A浦 PH永C T萎P TÍNH TOÁN V閏I TÌNH TR萎NG D頴 LI烏U VÀO....................................................... 45
2.5. CHI PHÍ TH衛C HI烏N THU一T TOÁN.................................................................................................... 46
¦ ii }
§3. A烏 QUY VÀ GI謂I THU一T A烏 QUY ......................................................................................... 50
3.1. KHÁI NI烏M V陰 A烏 QUY ........................................................................................................................50
3.2. GI謂I THU一T A烏 QUY.............................................................................................................................50
3.3. VÍ D影 V陰 GI謂I THU一T A烏 QUY ..........................................................................................................51
3.4. HI烏U L衛C C曳A A烏 QUY .......................................................................................................................55
§4. C遺U TRÚC D頴 LI烏U BI韻U DI右N DANH SÁCH.................................................................... 58
4.1. KHÁI NI烏M DANH SÁCH ......................................................................................................................58
4.2. BI韻U DI右N DANH SÁCH TRONG MÁY TÍNH ....................................................................................58
§5. NG;N X蔭P VÀ HÀNG A営I ........................................................................................................ 64
5.1. NG;N X蔭P (STACK)...............................................................................................................................64
5.2. HÀNG A営I (QUEUE)...............................................................................................................................66
§6. CÂY (TREE).................................................................................................................................. 70
6.1. A卯NH NGH┃A............................................................................................................................................70
6.2. CÂY NH卯 PHÂN (BINARY TREE) .........................................................................................................71
6.3. BI韻U DI右N CÂY NH卯 PHÂN ..................................................................................................................73
6.4. PHÉP DUY烏T CÂY NH卯 PHÂN..............................................................................................................75
6.5. CÂY K_PHÂN ..........................................................................................................................................76
6.6. CÂY T蔚NG QUÁT...................................................................................................................................77
§7. KÝ PHÁP TI陰N T渦, TRUNG T渦 VÀ H一U T渦 ....................................................................... 80
7.1. BI韻U TH永C D姶閏I D萎NG CÂY NH卯 PHÂN .........................................................................................80
7.2. CÁC KÝ PHÁP CHO CÙNG M浦T BI韻U TH永C....................................................................................80
7.3. CÁCH TÍNH GIÁ TR卯 BI韻U TH永C ........................................................................................................81
7.4. CHUY韻N T洩 D萎NG TRUNG T渦 SANG D萎NG H一U T渦...................................................................84
7.5. XÂY D衛NG CÂY NH卯 PHÂN BI韻U DI右N BI韻U TH永C......................................................................87
§8. S溢P X蔭P (SORTING) .................................................................................................................. 89
8.1. BÀI TOÁN S溢P X蔭P................................................................................................................................89
8.2. THU一T TOÁN S溢P X蔭P KI韻U CH窺N (SELECTIONSORT)...............................................................91
8.3. THU一T TOÁN S溢P X蔭P N蔚I B窺T (BUBBLESORT)...........................................................................92
8.4. THU一T TOÁN S溢P X蔭P KI韻U CHÈN (INSERTIONSORT) ................................................................92
8.5. S溢P X蔭P CHÈN V閏I A浦 DÀI B姶閏C GI謂M D井N (SHELLSORT) .....................................................94
8.6. THU一T TOÁN S溢P X蔭P KI韻U PHÂN AO萎N (QUICKSORT) ............................................................95
8.7. THU一T TOÁN S溢P X蔭P KI韻U VUN A渦NG (HEAPSORT) ..............................................................101
8.8. S溢P X蔭P B稲NG PHÉP A蔭M PHÂN PH渦I (DISTRIBUTION COUNTING)......................................104
8.9. TÍNH 蔚N A卯NH C曳A THU一T TOÁN S溢P X蔭P (STABILITY) .........................................................105
8.10. THU一T TOÁN S溢P X蔭P B稲NG C愛 S渦 (RADIX SORT).................................................................106
8.11. THU一T TOÁN S溢P X蔭P TR浦N (MERGESORT)..............................................................................111
8.12. CÀI A咽T ...............................................................................................................................................114
8.13. AÁNH GIÁ, NH一N XÉT......................................................................................................................122
§9. TÌM KI蔭M (SEARCHING) ....................................................................................................... 126
9.1. BÀI TOÁN TÌM KI蔭M ...........................................................................................................................126
9.2. TÌM KI蔭M TU井N T衛 (SEQUENTIAL SEARCH) ...............................................................................126
9.3. TÌM KI蔭M NH卯 PHÂN (BINARY SEARCH)........................................................................................126
9.4. CÂY NH卯 PHÂN TÌM KI蔭M (BINARY SEARCH TREE - BST).........................................................127
¦ iii }
9.5. PHÉP B;M (HASH)............................................................................................................................... 132
9.6. KHOÁ S渦 V閏I BÀI TOÁN TÌM KI蔭M ................................................................................................ 133
9.7. CÂY TÌM KI蔭M S渦 H窺C (DIGITAL SEARCH TREE - DST)............................................................ 133
9.8. CÂY TÌM KI蔭M C愛 S渦 (RADIX SEARCH TREE - RST) .................................................................. 136
9.9. NH頴NG NH一N XÉT CU渦I CÙNG ...................................................................................................... 140
PH井N 3. QUY HO萎CH A浦NG .................................................................... 143
§1. CÔNG TH永C TRUY H唄I..........................................................................................................144
1.1. VÍ D影 ...................................................................................................................................................... 144
1.2. C謂I TI蔭N TH永 NH遺T........................................................................................................................... 145
1.3. C謂I TI蔭N TH永 HAI............................................................................................................................... 147
1.4. CÀI A咽T A烏 QUY ................................................................................................................................. 147
§2. PH姶愛NG PHÁP QUY HO萎CH A浦NG ...................................................................................149
2.1. BÀI TOÁN QUY HO萎CH ..................................................................................................................... 149
2.2. PH姶愛NG PHÁP QUY HO萎CH A浦NG ................................................................................................ 149
§3. M浦T S渦 BÀI TOÁN QUY HO萎CH A浦NG ............................................................................153
3.1. DÃY CON A愛N AI烏U T;NG DÀI NH遺T........................................................................................... 153
3.2. BÀI TOÁN CÁI TÚI............................................................................................................................... 158
3.3. BI蔭N A蔚I XÂU ...................................................................................................................................... 160
3.4. DÃY CON CÓ T蔚NG CHIA H蔭T CHO K............................................................................................ 164
3.5. PHÉP NHÂN T蔚 H営P DÃY MA TR一N............................................................................................... 169
3.6. BÀI T一P LUY烏N T一P........................................................................................................................... 172
PH井N 4. CÁC THU一T TOÁN TRÊN A唄 TH卯 .......................................... 177
§1. CÁC KHÁI NI烏M C愛 B謂N .......................................................................................................178
1.1. A卯NH NGH┃A A唄 TH卯 (GRAPH).......................................................................................................... 178
1.2. CÁC KHÁI NI烏M................................................................................................................................... 179
§2. BI韻U DI右N A唄 TH卯 TRÊN MÁY TÍNH..................................................................................181
2.1. MA TR一N K陰 (ADJACENCY MATRIX)............................................................................................. 181
2.2. DANH SÁCH C萎NH (EDGE LIST) ...................................................................................................... 182
2.3. DANH SÁCH K陰 (ADJACENCY LIST) ............................................................................................... 183
2.4. NH一N XÉT............................................................................................................................................. 184
§3. CÁC THU一T TOÁN TÌM KI蔭M TRÊN A唄 TH卯...................................................................186
3.1. BÀI TOÁN .............................................................................................................................................. 186
3.2. THU一T TOÁN TÌM KI蔭M THEO CHI陰U SÂU (DEPTH FIRST SEARCH)...................................... 187
3.3. THU一T TOÁN TÌM KI蔭M THEO CHI陰U R浦NG (BREADTH FIRST SEARCH) ............................ 189
3.4. A浦 PH永C T萎P TÍNH TOÁN C曳A BFS VÀ DFS ................................................................................ 192
§4. TÍNH LIÊN THÔNG C曳A A唄 TH卯..........................................................................................193
4.1. A卯NH NGH┃A ......................................................................................................................................... 193
4.2. TÍNH LIÊN THÔNG TRONG A唄 TH卯 VÔ H姶閏NG ........................................................................... 194
¦ iv }
4.3. A唄 TH卯 A井Y A曳 VÀ THU一T TOÁN WARSHALL ...........................................................................194
4.4. CÁC THÀNH PH井N LIÊN THÔNG M萎NH ........................................................................................197
§5. VÀI 永NG D影NG C曳A DFS và BFS ......................................................................................... 207
5.1. XÂY D衛NG CÂY KHUNG C曳A A唄 TH卯............................................................................................207
5.2. T一P CÁC CHU TRÌNH C愛 S雲 C曳A A唄 TH卯......................................................................................210
5.3. BÀI TOÁN A卯NH CHI陰U A唄 TH卯........................................................................................................210
5.4. LI烏T KÊ CÁC KH閏P VÀ C井U C曳A A唄 TH卯......................................................................................214
§6. CHU TRÌNH EULER, A姶云NG AI EULER, A唄 TH卯 EULER ............................................. 217
6.1. BÀI TOÁN 7 CÁI C井U ..........................................................................................................................217
6.2. A卯NH NGH┃A..........................................................................................................................................217
6.3. A卯NH LÝ .................................................................................................................................................217
6.4. THU一T TOÁN FLEURY TÌM CHU TRÌNH EULER...........................................................................218
6.5. CÀI A咽T .................................................................................................................................................219
6.6. THU一T TOÁN T渦T H愛N......................................................................................................................221
§7. CHU TRÌNH HAMILTON, A姶云NG AI HAMILTON, A唄 TH卯 HAMILTON .................. 224
7.1. A卯NH NGH┃A..........................................................................................................................................224
7.2. A卯NH LÝ .................................................................................................................................................224
7.3. CÀI A咽T .................................................................................................................................................225
§8. BÀI TOÁN A姶云NG AI NG溢N NH遺T..................................................................................... 229
8.1. A唄 TH卯 CÓ TR窺NG S渦.........................................................................................................................229
8.2. BÀI TOÁN A姶云NG AI NG溢N NH遺T .................................................................................................229
8.3. TR姶云NG H営P A唄 TH卯 KHÔNG CÓ CHU TRÌNH ÂM - THU一T TOÁN FORD BELLMAN .........231
8.4. TR姶云NG H営P TR窺NG S渦 TRÊN CÁC CUNG KHÔNG ÂM - THU一T TOÁN DIJKSTRA...........233
8.5. THU一T TOÁN DIJKSTRA VÀ C遺U TRÚC HEAP .............................................................................236
8.6. TR姶云NG H営P A唄 TH卯 KHÔNG CÓ CHU TRÌNH - S溢P X蔭P TÔ PÔ..............................................239
8.7. A姶云NG AI NG溢N NH遺T GI頴A M窺I C咽P A迂NH - THU一T TOÁN FLOYD...................................242
8.8. NH一N XÉT .............................................................................................................................................244
§9. BÀI TOÁN CÂY KHUNG NH碓 NH遺T ................................................................................... 248
9.1. BÀI TOÁN CÂY KHUNG NH碓 NH遺T ................................................................................................248
9.2. THU一T TOÁN KRUSKAL (JOSEPH KRUSKAL - 1956) ...................................................................248
9.3. THU一T TOÁN PRIM (ROBERT PRIM - 1957)....................................................................................253
§10. BÀI TOÁN LU唄NG C衛C A萎I TRÊN M萎NG...................................................................... 257
10.1. CÁC KHÁI NI烏M .................................................................................................................................257
10.2. M萎NG TH咽NG D姶 VÀ A姶云NG T;NG LU唄NG ............................................................................260
10.3. THU一T TOÁN FORD-FULKERSON (L.R.FORD & D.R.FULKERSON - 1962) .............................262
10.4. THU一T TOÁN PREFLOW-PUSH (GOLDBERG - 1986) ..................................................................266
10.5. M浦T S渦 M雲 R浦NG.............................................................................................................................272
§11. BÀI TOÁN TÌM B浦 GHÉP C衛C A萎I TRÊN A唄 TH卯 HAI PHÍA .................................... 280
11.1. A唄 TH卯 HAI PHÍA (BIPARTITE GRAPH) .........................................................................................280
11.2. BÀI TOÁN GHÉP AÔI KHÔNG TR窺NG VÀ CÁC KHÁI NI烏M .....................................................280
11.3. THU一T TOÁN A姶云NG M雲...............................................................................................................281
11.4. CÀI A咽T ...............................................................................................................................................282
¦ v }
§12. BÀI TOÁN TÌM B浦 GHÉP C衛C A萎I V閏I TR窺NG S渦 C衛C TI韻U TRÊN A唄 TH卯 HAI
PHÍA - THU一T TOÁN HUNGARI .................................................................................................288
12.1. BÀI TOÁN PHÂN CÔNG .................................................................................................................... 288
12.2. PHÂN TÍCH.......................................................................................................................................... 288
12.3. THU一T TOÁN...................................................................................................................................... 289
12.4. BÀI TOÁN TÌM B浦 GHÉP C衛C A萎I V閏I TR窺NG S渦 C衛C A萎I TRÊN A唄 TH卯 HAI PHÍA....... 298
12.5. NÂNG C遺P........................................................................................................................................... 298
§13. BÀI TOÁN TÌM B浦 GHÉP C衛C A萎I TRÊN A唄 TH卯.........................................................304
13.1. CÁC KHÁI NI烏M................................................................................................................................. 304
13.2. THU一T TOÁN EDMONDS (1965) ..................................................................................................... 305
13.3. THU一T TOÁN LAWLER (1973)......................................................................................................... 307
13.4. CÀI A咽T ............................................................................................................................................... 309
13.5. A浦 PH永C T萎P TÍNH TOÁN............................................................................................................... 313
TÀI LI烏U A窺C THÊM.................................................................................. 315
¦ vi }
HÌNH V淫
Hình 1: Cây tìm ki院m quay lui trong bài toán li羽t kê dãy nh鵜 phân .......................................................................13
Hình 2: X院p 8 quân h壱u trên bàn c運 8x8 ...............................................................................................................19
Hình 3: A逢運ng chéo AB-TN mang ch雨 s嘘 10 và đ逢運ng chéo AN-TB mang ch雨 s嘘 0............................................20
Hình 4: L逢u đ欝 thu壱t gi違i (Flowchart)...................................................................................................................36
Hình 5: Ký pháp Θ l噂n, Ο l噂n và Ω l噂n ................................................................................................................41
Hình 6: Tháp Hà N瓜i .............................................................................................................................................54
Hình 7: C医u trúc nút c栄a danh sách n嘘i đ挨n ..........................................................................................................59
Hình 8: Danh sách n嘘i đ挨n ....................................................................................................................................59
Hình 9: C医u trúc nút c栄a danh sách n嘘i kép ..........................................................................................................61
Hình 10: Danh sách n嘘i kép...................................................................................................................................61
Hình 11: Danh sách n嘘i vòng m瓜t h逢噂ng ..............................................................................................................61
Hình 12: Danh sách n嘘i vòng hai h逢噂ng ...............................................................................................................62
Hình 13: Dùng danh sách vòng mô t違 Queue ........................................................................................................67
Hình 14: Di chuy吋n toa tàu....................................................................................................................................69
Hình 15: Di chuy吋n toa tàu (2) ..............................................................................................................................69
Hình 16: Cây..........................................................................................................................................................70
Hình 17: M泳c c栄a các nút trên cây ........................................................................................................................71
Hình 18: Cây bi吋u di宇n bi吋u th泳c ..........................................................................................................................71
Hình 19: Các d衣ng cây nh鵜 phân suy bi院n..............................................................................................................72
Hình 20: Cây nh鵜 phân hoàn ch雨nh và cây nh鵜 phân đ亥y đ栄...................................................................................72
Hình 21: Aánh s嘘 các nút c栄a cây nh鵜 phân đ亥y đ栄 đ吋 bi吋u di宇n b茨ng m違ng ........................................................73
Hình 22: Nh逢嬰c đi吋m c栄a ph逢挨ng pháp bi吋u di宇n cây nh鵜 phân b茨ng m違ng ........................................................74
Hình 23: C医u trúc nút c栄a cây nh鵜 phân.................................................................................................................74
Hình 24: Bi吋u di宇n cây nh鵜 phân b茨ng c医u trúc liên k院t ........................................................................................75
Hình 25: Aánh s嘘 các nút c栄a cây 3_phân đ吋 bi吋u di宇n b茨ng m違ng......................................................................77
Hình 26: Bi吋u di宇n cây t鰻ng quát b茨ng m違ng........................................................................................................78
Hình 27: C医u trúc nút c栄a cây t鰻ng quát................................................................................................................79
Hình 28: Bi吋u th泳c d逢噂i d衣ng cây nh鵜 phân ..........................................................................................................80
Hình 29: Vòng l員p trong c栄a QuickSort ................................................................................................................96
Hình 30: Tr衣ng thái tr逢噂c khi g丑i đ羽 quy ..............................................................................................................97
Hình 31: Heap......................................................................................................................................................102
Hình 32: Vun đ嘘ng ..............................................................................................................................................102
Hình 33: A違o giá tr鵜 k[1] cho k[n] và xét ph亥n còn l衣i ........................................................................................103
Hình 34: Vun ph亥n còn l衣i thành đ嘘ng r欝i l衣i đ違o tr鵜 k[1] cho k[n-1] .................................................................103
Hình 35: Aánh s嘘 các bit .....................................................................................................................................106
Hình 36: Thu壱t toán s逸p x院p tr瓜n.........................................................................................................................111
¦ vii }
Hình 37: Máy Pentium 4, 3.2GHz, 2GB RAM t臼 ra ch壱m ch衣p khi s逸p x院p 108
khoá ∈ [0..7.107
] cho dù nh英ng
thu壱t toán s逸p x院p t嘘t nh医t đã đ逢嬰c áp d映ng .............................................................................................. 123
Hình 38: Cây nh鵜 phân tìm ki院m ......................................................................................................................... 128
Hình 39: Xóa nút lá 荏 cây BST ........................................................................................................................... 129
Hình 40. Xóa nút ch雨 có m瓜t nhánh con trên cây BST ........................................................................................ 130
Hình 41: Xóa nút có c違 hai nhánh con trên cây BST thay b茨ng nút c詠c ph違i c栄a cây con trái............................ 130
Hình 42: Xóa nút có c違 hai nhánh con trên cây BST thay b茨ng nút c詠c trái c栄a cây con ph違i............................ 131
Hình 43: Aánh s嘘 các bit ..................................................................................................................................... 133
Hình 44: Cây tìm ki院m s嘘 h丑c............................................................................................................................. 134
Hình 45: Cây tìm ki院m c挨 s嘘............................................................................................................................... 136
Hình 46: V噂i đ瓜 dài dãy bit z = 3, cây tìm ki院m c挨 s嘘 g欝m các khoá 2, 4, 5 và sau khi thêm giá tr鵜 7............... 137
Hình 47: RST ch泳a các khoá 2, 4, 5, 7 và RST sau khi lo衣i b臼 giá tr鵜 7 ............................................................. 138
Hình 48: Cây tìm ki院m c挨 s嘘 a) và Trie tìm ki院m c挨 s嘘 b).................................................................................. 140
Hình 49: Hàm đ羽 quy tính s嘘 Fibonacci .............................................................................................................. 151
Hình 50: Tính toán và truy v院t ............................................................................................................................ 154
Hình 51: Truy v院t ................................................................................................................................................ 163
Hình 52: Ví d映 v隠 mô hình đ欝 th鵜........................................................................................................................ 178
Hình 53: Phân lo衣i đ欝 th鵜..................................................................................................................................... 179
Hình 54................................................................................................................................................................ 182
Hình 55................................................................................................................................................................ 183
Hình 56: A欝 th鵜 và đ逢運ng đi................................................................................................................................ 186
Hình 57: A欝 th鵜 và cây DFS ................................................................................................................................ 189
Hình 58: Th泳 t詠 th<m đ雨nh c栄a BFS ................................................................................................................... 189
Hình 59: A欝 th鵜 và cây BFS ................................................................................................................................ 192
Hình 60: A欝 th鵜 G và các thành ph亥n liên thông G1, G2, G3 c栄a nó .................................................................. 193
Hình 61: Kh噂p và c亥u.......................................................................................................................................... 193
Hình 62: Liên thông m衣nh và liên thông y院u ...................................................................................................... 194
Hình 63: A欝 th鵜 đ亥y đ栄 ........................................................................................................................................ 195
Hình 64: A挨n đ欝 th鵜 vô h逢噂ng và bao đóng c栄a nó............................................................................................. 195
Hình 65: Ba d衣ng cung ngoài cây DFS ............................................................................................................... 198
Hình 66: Thu壱t toán Tarjan “b飲” cây DFS .......................................................................................................... 200
Hình 67: Aánh s嘘 l衣i, đ違o chi隠u các cung và duy羽t BFS v噂i cách ch丑n các đ雨nh xu医t phát ng逢嬰c l衣i v噂i th泳 t詠
duy羽t xong (th泳 t詠 11, 10… 3, 2, 1)........................................................................................................... 206
Hình 68: A欝 th鵜 G và m瓜t s嘘 ví d映 cây khung T1, T2, T3 c栄a nó ....................................................................... 209
Hình 69: Cây khung DFS (a) và cây khung BFS (b) (M┡i tên ch雨 chi隠u đi th<m các đ雨nh) ................................ 209
Hình 70: Phép đ鵜nh chi隠u DFS............................................................................................................................ 212
Hình 71: Phép đánh s嘘 và ghi nh壱n cung ng逢嬰c lên cao nh医t ............................................................................. 214
Hình 72: Mô hình đ欝 th鵜 c栄a bài toán b違y cái c亥u ............................................................................................... 217
Hình 73................................................................................................................................................................ 218
Hình 74................................................................................................................................................................ 218
¦ viii }
Hình 75 ................................................................................................................................................................224
Hình 76: Phép đánh l衣i ch雨 s嘘 theo th泳 t詠 tôpô....................................................................................................239
Hình 77: Hai cây g嘘c r1 và r2 và cây m噂i khi h嬰p nh医t chúng.............................................................................249
Hình 78: M衣ng v噂i các kh違 n<ng thông qua (1 phát, 6 thu) và m瓜t lu欝ng c栄a nó v噂i giá tr鵜 7............................257
Hình 79: M衣ng G và m衣ng th員ng d逢 Gf
t逢挨ng 泳ng (ký hi羽u c[u,v]:f[u,v] ch雨 kh違 n<ng thông qua c[u, v] và lu欝ng
d逢挨ng t逢挨ng 泳ng f[u, v] trên cung (u, v)) ..................................................................................................260
Hình 80: M衣ng th員ng d逢 và đ逢運ng t<ng lu欝ng ....................................................................................................261
Hình 81: Lu欝ng d逢挨ng trên m衣ng G tr逢噂c và sau khi t<ng .................................................................................262
Hình 82: M衣ng gi違 c栄a m衣ng có nhi隠u đi吋m phát và nhi隠u đi吋m thu..................................................................273
Hình 83: Thay m瓜t đ雨nh u b茨ng hai đ雨nh uin, uout.................................................................................................273
Hình 84: M衣ng gi違 c栄a m衣ng có kh違 n<ng thông qua c栄a các cung b鵜 ch員n hai phía..........................................274
Hình 85: A欝 th鵜 hai phía ......................................................................................................................................280
Hình 86: A欝 th鵜 hai phía và b瓜 ghép M ...............................................................................................................281
Hình 87: Mô hình lu欝ng c栄a bài toán tìm b瓜 ghép c詠c đ衣i trên đ欝 th鵜 hai phía...................................................285
Hình 88: Phép xoay tr丑ng s嘘 c衣nh.......................................................................................................................289
Hình 89: Thu壱t toán Hungari...............................................................................................................................292
Hình 90: Cây pha “m丑c” l噂n h挨n sau m厩i l亥n xoay tr丑ng s嘘 c衣nh và tìm đ逢運ng................................................299
Hình 91: A欝 th鵜 G và m瓜t b瓜 ghép M..................................................................................................................304
Hình 92: Phép ch壱p Blossom...............................................................................................................................306
Hình 93: N荏 Blossom đ吋 dò đ逢運ng xuyên qua Blossom.....................................................................................306
¦ ix }
CH姶愛NG TRÌNH
P_1_02_1.PAS * Thu壱t toán sinh li羽t kê các dãy nh鵜 phân đ瓜 dài n ....................................................................... 6
P_1_02_2.PAS * Thu壱t toán sinh li羽t kê các t壱p con k ph亥n t穎 .............................................................................. 8
P_1_02_3.PAS * Thu壱t toán sinh li羽t kê hoán v鵜 .................................................................................................... 9
P_1_03_1.PAS * Thu壱t toán quay lui li羽t kê các dãy nh鵜 phân đ瓜 dài n ............................................................... 12
P_1_03_2.PAS * Thu壱t toán quay lui li羽t kê các t壱p con k ph亥n t穎...................................................................... 14
P_1_03_3.PAS * Thu壱t toán quay lui li羽t kê các ch雨nh h嬰p không l員p ch壱p k ..................................................... 16
P_1_03_4.PAS * Thu壱t toán quay lui li羽t kê các cách phân tích s嘘...................................................................... 18
P_1_03_5.PAS * Thu壱t toán quay lui gi違i bài toán x院p h壱u ................................................................................. 21
P_1_04_1.PAS * K悦 thu壱t nhánh c壱n dùng cho bài toán ng逢運i du l鵜ch................................................................ 26
P_1_04_2.PAS * Dãy ABC................................................................................................................................... 28
P_2_07_1.PAS * Tính giá tr鵜 bi吋u th泳c RPN ........................................................................................................ 82
P_2_07_2.PAS * Chuy吋n bi吋u th泳c trung t嘘 sang d衣ng RPN ............................................................................... 85
P_2_08_1.PAS * Các thu壱t toán s<p x院p............................................................................................................. 114
P_3_01_1.PAS * A院m s嘘 cách phân tích s嘘 n..................................................................................................... 145
P_3_01_2.PAS * A院m s嘘 cách phân tích s嘘 n..................................................................................................... 146
P_3_01_3.PAS * A院m s嘘 cách phân tích s嘘 n..................................................................................................... 146
P_3_01_4.PAS * A院m s嘘 cách phân tích s嘘 n..................................................................................................... 147
P_3_01_5.PAS * A院m s嘘 cách phân tích s嘘 n dùng đ羽 quy ................................................................................ 147
P_3_01_6.PAS * A院m s嘘 cách phân tích s嘘 n dùng đ羽 quy ................................................................................ 148
P_3_03_1.PAS * Tìm dãy con đ挨n đi羽u t<ng dài nh医t........................................................................................ 154
P_3_03_2.PAS * C違i ti院n thu壱t toán tìm dãy con đ挨n đi羽u t<ng dài nh医t ........................................................... 156
P_3_03_3.PAS * Bài toán cái túi ........................................................................................................................ 159
P_3_03_4.PAS * Bi院n đ鰻i xâu ............................................................................................................................ 163
P_3_03_5.PAS * Dãy con có t鰻ng chia h院t cho k ............................................................................................... 165
P_3_03_6.PAS * Dãy con có t鰻ng chia h院t cho k ............................................................................................... 167
P_3_03_7.PAS * Nhân t嘘i 逢u dãy ma tr壱n.......................................................................................................... 171
P_4_03_1.PAS * Thu壱t toán tìm ki院m theo chi隠u sâu ........................................................................................ 187
P_4_03_2.PAS * Thu壱t toán tìm ki院m theo chi隠u r瓜ng ...................................................................................... 190
P_4_04_1.PAS * Thu壱t toán Warshall li羽t kê các thành ph亥n liên thông ........................................................... 196
P_4_04_2.PAS * Thu壱t toán Tarjan li羽t kê các thành ph亥n liên thông m衣nh...................................................... 203
P_4_05_1.PAS * Li羽t kê các kh噂p và c亥u c栄a đ欝 th鵜.......................................................................................... 215
P_4_06_1.PAS * Thu壱t toán Fleury tìm chu trình Euler..................................................................................... 219
P_4_06_2.PAS * Thu壱t toán hi羽u qu違 tìm chu trình Euler.................................................................................. 221
P_4_07_1.PAS * Thu壱t toán quay lui li羽t kê chu trình Hamilton ....................................................................... 225
P_4_08_1.PAS * Thu壱t toán Ford-Bellman ........................................................................................................ 232
P_4_08_2.PAS * Thu壱t toán Dijkstra.................................................................................................................. 234
P_4_08_3.PAS * Thu壱t toán Dijkstra và c医u trúc Heap...................................................................................... 237
¦ x }
P_4_08_4.PAS * A逢運ng đi ng逸n nh医t trên đ欝 th鵜 không có chu trình.................................................................240
P_4_08_5.PAS * Thu壱t toán Floyd .....................................................................................................................243
P_4_09_1.PAS * Thu壱t toán Kruskal ..................................................................................................................250
P_4_09_2.PAS * Thu壱t toán Prim.......................................................................................................................254
P_4_10_1.PAS * Thu壱t toán Ford-Fulkerson......................................................................................................264
P_4_10_2.PAS * Thu壱t toán Preflow-push .........................................................................................................269
P_4_11_1.PAS * Thu壱t toán đ逢運ng m荏 tìm b瓜 ghép c詠c đ衣i..............................................................................283
P_4_12_1.PAS * Thu壱t toán Hungari..................................................................................................................295
P_4_12_2.PAS * Cài đ員t ph逢挨ng pháp Kuhn-Munkres O(k3
) ............................................................................300
P_4_13_1.PAS * Ph逢挨ng pháp Lawler áp d映ng cho thu壱t toán Edmonds ..........................................................310
B謂NG CÁC KÝ HI烏U A姶営C S盈 D影NG
⎢ ⎥ x⎣ ⎦ Floor of x: S嘘 nguyên l噂n nh医t ≤ x
⎡ ⎤ x⎢ ⎥ Ceiling of x: S嘘 nguyên nh臼 nh医t ≥ x
n k P S嘘 ch雨nh h嬰p không l員p ch壱p k c栄a n ph亥n t穎 =
n!
(n k)! −
n
k
⎛ ⎞ ⎜ ⎟ ⎝ ⎠
Binomial coefficient: H羽 s嘘 c栄a h衣ng t穎
k
x trong đa th泳c ( )n
x 1+
= S嘘 t鰻 h嬰p ch壱p k c栄a n ph亥n t穎 = ( )
n!
k! n k ! −
O .( ) Ký pháp ch英 O l噂n
Θ( ). Ký pháp Θ l噂n
Ω( ). Ký pháp Ω l噂n
o .( ) Ký pháp ch英 o nh臼
ω( ). ký pháp ω nh臼
a i..j [ ] Các ph亥n t穎 trong m違ng a tính t瑛 ch雨 s嘘 i đ院n ch雨 s嘘 j
n! n factorial: Giai th瑛a c栄a n = 1.2.3…n
a b ↑
b
a
a b ↑↑ {
a
... a
b copies of a
a
a
log x Logarithm to base a of x: Logarithm c挨 s嘘 a c栄a x ( b
a
log a b = )
lg x Logarithm nh鵜 phân (c挨 s嘘 2) c栄a x
ln x Logarithm t詠 nhiên (c挨 s嘘 e) c栄a x
*
a
log x S嘘 l亥n l医y logarithm c挨 s嘘 a đ吋 thu đ逢嬰c s嘘 ≤ 1 t瑛 x ( *
a
log (a b) b ↑↑ = )
*
lg x *
2
log x
*
ln x *
e
log x
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 đã cho 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ê.
A吋 gi違i bài toán li羽t kê, c亥n ph違i 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 ph違i đá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.