Tài liệu Specialized school book in computer science (bai giang chuyen de tin hoc)

i M CL C PH N 1. BÀI TOÁN LI T KÊ ................................................................................. 1 §1. NH C L I M T S KI N TH C IS 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 4.2. S U.........................................................................................................................................24 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 §1. CÁC B 1.1. XÁC CC LI U VÀ GI I THU T ............................................. 33 B N KHI TI N HÀNH GI I CÁC BÀI TOÁN TIN H C...............................34 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 1.6. T I U CH ......................................................................................................................................................37 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 2.3. NH PH C T P TÍNH TOÁN C A GI I THU T ....................................................................40 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 ii §3. QUY VÀ GI I THU T 3.1. KHÁI NI M V QUY ............................................................................................... 45 QUY.............................................................................................................................. 45 3.2. GI I THU T QUY .................................................................................................................................. 45 3.3. VÍ D V GI I THU T 3.4. HI U L C C A §4. C U TRÚC D QUY ................................................................................................................ 46 QUY ............................................................................................................................. 50 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 7.1. BI U TH C D VÀ H U T ............................................................................. 74 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 8.8. S P X P B NG PHÉP 8.9. TÍNH N NG (HEAPSORT) ...................................................................... 92 M PHÂN PH I (DISTRIBUTION COUNTING) ............................................. 95 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 iii 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 §2. PH T QUY ........................................................................................................................................137 NG PHÁP QUY HO CH NG .........................................................................................139 2.1. BÀI TOÁN QUY HO CH ............................................................................................................................139 2.2. PH §3. M T S NG PHÁP QUY HO CH NG.......................................................................................................139 BÀI TOÁN QUY HO CH 3.1. DÃY CON NG ..................................................................................143 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 §1. CÁC KHÁI NI M C 1.1. NH NGH A TH .................................................. 169 B N .............................................................................................................170 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 iv 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 4.1. TH ............................................................................................... 190 NH NGH A ............................................................................................................................................... 190 4.2. TÍNH LIÊN THÔNG TRONG 4.3. TH Y TH VÔ H NG.................................................................................. 191 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 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 5.3. NH CHI U TH ............................... 205 TH ........................................................................................ 208 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 8.1. NG I NG N NH T .......................................................................................... 230 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 8.7. NG H P TH KHÔNG CÓ CHU TRÌNH - TH NG I NG N NH T GI A M I C P T TÔ PÔ .................................................... 240 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, 10.3. CÀI NG T NG LU NG, NH LÝ FORD - FULKERSON................................................. 256 T ..................................................................................................................................................... 258 v 10.4. THU T TOÁN FORD - FULKERSON (L.R.FORD & D.R.FULKERSON - 1962)..................................262 §11. BÀI TOÁN TÌM B 11.1. GHÉP C C I TRÊN TH HAI PHÍA...........................................266 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 11.4. CÀI NG M ......................................................................................................................267 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 13.5. TÀI LI U T ......................................................................................................................................................295 PH C T P TÍNH TOÁN .....................................................................................................................299 C THÊM.......................................................................................... 301 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: ng chéo B-TN mang ch s 10 và Hình 4: L u ng chéo N-TB mang ch s 0 ...................................................... 19 thu t gi i (Flowchart).............................................................................................................................. 36 Hình 5: Tháp Hà N i ........................................................................................................................................................ 49 Hình 6: C u trúc nút c a danh sách n i Hình 7: Danh sách n i n..................................................................................................................... 53 n............................................................................................................................................... 53 Hình 8: C u trúc nút c a danh sách n i kép ..................................................................................................................... 55 Hình 9: Danh sách n i kép ............................................................................................................................................... 55 Hình 10: Danh sách n i vòng m t h ng......................................................................................................................... 55 Hình 11: Danh sách n i vòng hai h ng .......................................................................................................................... 56 Hình 12: Dùng danh sách vòng mô t Queue................................................................................................................... 61 Hình 13: Di chuy n toa tàu............................................................................................................................................... 63 Hình 14: Di chuy n toa tàu (2) ......................................................................................................................................... 63 Hình 15: Cây .................................................................................................................................................................... 64 Hình 16: M c c a các nút trên cây................................................................................................................................... 65 Hình 17: Cây bi u di n bi u th c..................................................................................................................................... 65 Hình 18: Các d ng cây nh phân suy bi n ........................................................................................................................ 66 Hình 19: Cây nh phân hoàn ch nh và cây nh phân y Hình 20: ánh s các nút c a cây nh phân bi u di n b ng m ng................................................................... 67 Hình 21: Nh c i m c a ph y ............................................................................................. 66 ng pháp bi u di n cây b ng m ng.................................................................................. 68 Hình 22: C u trúc nút c a cây nh phân ........................................................................................................................... 68 Hình 23: Bi u di n cây b ng c u trúc liên k t.................................................................................................................. 69 Hình 24: ánh s các nút c a cây 3_phân bi u di n b ng m ng................................................................................. 71 Hình 25: Bi u di n cây t ng quát b ng m ng .................................................................................................................. 72 Hình 26: C u trúc nút c a cây t ng quát .......................................................................................................................... 73 Hình 27: Bi u th c d i d ng cây nh phân..................................................................................................................... 74 Hình 28: Vòng l p trong c a QuickSort........................................................................................................................... 89 Hình 29: Tr ng thái tr c khi g i quy ......................................................................................................................... 90 Hình 30: Heap .................................................................................................................................................................. 92 Hình 31: Vun Hình 32: ng........................................................................................................................................................... 93 o giá tr k1 cho kn và xét ph n còn l i............................................................................................................ 93 Hình 33: Vun ph n còn l i thành ng r i l i o tr k1 cho kn-1 ...................................................................................... 94 Hình 34: ánh s các bit .................................................................................................................................................. 97 Hình 35: Thu t toán s p x p tr n ................................................................................................................................... 102 Hình 36: Cài t các thu t toán s p x p v i d li u l n................................................................................................. 114 Hình 37: Cây nh phân tìm ki m .................................................................................................................................... 118 Hình 38: Xóa nút lá cây BST ...................................................................................................................................... 119 Hình 39. Xóa nút ch có m t nhánh con trên cây BST ................................................................................................... 120 vii Hình 40: 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 .......................................120 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 trái c a cây con ph i .......................................120 Hình 42: ánh s các bit.................................................................................................................................................123 Hình 43: Cây tìm ki m s h c.........................................................................................................................................124 Hình 44: Cây tìm ki m c s ..........................................................................................................................................126 Hình 45: 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 ..........................127 Hình 46: RST ch a các khoá 2, 4, 5, 7 và RST sau khi lo i b giá tr 7 .........................................................................128 Hình 47: Cây tìm ki m c s a) và Trie tìm ki m c s b) .............................................................................................130 Hình 48: Hàm quy tính s Fibonacci..........................................................................................................................141 Hình 49: Tính toán và truy v t ........................................................................................................................................144 Hình 50: Truy v t............................................................................................................................................................153 Hình 51: Ví d v mô hình Hình 52: Phân lo i th ...................................................................................................................................170 th ................................................................................................................................................171 Hình 53 ...........................................................................................................................................................................174 Hình 54 ...........................................................................................................................................................................175 Hình 55: th và ng i ...........................................................................................................................................177 Hình 56: Cây DFS...........................................................................................................................................................180 Hình 57: Cây BFS ...........................................................................................................................................................184 Hình 58: Thu t toán loang ..............................................................................................................................................187 Hình 59: th G và các thành ph n liên thông G1, G2, G3 c a nó ..............................................................................190 Hình 60: Kh p và c u .....................................................................................................................................................190 Hình 61: Liên thông m nh và liên thông y u..................................................................................................................191 Hình 62: th Hình 63: n y ....................................................................................................................................................192 th vô h ng và bao óng c a nó ........................................................................................................192 Hình 64: Ba d ng cung ngoài cây DFS ...........................................................................................................................196 Hình 65: Thu t toán Tarjan "b " cây DFS ......................................................................................................................198 Hình 66: á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) ................................................................................................................................204 Hình 67: th G và m t s ví d cây khung T1, T2, T3 c a nó ...................................................................................207 Hình 68: Cây khung DFS (a) và cây khung BFS (b) (M i tên ch chi u i th m các Hình 69: Phép nh)............................................207 nh chi u DFS........................................................................................................................................210 Hình 70: Phép ánh s và ghi nh n cung ng Hình 71 Duy t DFS, xác Hình 72: Mô hình c lên cao nh t.........................................................................................212 nh cây DFS và các cung ng c............................................................................................215 th c a bài toán b y cái c u...........................................................................................................218 Hình 73 ...........................................................................................................................................................................219 Hình 74 ...........................................................................................................................................................................219 Hình 75 ...........................................................................................................................................................................225 Hình 76: Phép ánh l i ch s theo th t tôpô ...............................................................................................................240 Hình 77: Hai cây g c r1 và r2 và cây m i khi h p nh t chúng ........................................................................................248 Hình 78: M ng v i các kh n ng thông qua (1 phát, 6 thu) Hình 79: M ng G, lu ng trên các cung (1 phát, 6 thu) và Hình 80: Lu ng trên m ng G tr và m t lu ng c a nó v i giá tr 7 ...................................256 th t ng lu ng t ng ng..................................................257 c và sau khi t ng........................................................................................................258 viii Hình 81: th hai phía ................................................................................................................................................. 266 Hình 82: th hai phía và b ghép M .......................................................................................................................... 267 Hình 83: 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 ............................................................. 271 Hình 84: Phép xoay tr ng s c nh.................................................................................................................................. 274 Hình 85: Thu t toán Hungari.......................................................................................................................................... 277 Hình 86: Cây pha "m c" l n h n sau m i l n xoay tr ng s c nh và tìm Hình 87: ng........................................................... 285 th G và m t b ghép M............................................................................................................................. 290 Hình 88: Phép ch p Blossom ......................................................................................................................................... 292 Hình 89: N Blossom dò ng xuyên qua Blossom................................................................................................ 292 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.................................................................15 P_1_03_4.PAS * Thu t toán quay lui li t kê các cách phân tích s ..................................................................................17 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....................................................................................................................76 P_2_07_2.PAS * Chuy n bi u th c trung t sang d ng RPN...........................................................................................79 P_2_08_1.PAS * Các thu t toán s p x p ........................................................................................................................105 P_3_01_1.PAS * m s cách phân tích s n ................................................................................................................135 P_3_01_2.PAS * m s cách phân tích s n ................................................................................................................136 P_3_01_3.PAS * m s cách phân tích s n ................................................................................................................136 P_3_01_4.PAS * m s cách phân tích s n ................................................................................................................137 P_3_01_5.PAS * m s cách phân tích s n dùng quy............................................................................................137 P_3_01_6.PAS * m s cách phân tích s n dùng quy............................................................................................138 P_3_03_1.PAS * Tìm dãy con n i u t ng dài nh t....................................................................................................144 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.......................................................................146 P_3_03_3.PAS * Bài toán cái túi ....................................................................................................................................149 P_3_03_4.PAS * Bi n i xâu........................................................................................................................................153 P_3_03_5.PAS * Dãy con có t ng chia h t cho k...........................................................................................................156 P_3_03_6.PAS * Dãy con có t ng chia h t cho k...........................................................................................................158 P_3_03_7.PAS * Nhân t i u dãy ma tr n .....................................................................................................................162 P_4_03_1.PAS * Thu t toán tìm ki m theo chi u sâu ....................................................................................................178 P_4_03_2.PAS * Thu t toán tìm ki m theo chi u sâu không quy .............................................................................181 P_4_03_3.PAS * Thu t toán tìm ki m theo chi u r ng dùng hàng P_4_03_4.PAS * Thu t toán tìm ki m theo chi u r ng dùng ph i ..........................................................................185 ng pháp loang .........................................................187 P_4_04_1.PAS * Thu t toán Warshall li t kê các thành ph n liên thông .......................................................................194 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 .................................................................201 P_4_05_1.PAS * Phép nh chi u DFS và li t kê c u ....................................................................................................213 P_4_05_2.PAS * Li t kê các kh p c a th .................................................................................................................216 P_4_06_1.PAS * Thu t toán Fleury tìm chu trình Euler.................................................................................................220 P_4_06_2.PAS * Thu t toán hi u qu tìm chu trình Euler .............................................................................................223 P_4_07_1.PAS * Thu t toán quay lui li t kê chu trình Hamilton ...................................................................................226 P_4_08_1.PAS * Thu t toán Ford-Bellman....................................................................................................................233 P_4_08_2.PAS * Thu t toán Dijkstra .............................................................................................................................235 P_4_08_3.PAS * Thu t toán Dijkstra và c u trúc Heap .................................................................................................237 x P_4_08_4.PAS * ng i ng n nh t trên th không có chu trình ........................................................................... 241 P_4_08_5.PAS * Thu t toán Floyd ................................................................................................................................ 243 P_4_09_1.PAS * Thu t toán Kruskal............................................................................................................................. 249 P_4_09_2.PAS * Thu t toán Prim.................................................................................................................................. 252 P_4_10_1.PAS * Thu t toán tìm lu ng c c i trên m ng ............................................................................................ 259 P_4_10_2.PAS * Thu t toán Ford-Fulkerson................................................................................................................. 262 P_4_11_1.PAS * Thu t toán ng m tìm b ghép c c i ........................................................................................ 269 P_4_12_1.PAS * Thu t toán Hungari ............................................................................................................................ 280 P_4_12_2.PAS * Cài P_4_13_1.PAS * Ph t ph ng pháp Kuhn-Munkres O(n3) ....................................................................................... 286 ng pháp Lawler áp d ng cho thu t toán Edmonds..................................................................... 296 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 t ng cho tr nh t c có bao nhiêu i t nh. Bài toán ó g i là bài toán Trong l p các bài toán nh ng c u hình tìm i ng tho mãn nh ng i u ki n m. m, có nh ng bài toán còn yêu c u ch rõ 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ê. gi i bài toán li t kê, c n ph i xác th theo ó l n l t xây d ng nh c m t thu t toán có 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 hai yêu c u d i ây: Không c l p l i m t c u hình Không c 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 c m t s bài toán t h p hi n nay. Khó kh n chính c a ph pháp này chính là s bùng n t h p d n t i s gian và th i gian th c hi n ch gi i ng òi h i l n v không 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ành toán h c. ng pháp li t kê ã thúc y s phát tri n c a nhi u 2 Chuyên §1. NH C L I M T S KI N TH C IS T H P Cho S là m t t p h u h n g m n ph n t và k là m t s t nhiên. G i X là t p các s nguyên d ng t 1 n k: X = {1, 2, …, k} 1.1. CH NH H P L P M i ánh x f: X S. Cho t ng ng v i m i i X, m t và ch m t ph n t f(i) S. c g i là m t ch nh h p l p ch p k c a S. Nh ng do X là t p h u h n (k ph n t ) nên ánh x f có th xác nh qua b ng các giá tr f(1), f(2), …, f(k). Ví d : S = {A, B, C, D, E, F}; k = 3. M t ánh x f có th cho nh sau: i f(i) V y có th 1 E 2 C 3 E ng nh t f v i dãy giá tr (f(1), f(2), …, f(k)) và coi dãy giá tr này c ng là m t ch nh h p l p ch p k c a S. Nh ví d trên (E, C, E) là m t ch nh h p l p ch p 3 c a S. D dàng ch ng minh c k t qu sau b ng quy n p ho c b ng ph ng pháp ánh giá kh n ng l a ch n: S ch nh h p l p ch p k c a t p g m n ph n t : k nk An 1.2. CH NH H P KHÔNG L P Khi f là n ánh có ngh a là v i i, j X ta có f(i) = f(j) i = j. Nói m t cách d hi u, khi dãy giá tr f(1), f(2), …, f(k) g m các ph n t thu c S khác nhau ôi m t thì f c g i là m t ch nh h p không l p ch p k c a S. Ví d m t ch nh h p không l p (C, A, E): i f(i) 1 C 2 A 3 E S ch nh h p không l p ch p k c a t p g m n ph n t : Ak n n! (n k )! n (n 1)(n 2)...(n k 1) 1.3. HOÁN V Khi k = n. M t ch nh h p không l p ch p n c a S c g i là m t hoán v các ph n t c a S. Ví d : m t hoán v : (A, D, C, E, B, F) c a S = {A, B, C, D, E, F} i f(i) 1 A 2 D 3 C 4 E 5 B 6 F ý r ng khi k = n thì s ph n t c a t p X = {1, 2, …, n} úng b ng s ph n t c a S. Do tính ch t ôi m t khác nhau nên dãy f(1), f(2), …, f(n) s li t kê c h t các ph n t trong S. Nh v y f là toàn ánh. M t khác do gi thi t f là ch nh h p không l p nên f là n ánh. Ta có t ng ng 1-1 i h c S ph m Hà N i, 1999-2002 Bài toán li t kê 3 gi a các ph n t c a X và S, do ó f là song ánh. V y nên ta có th nh ngh a m t hoán v c a S là m t song ánh gi a {1, 2, …, n} và S. S hoán v c a t p g m n ph n t = s ch nh h p không l p ch p n: Pn 1.4. T n! H P M t t p con g m k ph n t c a S c g i là m t t h p ch p k c a S. L y m t t p con k ph n t c a S, xét t t c k! hoán v c a t p con này. D th y r ng các hoán v ó là các ch nh h p không l p ch p k c a S. Ví d l y t p {A, B, C} là t p con c a t p S trong ví d trên thì: (A, B, C), (C, A, B), (B, C, A), … là các ch nh h p không l p ch p 3 c a S. i u ó t c là khi li t kê t t c các ch nh h p không l p ch p k thì m i t h p ch p k s S t h p ch p k c a t p g m n ph n t : Ck n Ak n k! n! k!(n k )! S t p con c a t p n ph n t : C0 n Lê Minh Hoàng C1 n ... C n n 2n c tính k! l n. V y: 4 Chuyên §2. PH Ph NG PHÁP SINH (GENERATION) ng pháp sinh có th áp d ng gi i bài toán li t kê t h p t ra n u nh hai i u ki n sau tho mãn: Có th xác nh cc u hình Xây d ng c m t th t trên t p các c u hình t h p c n li t kê. T u tiên và c u hình cu i cùng trong th t ó có th bi t ó. c thu t toán t m t c u hình ch a ph i c u hình cu i, sinh ra c c u hình k ti p nó. Ph ng pháp sinh có th mô t nh sau: ; repeat < a ra c u hình ang có>; ; until ; Th t t i n Trên các ki u d li u n gi n chu n, ng i ta th ng nói t i khái ni m th t . Ví d trên ki u s thì có quan h : 1 < 2; 2 < 3; 3 < 10; …, trên ki u ký t Char thì c ng có quan h 'A' < 'B'; 'C' < 'c'… Xét quan h th t toàn ph n "nh h n ho c b ng" ký hi u " " trên m t t p h p S, là quan h hai ngôi tho mãn b n tính ch t: V i a, b, c S Tính ph bi n: Ho c là a Tính ph n x : a Tính ph n kh i ph i a; a i x ng: N u a Tính b c c u: N u có a Trong tr b, ho c b ng h p a b và b b và b b và a a thì b t bu c a = b. c thì a c. b, ta dùng ký hi u "<" cho g n, (ta ng m hi u các ký hi u nh , >, nh ngh a) Ví d nh quan h " " trên các s nguyên c ng nh trên các ki u vô h ng, li t kê là quan h th t toàn ph n. Trên các dãy h u h n, ng i ta c ng xác nh m t quan h th t : Xét a = (a1, a2, …, an) và b = (b1, b2, …, bn); trên các ph n t c a a1, …, an, b1, …, bn ã có quan h th t " ". Khi ó a Ho c ai = bi v i i: 1 b n u nh i n. Ho c t n t i m t s nguyên d ng k: 1 k 0) and (xi = 1) do i := i - 1; if i > 0 then begin Lê Minh Hoàng u tiên thì thay nó b ng s 1 và t t t c các ph n 6 Chuyên xi := 1; for j := i + 1 to n do xj := 0; end; D li u vào (Input): nh p t file v n b n BSTR.INP ch a s nguyên d ng n K t qu ra (Output): ghi ra file v n b n BSTR.OUT các dãy nh phân dài n. BSTR.INP 3 30 BSTR.OUT 000 001 010 011 100 101 110 111 P_1_02_1.PAS * Thu t toán sinh li t kê các dãy nh phân dài n program Binary_Strings; const InputFile = 'BSTR.INP'; OutputFile = 'BSTR.OUT'; max = 30; var x: array[1..max] of Integer; n, i: Integer; f: Text; begin Assign(f, InputFile); Reset(f); ReadLn(f, n); Close(f); Assign(f, OutputFile); Rewrite(f); FillChar(x, SizeOf(x), 0); {C u hình ban u x1 = x2 = … = xn := 0} repeat {Thu t toán sinh} for i := 1 to n do Write(f, x[i]); {In ra c u hình hi n t i} WriteLn(f); i := n; {xi là ph n t cu i dãy, lùi d n i cho t i khi g p s 0 ho c khi i = 0 thì d ng} while (i > 0) and (x[i] = 1) do Dec(i); if i > 0 then {Ch a g p ph i c u hình 11…1} begin x[i] := 1; {Thay xi b ng s 1} FillChar(x[i + 1], (n - i) * SizeOf(x[1]), 0); { t xi + 1 = xi + 2 = … = xn := 0} end; until i = 0; { ã h t c u hình} Close(f); end. 2.2. LI T KÊ CÁC T P CON K PH N T Ta s l p ch ng trình li t kê các t p con k ph n t c a t p {1, 2, …, n} theo th t t Ví d : v i n = 5, k = 3, ta ph i li t kê i n 10 t p con: 1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5} 6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10.{3, 4, 5} Nh v y t p con u tiên (c u hình kh i t o) là {1, 2, …, k}. C u hình k t thúc là {n - k + 1, n - k + 2, …, n}. Nh n xét: Ta s in ra t p con b ng cách in ra l n l t các ph n t c a nó theo th t t ng d n. T ó, ta có nh n xét n u x = {x1, x2, …, xk} và x1 < x2 < … < xk thì gi i h n trên (giá tr l n nh t có th nh n) c a xk là n, c a xk-1 là n - 1, c a xk-2 là n - 2… i h c S ph m Hà N i, 1999-2002 Bài toán li t kê 7 C th : gi i h n trên c a xi = n - k + i; Còn t t nhiên, gi i h n d i c a xi (giá tr nh nh t xi có th nh n) là xi-1 + 1. Nh v y n u ta ang có m t dãy x t t c các ph n t trong x u ã i di n cho m t t p con, n u x là c u hình k t thúc có ngh a là t t i gi i h n trên thì quá trình sinh k t thúc, n u không thì ta ph i sinh ra m t dãy x m i t ng d n tho mãn v a l n h n dãy c theo ngh a không có m t t p con k ph n t nào chen gi a chúng khi s p th t t i n. Ví d : n = 9, k = 6. C u hình ang có x = {1, 2, 6, 7, 8, 9}. Các ph n t x3 h n trên nên x4, x3 lên n x6 ã t t i gi i sinh c u hình m i ta không th sinh b ng cách t ng m t ph n t trong s các x6, x5, c, ta ph i t ng x2 = 2 lên thành x2 = 3. hình này ã tho mãn l n h n c u hình tr c c u hình m i là x = {1, 3, 6, 7, 8, 9}. C u c nh ng ch a tho mãn tính ch t v a ta l i thay x3, x4, x5, x6 b ng các gi i h n d l n mu n v y i c a nó. T c là: x3 := x2 + 1 = 4 x4 := x3 + 1 = 5 x5 := x4 + 1 = 6 x6 := x5 + 1 = 7 Ta c c u hình m i x = {1, 3, 4, 5, 6, 7} là c u hình k ti p. N u mu n tìm ti p, ta l i nh n th y r ng x6 = 7 ch a t gi i h n trên, nh v y ch c n t ng x6 lên 1 là c x = {1, 3, 4, 5, 6, 8}. V y k thu t sinh t p con k ti p t t p ã có x có th xây d ng nh sau: Tìm t cu i dãy lên u cho t i khi g p m t ph n t xi ch a t gi i h n trên n - k + i. i := n; while (i > 0) and (xi = n - k + i) do i := i - 1; (1, 2, 6, 7, 8, 9); N u tìm th y: if i > 0 then T ng xi ó lên 1. xi := xi + 1; (1, 3, 6, 7, 8, 9) t t t c các ph n t phía sau xi b ng gi i h n d i: for j := i + 1 to k do x j := xj-1 + 1; (1, 3, 4, 5, 6, 7) Input: file v n b n SUBSET.INP ch a hai s nguyên d ng n, k (1 k n 30) cách nhau ít nh t m t d u cách Output: file v n b n SUBSET.OUT các t p con k ph n t c a t p {1, 2, …, n} Lê Minh Hoàng 8 Chuyên SUBSET.INP 5 3 SUBSET.OUT {1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} {2, 3, 5} {2, 4, 5} {3, 4, 5} P_1_02_2.PAS * Thu t toán sinh li t kê các t p con k ph n t program Combination; const InputFile = 'SUBSET.INP'; OutputFile = 'SUBSET.OUT'; max = 30; var x: array[1..max] of Integer; n, k, i, j: Integer; f: Text; begin Assign(f, InputFile); Reset(f); ReadLn(f, n, k); Close(f); Assign(f, OutputFile); Rewrite(f); for i := 1 to k do x[i] := i; {x1 := 1; x2 := 2; … ; x3 := k (C u hình kh i t o)} repeat {In ra c u hình hi n t i} Write(f, '{'); for i := 1 to k - 1 do Write(f, x[i], ', '); WriteLn(f, x[k], '}'); {Sinh ti p} i := k; {xi là ph n t cu i dãy, lùi d n i cho t i khi g p m t xi ch a t gi i h n trên n - k + i} while (i > 0) and (x[i] = n - k + i) do Dec(i); if i > 0 then {N u ch a lùi n 0 có ngh a là ch a ph i c u hình k t thúc} begin Inc(x[i]); {T ng xi lên 1, t các ph n t ng sau xi b ng gi i h n d i c a nó} for j := i + 1 to k do x[j] := x[j - 1] + 1; end; until i = 0; {Lùi n t n 0 có ngh a là t t c các ph n t ã t gi i h n trên - h t c u hình} Close(f); end. 2.3. LI T KÊ CÁC HOÁN V Ta s l p ch ng trình li t kê các hoán v c a {1, 2, …, n} theo th t t Ví d v i n = 4, ta ph i li t kê i n. 24 hoán v : 1.1234 2.1243 3.1324 4.1342 5.1423 6.1432 7.2134 8.2143 9.2314 10.2341 11.2413 12.2431 13.3124 14.3142 15.3214 16.3241 17.3412 18.3421 19.4123 20.4132 21.4213 22.4231 23.4312 24.4321 Nh v y hoán v u tiên s là (1, 2, …, n). Hoán v cu i cùng là (n, n-1, … , 1). Hoán v s sinh ra ph i l n h n hoán v hi n t i, h n th n a ph i là hoán v v a l n h n hoán v hi n t i theo ngh a không th có m t hoán v nào khác chen gi a chúng khi s p th t . Gi s hoán v hi n t i là x = (3, 2, 6, 5, 4, 1), xét 4 ph n t cu i cùng, ta th y chúng d n, i u ó có ngh a là cho dù ta có hoán v 4 ph n t này th nào, ta c ng c x p gi m c m t hoán v bé i h c S ph m Hà N i, 1999-2002 Bài toán li t kê 9 h n hoán v hi n t i!. Nh v y ta ph i xét n x2 = 2, thay nó b ng m t giá tr khác. Ta s thay b ng giá tr nào?, không th là 1 b i n u v y s 3 r i (ph n t sau không c hoán v nh h n, không th là 3 vì ã có x1 = c ch n vào nh ng giá tr mà ph n t tr 4, 5, 6. Vì c n m t hoán v v a c ã ch n). Còn l i các giá tr l n h n hi n t i nên ta ch n x2 = 4. Còn các giá tr (x3, x4, x5, x6) s l y trong t p {2, 6, 5, 1}. C ng vì tính v a l n nên ta s tìm bi u di n nh nh t c a 4 s này gán cho x3, x4, x5, x6 t c là (1, 2, 5, 6). V y hoán v m i s là (3, 4, 1, 2, 5, 6). (3, 2, 6, 5, 4, 1) (3, 4, 1, 2, 5, 6). Ta có nh n xét gì qua ví d này: o n cu i c a hoán v c x p gi m d n, s x5 = 4 là s nh nh t trong o n cu i gi m d n tho mãn i u ki n l n h n x2 = 2. N u = 4 và o n cu i v n c x2 c s p x p gi m d n. Khi ó mu n bi u di n nh nh t cho các giá tr trong o n cu i thì ta ch c n Trong tr i ch x5 cho x2 thì ta s o ng c o n cu i. ng h p hoán v hi n t i là (2, 1, 3, 4) thì hoán v k ti p s là (2, 1, 4, 3). Ta c ng có th coi hoán v (2, 1, 3, 4) có o n cu i gi m d n, o n cu i này ch g m 1 ph n t (4) V y k thu t sinh hoán v k ti p t hoán v hi n t i có th xây d ng nh sau: Xác nh o n cu i gi m d n dài nh t, tìm ch s i c a ph n t xi ó. i u này ng ngh a v i vi c tìm t v trí sát cu i dãy lên ng li n tr c o n cu i u, g p ch s i u tiên th a mãn xi < xi+1. N u toàn dãy ã là gi m d n, thì ó là c u hình cu i. i := n - 1; while (i > 0) and (xi > xi+1) do i := i - 1; Trong o n cu i gi m d n, tìm ph n t xk nh nh t tho mãn i u ki n xk > xi. Do o n cu i gi m d n, i u này th c hi n b ng cách tìm t cu i dãy lên u g p ch s k u tiên tho mãn xk > xi (có th dùng tìm ki m nh phân). k := n; while xk < xi do k := k - 1; i ch xk và xi, l t ng c th t o n cu i gi m d n (t xi+1 Input: file v n b n PERMUTE.INP ch a s nguyên d ng n 12 Output: file v n b n PERMUTE.OUT các hoán v c a dãy (1, 2, …, n) PERMUTE.INP 3 PERMUTE.OUT 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 P_1_02_3.PAS * Thu t toán sinh li t kê hoán v program Permutation; const InputFile = 'PERMUTE.INP'; OutputFile = 'PERMUTE.OUT'; max = 12; var n, i, k, a, b: Integer; x: array[1..max] of Integer; f: Text; Lê Minh Hoàng n xk) tr thành t ng d n. 10 Chuyên procedure Swap(var X, Y: Integer); {Th t c var Temp: Integer; begin Temp := X; X := Y; Y := Temp; end; o giá tr hai tham bi n X, Y} begin Assign(f, InputFile); Reset(f); ReadLn(f, n); Close(f); Assign(f, OutputFile); Rewrite(f); for i := 1 to n do x[i] := i; {Kh i t o c u hình u: x1 := 1; x2 := 2; …, xn := n} repeat for i := 1 to n do Write(f, x[i], ' '); {In ra c u hình hoán v hi n t i} WriteLn(f); i := n - 1; while (i > 0) and (x[i] > x[i + 1]) do Dec(i); if i > 0 then {Ch a g p ph i hoán v cu i (n, n-1, … ,1)} begin k := n; {xk là ph n t cu i dãy} while x[k] < x[i] do Dec(k); {Lùi d n k tìm g p xk u tiên l n h n xi } Swap(x[k], x[i]); { i ch xk và xi} a := i + 1; b := n; {L t ng c o n cu i gi m d n, a: u o n, b: cu i o n} while a < b do begin Swap(x[a], x[b]); { i ch xa và xb} Inc(a); {Ti n a và lùi b, i ch ti p cho t i khi a, b ch m nhau} Dec(b); end; end; until i = 0; {Toàn dãy là dãy gi m d n - không sinh ti p c - h t c u hình} Close(f); end. Bài t p: Bài 1 Các ch ch ng trình trên x lý không t t trong tr ng h p t m th ng trình li t kê dãy nh phân c ng nh trong ch v i ch ng, ó là tr ng h p n = 0 ng trình li t kê hoán v , tr iv i ng h p k = 0 i ng trình li t kê t h p, hãy kh c ph c i u ó. Bài 2 Li t kê các dãy nh phân 1}. Hãy l p ch dài n có th coi là li t kê các ch nh h p l p ch p n c a t p 2 ph n t {0, ng trình: Nh p vào hai s n và k, li t kê các ch nh h p l p ch p k c a {0, 1, …, n -1}. G i ý: thay h c s 2 b ng h c s n. Bài 3 Hãy li t kê các dãy nh phân dài n mà trong ó c m ch s "01" xu t hi n úng 2 l n. Bài 4. Nh p vào m t danh sách n tên ng i. Li t kê t t c các cách ch n ra úng k ng i trong s n ng i ó. i h c S ph m Hà N i, 1999-2002