Giáo trình Thiết kế và đánh giá thuật toán

122 trang Đức Chiến 03/01/2024 1760

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Thiết kế và đánh giá thuật toán", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_thiet_ke_va_danh_gia_thuat_toan.pdf

Nội dung text: Giáo trình Thiết kế và đánh giá thuật toán

Thieát keá vaø ñaùnh giaù thuaät toaùn - 1 - MUÏC LUÏC LÔØI NOÙI ÑAÀU - 6 - Chöông 1 : GIÔÙI THIEÄU THIEÁT KEÁ, ÑAÙNH GIAÙ THUAÄT TOAÙN .- 8 - I. Ñònh nghóa tröïc quan veà Thuaät toaùn - 8 - 1. Ñònh nghóa - 8 - 2. Caùc ñaëc tröng cô baûn cuûa thuaät toaùn - 9 - 3. Ñaëc taû thuaät toaùn - 9 - II. Caùc daïng dieãn ñaït thuaät toaùn - 9 - 1. Daïng löu ñoà ( sô ñoà khoái ) - 10 - 2. Daïng ngoân ngöõ töï nhieân - 10 - 3. Ngoân ngöõ laäp trình - 10 - 4. Daïng maõ giaû - 10 - III. Thieát keá thuaät toaùn - 12 - 1. Modul hoùa vaø thieát keá töø treân xuoáng (Top-Down) - 13 - 2. Phöông phaùp laøm mòn daàn (hay tinh cheá töøng böôùc ) - 13 - 3. Moät soá phöông phaùp thieát keá - 15 - IV. Phaân tích thuaät toaùn - 17 - 1. Caùc böôùc trong quaù trình phaân tích ñaùnh giaù thôøi gian chaïy cuûa thuaät toaùn - 17 - 2. Caùc kyù hieäu tieäm caän - 18 - 3. Moät soá lôùp caùc thuaät toaùn - 19 - 4. Phaân tích thuaät toaùn ñeä qui. - 21 - 5. Caùc pheùp toaùn treân caùc kyù hieäu tieäm caän - 25 - 6. Phaân tích tröôøng hôïp trung bình - 26 - V. Toái öu thuaät toaùn - 27 - 1. Kyõ thuaät toái öu caùc voøng laëp - 27 - 2. Toái öu vieäc reõ nhaùnh - 30 - Baøi taäp - 30 - Chöông 2 : PHÖÔNG PHAÙP CHIA ÑEÅ TRÒ - 33 - I. Môû ñaàu - 33 - 1. YÙ töôûng - 33 - 2. Moâ hình - 33 - II. Thuaät toaùn tìm kieám nhò phaân - 33 - 1. Phaùt bieåu baøi toaùn - 33 - 2. YÙ töôûng - 33 - 3. Moâ taû thuaät toaùn - 33 - Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 2 - 4. Ñoä phöùc taïp thôøi gian cuûa thuaät toaùn - 34 - 5. Caøi ñaët - 34 - III. Baøi toaùn MinMax - 35 - 1. Phaùt bieåu baøi toaùn - 35 - 2. YÙ töôûng - 35 - 3. Thuaät toaùn - 35 - 4. Ñoä phöùc taïp thuaät toaùn - 36 - 5. Caøi ñaët - 36 - IV. Thuaät toaùn QuickSort - 36 - 1. YÙ töôûng - 37 - 2. Moâ taû thuaät toaùn - 37 - 3. Ñoä phöùc taïp cuûa thuaät toaùn - 38 - V. Thuaät toaùn nhaân Strassen nhaân 2 ma traän - 39 - 1. Baøi toaùn - 39 - 2. Moâ taû - 39 - VI. Baøi toaùn hoaùn ñoåi 2 phaàn trong 1 daõy - 41 - 1. Phaùt bieåu baøi toaùn - 41 - 2. YÙ töôûng - 41 - 3. Thuaät toaùn - 41 - 4. Ñoä phöùc taïp thuaät toaùn - 43 - 5. Caøi ñaët - 43 - VII. Troän hai ñöôøng tröïc tieáp - 44 - 1. Baøi toaùn - 44 - 2. YÙ töôûng - 44 - 3. Thieát keá - 45 - Baøi taäp - 50 - Chöông 3 : PHÖÔNG PHAÙP QUAY LUI - 53 - I. Môû ñaàu - 53 - 1. YÙ töôûng .- 54- 2. Moâ hình - 53 - II. Baøi toaùn Ngöïa ñi tuaàn - 54 - 1. Phaùt bieåu baøi toaùn - 54 - 2. Thieát keá thuaät toaùn - 55 - III. Baøi toaùn 8 haäu - 57 - 1. Phaùt bieåu baøi toaùn - 57 - 2. Thieát keá thuaät toaùn - 57 - IV. Baøi toaùn lieät keâ caùc daõy nhò phaân ñoä daøi n - 59 - Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 3 - 1. Phaùt bieåu baøi toaùn - 59 - 2. Thieát keá thuaät toaùn - 59 - V. Baøi toaùn lieät keâ caùc hoaùn vò - 60 - 1. Phaùt bieåu baøi toaùn - 60 - 2. Thieát keá thuaät toaùn - 60 - VI. Baøi toaùn lieät keâ caùc toå hôïp - 61 - 1. Phaùt bieåu baøi toaùn - 61 - 2. Thieát keá thuaät toaùn - 61 - VII. Baøi toaùn tìm kieám ñöôøng ñi treân ñoà thò - 61 - 1. Phaùt bieåu baøi toaùn - 61 - 2. Thuaät toaùn DFS ( Depth First Search) - 62 - 3. Thuật toaùn BFS ( Breadth First Search) - 64 - Baøi taäp - 66 - Chöông 4: PHÖÔNG PHAÙP NHAÙNH CAÄN - 69 - I. Môû ñaàu - 69 - 1. YÙ töôûng - 69 - 2. Moâ hình - 69 - II. Baøi toaùn nguôøi du lòch - 70 - 1. Baøi toaùn - 70 - 2. YÙ töôûng - 70 - 3. Thieát keá - 71 - 4. Caøi ñaët - 73 - III. Baøi toaùn caùi tuùi xaùch - 74 - 1. Baøi toaùn - 74 - 2. YÙ töôûng - 74 - 3. Thieát keá thuaät toaùn - 75 - 4. Caøi ñaët - 78 - Baøi taäp - 79 - Chöông 5: PHÖÔNG PHAÙP THAM LAM - 81 - I. Môû ñaàu - 81 - 1. YÙ töôûng - 81 - 2. Moâ hình - 81 - II. Baøi toaùn ngöôøi du lòch - 82 - 1. Baøi toaùn - 82 - 2. YÙ töôûng - 82 - 3. Thuaät toaùn - 82 - 4. Ñoä phöùc taïp cuûa thuaät toaùn - 83 - Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 4 - 5. Caøi ñaët - 83 - III. Thuaät toaùn Dijkstra -Tìm ñöôøng ñi ngaén nhaát trong ñoà thò coù troïng soá - 84 - 1. Baøi toaùn - 84 - 2. YÙ töôûng - 85 - 3. Moâ taû thuaät toaùn - 85 - 4. Caøi ñaët - 87 - 5. Ñoä phöùc taïp cuûa thuaät toaùn - 90 - IV. Thuaät toaùn Prim – Tìm caây bao truøm nhoû nhaát - 90 - 1. Baøi toaùn - 90 - 2. YÙ töôûng - 90 - 3. Moâ taû thuaät toaùn - 90 - 4. Caøi ñaët - 91 - 5. Ñoä phöùc taïp thuaät toaùn - 93 - V. Baøi toaùn ghi caùc baøi haùt - 93 - 1. Phaùt bieåu baøi toaùn - 93 - 2. Thieát keá - 93 - 3. Ñoä phöùc taïp cuûa thuaät toaùn - 94 - 4. Caøi ñaët - 94 - VI. Baøi toaùn chieác tuùi xaùch (Knapsack) - 95 - 1. Phaùt bieåu baøi toaùn - 95 - 2. Thieát keá thuaät toaùn - 95 - 3. Ñoä phöùc taïp cuûa thuaät toaùn - 96 - 4. Caøi ñaët - 96 - VII. Phöông phaùp tham lam vaø Heuristic - 97 - Baøi taäp - 98 - Chöông 6 : PHÖÔNG PHAÙP QUY HOAÏCH ÑOÄNG - 100 - I. Phöông phaùp toång quaùt - 100 - II. Thuaät toaùn Floyd -Tìm ñöôøng ñi ngaén nhaát giöõa caùc caëp ñænh - 100 - 1. Baøi toaùn - 100 - 2. YÙ töôûng - 101 - 3. Thieát keá - 101 - 4. Caøi ñaët - 103 - 5. Ñoä phöùc taïp cuûa thuaät toaùn - 104 - III. Nhaân toå hôïp nhieàu ma traän - 104 - 1. Baøi toaùn - 104 - Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 5 - 2. YÙ töôûng - 104 - 3. Thieát keá - 105 - 4. Ñoä phöùc taïp cuûa thuaät toaùn - 106 - 5. Caøi ñaët - 106 - IV. Caây nhò phaân tìm kieám toái öu (Optimal Binary Search Tree) - 107 - 1. Phaùt bieåu baøi toaùn - 108 - 2. YÙ töôûng - 108 - 3. Thieát keá thuaät toaùn - 109 - 4. Ñoä phöùc taïp cuûa thuaät toaùn - 110 - 5. Caøi ñaët - 111 - V. Daõy chung daøi nhaát cuûa 2 daõy soá - 111 - 1. Baøi toaùn - 111 - 2. YÙ töôûng - 112 - 3. Thuaät toaùn - 112 - 4. Ñoä phöùc taïp cuûa thuaät toaùn - 114 - 5. Caøi ñaët - 114 - VI. Baøi toaùn ngöôøi du lòch - 115 - 1. YÙ töôûng - 116 - 2. Thieát keá thuaät toaùn - 116 - 3. Ñoä phöùc taïp cuûa thuaät toaùn - 118 - Baøi taäp - 118 - PHUÏ LUÏC - 120 - TAØI LIEÄU THAM KHAÛO - 122 - Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 6 - LÔØI NOÙI ÑAÀU Giaùo trình “ Thieát keá vaø ñaùnh giaù thuaät toaùn “ coù noäi dung tieáp sau giaùo trình “Caáu truùc döõ lieäu vaø thuaät toaùn 1” vaø “ Toaùn cao caáp A4”, trình baøy trong 3 tín chæ lyù thuyeát vaø 1 tín chæ thöïc haønh cho caùc sinh vieân ngaønh Toaùn – Tin hoïc vaø Coâng ngheä thoâng tin. Troïng taâm chính cuûa giaùo trình : - Trình baøy moät soá phöông phaùp thieát keá thuaät toaùn thoâng duïng. - Tìm hieåu cô sôû phaân tích ñoä phöùc taïp cuûa thuaät toaùn. Noäi dung giaùo trình goàm 6 chöông : CHÖÔNG 1 : GIÔÙI THIEÄU THIEÁT KEÁ VAØ ÑAÙNH GIAÙ THUAÄT TOAÙN. Chöông naøy giôùi thieäu khaùi nieäm tröïc quan cuûa thuaät toaùn, ngoân ngöõ moâ taû thuaät toaùn, phaân tích thuaät toaùn, caûi tieán thuaät toaùn. CHÖÔNG 2 : PHÖÔNG PHAÙP CHIA ÑEÅ TRÒ Chöông naøy trình baøy kyõ thuaät thieát keá chia ñeå trò, moâ hình thuû tuïc thöôøng söû duïng vaø caùc baøi toaùn minh hoïa nhö : baøi toaùn MinMax, thuaät toaùn Strassen veà nhaân ma traän, thuaät toaùn troän tröïc tieáp, . . . CHÖÔNG 3 : PHÖÔNG PHAÙP QUAY LUI Giôùi thieäu moâ hình ñeä quy quay lui vaø caùc baøi toaùn minh hoïa nhö : baøi toaùn “ ngöïa ñi tuaàn”, baøi toaùn “ taùm haäu “, caùc baøi toaùn toå hôïp, caùc thuaät toaùn tìm kieám treân ñoà thò DFS, BFS. . . CHÖÔNG 4 : PHÖÔNG PHAÙP NHAÙNH CAÄN Chöông naøy moâ taû kyõ thuaät ñaùnh giaù nhaùnh caän trong quaù trình quay lui ñeå tìm lôøi giaûi toái öu cuûa baøi toaùn. Caùc baøi toaùn duøng ñeå minh hoïa nhö baøi toaùn “ Ngöôøi du lòch “, baøi toaùn “ chieác tuùi xaùch “. CHÖÔNG 5 : PHÖÔNG PHAÙP THAM LAM Giôùi thieäu phöông phaùp tìm kieám nhanh lôøi giaûi chaáp nhaän ñöôïc (vaø coù theå laø toái öu) cuûa baøi toaùn toái öu. Caùc baøi toaùn minh hoïa nhö : baøi toaùn “ Ngöôøi du lòch”, thuaät toaùn Dijkstra tìm ñöôøng ñi ngaén nhaát töø moät ñænh ñeán caùc ñænh coøn laïi cuûa ñoà thò, baøi toaùn “ chieác tuùi xaùch “, . . CHÖÔNG 6 : PHÖÔNG PHAÙP QUY HOAÏCH ÑOÄNG Chöông naøy moâ taû yù töôûng, caùc thao taùc chính söû duïng trong thuaät toaùn quy hoaïch ñoäng. Caùc baøi toaùn minh hoïa nhö thuaät toaùn Floyd tìm ñöôøng ñi ngaén nhaát giöõa caùc caëp ñænh cuûa moät ñôn ñoà thò, baøi toaùn nhaân toå hôïp caùc ma traän, caây nhò phaân tìm kieám toái öu Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 7 - Vì trình ñoä ngöôøi bieân soaïn coù haïn neân taäp giaùo trình khoâng traùnh khoûi nhieàu khieám khuyeát, chuùng toâi raát mong söï goùp yù cuûa caùc baïn ñoàng nghieäp vaø sinh vieân. Cuoái cuøng, chuùng toâi caûm ôn söï ñoäng vieân, giuùp ñôõ nhieät thaønh cuûa caùc baïn ñoàng nghieäp trong khoa Toaùn-Tin hoïc ñeå taäp giaùo trình naøy ñöôïc hoaøn thaønh. Ñaølaït, ngaøy 10 thaùng 11 naêm 2002 TRAÀN TUAÁN MINH Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 8 - CHÖÔNG 1 : GIÔÙI THIEÄU THIEÁT KEÁ, ÑAÙNH GIAÙ THUAÄT TOAÙN Thuaät ngöõ thuaät toaùn (Algorithm ) laø töø vieát taét cuûa teân moät nhaø toaùn hoïc ôû theá kyû IX : Abu Ja’fa Mohammed ibn Musa al-Khowarizmi . Ñaàu tieân, thuaät toaùn ñöôïc hieåu nhö laø caùc quy taéc thöïc hieän caùc pheùp toaùn soá hoïc vôùi caùc con soá ñöôïc vieát trong heä thaäp phaân. Cuøng vôùi söï phaùt trieân cuûa maùy tính , khaùi nieäm thuaät toaùn ñöôïc hieåu theo nghóa roäng hôn. Moät ñònh nghóa hình thöùc veà thuaät toaùn ñöôïc nhaø toaùn hoïc ngöôøi Anh laø Alanh Turing ñöa ra vaøo naêm 1936 thoâng qua maùy Turing. Coù theå noùi lyù thuyeát thuaät toaùn ñöôïc hình thaønh töø ñoù. Lyù thuyeát thuaät toaùn quan taâm ñeán nhöõng vaán ñeà sau : 1. Giaûi ñöôïc baèng thuaät toaùn : Lôùp baøi toaùn naøo giaûi ñöôïc baèng thuaät toaùn, lôùp baøi toaùn khoâng giaûi ñöôïc baèng thuaät toaùn. 2. Toái öu hoùa thuaät toaùn : Thay nhöõng thuaät toaùn chöa toát baèng nhöõng thuaät toaùn toát hôn. 3. Trieån khai thuaät toaùn : Xaây döïng nhöõng ngoân ngöõ thöïc hieän treân maùy tính ñeå maõ hoùa thuaät toaùn. Höôùng nghieân cöùu thöù 2 thuoäc phaïm vi cuûa lónh vöïc phaân tích thuaät toaùn : Ñaùnh löôïng möùc ñoä phöùc taïp cuûa thuaät toaùn ; coøn höôùng thöù ba thöôøng ñöôïc xeáp vaøo khoa hoïc laäp trình. Chöông ñaàu tieân cuûa giaùo trình seõ giôùi thieäu thuaät toaùn theo nghóa tröïc quan vaø moät soá khaùi nieäm môû ñaàu veà phaân tích vaø thieát keá thuaät toaùn. I. Ñònh nghóa tröïc quan veà Thuaät toaùn 1. Ñònh nghóa Thuaät toaùn laø moät daõy höõu haïn caùc thao taùc ñöôïc boá trí theo moät trình töï xaùc ñònh, ñöôïc ñeà ra tröôùc, nhaèm giaûi quyeát moät baøi toaùn nhaát ñònh. - Thao taùc , hay coøn goïi laø taùc vuï, pheùp toaùn ( Operation ) hay leänh (Command), chæ thò (Instruction) laø moät haønh ñoäng caàn ñöôïc thöïc hieän bôûi cô cheá thöïc hieän thuaät toaùn. Moãi thao taùc bieán ñoåi baøi toaùn töø moät traïng thaùi tröôùc (hay traïng thaùi nhaäp) sang traïng thaùi sau (hay traïng thaùi xuaát).Thöïc teá moãi thao taùc thöôøng söû duïng moät soá ñoái töôïng trong traïng thaùi nhaäp (caùc ñoái töôïng nhaäp )vaø saûn sinh ra caùc ñoái töôïng môùi trong traïng thaùi xuaát (caùc ñoái töôïng xuaát). Quan heä giöõa 2 traïng thaùi xuaát vaø nhaäp cho thaáy taùc ñoäng cuûa thao taùc. Daõy caùc thao taùc cuûa thuaät toaùn noái tieáp nhau nhaèm bieán ñoåi baøi toaùn töø traïng thaùi ban ñaàu ñeán traïng thaùi keát quaû. Moãi thao taùc coù theå phaân tích thaønh caùc thao taùc ñôn giaûn hôn. - Trình töï thöïc hieän caùc thao taùc phaûi ñöôïc xaùc ñònh roõ raøng trong thuaät toaùn. Cuøng moät taäp hôïp thao taùc nhöng xeáp ñaët theo trình töï khaùc nhau seõ cho keát quaû khaùc nhau. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 9 - 2. Caùc ñaëc tröng cô baûn cuûa thuaät toaùn a) Tính xaùc ñònh Caùc thao taùc, caùc ñoái töôïng, phöông tieän trong thuaät toaùn phaûi coù yù nghóa roõ raøng, khoâng ñöôïc gaây nhaàm laãn. Noùi caùch khaùc, hai cô cheá hoaït ñoäng khaùc nhau (ngöôøi hoaëc maùy ) cuøng thöïc hieän moät thuaät toaùn, söû duïng caùc ñoái töôïng, phöông tieän nhaäp phaûi cho cuøng moät keát quaû. b) Tính döøng (hay höõu haïn) Ñoøi hoûi thuaät toaùn phaûi döøng vaø cho keát quaû sau moät soá höõu haïn caùc böôùc . c) Tính ñuùng cuûa thuaät toaùn Thuaät toaùn ñuùng laø thuaät toaùn cho keát quaû thoûa maõn ñaëc taû thuaät toaùn vôùi moïi tröôøng hôïp cuûa caùc ñoái töôïng, phöông tieän nhaäp. Thuaät toaùn sai khi sai trong (ít nhaát ) moät tröôøng hôïp. d) Tính phoå duïng Thuaät toaùn ñeå giaûi moät lôùp baøi toaùn goàm nhieàu baøi toaùn cuï theå, lôùp ñoù ñöôïc xaùc ñònh bôûi ñaëc taû. Dó nhieân coù lôùp baøi toaùn chæ goàm 1 baøi. Thuaät toaùn khi ñoù seõ khoâng caàn söû duïng ñoái töôïng, phöông tieän nhaäp naøo caû. 3. Ñaëc taû thuaät toaùn Moãi thuaät toaùn nhaèm giaûi quyeát moät lôùp caùc baøi toaùn cuï theå. Moãi laàn thöïc hieän thuaät toaùn caàn phaûi cung caáp cho cô cheá thöïc hieän moät soá ñoái töôïng hay phöông tieän caàn thieát naøo ñoù. Caùc ñoái töôïng hay phöông tieän naøy phaân bieät baøi toaùn cuï theå trong lôùp baøi toaùn maø thuaät toaùn giaûi quyeát. Laøm sao ñònh roõ lôùp baøi toaùn maø moät thuaät toaùn giaûi quyeát? Ñoù laø ñaëc taû thuaät toaùn. Ñaëc taû thuaät toaùn caàn chæ ra caùc ñaëc ñieåm sau : 1. Caùc ñoái töôïng vaø phöông tieän cuûa thuaät toaùn caàn söû duïng (nhaäp). 2. Ñieàu kieän raøng buoäc (neáu coù) treân caùc ñoái töôïng vaø phöông tieän ñoù. 3. Caùc saûn phaåm ,keát quaû (xuaát). 4. Caùc yeâu caàu treân saûn phaåm, keát quaû. Thöôøng xuaát hieän döôùi daïng quan heä giöõa keát quaû vaø caùc ñoái töôïng, phöông tieän söû duïng. THUAÄT INPUT TOAÙN OUTPUT II. Caùc daïng dieãn ñaït thuaät toaùn Thuaät toaùn coù theå dieãn ñaït döôùi nhieàu hình thöùc, chaúng haïn döôùi daïng löu ñoà, daïng ngoân ngöõ töï nhieân, daïng maõ giaû hoaëc moät ngoân ngöõ laäp trình naøo ñoù . Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 10 - 1. Daïng löu ñoà ( sô ñoà khoái ) Duøng caùc hình veõ ( coù qui öôùc ) ñeå dieãn ñaït thuaät toaùn .Löu ñoà cho hình aûnh tröïc quan vaø toång theå cuûa thuaät toaùn ,cho neân thöôøng ñöôïc söû duïng. 2. Daïng ngoân ngöõ töï nhieân Thuaät toaùn coù theå trình baøy döôùi daïng ngoân ngöõ töï nhieân theo trình töï caùc böôùc thöïc hieän trong thuaät toaùn . 3. Ngoân ngöõ laäp trình. Duøng caáu truùc leänh, döõ lieäu cuûa moät ngoân ngöõ laäp trình naøo ñoù ñeå moâ taû. 4. Daïng maõ giaû Thuaät toaùn trình baøy trong daïng vaên baûn baêng ngoân ngöõ töï nhieân tuy deã hieåu nhöng khoù caøi ñaët. Duøng moät ngöõ laäp trình naøo ñoù ñeå dieãn taû thì phöùc taïp, khoù hieåu. Thoâng thöôøng thuaät toaùn cuõng ñöôïc trao ñoåi döôùi daïng vaên baûn - tuy khoâng raøng buoäc nhieàu vaøo cuù phaùp xaùc ñònh nhö caùc ngoân ngöõ laäp trình, nhöng cuõng tuaân theo moät soá quy öôùc ban ñaàu - Ta goïi daïng naøy laø maõ giaû. Tuøy theo vieäc ñònh höôùng caøi ñaët thuaät toaùn theo ngoân ngöõ laäp trình naøo ta dieãn ñaït thuaät toaùn gaàn vôùi ngoân ngöõ aáy. Trong phaàn naøy ta trình baøy moät soá quy öôùc cuûa ngoân ngöõ maõ giaû trong daïng gaàn C/C++. a) Kyù töï - Boä chöõ caùi : 26 chöõ caùi. - 10 chöõ soá thaäp phaân. - Caùc daáu pheùp toaùn soá hoïc. - Caùc daáu pheùp toaùn quan heä. . . . b) Caùc töø : Gheùp caùc kyù töï chöõ, soá, daáu gaïch döôùi ( _ ). Caùc töø sau xem nhö laø caùc töø khoùa : if, else, case, for, while , do while c) Caùc pheùp toaùn soá hoïc vaø logic - Caùc pheùp toaùn soá hoïc : +, -, *, /, %. - Caùc pheùp toaùn Logic : &&, ||, ! cuûa C/C++. d) Bieåu thöùc vaø thöù töï öu tieân caùc pheùp toaùn trong bieåu thöùc (Nhö C/C++). e) Caùc caâu leänh 1. Leänh gaùn : x = Bieåu thöùc; 2. Leänh gheùp ( Khoái leänh ) : [ A1 ; . . . An; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 11 - } 3. Caáu truùc reõ nhaùnh : if (C) if (C) A A else B Trong ñoù C laø bieåu thöùc logic, A vaø B laø caùc khoái leänh. 4. Caáu truùc choïn : bt Maõ giaû Switch(Bt) C1 1 A1 Case C1 : A1; Case C2 : A2; 0 . . . . . . Case Cn : An C2 1 A2 [default : An+1;] Trong ñoù : 0 - bt : Bieåu thöùc nguyeân. - Ci laø caùc giaù trò nguyeân ñoâi moät khaùc Cn 1 An nhau. - Ai laø nhoùm leänh. 0 An+1 5. Laëp vôùi kieåm tra ñieàu kieän tröôùc (While). Maõ giaû : While C A; C 0 1 A Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 12 - 6. Laëp vôùi kieåm tra ñieàu kieän sau (do while). Maõ giaû : do A A; while (C); 1 C 0 7. Laëp vôùi soá laàn laëp xaùc ñònh Maõ giaû : For (bt1;bt2;bt3) A bt1 Trong ñoù : - bt1 : Khôûi ñaàu giaù trò bieán ñieàu khieån. 0 - bt2 : Bieåu thöùc ñieàu kieän, xaùc ñònh ñieàu bt2 kieän laëp. - bt3 : Khôûi ñaàu laïi bieán ñieàu khieån - A laø khoái leänh. 1 A bt3 8. Caâu leänh vaøo ra : Ñoïc : scanf(danh_saùch_bieán); Vieát : printf(Danh_saùch_bieán); 9. Caâu leänh baùt ñaàu vaø keát thuùc : { . . . } 10. Haøm (Function): Type teân_haøm (Danh saùch caùc type vaø ñoái) { . . . } 11. Lôøi goïi haøm : teân_haøm (Danh saùch caùc tham soá thöïc); 12. Caâu leänh return return (bt) : Gaùn giaù trò bieåu thöùc bt cho haøm. III. Thieát keá thuaät toaùn Thuaät toaùn ñöôïc thieát keá moät caùch coù caáu truùc, coâng cuï chuû yeáu laø : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 13 - 1. Modul hoùa vaø thieát keá töø treân xuoáng (Top-Dow) Caùc baøi toaùn giaûi ñöôïc treân maùy tính ngaøy caøng phöùc taïp vaø ña daïng. Caùc thuaät toaùn giaûi chuùng ngaøy caøng coù quy moâ lôùn ñoøi hoûi nhieàu thôøi gian vaø coâng söùc cuûa nhieàu ngöôøi. Tuy nhieân coâng vieäc seõ ñôn giaûn hôn neáu nhö ta chia baøi toaùn ra thaønh caùc baøi toaùn nhoû. Ñieàu ñoù cuõng coù nghóa laø neáu coi baøi toaùn laø modul chính thì caàn chia thaønh caùc modul con. Ñeán löôït mình caùc modul con laïi phaân raõ thaønh caùc modul con thích hôïp Nhö vaäy vieäc toå chöùc lôøi giaûi theå hieän theo moät caáu truùc phaân caáp : A A1 A2 A3 A1 A1 A3 A3 A3 . . . . . . . . . Chieán thuaät giaûi baøi toaùn nhö vaäy laø “chia ñeå trò”, theå hieän chieán thuaät ñoù ta duøng thieát keá töø treân xuoáng. Ñoù laø caùch nhìn nhaän vaán ñeà moät caùch toång quaùt, ñeà caäp ñeán caùc coâng vieäc chính, sau ñoù môùi boå sung daån caùc chi tieát. 2. Phöông phaùp laøm mòn daàn (hay tinh cheá töøng böôùc ) Laø phöông phaùp thieát keá phaûn aùnh tinh thaàn modul hoùa vaø thieát keá töø treân xuoáng. Ñaàu tieân thuaät toaùn ñöôïc trình baøy döôùi daïng ngoân ngöõ töï nhieân theå hieän yù chính coâng vieäc. Caùc böôùc sau seõ chi tieát hoùa daàn töông öùng vôùi caùc coâng vieäc nhoû hôn. Ñoù laø caùc böôùc laøm mòn daàn ñaëc taû thuaät toaùn vaø höôùng veà ngoân ngöõ laäp trình maø ta döï ñònh caøi ñaët. Quaù trình thieát keá vaø phaùt trieån thuaät toaùn seõ theå hieän daàn töø ngoân ngöõ töï nhieân, sang ngoân ngöõ maõ giaû roài ñeán ngoân ngöõ laäp trình, vaø ñi töø möùc “laøm caùi gì “ñeán “laøm nhö theá naøo”. Ví duï : Baøi toaùn naén teân . Moät teân coù theå coù moät hay nhieøu töø, caùc töø taùch bieät bôûi ít nhaát 1 daáu caùch (khoaûng traéng, tab, ). Töø laø moät daõy caùc kyù töï khaùc daáu caùch. Vieäc naén teân thöïc hieän theo caùc quy caùch : (i) Khöû caùc daáu caùch ôû ñaàu vaø cuoái cuûa teân (caû hoï vaø teân ñöôïc goïi taét laø teân ). (ii) Khöû bôùt caùc daáu caùch ôû giöõa caùc töø, chæ ñeå laïi moät daáu caùch. (iii) Caùc chöõ caùi ñaàu töø ñöôïc vieát hoa, ngoøai ra moïi chöõ caùi coøn laïi ñöôïc vieát thöôøng. Chöông trình ñöôïc phaùt thaûo bôûi : Möùc 0 : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 14 - Naén x thaønh x theo caùc quy taéc (i-iii). Möùc 1 : Do teân ñöôïc taïo bôûi caùc töø , neân naén teân thì ta phaûi naén caùc töø. Ta naén töøng töø trong teân cho ñeán heát caùc töø. YÙ töôûng ôû muùc 1 ñöôïc laøm mòn hôn nhö sau : Khi (coøn töø w trong x) ta thöïc hieän Naén laïi töø w trong x; Ñaët moät daáu caùch neáu caàn; Möùc 2 : Ta chi tieát hôn thao taùc :”Ñaët moät daáu caùch neáu caàn”. Roõ raøng daáu caùch noái chæ ñaët sau moãi töø, tröø töø cuoái cuøng. Nhö vaäy sau khi xöû lyù xong töø cuoái thì ta khoâng ñaët daáu caùch. Vaäy ta coù theå vieát : Khi (coøn töø w trong x) ta thöïc hieän Naén laïi töø w trong x; Neáu w chöa phaûi laø töø cuoái trong x thì Ñaët moät daáu caùch sau w; Möùc 3 : Ñeå xöû lyù döõ lieäu ñöôïc roõ raøng, taïm thôøi ta coi teân ñích laø y vaø teân nguoàn laø x. y = töø roång; Khi (coøn töø w trong x) ta thöïc hieän Naén laïi töø w trong x; Gheùp w vaøo sau y; Neáu w chöa phaûi laø töø cuoái trong x thì Gheùp daáu caùch vaøo sau y; Möùc 4 : Ta cuï theå hoùa theá naøo laø 1 töø . Deã thaáy laø moät töø w cuûa x laø moät daõy kyù töï khoâng chöùa daáu caùch vaø ñöôïc chaën ñaàu vaø cuoái bôûi daáu caùch hoaëc töø roång. Coù theå nhaän daïng ñöôïc töø w trong x baèng thao taùc ñôn giaûn sau ñaây : a) Vöôït daõy daáu caùch ñeå ñeán ñaàu töø. b) Vöôït daõy kyù töï khaùc daáu caùch ñeå ñeán heát töø. Ta chuù yù raèng tín hieäu keát thuùc cuûa x laø kyù töï NULL. Ta coù theå vieát haøm naén teân nhö sau : void Nanten(char x[]) { char y[max]; int i; y[0] = '\0'; // Vöôït daõy daáu caùch bieân traùi i = 0; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 15 - while (x[i] == cach ) i++; //Cho keát quaû : x[i] laø ñaàu 1 töø hay laø x[i] = NULL while (x[i] != NULL) // Tröôøng hôïp x[i] ñaàu 1 töø { ghepkt(Hoa(x[i]),y); // Kyù töï ñaàu laø Hoa i++; //Sang thaân töø hoaëc rôi vaøo keát while ((x[i] != cach )&& (x[i] != NULL)) // Thaân 1 töø { // Xöû lyù thaân töø ghepkt(Thuong(x[i]),y); // Trong thaân töø, KT vieát thöôøng i++; } // Xöû lyù xong 1 töø, tìm ñeán töø tieáp theo while (x[i] == cach) i++; // Vöôït daáu caùch sau 1 töø if (x[i] != NULL) // Töø vöøa xöû lyù chöa phaûi laø töø cuoái ghepkt(cach,y); } strcpy( y,x); } Möùc 5 : Ta vieát theâm caùc haøm : Hoa(char x) : Ñoåi kyù töï thöôøng thaønh Hoa; Thuong(char x): Ñoåi kyù töï hoa thaønh thöôøng. ghepkt (char ch, char y[ ]); Gheùp kyù töï ch vaøo cuoái xaâu y, löu tröû laïi vaøo y. Nhaän xeùt raèng khoaûng caùch d = | ‘A’ - ‘a’| ( = 32) chính laø ñoä leäch boä chöõ hoa ñeán chöõ thöôøng. Vaäy neáu ch laø chöõ thöôøng thì ch -d seõ laø maõ cuûa töø hoa töông öùng, vaø ngöôïc laïi, neáu ch laø chöõ hoa thì ch + d seõ laø maõ cuûa töø thöôøng töông öùng. Töø ñoù suy ra caùch caøi ñaët caùc haøm Hoa() vaø Thuong(). Coøn haøm gheùp(), Chæ caàn xaùc ñònh cuoái cuûa y, sau ñoù cheùp ch vaøo cuoái cuûa y laø xong. 3. Moät soá phöông phaùp thieát keá Treân cô sôû lyù thuyeát maùy Turing, ta chia ñöôïc caùc baøi toaùn thaønh 2 lôùp khoâng giao nhau : Lôùp giaûi ñöôïc baèng thuaät toaùn , vaø lôùp khoâng giaûi ñöôïc baèng thuaät toaùn. Ñoái vôùi lôùp caùc baøi toaùn giaûi ñöôïc baèng thuaät toaùn, döïa vaøo caùc ñaëc tröng cuûa quaù trình thieát keá cuûa thuaät toaùn, ta coù theå chæ ra moät soá caùc phöông phaùp thieát keá thuaät toaùn cô baûn sau ñaây : a) Phöông phaùp chia ñeå tri. ( Divide-and-Conquer method ). YÙ töôûng laø : Chia döõ lieäu thaønh töøng mieàn ñuû nhoû, giaûi baøi toaùn treân caùc mieàn ñaõ chia roài toång hôïp keát quaû laïi . Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 16 - Chaúng haïn nhö thuaät toaùn Quicksort. b) Phöông phaùp quay lui ( BackTracking method ). Tìm kieám theo öu tieân. Ñoái vôùi moãi böôùc thuaät toaùn, öu tieân theo ñoä roäng hay chieàu saâu ñeå tìm kieám. Chaúng haïn thuaät toaùn giaûi baøi toaùn 8 haäu. c) Phöông phaùp tham lam ( Greedy Method ). YÙ töôûng laø : Xaùc ñònh traät töï xöû lyù ñeå coù lôïi nhaát, Saép xeáp döõ lieäu theo traät töï ñoù, roài xöû lyù döõ lieäu theo traät töï ñaõ neâu. Coâng söùc boû ra laø tìm ra traät töï ñoù. Chaúng haïn thuaät toaùn tìm caây bao truøm nhoû nhaát (Shortest spanning Trees). d) Phöông phaùp Quy hoaïch ñoäng (Dynamic Programming method). Phöông phaùp quy hoaïch ñoäng döïa vaøo moät nguyeân lyù, goïi laø nguyeân lyù toái öu cuûa Bellman : “ Neáu lôøi giaûi cuûa baøi toaùn laø toái öu thì lôøi giaûi cuûa caùc baøi toaùn con cuõng toái öu ”. Phöông phaùp naøy toå chöùc tìm kieám lôøi giaûi theo kieåu töø döôùi leân. Xuaát phaùt töø caùc baøi toaùn con nhoû vaø ñôn giaûn nhaát, toå hôïp caùc lôøi giaûi cuûa chuùng ñeå coù lôøi giaûi cuûa baøi toaùn con lôùn hôn vaø cöù nhö theá cuoái cuøng ñöôïc lôøi giaûi cuûa baøi toaùn ban ñaàu. Chaúng haïn thuaät toaùn “chieác tuùi xaùch” (Knapsack). e) Phöông phaùp nhaùnh caän ( branch-and-bound method ). YÙ töôûng laø : Trong quaù trình tìm kieám lôøi giaûi, ta phaân hoaïch taäp caùc phöông aùn cuûa baøi toaùn ra thaønh hai hay nhieàu taäp con ñöôïc bieåu dieãn nhö laø caùc nuùt cuûa caây tìm kieám vaø coá gaêng baèng pheùp ñaùnh giaù caän cho caùc nuùt, tìm caùch loaïi boû caùc nhaùnh cuûa caây maø ta bieát chaéc khoâng chöa phöông aùn toái öu. Chaúng haïn thuaät toaùn giaûi baøi toaùn ngöôøi du lòch. . . . Ta coù theå minh hoïa bôûi hình veõ sau : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 17 - IV. Phaân tích thuaät toaùn Khi xaây döïng ñöôïc thuaät toaùn ñeå giaûi baøi toaùn thì coù haèng loaït vaán ñeà ñöôïc ñaët ra ñeå phaân tích. Thöôøng laø caùc vaán ñeà sau : - Yeâu caàu veà tính ñuùng ñaén cuûa thuaät toaùn, thuaät toaùn coù cho lôøi giaûi ñuùng cuûa baøi toaùn hay khoâng ? - Tính ñôn giaûn cuûa thuaät toaùn. Thöôøng ta mong muoán coù ñöôïc moät thuaät toaùn ñôn giaûn, deã hieåu, deã laäp trình. Ñaëc bieät laø nhöõng thuaät toaùn chæ duøng moät vaøi laàn ta caàn coi troïng tính chaát naøy, vì coâng söùc vaø thôøi gian boû ra ñeå xaây döïng thuaät toaùn thöôøng lôùn hôn raát nhieàu so vôùi thôøi gian thöïc hieän noù. - Yeâu caàu veà khoâng gian : thuaät toaùn ñöôïc xaây döïng coù phuø hôïp vôùi boä nhôù cuûa maùy tính hay khoâng ? - Yeâu caàu veà thôøi gian : Thôøi gian chaïy cuûa thuaät toaùn coù nhanh khoâng ? Moät baøi toaùn thöôøng coù nhieàu thuaät toaùn ñeå giaûi, cho neân yeâu caàu moät thuaät toaùn daãn nhanh ñeán keát quaû laø moät ñoøi hoûi ñöông nhieân. . . . . . . . Trong phaàn naøy ta quan taâm chuû yeáu ñeán toác ñoä cuûa thuaät toaùn. Ta cuõng löu yù raèng thôøi gian chaïy cuûa thuaät toaùn vaø dung löôïng boä nhôù nhieàu khi khoâng caân ñoái ñöôïc ñeå coù moät giaûi phaùp troïn veïn. Chaúng haïn, thuaät toaùn saép xeáp noäi seõ coù thôøi gian chaïy nhanh hôn vì döõ lieäu ñöôïc löu tröû trong boä nhôù trong, vaø do ñoù khoâng phuø hôïp trong tröôøng hôïp kích thöôùc döõ lieäu lôùn. Ngöôïc laïi, caùc thuaät toaùn saép xeáp ngoaøi phuø hôïp vôùi kích thöôùc döõ lieäu lôùn vì döõ lieäu ñöôïc löu tröû chính ôû caùc thieát bò ngoaøi, nhöng khi ñoù toác ñoä laïi chaäm hôn. 1. Caùc böôùc trong quaù trình phaân tích ñaùnh giaù thôøi gian chaïy cuûa thuaät toaùn - Böôùc ñaàu tieân trong vieäc phaân tích thôøi gian chaïy cuûa thuaät toaùn laø quan taâm ñeán kích thöôùc döõ lieäu, seõ ñöôïc duøng nhö döõ lieäu nhaäp cuûa thuaät toaùn vaø quyeát Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 18 - ñònh phaân tích naøo laø thích hôïp. Ta coù theå xem thôøi gian chaïy cuûa thuaät toaùn laø moät haøm theo kích thöôùc cuûa döõ lieäu nhaäp. Neáu goïi n laø kích thöôùc cuûa döõ lieäu nhaäp thì thôøi gian thöïc hieän T cuûa thuaät toaùn ñöôïc bieåu dieãn nhö moät haøm theo n, kyù hieäu laø : T(n). - Böôùc thöù hai trong vieäc phaân tích ñaùnh giaù thôøi gian chaïy cuûa moät thuaät toaùn laø nhaân ra caùc thao taùc tröøu töôïng cuûa thuaät toaùn ñeå taùch bieät söï phaân tích vaø söï caøi ñaët. Bôûi vì ta bieát raèng toác ñoä xöû lyù cuûa maùy tính vaø caùc boä dòch cuûa caùc ngoân ngöõ laäp trình caáp cao ñeàu aûnh höôûng ñeán thôøi gian chaïy cuûa thuaät toaùn, nhöng nhöõng yeáu toá naøy aûnh höôûng khoâng ñoàng ñeàu vôùi caùc loïai maùy treân ñoù caøi ñaët thuaät toaùn, vì vaäy khoâng theå döïa vaøo chuùng ñeå ñaùnh giaù thôøi gian chaïy cuûa thuaät toaùn. Chaúng haïn ta taùch bieät söï xem xeùt coù bao nhieâu pheùp toaùn so saùnh trong moät thuaät toaùn saép xeáp khoûi söï xaùc ñònh caàn bao nhieâu micro giaây chaïy treân moät maùy tính cuï theå. Yeáu toá thöù nhaát döôïc xaùc ñònh bôûi tính chaát cuûa thuaät toaùn, coøn yeùu toá thöù hai ñöôïc xaùc ñònh bôûi tính naêng cuûa maùy tính. Ñieàu naøy cho ta thaáy raèng T(n) khoâng theå ñöôïc bieåu dieãn baèng giaây, phuùt ñöôïc; caùch toát hôn laø bieåu dieãn theo soá caùc chæ thò trong thuaät toaùn. Ví duï : Xeùt : for(i = 1; i < n; i++) (1) for(j = 1; j < n; j++) (2) Kyù hieäu : T(n) laø thôøi gian thöïc hieän caâu leänh (2) : 1 1 2 3 . . . n-1 (2) n n n n T(n) = n + + n = (n −1)n 142L43 (n−1)la)n - Böôùc thöù ba trong vieäc phaân tích ñaùnh giaù thôøi gian chaïy cuûa moät thuaät toaùn laø söï phaân tích veà maët toaùn hoïc vôùi muïc ñích tìm ra caùc giaù trò trung bình vaø tröôøng hôïp xaáu nhaát cho moãi ñaïi löôïng cô baûn. Chaúng haïn, khi saép xeáp moät daõy caùc phaàn töû, thôøi gian chaïy cuûa thuaät toaùn hieån nhieân coøn phuï thuoäc vaøo tính chaát cuûa döõ lieäu nhaäp nhö : * Daõy coù thöù töï thuaän. * Daõy coù thöù töï ngöôïc. * Caùc soá haïng cuûa daõy coù thöù töï ngaãu nhieân. 2. Caùc kyù hieäu tieäm caän a) Kyù hieäu O lôùn (big – oh) : Ñònh nghóa : Cho haøm f : N* ⎯⎯→ N* . Ta ñònh nghóa : * + O(f(n)) = {t : N* ⎯⎯→ N | ∃ c∈ R , ∃n0 ∈ N, ∀ n ≥ n0 , t(n) ≤ cf(n)} O(f(n)) goïi laø caáp cuûa f(n). Vôùi t : N* ⎯⎯→ N* + t(n) ∈ O(f(n)) ⇔ ∃ c∈ R , ∃n0 ∈ N, ∀ n ≥ n0 , t(n) ≤ cf(n) . Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 19 - Nhaän xeùt : a) t(n) ∈ O(t(n)) + b) t(n) ∈ O(f(n)) ⇒ ∃ c∈ R , ∀ n ∈ N , t(n) ≤ cf(n) . Caùc tính chaát : Tính chaát 1 : Vôùi moïi haøm f : N* ⎯⎯→ N* : 2 2 ⎪⎧• f (n) ∈O(n ) f (n) ∈O(n) ⇒ ⎨ f (n) n ⎩⎪• 2 ∈O(2 ) Tính chaát 2: a) f(n) ∈ O(g(n)) vaø g(n) ∈ O(h(n)) ⇒ f(n) ∈ O(h(n)). b) g(n) ∈ O(h(n)) ⇒ O(g(n)) ⊆ O(h(n)). Tính chaát 3: a) O(f(n)) = O(g(n)) ⇔ g(n) ∈ O(f(n)) vaø f(n) ∈ O(g(n)). b) O(f(n)) ⊂ O(g(n)) ⇔ f(n) ∈ O(g(n)) vaø g(n) ∉ O(f(n)). Tính chaát 4: fn() a) lim = c ≠ 0 ⇔ O(f(n)) = O(g(n)) n→∞ gn() fn() b) lim = 0 ⇒ O(f(n)) ⊂ O(g(n)) = O(g(n)± f(n)) n→∞ gn() Ví duï : - Haøm f(n) = 2n5 + 3n3 + 6n2 + 2 coù caáp O(n5 ) vì : 23nn53++6n2+2 lim =≠20. n→∞ n5 - Haøm f(n) = 2n laø O(n! ) vì : 2n lim = 0 . n→∞ n! - Haøm 2n+1 ∈ O(2n ) . b) Kyù hieäu Ω : Kyù hieäu naøy duøng ñeå chæ chaën döôùi cuûa thôøi gian chaïy cuûa thuaät toaùn Ta ñònh nghóa : * + Ω (f(n)) = {t : N ⎯⎯→ N | ∃ c∈ R , ∃n0 ∈ N, ∀ n ≥ n0 , t(n) ≥ cf(n)} Tính chaát 6: Cho f, g : N ⎯⎯→ N* , Ta coù : f(n) ∈ O(g(n)) ⇔ g(n) ∈ Ω (f(n)). c) Kyù hieäu θ : Ñònh nghóa : θ(f(n)) = O(f(n)) ∩ Ω (f(n)). Tính chaát 7: + f(n) ∈ θ (g(n)) ⇔ ∃ c,d∈ R , ∃n0 ∈ N, ∀ n ≥ n0 , cg(n) ≤ f(n) ≤ dg(n) . 3. Moät soá lôùp caùc thuaät toaùn Haàu heát caùc thuaät toaùn ñöôïc giôùi thieäu trong giaùo trình naøy tieäm caän tôùi moät trong caùc haøm sau : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 20 - (1) 1 : Neáu taát caû caùc chæ thò cuûa chöông trình ñeàu ñöôïc thöïc hieän chæ moät vaøi laàn vaø ta noùi thôøi gian chaïy cuûa noù laø haèng soá. (2) Logn : Khi thôøi gian chaïy cuûa chöông trình laø Logarit. Thôøi gian chaïy thuoäc loaïi naøy xuaát hieän trong caùc chöông trình maø giaûi 1 baøi toùan lôùn baèng caùch chuyeån noù thaønh 1 baøi toaùn nhoû hôn, baèng caùch caét boû kích thöôùc moät haèng soá naøo ñoù. Cô soá Logarit coù theå laøm thay ñoåi haèng soá ñoù nhöng khoâng nhieàu. (3) n : Khi thôøi gian chaïy cuûa chöông trình laø tuyeán tính. (4) nLogn : Thôøi gian chaïy thuoäc loaïi naøy xuaát hieän trong caùc chöông trình maø giaûi 1 baøi toaùn lôùn baèng caùch chuyeån noù thaønh caùc baøi toaùn nhoû hôn, keù ñeán giaûi quyeát chuùng 1 caùch ñoäc laäp, sau ñoù toå hôïp caùc lôøi giaûi. (5) n2 : Thôøi gian chaïy cuûa thuaät toaùn laø baäc 2, thöôøng laø xöû lyù caùc caëp phaàn töû döõ lieäu (coù theå laø 2 voøng laëp loàng nhau). Tröôøng hôïp naøy chæ coù yù nghóa thöïc teá khi baøi toaùn nhoû. (6) n3 : Moät thuaät toaùn xöû lyù boä ba caùc phaàn töû döõ lieäu (coù theå laø 3 voøng laëp loàng nhau) coù thôøi gian chaïy baäc 3. Tröôøng hôïp naøy chæ coù yù nghóa thöïc teá khi baøi toaùn nhoû. (7) . 2n : Sau ñaây laø caùc giaù trò xaáp xæ cuûa caùc haøm treân : n \ Haøm n lg n Nlgn n2 n3 2n 1 1 0 0 1 1 2 2 2 1 2 4 8 4 4 n 2 8 16 64 16 8 8 3 24 64 512 256 16 16 4 64 256 4096 65536 32 32 5 160 1024 32768 2.147.483.648 Deã thaáy raèng : O(1) ⊂ O(lg n) ⊂ O(n) ⊂ O(nlgn) ⊂ O(n2 ) ⊂ O(n3 ) ⊂ O(2n ). Caùc haøm loaïi : 2n, n!, nn thöôøng ñöôïc goïi laø caùc haøm loaïi muõ. thuaät toaùn vôùi thôøi gian chaïy coù caáp haøm loaïi muõ thì toác ñoä raát chaäm. 3 2 Caùc haøm loaïi : n , n , nLog2 n, n, Log2 n thöôøng ñöôïc goïi laø caùc haøm loaïi ña thöùc. Thuaät toaùn vôùi thôøi gian chaïy coù caáp haøm ña thöùc thöôøng chaáp nhaän ñöôïc. Ghi chuù : Caùc haèng soá bò boû qua trong bieåu thöùc ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùn coù theå coù yù nghóa quan troïng trong öùng duïng cuï theå. Giaû söû thuaät toaùn 1 ñoøi hoûi thôøi 2 gian laø C1n, coøn thuaät toaùn 2 ñoøi hoûi thôøi gian laø C2n . Dó nhieân laø vôùi n ñuû lôùn thì thuaät toaùn 1 nhanh hôn thuaät toaùn 2. Nhöng vôùi n nhoû thì coù theå thuaät toaùn 1 nhanh hôn thuaät toaùn 2. Chaúng haïn, vôùi C1 = 200, C2 = 10, vaø vôùi n = 5, thì thuaät toaùn 1 ñoøi hoûi thôøi gian 1000, trong khi ñoù thuaät toaùn 2 chæ coù 250. Ví duï : Thuaät toaùn Choïn tröïc tieáp (Straight Selection) : SSS Saép xeáp taêng daàn daõy caùc khoùa : x[1],x[2],. . .,x[n]. YÙ töôûng : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 21 - - Böôùc i choïn phaàn töû nhoû nhaát cuûa daõy x[i],x[i+1],. . .,x[n], ñoåi choã phaàn töû nhoû nhaát naøy cho x[i]. - Laëp thao taùc naøy vôùi i = 1 n-1. Thuaät toaùn : 1 for (i =1;i <= n-1;i++) { 2 k = i; Khôûi ñoäng chæ soá cuûa giaù trò nhoû nhaát : (k = = i) 3 a = x[i]; Laáy ra giaù trò cuûa phaàn töû thöù i 4 for (j=i+1;j <= n; j++) Tìm phaàn töû nhoû nhaát trong maûng x[i] x[n] 5 if (x[ j] < a) { 6 a = x[j]; 7 k = j; Giöõ vò trí cuûa phaàn töû nhoû nhaát } a laø giaù trò nhoû nhaát (Khi ñoù : x[k] = = a) 8 x[k] = x[i]; Ñoåi vò trí cuûa phaàn töû nhoû nhaát 9 x[i] = a; Cho phaàn töû a vò trí thöù i. } Ñoä phöùc taïp thuaät toaùn: Leänh (1) thöïc hieän n laàn, (Laàn n ñeå thoaùt khoûi for). Moãi leänh (2), (3), (8), (9) thöïc hieän n-1 laàn. nn()+ 1 Leänh (4) thöïc hieän n + (n-1) + +2 = − 1 laàn. 2 nn()− 1 Leänh (5) thöïc hieän A = (n-1)+(n-2)+ +1 = laàn. // So saùnh 2 • Xeùt tröôøng hôïp xaáu nhaát : Töùc laø leänh (5) luoân thoûa ñieàu kieän, töông öùng daõy coù thöù töï ngöôïc laïi, nn()− 1 Moãi leänh (6), (7) thöïc hieän laàn. 2 Do ñoù : T(n) = n + 4(n-1) + n(n+1)/2 - 1 + 3n(n-1)/2 = 2n2 + 4n - 5 ≤ 6n2 . T(n) ∈ θ (n2 ) • Xeùt tröôøng hôïp toát nhaát Töùc laø leänh (5) luoân khoâng thoûa ñieàu kieän, töông öùng daõy coù thöù töï thuaän, (6) vaø (7) khoâng thöïc hieän laàn naøo. Ta coù : T(n) = n2 + 5n - 5 ∈ θ (n2 ). 4. Phaân tích thuaät toaùn ñeä qui. Phaàn lôùn caùc thuaät toaùn ñeàu döïa treân söï phaân raõ ñeä qui moät baøi toaùn lôùn thaønh caùc baøi toaùn nhoû, roài duøng lôøi giaûi caùc baøi toaùn nhoû ñeå giaûi baøi toaùn ban ñaàu. Thôøi gian chaïy cuûa thuaät toaùn nhö theá ñöôïc xaùc ñònh bôûi kích thöôùc vaø soá löôïng caùc Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 22 - baøi toaùn con vaø giaù phaûi traû cuûa söï phaân raõ. Neân caùc thuaät toaùn ñeä qui coù thôøi gian chaïy phuï thuoäc vaøo thôøi gian chaïy cho caùc döõ lieäu nhaäp coù kích thöôùc nhoû hôn, ñieàu naøy ñöôïc dieãn dòch thaønh moät coâng thöùc toaùn hoïc goïi laø coâng thöùc truy hoài. Do ñoù, ñeå tính ñoä phöùc taïp cuûa thuaät toaùn, ta thöôøng phaûi giaûi caùc phöông trình truy hoài. Coù nhieàu caùch giaûi, ta nghieân cöùu caùc caùch thöôøng duøng sau. A. Phöông phaùp thay theá : Döïa vaøo daïng truy hoài cuûa phöông trình ñeå tính ñoä phöùc taïp cuûa thuaät toaùn döïc vaøo caùc kích thuôùc döõ lieäu nhoû hôn. Moät soá coâng thöùc thöôøng gaëp sau ñaây ñöôïc giaûi baèng phöông phaùp thay theá : Coâng thöùc 1: ⎧TN −1 + N; N ≥ 2 TN = ⎨ ⎩1; N = 1 Coâng thöùc naøy thöôøng duøng cho caùc chöông trình ñeä qui maø coù voøng laëp duyeät qua döõ lieäu nhaäp ñeå boû bôùt 1 phaàn töû . TN = TN-1 + N = TN-2 + (N-1) +N = TN-23+ +(N-2) + (N-1) +N = . . . = 1 + 2 + . . . + N N(N +1) = . 2 Coâng thöùc 2: ⎧T +1; N ≥ 2 ⎪ N 2 TN = ⎨ ⎩⎪0; N = 1 Coâng thöùc naøy thöôøng duøng cho caùc thuaät toaùn ñeä qui maø taïi moãi böôùc chia döõ lieäu nhaäp thaønh 2 phaàn . Giaû söû N = 2n , coù : T = T +1 = T + 2 = L = n. 2n 2n −1 2n − 2 Suy ra : TN = log2 N . Coâng thöùc 3: ⎧T + N; N ≥ 2 ⎪ N 2 TN = ⎨ ⎩⎪0; N = 1 Coâng thöùc naøy thöôøng duøng cho caùc thuaät toaùn ñeä qui maø taïi moãi böôùc thöïc hieän, chia ñoâi döõ lieäu nhaäp nhöng coù kieåm tra moãi phaàn töû cuûa döõ lieäu nhaäp. N N N TN = N + + + L ≅ 2N. 2 4 8 Coâng thöùc 4: ⎧2T +1; N ≥ 2 ⎪ N 2 TN = ⎨ ⎩⎪0; N = 1 Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 23 - Coâng thöùc naøy thöôøng duøng cho caùc thuaät toaùn theo phöông phaùp chia ñeå trò. T = 2T + n 2n 2n−1 2 T T T 2n 2n−1 2n−2 = +1 = +1+1 = L = n 2n 2n −1 2n − 2 ⇒ T = n2n 2n ⇒ TN = NLog2N B. Duøng phöông trình ñaëc tröng ñeå giaûi phöông trình truy hoài : B1) Phöông trình truy hoài tuyeán tính thuaàn nhaát vôùi caùc heä soá khoâng ñoåi : Xeùt phöông trình daïng : a0t n+a1tn−1 +L+ ak tn−k = 0 (1) Trong ñoá caùc ti ,i = n,n −1,L,n − k laø caùc aån soá. n Ñaët tn = X , ta ñöa (1) veà daïng : n−k k k−1 X (a0 X +a1X +L+ ak−1X + ak ) = 0 (2) ⎡X n−k = 0 ⇔ ⎢ k k−1 ⎣⎢a0 X +a1X +L+ ak−1X + ak = 0 X = 0 hieån nhieân laø nghieäm cuûa (2), nhöng ta quan taâm ñeán nghieäm cuûa phöông trình : k k −1 p(X ) = a0 X +a1X + L + ak −1 X + ak = 0 (3) Phöông trình (3) goïi laø phöông trình ñaëc tröng baäc k cuûa phöông trình truy hoài (1) . TH1 : Taát caû caùc nghieäm cuûa (3 ) ñeàu laø nghieäm ñôn. Giaû söû raèng X1, X 2 ,L, X k laø caùc nghieäm ñôn cuûa (3), thì ta coù theå kieåm tra k n ñöôïc tn = ∑ci X i , vôùi c1, c2, , ck laø caùc haèng xaùc ñònh töø k ñieàu kieän ban ñaàu i=1 laø nghieäm cuûa (3). TH2 : Phöông trình (3 ) coù nghieäm boäi. - Giaû söû u laø nghieäm keùp cuûa (3). Vôùi n > k, xeùt ña thöùc p baäc n : n n−1 n−k n−k q(X ) = a0 nX +a1(n −1)X + L + ak (n − k)X = X (X p(X ))' Vì u laø nghieäm keùp cuûa (3), neân toàn taïi ña thöùc r thoûa : p(X ) = (X − u) 2 r(X ) Khi ñoù : q(X ) = X[X n−k (X − u) 2 r(X )]'= 0 n n−1 n−k Do ñoù : a0 nu +a1(n −1)u + L + ak (n − k)u = 0 n Töùc laø : tn = nu cuõng laø nghieäm cuûa (1). Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 24 - - Toång quaùt, neáu u laø nghieäm boäi m cuûa (3) thì : n n 2 n m-1 n tn = u , nu , n u , . . ., n u cuõng laø nghieäm cuûa (1) Khi ñoù toå hôïp tuyeán tính cuûa caùc nghieäm naøy vaø caùc nghieäm khaùc cuûa phöông trình ñaëc tröng (3) seõ laø nghieäm cuûa (1). Ví duï 1 : ⎧T (n) − 6T(n −1) + 8T(n − 2) = 0 ⎪ ⎨T (0) = 1 ⎪ ⎩T (1) = 2 Xeùt phöông trình : T (n) − 6T (n −1) + 8T (n − 2) = 0 Ñaët : Xn = T(n) Ta coù : X n − 6X n−1 + 8X n−2 = 0 Phöông trình ñaëc tröng : X 2 − 6X + 8 = 0 Coù caùc nghieäm : X1 = 2, X2 = 4 n n Vaäy : T(n) = c1X1 + c2 X 2 Do : 0 0 T(0) = 1 ⇒ c1X1 + c2 X 2 = 1 ⇒ c1 + c2 = 1 T(1) = 2 ⇒ c1X1 + c2 X 2 = 2 ⇒ 2c1 + 4c2 = 2 ⎧c1 + c2 = 1 Vaäy coù : ⎨ ⇒ c1 = 1,c2 = 0. ⎩2c1 + 4c2 = 2 Ví duï 2 : ⎧5T(n −1) − 8T(n − 2) + 4T(n − 3);n ≥ 3 ⎪ ⎪0;n = 0 T(n) = ⎨ ⎪1;n = 1 ⎩⎪2;n = 2 Ta coù phöông trình : T (n) − 5T (n −1) + 8T (n − 2) − 4T (n − 3) = 0 Phöông trình ñaëc tröng töông öùng laø : X 3 − 5X 2 + 8X − 4 = 0 ⇔ (X −1)(X − 2) 2 = 0 Vaäy ta coù caùc nghieäm cuûa phöông trình ñaëc tröng : 1 (ñôn), 2 (keùp) n n n Neân nghieäm chung laø : T (n) = c11 + c2 2 + c3n2 Döïa vaøo caùc ñieàu kieän ñaàu, ta coù : ⎧c1 + c2 = 0 ⎪ ⎨c1 + 2c2 + 2c3 = 1 ⎪ ⎩c1 + 4c2 + 8c3 = 2 1 Suy ra : c = −2;c = 2;c = − 1 2 3 2 Vaäy : T(n) = 2n+1 − n2n−1 − 2 Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 25 - B2) Phöông trình truy hoài tuyeán tính khoâng thuaàn nhaát vôùi caùc heä soá khoâng ñoåi : n Phöông trình daïng : a0t n +a1tn−1 +L + ak tn−k = b p(n) Vôùi b laø haèng soá, p laø ña thöùc baäc d theo n. Bieán ñoåi veà daïng thuaàn nhaát. Ví duï : n tn − 2tn−1 = 3 ⎡(2) : t − 2t = 3n+1; Ta coù : n+1 n ⎢ n+1 ⎣⎢(3) : 3tn − 6tn−1 = 3 ; do nhaân 2 veá cuûa (1) cho 3 Laáy (2) – (3), ñöôïc daïng thuaàn nhaát : tn+1 − 5tn + 6tn−1 = 0 5. Caùc pheùp toaùn treân caùc kyù hieäu tieäm caän a) Pheùp toaùn coäng : θ( f(n)) + θ (g(n)) = Max(θ( f(n)) , θ (g(n)) Nhaän xeùt : - θ( f(n)) + θ (g(n)) = θ( f(n) + g(n)) = θ (Max(f(n),g(n)) - Ñaëc bieät , Neáu c laø haèng soá , thì : θ( cf(n)) = θ( f(n)) b) Pheùp toaùn nhaân : θ(f(n))θ (g(n)) = θ(f(n)g(n)) Ñaëc bieät : θ( f(n)2 ) = (θ(f(n))2 c) Pheùp toaùn tích cöïc : Ñoù laø leänh trong thuaät toaùn maø thôøi gian thöïc hieän noù khoâng ít hôn thôøi gian thöïc hieän caùc leänh khaùc. Khi ñaùnh giaù thôøi gian thöïc hieän cuûa thuaät toaùn, ta chæ caàn quan taâm ñeán caùc böôùc thöïc hieän cuûa pheùp toaùn naøy. Ví duï : Saép taêng daàn caùc phaàn töø cuûa daõy soá x. Duøng thuaät toaùn cheøn tröïc tieáp SIS (straight insertion Sort): YÙ töôûng : ÔÛ böôùc i , giaû söû daõy : x[1], , x[i] ñaõ coù thöù töï. Tìm vò trí thích hôïp cuûa phaàn töû x[i+1] ñeå cheøn noù vaøo daõy x[1], , x[i], keát quaû laø ta coù daõy x[1], , x[i+1] coù thöù töï. Thöïc hieän thao taùc treân vôùi i = 1,2,, , n-1. Thuaät toaùn : for (i =1; i<= n-1; i++) { a = x[i+1]; bieán taïm a nhaän giaù trò cuûa x[i+1] x[0] = a; j = i; Chuaån bò cho a tieán veà traùi (khôûi ñoäng j While (a < x[j]) a coøn < x[j], a coøn tieán veà traùi { x[ j+1] = x[ j]; dôøi giaù trò veà phaûi Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 26 - j = j-1; Chuaån bò cho a tieán tieáp veà traùi } a ≥ x[j] x[j+1] = a; Cheøn x[i+1] vaøo vò trí thích hôïp - laø sau x[j]. } Coù theå xem pheùp toaùn tích cöïc ôû ñaây laø : a< x[j]; Trong tröôøng hôïp xaáu nhaát, töông öùng daõy giaûm daàn. Soá laàn thöïc hieän cuûa pheùp toaùn naøy laø : n(n +1) 2 + ⋅ ⋅ ⋅ + n = −1 . 2 Vaäy : T(n) ∈ θ (n2). Trong tröôøng hôïp toát nhaát, töông öùng daõy taêng daàn.Soá laàn thöïc hieän cuûa pheùp toaùn naøy laø : n - 1 Vaäy : T(n) ∈ θ (n). 6. Phaân tích tröôøng hôïp trung bình Ta bieát raèng thôøi gian thöïc hieän thuaät toaùn khoâng phaûi chæ phuï thuoäc vaøo kích thöôùc döõ lieäu maø coøn phuï thuoäc vaøo tình traïng döõ lieäu nhaäp nöõa. Chaúng haïn, khi xeáp taêng daàn moät daõy caùc soá nguyeân, thì caùc soá ñaõ coù saün thöù töï taêng daàn, hoaëc ngöôïc laïi, hoaëc ngaãu nhieân. Phaàn treân ta ñaõ xeùt trong nhöõng khaû naêng toát nhaát hoaëc xaáu nhaát cuûa thuaät toaùn . Baây giôø ta phaân tích trong tröôøng hôïp ngaãu nhieân, töùc laø ñaùnh giaù ñoä phöùc taïp trung bình thôøi gian thöïc hieän thuaät toaùn . Vieäc ñaùnh giaù trung bình thöôøng khoù vaø phöùc taïp ñoøi hoûi nhöõng coâng cuï toaùn hoïc tinh vi, hôn nöõa vieäc tính trung bình coù theå coù nhieàu caùch quan nieäm khaùc nhau.ÔÛ ñaây, vieäc ñaùnh giaù ñoä phöùc taïp thuaät toaùn trong tröôøng hôïp trung bình ta döïa treân cô sôû lyù thuyeát xaùc suaát ( rôøi raïc ) . Ví duï : Xeùt thuaät toaùn cheøn tröïc tieáp . Xeùt böôùc thöù i cuûa voøng laëp. Danh saùch coù i phaàn töû ñaõ ñöôïc saép. Phaàn töû x[i+1] coù theå cheøn vaøo i-1 khe giöõa caùc x[j], j ∈ {1, i} vaø theâm 2 vò trí ñaàu cuoái nöõa (Cheøn tröôùc x[1] vaø cheøn sau x[i] ), toång coäng laø coù i+1 vò trí coù theå cheøn x[i+1]. Giaû söû khaû naêng cuûa moãi vò trí ñöôïc x[i+1] cheøn vaøo laø ñoàng ñeàu. Töùc laø xaùc 1 suaát cuûa moãi vò trí ñöôïc x[i+1] cheøn vaøo laø . i +1 Goïi Xi laø bieán ngaãu nhieân chæ soá löôïng caùc pheùp toaùn so saùnh caàn thieát ñeå x[i+1] cheøn vaøo vò trí thích hôïp cuûa noù trong moãi böôùc. Ta coù : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 27 - X1 X2 Xi i+1 i 3 2 1 Vò trí (Töø phaûi sang traùi) I i 3 2 1 Xi 1 1 1 1 1 p i +1 i +1 i +1 i +1 i +1 1 1 1 1 i E(X ) =1 + 2 + 3 + +i⋅ + i i +1 i +1 i +1 L i +1 i +1 1 = (1+ 2 + + (i −1) + i + i) i +1 L 1 i(i +1) i = ⋅ + i +1 2 i +1 i i = + 2 i +1 Neáu goïi Y laø bieán ngaãu nhieân xaùc ñònh bôûi toång caùc so saùnh trong saép xeáp thì : Y = X1 + X2 + ⋅ ⋅ ⋅ +Xn-1 Ta coù : n−1 n−1 i n−1 i 1 n−1 n−1 1 E(Y) = ∑ E(X i ) = ∑ + ∑ = ∑i + ∑ (1− ) i=1 i=1 2 i=1 i +1 2 i=1 i=1 i +1 1 n(n −1) n 1 = ⋅ + n − 2 2 ∑ i i=1 n 2 3n = + − H 4 4 n n 1 Trong ñoù : H n = ∑ ≤ lgn + 1 ; ( Hn laø soá Harmonic baäc n .) i=1 i Neân giaù trò trung bình cuûa caùc pheùp toaùn so saùnh trong thuaät toaùn töông n2 ñöông vôùi , Vaäy ñoä phöùc taïp trung bình cuûa thuaät toaùn laø θ (n2 ). 4 V. Toái öu thuaät toaùn Tieán trình toång quaùt cuûa vieäc taïo ra caùc söûa ñoåi ngaøy caøng tieán boä hôn cho moät thuaät toaùn ñeå sinh ra moät phieân baûn khaùc chaïy nhanh hôn ñöôïc goïi laø toái öu thuaät toaùn. Khi toái öu moät thuaät toaùn ta thöôøng döïa vaøo moät nguyeân lyù, ñoù laø nguyeân lyù Profile : “ Tìm ñieåm maát thôøi gian nhieàu nhaát cuûa thuaät toaùn “. Moät soá kyõ thuaät sau thöôøng duøng ñeå toái öu thuaät toaùn : 1. Kyõ thuaät toái öu caùc voøng laëp Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 28 - Ñaây laø ñieåm quan taâm ñaàu tieân khi caûi tieán thuaät toaùn, vì voøng laëp laø caâu leänh thöôøng laøm taêng ñoä phöùc taïp cuûa thuaät toaùn. Vieäc caûi tieán taäp trung vaøo : - Coá gaéng giaûm caùc voøng laëp loàng nhau. - Taêng soá leänh thöïc hieän trong moät böôùc laëp ñeå giaûm soá löôïng caùc böôùc laëp. - Taùch caùc leänh khoâng phuï thuoäc vaøo chæ soá laëp ra khoûi voøng laëp. . . . Ví duï 1: Xeùt thuaät toaùn tính giaù trò cuûa ex theo coâng thöùc gaàn ñuùng : xi xx2 n ∑ =+1 x + +LL+ + i≥0 i!!2 n! Thuaät toaùn 1 :{ Tính töøng soá haïng roài coäng laïi.} Input x,n n xi Ouput S = ∑ . i=1 i! Moâ taû : S = 1; for( i = 1; i<= n;i++) { p = 1; for (j:= 1; j <= i ;j++ ) p = p*x/j; S = S + p; } Ta coù theå coi pheùp toaùn tích cöïc ôû ñaây laø pheùp p := p*x/j . nn()+ 1 Ta thaáy noù thöïc hieän ñöôïc : 1+2+. . .+n = laàn. 2 Neân T(n) ∈ θ (n2 ). Thuaät toaùn 2 : Ta xem xeùt voøng laëp trong coù caàn thieát hay khoâng ? xi Nhaän xeùt raèng voøng laëp trong ñöôïc duøng ñeå tính , nhöng moãi soá haïng i! trong toång, soá haïng sau coù theå ñöôïc tính döïa vaøo soá haïng tröôùc : x 2 x x = ⋅ ; 2! 1! 2 L; x n x n−1 x n = ⋅ n! (n −1)! n xi Neân voøng laëp trong coù theå boû ñi vì coù theå tính theo coâng thöùc treân. Vaäy i! thuaät toaùn coù theå vieát laïi nhö sau : S = 1; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 29 - p = 1; for( i = 1; i<= n;i++) { xi p = p*x/i; // i! S = S + p; } Chaúng haïn coù theå coi pheùp toaùn tích cöïc ôû ñaây laø pheùp p := p*x/i . Do ñoù : T(n) ∈ θ (n). Ví duï 2 : Ta xeùt thuaät toaùn nhaân 2 ma traän vuoâng caáp n. TT1 : Input a,b ∈ MatN (n) Output c∈ MatN (n) Nhan1(a,b,c) ≡ for(i =1; i<=n; i++) for(j = 1; j <= n; j++) { c[i][j] = 0; for (k = 1; k <= n; k++) c[i][j] += a[i][k]*b[k][j]; } Theo TT1, moãi laàn ta chæ tính 1 phaàn töû c[i][j] trong voøng laëp theo k. Giôø ta caûi tieán, trong tröôøng hôïp n chaün, tính moät laàn 4 giaù trò : c[i][j] c[i][j+1] c[i][j] c[i][jj] c[i+1][j] c[i+1][j+1] c[ii][j] c[ii][jj] TT2 : Nhan2(a,b,c) ≡ i = 1; while (i < n) { ii = i+1; j = 1; while ( j < n ) { jj = j+1; c[i][j] = 0; c[i][jj] = 0; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 30 - c[ii][j] = 0; c[ii][jj] = 0; k = 1; while (k < n) { kk = k+1; c[i][j] = c[i][j] + a[i][k]*b[k][j] + a[i][kk]*b[kk][j]; c[i][jj] = c[i][jj]+a[i][k]*b[k][jj] + a[i][kk]*b[kk][jj]; c[ii][j] = c[ii][j]+a[ii][k]*b[k][j] + a[ii][kk]*b[kk][j]; c[ii][jj] = c[ii][jj]+a[ii][k]*b[k][jj] + a[ii][kk]*b[kk][jj]; k = k+2; } j = j + 2; } i = i + 2; } } Giaû thieát n chaün vì ta duøng böôùc nhaûy 2 2. Toái öu vieäc reõ nhaùnh - Ñoái vôùi bieåu thöùc logic keát hôïp baèng pheùp toaùn &&, neân vieát theo thöù töï xaùc suaát sai giaûm daàn : A1 && A2 && && An Xaùc suaát sai cuûa caùc Ai giaûm daàn . - Ñoái vôùi bieåu thöùc logic keát hôïp baèng pheùp toaùn ||, neân vieát theo thöù töï xaùc suaát ñuùng giaûm daàn : A1 || A2 || || An Xaùc suaát ñuùng cuûa caùc Ai giaûm daàn : . . . BAØI TAÄP Baøi 1 : Xaùc ñònh ñoä phöùc taïp cuûa caùc thuaät toaùn sau : r = m%n; gt (n) ≡ while(r) if (n == 0 || n == 1) { return 1; m = n; else n = r; return (n * gt(n-1)) ; r = m%n; } return n Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 31 - Fib(n) ≡ Fibo(n) ≡ if ( n Max) } { Max = a[j]; csmax = j; } } Baøi 3 : Tính thôøi gian thöïc hieän trung bình cuûa caùc pheùp toaùn so saùnh trong caùc thuaät toaùn : 1. Ñoåi choã tröïc tieáp. 2. Choïn tröïc tieáp. Baøi 4 : Xaùc ñònh T(n) , vôùi : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 32 - ⎧T(n) − 3T(n −1)48T (n − 2) = 0,n > 1 ⎪ 1. ⎨T(0) = 1 ⎪ ⎩T(1) = 2 ⎧ n ⎪T (n) = n + 4T ( ),n > 1 2. ⎨ 2 ⎩⎪T (1) = 1 ⎧T (n) = T(n −1) + T(n − 2),n > 1 ⎪ 3. ⎨T (0) = 1 ⎪ ⎩T (1) = 1 ⎧T (n) = 2T (n −1) +1;n > 1 ⎪ 4. ⎨T (0) = 0 ⎪ ⎩T (1) = 1 Baøi 5 : Caûi tieán thuaät toaùn cheøn tröïc tieáp baèng caùch : Duøng phöông phaùp tìm kieám nhò phaân ñeå xaùc ñònh vò trí caàn cheøn cuûa ai trong daõy con ñaõ coù thöù töï a1, , ai-1 . Thuaät toaùn caûi tieán goïi laø cheøn nhò phaân. Haõy thieát keá, caøi ñaët vaø ñaùnh giaù ñoä phöùc taïp thôøi gian cuûa thuaät toaùn. Baøi 6 : Tìm caùc ví duï veà caùc thuaät toaùn maø khi caûi tieán ( baèng caùch naøo ñoù ), soá laàn thöïc hieän cuûa thuaät toaùn giaûm ñaùng keå ( veà ñoä phöùc taïp tieäm caän, hoaëc veà tæ leä ) Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 33 - CHÖÔNG 2 : PHÖÔNG PHAÙP CHIA ÑEÅ TRÒ (Divide - and - conquer) I. Môû ñaàu 1. YÙ töôûng Coù leõ quan troïng vaø aùp duïng roäng raõi nhaát laø kyõ thuaät thieát keá “Chia ñeå trò” . Noù phaân raõ baøi toaùn kích thöôùc n thaønh caùc baøi toaùn con nhoû hôn maø vieäc tìm lôøi giaûi cuûa chuùng laø cuøng moät caùch. Lôøi giaûi cuûa baøi toaùn ñaõ cho ñöôïc xaây döïng töø lôøi giaûi cuûa caùc baøi toaùn con naøy . Ta coù theå noùi vaén taét yù töôûng chính cuûa phöông phaùp naøy laø : chia döõ lieäu thaønh töøng mieàn ñuû nhoû, giaûi baøi toaùn treân caùc mieàn ñaõ chia roài toång hôïp keát quaû laïi. 2. Moâ hình Neáu goïi D&C(ℜ) - Vôùi ℜ laø mieàn döõ lieäu - laø haøm theå hieän caùch giaûi baøi toaùn theo phöông phaùp chia ñeå trò thì ta coù theå vieát : void D&C(ℜ) { If (ℜ ñuû nhoû) giaûi baøi toaùn; Else { Chia ℜ thaønh ℜ1 , ,ℜm ; for (i = 1; i <=m; i++) D&C(ℜi); Toång hôïp keát quaû; } } Sau ñaây laø caùc minh hoïa kyõ thuaät thieát keá “ Chia ñeå trò “ . II. Thuaät toaùn tìm kieám nhò phaân. 1. Phaùt bieåu baøi toaùn Cho maûng n phaàn töû ñaõ ñöôïc saép taêng daàn vaø moät phaàn töû x. Tìm x coù trong maûng hay khoâng ? Neáu coù x trong maûng thì cho keát quaû laø 1, ngöôïc laïi cho keát quaû 0. Giaûi baèng thuaät toaùn tìm kieám nhò phaân . 2. YÙ töôûng Chia ñoâi maûng , moãi laàn so saùnh phaàn töû giöõa vôùi x, neáu phaàn töû x nhoû hôn thì laáy nöûa traùi, ngöôïc laïi thì laáy nöûa phaûi. 3. Moâ taû thuaät toaùn Input : a[1 n] Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 34 - ⎧1; x ∈ a Output : ⎨ ⎩0; x ∉ a Moâ taû : Tknp(a, x, Ñaàu, Cuoái) ≡ If (Ñaàu > Cuoái) return 0 ; {daõy troáng} Else { Giöõa = (Ñaàu + cuoái) / 2; If (x == a[Giöõa]) return 1; else if (x > a[Giöõa]) Tknp(a, x, Giöõa + 1, Cuoái) ; else Tknp(a, x, Ñaàu, Giöõa - 1) ; } 4. Ñoä phöùc taïp thôøi gian cuûa thuaät toaùn a) Tröôøng hôïp toát nhaát : töông öùng vôùi söï tìm ñöôïc x trong laàn so saùnh ñaàu tieân, töùc laø : a[Giöõa] == a[n/2] == x ( x naèm ôû vò trí giöõa maûng ). Ta coù : Ttoát (n) = O(1). b) Tröôøng hôïp xaáu nhaát : Ñoä phöùc taïp laø O(lg n). Thaät vaäy, Neáu goïi T(n) laø ñoä phöùc taïp cuûa thuaät toaùn , thì sau khi kieåm tra ñieàu kieän ( x == a[giöõa]) vaø sai thì goïi ñeä qui thuaät toaùn naøy vôùi döõ lieäu giaûm nöûa, neân thoûa maõn coâng thöùc truy hoài : T(n) = 1 + T[n/2] ; n ≥ 2 vaø T[1] = 0. 5. Caøi ñaët int tknp(int a[max],int x,int l, int r) { int mid; if ( l > r ) return 0; mid = (l+r)/2; if ( x == a[mid] ) return 1; if ( x > a[mid] ) return tknp(a,x,mid+1,r); return tknp(a,x,l,mid-1); } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 35 - III. Baøi toaùn MinMax 1. Phaùt bieåu baøi toaùn Tìm giaù trò Min, Max trong ñoaïn a[l r] cuûa maûng a[1 n]. 2. YÙ töôûng Taïi moãi böôùc, chia ñoâi ñoaïn caàn tìm roài tìm Min, Max cuûa töøng ñoaïn, sau ñoù toång hôïp laïi keát quaû. Neáu ñoaïn chia chæ coù 1 phaàn töû thì Min = Max vaø baèng phaàn töû ñoù. Minh hoïa : i 1 2 3 4 5 6 7 8 a[i] 10 1 5 0 9 3 15 19 Tìm giaù trò Min, Max trong ñoaïn a[2 7] cuûa maûng a[1 7] . Kyù hieäu : MinMax(a,l,r,Min,Max) cho Min vaø Max trong ñoaïn a[l r]. MinMax(a,2,7,Min,Max) Cho Min = 0 vaø Max = 15 trong ñoaïn a[2 7] 3. Thuaät toaùn Input : a[l r], ( l ≤ r ) Output : Min = Min (a[l], ,a[r]), Max = Max (a[l], ,a[r]). Moâ taû : MinMax(a,l, r, Min, Max) ≡ if (l == r) { Min = a[l]; Max = a[l]; } Else { MinMax(a,l, (l+r) / 2, Min1, Max1); MinMax(a,(l+r) /2 + 1, r , Min2, Max2); If (Min1 Max2) Max = Max1 Else Max = Max2; } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 36 - 4. Ñoä phöùc taïp thuaät toaùn Goïi T(n) laø soá pheùp toaùn so saùnh caàn thöïc hieän. Khi ñoù ta coù : ⎧T (n 2) + T(n 2) + 2 ; n > 2 ⎪ T(n) = ⎨1 ; n = 2 ⎪ ⎩0 ; n = 1 Vôùi n = 2k , thì : k −1 2 2 2 k −1 i T (n) = 2 + 2T (n / 2) = 2 + 2 + 2 T (n / 2 ) = L = 2 T (2) + ∑ 2 i=1 k 3n = ∑ 2i − 2k −1 = 2k +1 − 2k −1 − 2 = − 2 . i=1 2 Vaäy T(n) ∈ O(n). 5. Caøi ñaët void MinMax(int a[.], int l, int r, int &Min, int &Max ) { int Min1,Min2,Max1,Max2; if (l == r ) { Min = a[l]; Max= a[l]; } else { MinMax(a,l,(l+r)/2 , Min1, Max1); MinMax(a,(l+r) /2 + 1,r, Min2, Max2); if (Min1 Max2) Max = Max1; else Max = Max2; } } IV. Thuaät toaùn QuickSort Duøng thuaät toaùn QuickSort (QS) ñeå saép xeáp caùc giaù trò trong moät maûng caùc soá theo moät thöù töï, chaúng haïn taêng daàn. Phöông phaùp QuickSort (hay coøn goïi laø phaân ñoaïn) laø moät caûi tieán cuûa phöông phaùp saép xeáp ñoåi choã tröïc tieáp, do C.A.R. Hoare ñeà xuaát. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 37 - 1. YÙ töôûng Choïn ngaãu nhieân moät phaàn töû x. Duyeät daõy töø beân traùi ( theo chæ soá i ) trong khi coøn ai x. Ñoåi choã ai vaø aj neáu hai phía chöa vöôït qua nhau. . . . tieáp tuïc quùa trình duyeät vaø ñoåi choã nhö treân trong khi hai phía coøn chöa vöôït qua nhau ( töùc laø coøn coù i ≤ j). • Keát quûa phaân hoaïch daõy thaønh 3 phaàn : ak ≤ x vôùi k = 1, ,j (Daõy con thaáp); am ≥ x vôùi m = i, ,n (Daõy con cao); ah = x vôùi h = j+1, ,i - 1. (Vì theá phöông phaùp naøy coøn goïi laø saép xeáp baèng phaân hoaïch). ak am x Tieáp tuïc phaân hoaïch cho phaàn traùi (daõy con thaáp nhoû hôn x), cho phaàn phaûi ( lôùn hôn x) . . . cho ñeán khi caùc phaân hoaïch chæ coøn laïi moät phaàn töû, laø saép xeáp xong. Thuaät toaùn theå hieän yù töôûng ñeä qui vaø caùch thieát keá chia ñeå trò. 2. Moâ taû thuaät toaùn - Thuaät toaùn QuickSort Input : a[1 n] Output : a[1 n] khoâng giaûm. Moâ taû thuaät toaùn : QuickSort (a,n) ≡ QS(a,1,n) ; - Thuaät toaùn phaân hoaïch Input : a[1 n],l,r; Output : a[l r] taêng daàn Moâ taû : QS(a,l,r) ≡ i = l; j = r; x = a[(l+r)/2]; // Choïn phaàn töû giöõa do { while (a[i] x) j ; if (i <= j) { ñoåichoã a[i] vaø a[j]; i++; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 38 - j ; } } while (i i ) QS(a,i,r); 3. Ñoä phöùc taïp cuûa thuaät toaùn • Ñieàu toát nhaát coù theå xaûy ra trong QuickSort laø moãi giai ñoaïn phaân hoaïch phaân chia maûng thaønh 2 nöûa. Ñieàu naøy khieán cho soá laàn so saùnh caàn thieát cuûa QuickSort thoûa maõn coâng thuùc truy hoài “chia ñeå trò “ sau ñaây : Tn = 2Tn + n ≅ nLg n. 2 2Tn : Phí toån saép xeáp 2 maûng con. 2 n : Phí toån kieåm tra moãi phaàn töû. • Tröôøng hôïp xaáu nhaát öùng cho vieäc choïn phaàn töû x laïi coù giaù trò lôùn nhaát hoaëc nhoû nhaát trong daõy. Giaû söû phaàn töû lôùn nhaát ñöôïc choïn ( phaàn töû x ), khi ñoù moãi böôùc chia seõ chia n phaàn töû thaønh n-1 phaàn töû traùi vaø 1 phaàn töû phaûi. Keát quaû laø caàn tôùi n pheùp chia ( thay cho lgn), vaø nhö theá ñoä phöùc taïp seõ laø T(n) = O(n2 ). Trong tröôøng hôïp daõy nhaäp vaøo ñaõ coù thöù töï (thuaän hay ngöôïc), phaàn töû lôùn nhaát ñöôïc choïn seõ naèm ôû caùc bieân ( phaûi hoaëc traùi), cho neân thuaät toaùn QuickSort khoâng coù hieäu quaû. • Trong tröôøng hôïp trung bình : Coâng thöùc truy hoài ñeå tính soá laàn so saùnh maø QuickSort caàn ñeå hoaùn vò ngaãu nhieân n phaàn töû laø : 1 Tn = (n +1) + ∑(Tk −1 +Tn−k ) ; Vôùi n ≥ 2; C0 = C1 = 1. n 1≤k ≤n Giaù trò n+1 bao haøm chi phí so saùnh phaàn töû phaân hoaïch vôùi moãi phaàn töû coøn laïi, toång coøn laïi mang yù nghóa laø moãi phaàn töû k coù theå laø phaàn töû phaân hoaïch 1 vôùi xaùc suaát vaø sau ñoù coøn laïi caùc maûng con coù kích thöôùc k-1 vaø n-k. k 2 n Tn = n +1+ ∑Tk −1 n k =1 Thöïc hieän lieân tieáp caùc pheùp toaùn sau cho caû 2 veá : Nhaân cho n vaø tröø cho (n-1)Cn-1 : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 39 - 2 n nTn − (n −1)Tn−1 = n(n +1) + n ∑Tk −1 − (n −1)Tn−1 n k =1 n 2 n−1 = n(n +1) + 2∑Tk −1 − (n −1)[n + ∑Tk −1] k =1 n −1 k =1 n n−1 = n(n +1) − n(n −1) + 2∑Tk −1 − 2∑Tk −1 k =1 k =1 Ta ñöôïc : nTn − (n −1)Tn−1 = n(n + 1) − n(n −1) + 2Tn−1 Suy ra : nTn = (n +1)Tn−1 + 2n Chia caû 2 veá cho n(n+1) : T T 2 T 2 2 2 2 2 2 T n = n−1 + = n−2 + + = + + + + 1 n + 1 n n + 1 n −1 n n + 1 n + 1 n L 4 3 2 1 n 2 1 n+1 1 = + ∑ = + 2∑ 2 k =2 k + 1 2 k =3k n T n 1 1 n ≅ 2 ≅ 2 dx = 2ln(n) n + 1 ∑ k ∫ x k =3 1 Nhö vaäy, Ñoä phöùc taïp trung bình laø O(nlnn) V. Thuaät toaùn nhaân Strassen nhaân 2 ma traän 1. Baøi toaùn Cho 2 ma traän vuoâng a, b caáp n, n laø luyõ thöøa 2. Duøng thuaät toaùn Strassen nhaân 2 ma traän vuoâng caáp n. 2. Moâ taû ÖÙng duïng thieát keá chia ñeå trò, moãi ma traän A, B, C ta chia thaønh 4 ma traän con vaø bieåu dieãn tích 2 ma traän AxB = C theo caùc ma traän con ñoù : ⎡C11 C12 ⎤ ⎡A11 A12 ⎤ ⎡B11 B12 ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢C21 C22 ⎦⎥ ⎣⎢A21 A22 ⎦⎥ ⎣⎢B21 B22 ⎦⎥ Trong ñoù : C11 = A11B11 + A12B21 C12 = A11B12 + A12B22 C21 = A21B11 + A22B21 C22 = A21B12 + A22B22 Neáu theo caùch nhaân thoâng thöôøng, thì caùch chia ñeû trò naøy daãn ñeán coâng thöc truy hoài : T(n) = 8T(n/2) + θ(n2 ). Ñaùng tieác laø keát quaû naøy cho lôøi giaûi T(n) ∈ θ(n3 ). Nhöng theo khaùm phaù cuûa Strasen, chæ caàn 7 pheùp nhaân ñeä qui n/2 x n/2 ma traän vaø θ(n2 ) pheùp coäng tröø voâ höôùng theo coâng thöùc truy hoài : T(n) = 7T(n/2) + 18(n/2)2 ∈ O(nlg7) = O(n2.81). Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 40 - Cuï theå, ñeå nhaân 2 ma traän vuoâng caáp 2 , theo Strassen chæ caàn 7 pheùp nhaân vaø 18 pheùp coäng (tröø) caùc soâ. Ñeå tính : ⎡c11 c12 ⎤ ⎡a11 a12 ⎤ ⎡b11 b12 ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢c21 c22 ⎦⎥ ⎣⎢a21 a22 ⎦⎥ ⎣⎢b21 b22 ⎦⎥ - Ñaàu tieân tính 7 tích : m1 = (a12 - a22 ) (b21 + b22 ) m2 = (a11 + a22 ) (b11 + b22 ) m3 = (a11 - a21 ) (b11 + b12 ) m4 = (a11 + a12 ) b22 m5 = a11 (b12 – b22 ) m6 = a22 (b21 – b11 ) m7 = (a21 + a22 ) b11 - sau ñoù tính cij theo coâng thöùc : c11 = m1 + m2 – m4 + m6 c12 = m4 + m5 c21 = m6 + m7 c22 = m2 – m3 + m5 – m7 Thuaät toaùn coù theå vieát nhö sau : strass(a, b, c, n)≡ if ( n == 2 ) nhan2(a,b,c); else { tach(a,a11,a12,a21,a22,n); tach(b,b11,b12,b21,b22,n); tach(c,c11,c12,c21,c22,n); strass(a11,b11,d1,n/2); strass(a12,b21,d2,n/2); cong(d1,d2,c11,n/2); strass(a11,b12,d1,n/2); strass(a12,b22,d2,n/2); cong(d1,d2,c12,n/2); strass(a21,b11,d1,n/2); strass(a22,b21,d2,n/2); cong(d1,d2,c21,n/2); strass(a21,b12,d1,n/2); Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 41 - strass(a22,b22,d2,n/2); cong(d1,d2,c22,n/2); Hop(c11,c12,c21,c22,c,n); } VI. Baøi toaùn hoaùn ñoåi 2 phaàn trong 1 daõy 1. Phaùt bieåu baøi toaùn a[1 n] laø moät maûng goàm n phaàn töû. Ta caàn chuyeån m phaàn töû ñaàu tieân cuûa maûng vôùi phaàn coøn laïi cuûa maûng ( n-m phaân töû) maø khoâng duøng moät maûng phuï . Chaúng haïn, vôùi n = 8, a[8] = (1, 2, 3, 4, 5, 6, 7, 8) Neáu m = 3, thì keát quaû laø : ( 4, 5, 6, 7, 8, 1, 2, 3) Neáu m = 5, thì keát quaû laø : ( 6, 7, 8, 1, 2, 3, 4, 5) Neáu m = 4, thì keát quaû laø : ( 5, 6, 7, 8, 1, 2, 3, 4) 2. YÙ töôûng * Neáu m = n – m: Hoaùn ñoåi caùc phaàn töû cuûa 2 nöûa maûng coù ñoä daøi baèng nhau : * Neáu m ≠ n – m : - Neáu m = n – m : - Neáu m n – m : hoaùn ñoåi n-m phaàn töû ñaàu tieân vôùi n-m phaàn töû cuûa phaàn sau. Sau ñoù trong maûng a[n-m+1 . . n] ta hoaùn ñoåi n-m phaàn töû cuoái maûng vôùi caùc phaàn töû cuûa phaàn ñaàu. Nhö vaäy, baèng caùch aùp duïng phöông phaùp chia ñeå trò, ta chia baøi toaùn thaønh 2 baøi toaùn con : - Baøi toaùn thöù nhaát laø hoaùn ñoåi hai maûng con coù ñoä daøi baèng nhau, cuï theå laø hoaùn ñoåi nöûa soá phaàn töû ñaàu vaø cuoái cuûa maûng cho nhau baèng caùch ñoåi choã töøng caëp phaàn töû töông öùng. - Baøi toaùn thöù hai cuøng daïng vôùi baøi toaùn ñaõ cho nhöng kích thöôùc nhoû hôn, neân coù theå goïi thuaät toaùn ñeä qui ñeå giaûi vaø quaù trình goïi ñeä qui seõ döøng khi ñaït tôùi söï hoaùn ñoåi 2 phaàn coù ñoä daøi baèng nhau Vaäy maáu choát cuûa thuaät toaùn laø thöïc hieän thao taùc hoaùn ñoåi 2 nhoùm phaàn töû, laëp laïi thao taùc naøy trong khi soá löôïng phaàn töû cuûa 2 nhoùm cong khaùc nhau. Neân ta seõ thay thuaät toaùn ñeä qui baèng thuaät toaùn laëp. 3. Thuaät toaùn // Hoaùn ñoåi m phaàn töû ñaàu cuûa maûng vôùi phaàn coøn laïi. Input : a[1 n], m. (m ≤n) Output : a[1 n] vôùi tính chaát m phaàn töû ñaàu maûng a ( maûng nhaäp ) naèm cuoái maûng Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 42 - keát quaû, n-m phaàn töû cuoái maûng nhaäp naèm ôû ñaàu maûng keát quaû. Moâ taû thuaät toaùn : Transpose(a,n,m) ≡ i = m; j = n-m; m = m+1; Khi ( i ≠ j) Neáu ( i > j) { Exchange(a,m-i,m,j); i = i – j; } Ngöôïc laïi { j = j – i; Exchange(a,m-i,m+j,i); } Exchange(a,m-i,m,i); * Thuaät toaùn exchange : input a, i,j, //vò trí m; // Soá phaàn töû caàn hoaùn ñoåi output a Moâ taû : Exchange(a,i,j,m) ≡ Vôùi moïi p = 0 → m-1 Ñoåichoã (a[i+p], a[j+p]); Minh hoïa : n = 8, a[8] = ( 1, 2, 3, 4, 5, 6, 7, 8) , m = 3. - Maûng nhaäp : 1 2 3 4 5 6 7 8 Hoaùn ñoåi - Exchange(a,1,6,3) 6 7 8 4 5 1 2 3 Hoaùn ñoåi Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 43 - - Exchange(a,1,4,2) 4 5 8 6 7 1 2 3 Hoaùn ñoåi - Exchange(a,3,5,1) 4 5 7 6 8 1 2 3 Hoaùn ñoåi - Exchange(a,3,4,1) 4 5 6 7 8 1 2 3 - Keát thuùc thuaät toaùn. 4. Ñoä phöùc taïp thuaät toaùn Kí hieäu : T(i, j) laø soá phaàn töû caàn ñoåi choã ñeå hoaùn ñoåi daõy i phaàn töû vaø daõy j phaàn töû, ta coù coâng thöùc truy hoài sau : ⎧i; neáu i = j ⎪ T(i, j) = ⎨ j + T (i − j, j); neáu i > j ⎪ ⎩i + T(i, j − i); neáu i j) { Exchange(a,m-i,m,j); i = i - j; } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 44 - else { j = j - i; Exchange(a,m-i,m+j,i); } Exchange(a,m-i,m,i); } // void Exchange(day a, int i, int j, int m) { for (int k = 0; k <= m-1; k++) doicho(a[i+k], a[j+k]); } VII. Troän hai ñöôøng tröïc tieáp 1. Baøi toaùn Saép taêng daàn daõy caùc soá baèng thuaät toaùn troän hai ñöôøng tröïc tieáp. 2. YÙ töôûng Thuaät toaùn saép xeáp kieåu troän hai ñöôøng tröïc tieáp ñöôïc thöïc hieän theo nhieàu böôùc laëp : * Moãi böôùc laëp bao goàm hai giai ñoaïn : Giai ñoaïn 1 :( Phaân boá) Phaân boá luaân phieân töøng p phaàn töû töø daõy F vaøo caùc daõy trung gian F1, F2 trong khi chöa heát daõy F. Giai ñoaïn 2 :( Troän ) Troän töøng boä p phaàn töû trong daõy F1 vôùi p phaàn töû trong F2, keát quaû troän ñöôïc ñöa vaøo F, trong khi chöa heát daõy F1 vaø chöa heát daõy F2. * Caùc böôùc laëp coøn ñöôïc thöïc hieän trong khi p coøn ≤ soá caùc phaàn töû cuûa F . Böôùc ñaàu tieân p ñöôïc khôûi ñoäng baèng 1. Moãi böôùc laëp sau( sau moät laàn phaân boá vaø troän ), soá phaàn töû p seõ khôûi ñoäng laïi laø : p = p * 2 . Minh hoïa : Giaû söû F laø daõy duøng saép thöù töï , F coù noäi dung nhö sau : F 9 2 1 1 5 8 1 2 9 6 7 4 6 7 2 2 3 1 1 0 1 Ñaàu tieân ta phaân boá luaân phieân töøng phaàn töû cuûa daõy nguoàn F vaøo caùc daõy trung gian F1 , F2. • Trong laàn phaân boá ñaàu tieân ,ta coù : F1 90 1 5 1 9 7 6 21 3 1 F2 2 1 8 2 6 4 7 2 1 Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 45 - Ta thöïc hieän troän hai ñöôøng töøng phaàn töû ôû F1 vôùi töøng phaàn töû ôûû F2; Keát quaû troän ñöôïc ghi vaøo F. F 2-90 1-1 5-8 1-2 6-9 4-7 6-7 2-21 1-3 1 • Sang laàn thöù 2: F1 2-90 5-8 6-9 6-7 1-3 F2 1-1 1-2 4-7 2-21 1 F 1-1 –2-90 1-2-5-8 4-6-7-9 2-6-7-21 1-1-3 • Sang laàn thöù 3 : F1 1-1 –2-90 4-6-7-9 1-1-3 F2 1-2-5-8 2-6-7-21 F 1-1-1-2-2-5-8-90 2-4-6-6-7-7-9-21 1-1-3 • Sang laàn thöù 4 : F1 1-1-1-2-2-5-8-90 1-1-3 F2 2-4-6-6-7-7-9-21 F 1-1-1-2-2-2-4-5-6-6-7-7-8-9-21-90 1-1-3 • Sang laàn thöù 5 : F1 1-1-1-2-2-2-4-5-6-6-7-7-8-9-21-90 F2 1-1-3 F 1-1-1-1-1-2-2-2-3-4-5-6-6-7-7-8-9-21-90 Khi ñoù F ñöôïc saép thöù töï . 3. Thieát keá * Thuaät toaùn troän 2 ñöôøng tröïc tieáp : input F[1 n]; // daõy caàn saép Output F ñaõ ñöôïc saép Moâ taû: p = 1; Trong khi (p <= n) ta thöïc hieän : { - Phaân boá luaân phieân töøng p phaàn töû töø daõy F vaøo caùc daõy trung gian F1, F2 trong khi chöa heát daõy F. -Troän töøng caëp p phaàn töû trong daõy F1 vôùi p phaàn töû trong daõy F2, keát quaû ghi vaøo F, trong khi chöa heát daõy F1 vaø chöa heát daõy F2; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 46 - - Khôûi ñoäng laïi p : p = p*2; } Moâ taû treân coù theå vieát thaønh haøm : //F,n,F1,F2 laø caùc bieán toaøn cuïc void mergesort () { p = 1; while ( p <= n ) { distribution (p); merge(p); p = p * 2; } } Nhö vaäy, thuaät toaùn chuû yeáu ñöôïc xaây döïng treân 2 thao taùc : - distribution (p) : Phaân boá luaân phieân p phaàn töû töø daõy F vaøo caùc daõy trung gian F1, F2 trong khi chöa heát daõy F. - merge(p) : Troän töøng caëp p phaàn töû trong F1, vaø p phaàn töû trong F2, keát quaû löu tröû vaøo F, trong khi chöa heát daõy F1 vaø chöa heát daõy F2; a) Thuaät toaùn phaân boá Phaân boá luaân phieân p phaàn töû töø daõy F vaøo caùc daõy trung gian F1, F2 cho ñeán heát daõy F. a1) Thieát keá : Input F; Output F1,F2; Moâ taû Thöïc hieän { Ñoïc töøng p phaàn töû trong F vaø cheùp luaân phieân vaøo F1, F2; } Trong khi ( chöa heát daõy F); Trong moâ taû treân, coù 2 thao taùc con caàn phaûi löu yù : Thao taùc 1 : Laøm theá naøo ñeå xöû lyù moät caùch töï ñoäng vieäc cheùp luaân phieân vaøo F1 vaø F2. Ta thöïc hieän baèng caùch : Duøng moät khoaù k, vôùi k ∈ {1,2} vaø quy ñònh : Neáu k = 1 thì cheùp vaøo F1; Neáu k = 2 thì cheùp vaøo F2; Giaû söû ñaàu tieân cho k = 1 ñeå quyeát ñònh cheùp p phaàn töû cuûa F vaøo F1 tröôùc. Sau moãi laàn cheùp xong p phaàn töû, ta chæ caàn khôûi ñoäng laïi giaù trò k = 3-k . Thao taùc 2 : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 47 - Ñoïc p phaàn töû cuûa F cheùp vaøo F1 nhö theá naøo ? Ta ñoïc töøng phaàn töû cuûa F vaø cheùp phaàn töû ñoù vaøo F1; Vieäc ñoïc cheùp töøng phaàn töû naøy coøn ñöôïc thöïc hieän trong khi chöa ñuû p phaàn töû vaø chöa heát daõy F. Vaäy thao taùc phaân boá coù theå moâ taû chi tieát nhö sau : do { i = 1; while ( i <= p && chöa heát daõy F ) { Ñoïc phaàn töû thöù i trong F; if ( k == 1) cheùp vaøo F1; else cheùp vaøo F2; i++; } k = 3-k; } while ( chöa heát daõy F); Thao taùc phaân boá caøi ñaët thaønh moät haøm nhö sau : //F, F1, F2, n, h1,h2 laø caùc bieán toaøn cuïc. void distribute(int p) { int i, k=1, l = 1; h1 = 0; h2 = 0; do { i = 1; while( i<=p && l <= n) { if(k==1) { h1++; F1[h1] = F[l]; } else { h2++; F2[h2] = F[l]; } i++; l++; } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 48 - k = 3-k; } while(l <= n); } b) Thuaät toaùn troän töøng boä p phaàn töû trong F1 vaø p phaàn töû trong F2. Troän töøng boä p phaàn töû trong F1, vaø p phaàn töû trong F2, keát quaû löu tröû vaøo F, trong khi chöa heát F1 vaø F2. a1) Thieát keá : Input F1, F2; Output F; Moâ taû : Trong khi ( chöa heát daõy F1 vaø chöa heát daõy F2 ) { Troän töøng caëp p phaàn töû cuûa F1 vaø cuûa F2 vaøo F; } Trong khi (chöa heát daõy F1) cheùp caùc phaàn töû coøn laïi cuûa F1 vaøo F; Trong khi (chöa heát daõy F2) cheùp caùc phaàn töû coøn laïi cuûa F2 vaøo F; - Ta caàn chæ roõ coâng vieäc troän töøng caëp p phaàn töû cuûa F1 vaø cuûa F2 vaøo F hoaït ñoäng nhö theá naøo ? Ñoù laø : - (*) : Ñoïc töøng phaàn töû trong F1, trong F2, so saùnh giaù trò cuûa chuùng, giaù trò naøo nhoû hôn thì cheùp phaàn töû töông öùng vaøo F. Neáu laø phaàn töû cuûa F1 thì ñoïc tieáp 1 phaàn töû cuûa F1; ngöôïc laïi thì ñoïc tieáp 1 phaàn töû cuûa F2 - ( ) :Thao taùc treân coøn ñöôïc thöïc hieän trong khi : chöa ñoïc ñuû p phaàn töû trong F1 vaø chöa ñoïc ñuû p phaàn töû trong F2 vaø chöa heát daõy F1 vaø chöa heát daõy F2; - Voøng laëp ( ) döøng khi ñaõ ñoïc ñuû p phaàn töû trong F1, hoaëc ñaõ ñoïc ñuû p phaàn töû trong F2, hoaëc heát daõy F1 hoaëc heát daõy F2; Vaø khi ñoù ta caàn xöû lyù caùc tröôøng hôïp sau : Trong tröôøng hôïp chöa heát daõy F1 vaø chöa heát daõy F2 : Neáu chöa ñuû p phaàn töû trong F1, thì ñoïc vaø cheùp caùc phaàn töû cuûa F1 vaøo F cho ñuû p; Töông töï nhö vaäy cho F2. a2) Caøi ñaët : /* F,F1,F2,n,h1,h2 laø caùc bieán toaøn cuïc. Ta duøng caùc bieán : - r1 : ñeám caùc phaàn töû ñoïc ñöôïc trong daõy F1. - r2 : ñeám caùc phaàn tö ñoïc ñöôïc trong daõy F2 . - i1 : duyeät daõy F1 - i2 = 1 duyeät daõy F2 */ void merge(int p) Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 49 - { int t, i1 = 1,i2 = 1,r1,r2; int h = 0; while(i1 <= h1 && i2 <= h2) { r1=r2=1; while((r1 <= p) && (r2 <=p ) && i1 <= h1 && i2 <= h2) { if(F1[i1] <= F2[i2]) { h++; F[h] = F1[i1]; r1++; i1++; } else { h++; F[h] = F2[i2]; r2++; i2++; } } while(i1 <= h1 && r1 <= p) { h++; b[h] = b1[i1]; i1++; } while(i2 <= h2 && r2 <= p) { h++; b[h] = b2[i2]; i2++; } } while(i1 <= h1) { h++; b[h] = b1[i1]; i1++; } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 50 - while(i2 <= h2) { h++; b[h] = b2[i2]; i2++; } n = h; } 4. Ñoä phöùc taïp thuaät toaùn Ta nhaän xeùt raèng, trong phöông phaùp saép xeáp baèng troän hai ñöôøng tröïc tieáp, soá löôïng caùc böôùc sao cheùp caùc phaàn töû töø daõy naøy sang daõy kia coøn lôùn hôn soá löôïng caùc böôùc so saùnh giöõa caùc phaàn töû : Vì öùng vôùùi moät laàn so saùnh thì coù moät thao taùc sao cheùp, nhöng neáu moät daõy naøo ñoù xöû lyù caïn (heát daõy) thì phaàn ñuoâi cuûa daõy coøn laïi ñöôïc sao cheùp maø khoâng öùng vôùi moät pheùp so saùnh naøo. Vì theá, ñoái vôùi phöông phaùp naøy, ta choïn pheùp sao cheùp laøm caên cöù ñaùnh giaù thôøi gian thöïc hieän cuûa thuaät toaùn. Trong moãi laàn phaân boá vaø troän thì toaøn boä n phaàn töû ñöôïc duyeät qua, so saùnh vaø cheùp vaøo daõy ñích (output). Nhö vaäy thôøi gian chi phí cho moãi böôùc coù caáp laø O(n). Vì trong moãi böôùc (böôùc thöù k) ta giaûi quyeát ñöôïc 2k = p giaù trò vaø tieán trình döøng khi p ≥ n,neân ta coù lgn böôùc, do ñoù caáp thôøi gian chi phí cho phöông phaùp naøy laø O(nlgn). Moät nhöôïïc ñieåm cuûa phöông phaùp saép xeáp baèng kieåu troän hai ñöôøng tröïc tieáp laø chi phí cho khoâng gian quaù lôùn: noù ñoøi hoûi cung caáp vuøng nhôù 2n phaàn töû, gaáp ñoâi so vôùi phöông phaùp thoâng thöôøng. Do ñoù phöông phaùp naøy chæ thích hôïp khi ta thao taùc treân caùc teäp. Maët khaùc, phöông phaùp saép xeáp kieåu troän hai ñöôøng tröïc tieáp coù moät nhöôïc ñieåm quan troïng nöõa laø noù töï giôùi haïn soá löôïng caùc giaù trò coá ñònh laø 1,2,4, ,2k, trong ñoù 2k < n. Nhö vaäy ta luoân luoân phaûøi duyeät qua k böôùc chia vaø troän. Neáu cho pheùp soá löôïng caùc phaàn töû trong moät laàn troän coù kích thöôùc khaùc thì soá caùc böôùc coù theå giaûm ñi vaø trong tröôøng hôïp naøy vieäc saép xeáp coù khaû naêng keát thuùc sôùùm. BAØI TAÄP Baøi 1 : ( Nhaân caùc soá lôùn ) Kyõ thuaät chia ñeå trò nhaân 2 soá nguyeân döông x, y döôõi daïng chuoãi : Nhan(x,y) ≡ if( l(x), l(y) <= 4) Nhaân 2 soá nguyeân nguyeân kieåu long; else Giaû söû l(x) = l(y) = n; Taùch x thaønh 2 chuoãi con : a(Nöûa traùi), b (nöûa phaûi) Taùch y thaønh 2 chuoãi con : c(Nöûa traùi), d (nöûa phaûi) Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 51 - Kq = nhan(a,c)*10n + nhan(a,d)*10n/2 + nhan (b,c)*10n/2 + nhan(b,d); Baøi 2 : Thuaät toaùn nhaân 2 soá nguyeân n bit. Giaû söû x vaø y laø 2 soá nguyeân n bit. Kyõ thuaät “ chia ñeå trò “ cho pheùp nhaân xy laø taùch x, y ra 2 soá nguyeân n/2 bit : x a b n/2 bit traùi n/2 bit phaûi y c d vaø tính theo coâng thöùc : x*y = a*c*2n + ( (a-b)*(d-c) + a*c + b*d)*2n/2 + b*d Ghi chuù : - Taùch bit : Copy caùc bit. - Nhaân 2n cho a : Dòch chuyeån traùi a n bit. Baøi 3 : Cho x, s, n ∈ Z+. Giaû söû n x ≤ s , tính n x . Baøi 4 : Saép taêng daàn moät daõy x caùc soá, baèng thuaät toaùn troän töï nhieân : Trong khi (soá ñöôøng chaïy cuûa x > 1) - Taùch luaân phieân töøng ñöôøng chaïy cuûa x vaøo caùc daõy trung gian x1, x2; - Troän töøng caëp ñöôøng chaïy cuûa x1, x2 , löu tröû vaøo x; Ghi chuù : Ñöôøng chaïy trong x laø caùc daõy con coù thöù töï ( taêng daàn) coù chieàu daøi lôùn nhaát. Baøi 5 : Laäp lòch thi ñaáu voøng troøn 1 löôït cho n ñoäi boùng ñaù, n laø luyõ thöøa 2. Trong 1 ñôït thi ñaáu , moãi ñoäi ñaáu 1 traän. Ñaáu trong n-1 ñôït. Kyõ thuaät chia ñeå trò xaây döïng lòch cho moät nöûa soá ñoäi . Lòch naøy ñöôïc laäp neân do aùp duïng ñeä qui cuûa thuaät toaùn baèng caùch tìm lòch cho moät nöûa soá ñoäi khi chæ coøn 2 ñoäi thì ta coù moät caëp ñaáu ñôn giaûn. Caùc ñoäi ñöôïc ñaùnh soá töø 1 ñeán n. Giaû söû coù 8 ñoäi . Lòch thi ñaáu cho 4 ñoäi töø 1 ñeán 4 laáp ñaày goùc traùi treân ( 4 haøng 3 coät) coi nhö ñaõ laäp xong. Goùc traùi döôùi ( 4 haøng 3 coät ) phaûi cho vaøo caùc ñoäi coù soá thöù töï cao (töø 5 ñeán 8) ngöôïc vôùi caùc soá khaùc.Lòch con naøy taïo ra baèng caùch coäng 4 cho moãi soá nguyeân cuûa goùc traùi treân . Baây giôø ta ñaõ laøm ñôn giaûn baøi toaùn. Taát caû phaàn coøn laïi laø caùc ñoäi coù soá thaáp ñaáu vôùi caùc ñoäi coù soá cao. Ñieàu ñoù deã hieåu laø caùc ñoäi töø 1-4 ñaáu vôùi caùc ñoäi 5-8 töông öùng töø ñôït thöù 4 vaø hoaùn vò theo chu kyø 5 ñeán 8 trong caùc ñôït tieáp theo. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 52 - ñôït 1 ñôït 1 2 3 ñôït 1 2 3 4 5 6 7 ñoäi 1 2 → 1 2 3 4 ñoäi 1 2 3 4 5 6 7 8 2 1 2 1 4 3 → 2 1 4 3 6 7 8 5 3 4 1 2 3 4 1 2 7 8 5 6 4 3 2 1 4 3 2 1 8 5 6 7 5 6 7 8 1 4 3 2 6 5 8 7 2 1 4 3 7 8 5 6 3 2 1 4 8 7 6 5 4 3 2 1 Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 53 - CHÖÔNG 3 : PHÖÔNG PHAÙP QUAY LUI (Back Tracking) I. Môû ñaàu 1. YÙ töôûng Neùt ñaëc tröng cuûa phöông phaùp quay lui laø caùc böôùc höôùng tôùi lôøi giaûi cuoái cuøng cuûa baøi toaùn hoaøn toaøn ñöôïc laøm thöû. Taïi moãi böôùc, neáu coù moät löïa choïn ñöôïc chaáp nhaän thì ghi nhaän laïi löïa choïn naøy vaø tieán haønh caùc böôùc thöû tieáp theo. Coøn ngöôïc laïi khoâng coù löïa choïn naøo thích hôïp thì laøm laïi böôùc tröôùc, xoaù boû söï ghi nhaän vaø quay veà chu trình thöû caùc löïa choïn coøn laïi. Haønh ñoäng naøy ñöôïc goïi laø quay lui, thuaät toaùn theå hieän phöông phaùp naøy goïi laø quay lui. Ñieåm quan troïng cuûa thuaät toaùn laø phaûi ghi nhôù taïi moãi böôùc ñi qua ñeå traùnh truøng laëp khi quay lui. Deã thaáy laø caùc thoâng tin naøy caàn ñöôïc löu tröû vaøo moät ngaên xeáp, neân thuaät toaùn theå hieän yù thieát keá moät caùch ñeä quy. 2. Moâ hình Lời giải của baøi toaùn thöôøng bieåu dieãn baèng moät vec tô goàm n thaønh phaàn x = (x1, , xn ) phaûi thoûa maõn caùc ñieàu kieän naøo ñoù. Ñeå chæ ra lôøi giaûi x, ta phaûi xaây döïng daàn caùc thaønh phaàn lôøi giaûi xi . Taïi moãi böôùc i : - Ñaõ xaây döïng xong caùc thaønh phaàn x1, , xi-1 - Xaây döïng thaønh phaàn xi baèng caùch laàn löôït thöû taát caû caùc khaû naêng maø xi coù theå choïn : • Neáu moät khaû naêng j naøo ñoù phuø hôïp cho xi thì xaùc ñònh xi theo khaû naêng j. Thöôøng phaûi coù theâm thao taùc ghi nhaän traïng thaùi môùi cuûa baøi toaùn ñeå hoå trôï cho böôùc quay lui. Neáu i = n thì ta coù ñöôïc moät lôøi giaûi, nguôïc laïi thì tieán haønh böôùc i+1 ñeå xaùc ñònh xi+1 . • Neáu khoâng coù moät khaû naêng naøo chaáp nhaän ñöôïc cho xi thì ta luøi laïi böôùc tröôùc (böôùc 1-1) ñeå xaùc ñònh laïi thaønh phaàn xi-1. Ñeå ñôn giaûn, ta giaû ñònh caùc khaû naêng choïn löïa cho caùc xi taïi moãi böôùc laø nhö nhau, do ñoù ta phaûi coù theâm moät thao taùc kieåm tra khaû naêng j naøo laø chaáp nhaän ñöôïc cho xi . Moâ hình cuûa phöông phaùp quay lui coù theå vieát baèng thuû tuïc sau, vôùi n laø soá böôùc caàn phaûi thöïc hieän, k laø soá khaû naêng maø xi coù theå choïn löïa. Try(i) ≡ for ( j = 1 → k) If ( xi chaáp nhaän ñöôïc khaû naêng j) { Xaùc ñònh xi theo khaû naêng j; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 54 - Ghi nhaän traïng thaùi môùi; if( i < n) Try(i+1); else Ghi nhaän nghieäm; Traû laïi traïng thaùi cuõ cho baøi toaùn; } Ghi chuù : Tìm nghieäm baèng phöông phaùp quay lui coù theå chuyeån veà tìm kieám treân caây khoâng gian caùc traïng thaùi, vôùi caây ñöôïc xaây döïïng töøng möc nhö sau : - Caùc nuùt con cuûa goác (thuoäc möùc 1) laø caùc khaû naêng coù theå choïn cho x1. - Giaû söû xi-1 laømoät nuùt ôû möùc thöù i-1, khi ñoù caùc nuùt con cuûa xi-1 laø caùc khaû naêng maø xi coù theå choïn, moät khi ñaõ tìm ñöôïc caùc thaønh phaàn x1, , xi-1. Nhö vaäy, moãi nuùt xi cuûa caây bieåu dieãn moät lôøi giaûi boä phaän, ñoù laø caùc nuùt naèm treân ñöôøng ñi töø goác ñeán nuùt ñoù. Ta coù theå noùi vieäc tìm kieám nghieäm baèng phöông phaùp quay lui chính laø tìm kieám theo chieàu saâu treân caây khoâng gian caùc traïng thaùi. Goác x1 Möùc 1 x2 Möùc 2 x3 Möùc 3 . . . . . . . . Sau ñaây laø caùc minh hoaï veà kyõ thuaät thieát keá quay lui. II. Baøi toaùn Ngöïa ñi tuaàn 1. Phaùt bieåu baøi toaùn Cho baøn côø coù n x n oâ . Moät con ngöïa ñöôïc pheùp ñi theo luaät côø vua, ñaàu tieân ñöôïc ñaët ôû oâ coù toïa ñoä x0 , y0 . Vaán ñeà laø haõy chæ ra caùc haønh trình (neáu coù) cuûa ngöïa – Ñoù laø ngöïa ñi qua taát caû caùc oâ cuûa baøn côø, moãi oâ ñi qua ñuùng moät laàn . Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 55 - 2. Thieát keá thuaät toaùn Caùch giaûi quyeát roõ raøng laø xeùt xem coù theå thöïc hieän moät nöôùc ñi keá nöõa hay khoâng. Sô ñoà ñaàu tieân coù theå phaùt thaûo nhö sau : Try(i) ≡ for ( j = 1 → k) If ( xi chaáp nhaän ñöôïc khaû naêng k) { Xaùc ñònh xi theo khaû naêng k; Ghi nhaän traïng thaùi môùi; if( i ngöïa chöa ñi qua; h[x][y] = i ≡ OÂ ngöïa ñaõ ñi qua ôû böôùc thöù i (1 ≤ i ≤ n2 ). * Caùc khaû naêng chonï löïa cho xi ? Ñoù chính laø caùc nöôùc ñi cuûa ngöïa maø xi coù theå chaáp nhaän ñöôïc. Vôùi caëp toïa ñoä baét ñaàu nhö trong hình veõ, coù taát caû 8 oâ maø con ngöïa coù theå ñi ñeán. Giaû söû chuùng ñöôïc ñaùnh soá töø 0 ñeán 7 nhö hình sau : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 56 - Toïa 1 2 3 4 5 Toïa ñoä ñoä (a,b) (a,b) (-2,-1) 4 3 1 (-2,1) (-1,-2) 5 2 2 (-1,2) haøng x 3 → (1,-2) 6 1 4 (1,2) (2,-1) 7 0 5 (2,1) ↑ coät y ( 8 böôùc ñi coù theå coù cuûa con ngöïa ) Moät phöông phaùp ñôn giaûn ñeå coù ñöôïc u, v töø x, y laø ta duøng 2 maûng a vaø b löu tröû caùc sai bieät veà toïa ñoä .Neáu ta duøng moät chæ soá k ñeå ñaùnh soá “böôùc ñi keá ” thì chi tieát ñoù ñöôïc theå hieän bôûi : u = x +a[k]; v = y + b[k]; k = 0,7 . Ñieàu kieän “chaáp nhaän ñöôïc” coù theå ñöôïc bieåu dieãn nhö keát hôïp cuûa caùc ñieàu kieän : OÂ môùi phaûi thuoäc baøn côø (1 ≤ u ≤ n vaø 1 ≤ v ≤ n) vaø chöa ñi qua oâ ñoù, nghóa laø h[u,v] = 0; * Ñeå ghi nhaän nöôùc ñi hôïp leä ôû böôùc i, ta gaùn h[u][v] = i; vaø ñeå huûy moät nöôùc ñi thì ta gaùn h[u][v] = 0. * Ma traän h ghi nhaän keát quaû nghieäm. Neáu coù sao cho h = 0 thì ñoù khoâng phaûi laø lôøi giaûi cuûa baøi toaùn , coøn ngöôïc laø h chöùa ñöôøng ñi cuûa ngöïa. Vaäy thuaät toaùn coù theå moâ taû nhö sau : Input n, //Kích thöôùc baøn côø x, y;//Toaï ñoä xuaát phaùt ôû böôùc i Output h; Moâ taû : Try(i, x, y) ≡ for(k = 0; k <= 7; k++) { u = x + a[k]; v = y + b[k]; if (1 <= u ,v <= n &&h[u][v] == 0) { h[u][v] = i; if (i < n*n) Try(i+1,u,v); else xuat_h(); // In ma traän h } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 57 - h[u][v] = 0; } Thuû tuïc naøy xuaát taát caû caùc lôøi giaûi, neáu coù. Thuû tuïc ñeä qui ñöôïc khôûi ñoäng baèng moät leänh goïi caùc toïa ñoä ñaàu x0, y0 laø tham soá. OÂ xuaát phaùt coù trò 1, coøn caùc oâ khaùc ñöôïc ñaùnh daáu coøn troáng. H[x0 ][y0 ] = 1; Try(2,x , y ); Caùc maûng a vaø b coù theå khôûi ñaàu nhö sau : int a[8]= {2,1,-1,-2,-2,-1,1,2}; int b[8]= {1,2,2,1,-1,-2,-2,-1}; * Caùc lôøi giaûi sau laø moät soá keát quaû cho töø thuaät toaùn treân : n=5 x=1 y=1 n=6 x=2 y=3 1 6 15 10 21 36 17 6 29 8 11 14 9 20 5 16 19 30 1 10 5 28 19 2 7 22 11 16 35 18 7 12 9 8 13 24 17 4 23 20 31 2 27 4 25 18 3 12 23 34 15 22 25 32 13 21 24 33 14 3 26 * Vôùi n = 5, caùc toïa ñoä xuaát phaùt sau khoâng coù lôøi giaûi : (2,3), (3,2) III. Baøi toaùn 8 haäu 1. Phaùt bieåu baøi toaùn TAÙM QUAÂN HAÄU ÑÖÔÏC ÑAËT LEÂN BAØN CÔØ VUA sao cho chuùng khoâng aên ñöôïc nhau . Baøi toaùn naøy laø moät ví duï noåi tieáng veà vieäc duøng caùc phöông phaùp thöû vaø sai vaø phöông phaùp quay lui. 2. Thieát keá thuaät toaùn Maáu choát cuûa thuaät toaùn roõ raøng laø xeùt xem coù theå ñaët quaân haäu tieáp theo nhö theá naøo. Theo luaät côø vua, moät quaân haäu coù theå aên caùc quaân khaùc neáu naèm treân cuøng 1 ñöôøng, ñöôøng naøy coù theå laø : - Haøng, - Coät, - Caùc ñöôøng cheùo (ñi qua toïa ñoä vò trí cuûa haäu). Suy ra raèng moãi haøng chæ coù theå chöùa 1 vaø chæ 1 quaân haäu. Neân vieäc choïn vò trí cho quaân haäu thöù i coù theå giôùi haïn ñöôïc ôû haøng thöù i. Nhö theá tham soá i trôû thaønh chæ haøng, vaø quaù trình choïn vò trí cho quaân haäu tieán haønh treân toaøn giaù trò coù theå coù cuûa caùc coät j. Ta quy öôùc : x[i] // Chæ quaân haäu thöù i : naèm ôû haøng i. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 58 - x[i] = j // quaân haäu thöù i ñaët ôû coät j; Ñeå quaân haäu i (treân haøng i) chaáp nhaän coät j thì coät j vaø 2 ñöôøng cheùo qua oâ phaûi coøn troáng ( töùc laø khoâng coù quaân haäu khaùc chieám lónh) Löu yù raèng trong 2 ñöôøng cheùo : - Ñöôøng cheùo ngöôïc (vuoâng goùc vôùi ñöôøng cheùo chính) : taát caû caùc oâ ñeàu coù toång 2 toïa ñoä i vaø j laø haèng; - Ñöôøng cheùo thuaän (song song vôùi ñöôøng cheùo chính) : goàm taát caû caùc oâ (i,j) maø coù hieäu caùc toïa ñoä (i-j) laø haèng soá. Coät j Ñöôøng cheùo (i + j) Ñöôøng cheùo (i – j) Haøng i Do ñoù ta seõ choïn caùc maûng Boole 1 chieàu ñeå bieåu dieãn caùc traïng thaùi naøy : a[j] = 1 : Coù nghóa laø khoâng coù quaân haäu naøo ôû coät. b[i+j] = 1 : Coù nghóa laø khoâng coù quaân haäu naøo ôû ñöôøng cheùo ngöôïc (i+j) . c[i -j] = 1 : Coù nghóa laø khoâng coù quaân haäu naøo ôû ñöôøng cheùo thuaän (i- j) . Vì : 1 ≤ i,j ≤ 8 ⇒ 2 ≤ i+j ≤ 16 Vaø -7 ≤ i - j ≤ 7. Neân ta coù theå khai baùo : int x[8], a[8], b[15], c[15]; Vôùi caùc döõ lieäu ñaõ cho, thì leänh ñaët quaân haäu seõ theå hieän bôûi : x[ i ] = j; // ñaët quaân haäu thöù i treân coät j. a[ j ] = 0;//Khi ñaët haäu taïi coät j , thì coät j khoâng coøn troáng nöõa b[ i+ j ] = 0;//Caùc ñöôøng cheùo töông öùng cuõng khoâng coøn c[ i - j ] = 0;//troáng nöõa . Coøn leänh Dôøi quaân haäu laø : //Laøm cho haøng i vaø caùc ñöôøng cheùo töông öùng trôû thaønh troáng a[ j ] = 1; b[ i+ j ] = 1; c[ i - j ] = 1; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 59 - Coøn ñieàu kieän an toaøn laø oâ coù toïa ñoä ( i, j ) naèm ôû haøng vaø caùc ñöôøng cheùo chöa bò chieám (ñöôïc theå hieän baèng trò True). Do ñoù, coù theå ñöôïc theå hieän bôûi bieåu thöùc logic : a[ji ] && b[ i + j ] && c[ i - j ] Try(i) ≡ { for (j = 1; j <= 8; j++) if (a[j] && b[i+j] && c[i-j]) { x[i] = j; a[j] = 0; b[i+j] = 0; c[i-j] = 0; if (i < 8 ) try (i+1); else Xuaát(x); /* Sau khi in 1 lôøi giaûi xong,traû laïi tình traïng ban ñaàu coøn troáng cho haøng a[j], ñöôøng cheùo i+j vaø ñöôøng cheùo i-j, ñeå tìm lôøi giaûi khaùc */ a[ j ] = 1; b[i+j] = 1; c[i-j] = 1; } } Ghi chuù : Thuaät toaùn naøy tìm ñöôïc taát caû 92 lôøi giaûi. Thöïc ra laø chæ coù 12 lôøi giaûi khaùc nhau thaät söï, ñoù laø vì thuaät toaùn khoâng ghi nhaän tính ñoái xöùng. IV. Baøi toaùn lieät keâ caùc daõy nhò phaân ñoä daøi n 1. Phaùt bieåu baøi toaùn Lieät keâ caùc daõy coù chieàu daøi n döôùi daïng x1x2 xn , trong ñoù xi ∈ { 0,1 }. 2. Thieát keá thuaät toaùn Ta coù theå söû duïng sô ñoà tìm taát caû caùc lôøi giaûi cuûa baøi toaùn.Haøm Try(i) xaùc ñònh xi, trong ñoù xi chæ coù 1 trong 2 giaù trò laø 0 hay 1. Caùc giaù trò naøy maëc nhieân ñöôïc chaáp nhaän maø khoâng caàn phaûi thoaû maõn ñieàu kieän gì. Neân Haøm try(i) coù theå vieát nhö sau : Try ( i) ≡ for (j = 0; j <= 1; j++) Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 60 - { x[i] = j; if (i < n ) Try (i+1); else Xuaát(x); } Caây khoâng gian caùc traïng thaùi cuûa baøi toaùn coù theå moâ taû bôûi : 0 1 0 1 0 1 0 1 0 1 0 1 0 1 000 001 010 011 100 101 110 111 V. Baøi toaùn lieät keâ caùc hoaùn vò 1. Phaùt bieåu baøi toaùn Lieät keâ caùc hoaùn vò cuûa n soá nguyeân döông ñaàu tieân. 2. Thieát keá thuaät toaùn Ta bieåu dieãn caùc hoaùn vò döôùi daïng a1 an ; ai ∈{1, ,n} vaø ai ≠ aj neáu i ≠ j. Vôùi moïi i, ai chaáp nhaän giaù trò j neáu j chöa ñöôïc söû duïng, vaø vì vaäy ta caàn ghi nhôù j ñaõ ñöôïc söû duïng hay chöa khi quay lui. Ñeå laøm ñieàu naøy ta duøng moät daõy caùc bieán logic bj vôùi quy öôùc : ⎧1; neáu j chöa söû duïng ∀j = 1,n : b j = ⎨ ⎩0;neáu ngöôïc laïi. Sau khi gaùn j cho ai , ta caàn ghi nhôù cho bj ( bj = 0) vaø phaûi traû laïi traïng thaùi cuõ cho bj ( bj = True) khi thöïc hieän vieäc in xong moät hoaùn vò. Ta chuù yù raèng daõy caùc bieán bj seõ ñöôïc khôûi ñoäng baèng 1 Thuaät toaùn coù theå vieát nhö sau : Try( i)≡ { for ( j = 1; j <= n; j++) if ( b[j]) { a[i] = j; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 61 - b[j] = 0; // Ghi nhaän traïng thaùi môùi if (i < n) Try(i+1); else Xuaát(); b[j] = True; // Traû laïi traïng thaùi cuõ } } VI. Baøi toaùn lieät keâ caùc toå hôïp 1. Phaùt bieåu baøi toaùn Lieät keâ caùc toå hôïp chaëp k trong n phaàn töû. 2. Thieát keá thuaät toaùn Ta seõ bieåu dieãn toå hôïp döôùi daïng x1 xk ; Trong ñoù : 1 ≤ x1 < x2 < . . < xk ≤ n. Ta nhaän xeùt raèng vôùi moïi j ∈ {1, n}: xi chaáp nhaän j ⇔ j ∈ { ci-1+1, . ., n-k+i}. Caùc giaù trò j thoûa ñieàu kieän treân maëc nhieân ñöôïc chaáp nhaän, neân ta khoâng caàn duøng caùc bieán booole ñeå ghi nhôù nöõa. Thuaät toaùn coù theå vieát nhö sau : Try( i) ≡ for ( j = 1; j <= n ; j++) if( x[i-1] + 1 <= j <= n - k + i ) { x[i] = j; if (i < k) Try(i+1); else Xuaát(x); } VII. Baøi toaùn tìm kieám ñöôøng ñi treân ñoà thò 1. Phaùt bieåu baøi toaùn G = (V, U) laø ñôn ñoà thò (coù höôùng hoaëc voâ höôùng). V = {1,. ., n} laø taäp caùc ñænh, U laø taäp caïnh (cung). Vôùi s, t ∈ V, tìm taát caû caùc ñöôøng ñi töø s ñeán t. Caùc thuaät toaùn tìm kieám cô baûn : Thuật toaùn DFS : Tìm kieám theo chieàu saâu. Thuật toaùn BFS : Tìm kieám theo chieàu roäng. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 62 - 2. Thuaät toaùn DFS ( Depth First Search) a) YÙ töôûng Thuaät toaùn DFS tieán haønh tìm kieám trong ñoà thò theo chieàu saâu. Thuaät toaùn thöïc hieän vieäc thaêm taát caû caùc ñænh coù theå ñaït ñöôïc cho tôùi ñænh t töø ñænh s cho tröôùc. Ñænh ñöôïc thaêm caøng muoän seõ caøng sôùm ñöôïc duyeät xong (cô cheá LIFO – Vaøo Sau Ra Tröôùc). Neân thuaät toaùn coù theå toå chöùc baèng moät thuû tuïc ñeä quy quay lui. b) Moâ taû thuaät toaùn Input G = (V,U), s, t Output Taát caû caùc ñöôøng ñi töø s ñeán t (neáu coù). DFS ( int s) ≡ for ( u = 1; u <= n; u++) { if (chaáp nhaän ñöôïc) { Ghi nhaän noù; if (u ≠ t) DFS(u); else In ñöôøng ñi; boû vieäc ghi nhaän; } } c) Caøi ñaët Ta caàn moâ taû döõ lieäu ñoà thò vaø caùc meänh ñeà ñöôïc phaùt bieåu trong moâ hình. Ma traän seõ ñöôïc bieåu dieãn baèng ma traän keà : ⎧1;(i, j) ∈U aij = ⎨ ⎩0;(i, j) ∉U Ghi nhaän ñænh ñöôïc thaêm ñeå traùnh truøng laëp khi quay lui baèng caùch ñaùnh daáu. Ta söõ duïng moät maûng moät chieàu Daxet[] vôùi qui öôùc : Daxet[u] = 1 , u ñaõ ñöôïc thaêm. Daxet[u] = 0 , u chöa ñöôïc thaêm. Maûng Daxet[] luùc ñaàu khôûi ñoäng baèng 0 taát caû. Ñieàu kieän chaáp nhaän ñöôïc cho ñænh u chính laø u keà vôùi v (avu = 1) vaø u chöa ñöôïc thaêm ( Daxet[u] = 0). Ñeå ghi nhaän caùc ñænh trong ñöôøng ñi, ta duøng moät maûng moät chieàu Truoc[ ], vôùi qui öôùc : Truoc[u] = v ⇔ v laø ñænh ñöùng tröôùc ñænh u, vaø u keà vôùi v Ta khôûi ñoäng maûng Truoc[ ] baèng 0 taát caû. Thuaät toaùn coù theå vieát laïi nhö sau : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 63 - Input G = (aij)nxn , s, t Output Taát caû caùc ñöôøng ñi töø s ñeán t (neáu coù). void DFS( s) ≡ int u; daxet[s] = 1; for( u = 1;u <= n; u++) { if( a[s][u] && !daxet[u]) { Truoc[u] = s; if ( u == t ) Xuat_duongdi(); else DFS(u); daxet[u] = 0; } } Maûng truoc[ ] löu tröû caùc ñænh treân ñöôøng ñi, Neáu keát thuùc thuaät toaùn, Daxet[t] = 0 ( Truoc[t] = 0 ) thì khoâng coù ñöôøng ñi töø s ñeán t. Trong tröôøng hôïp toàn taïi ñöôøng ñi, xuaát ñöôøng ñi chính laø xuaát maûng Truoc[ ]. Thao taùc naøy coù theå vieát nhö sau : Xuat_duongdi()≡ cout<<t<<"< "; j = t; while ( truoc[j] != s) { cout<<truoc[j]<<"< "; j = truoc[j]; } cout<<s<<endl; Vôùi ñoà thò coù höôùng cho bôûi ma traän keà : 7 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 Keát quaû : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 64 - s = 1, t = 4 s = 2, t = 5 4 ← 1 5 ← 6 ← 1 ← 4 ← 3 ← 2 4 ← 7 ← 1 5 ← 6 ← 3 ← 2 5 ← 6 ← 1 ← 4 ← 2 5 ← 6 ← 3 ← 4 ← 2 3. Thuật toaùn BFS ( Breadth First Search) a) YÙ töôûng Thuaät toaùn BFS tieán haønh tìm kieám treân ñoà thò theo chieàu roäng. Thuaät toaùn thöïc hieän vieäc thaêm taát caû caùc ñænh coù theå ñaït ñöôïc cho tôùi ñænh t töø ñænh s cho tröôùc theo töøng möùc keà. Ñænh ñöôïc thaêm caøng sôùm thì seõ caøng sôùm ñöôïc duyeät xong (cô cheá FIFO – Vaøo Tröôùc Ra Tröôùc). b) Moâ taû thuaät toaùn Input G = (V,E), s, t ∈ V; Output Ñöôøng ñi töø s ñeán t. Moâ taû : - Böôùc 0 : A0 = {s}. - Böôùc 1 : A1 = {x ∈V \ A0 : (s, x) ∈ E}. - Böôùc 2 : A2 = {x ∈V \ [A0 ∪ A1 ] : ∃y ∈ A1 ,(y, x) ∈ E}. - . . . i−1 - Böôùc i : Ai = {x ∈V \ Ak : ∃y ∈ Ai−1 ,(y,x) ∈ E}. Uk =0 - Thuaät toaùn coù khoâng quaù n böôùc laëp; moät trong hai tröôøng hôïp sau xaûy ra : - Neáu vôùi moïi i, t ∉ Ai : khoâng coù ñöôøng ñi töø s ñeán t; - Ngöôïc laïi, t ∈ A(m) vôùi m naøo ñoù. Khi ñoù toàn taïi ñöôøng ñi töø s tôùi t, vaø ñoù laø moät ñöôøng ñi ngaén nhaát töø s ñeán t. Trong tröôøng hôïp naøy, ta xaùc ñònh ñöôïc caùc ñænh treân ñöôøng ñi baèng caùch quay ngöôïc laïi töø t ñeán caùc ñænh tröôùc t trong töøng caùc taäp tröôùc cho ñeán khi gaëp s. Minh hoaï : Cho ñôn ñoà thò coù höôùng : Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 65 - 1 6 2 5 3 4 Tìm ñöôøng ñi töø ñænh (1) ñeán ñænh (4) : A(0) = {1}; A(1) = {2,3,5} A(2) = {6} A(3) = {4} Ñöôøng ñi ngaén nhaát tìm ñöôïc laø 4 ← 6 ← 5 ← 1 , coù chieàu daøi laø 3. c) Caøi ñaët Trong thuaät toaùn BFS, ñænh ñöôïc thaêm caøng sôùm seõ caøng sôùm trôû thaønh duyeät xong, neân caùc ñænh ñöôïc thaêm seõ ñöôïc löu tröû trong haøng ñôïi queue. Moät ñænh seõ trôû thaønh duyeät xong ngay sau khi ta xeùt xong taát caû caùc ñænh keà cuûa noù . Ta duøng moät maûng logic Daxet[ ] ñeå ñaùnh daáu caùc ñænh ñöôïc thaêm, maûng naøy ñöôïc khôûi ñoäng baèng 0 taát caû ñeå chæ raèng luùc ñaàu chöa ñænh naøo ñöôïc thaêm. Moät maûng truoc[ ] ñeå löu tröû caùc ñænh naèm treân ñöôøng ñi ngaén nhaát caàn tìm (neáu coù), vôùi yù nghóa Truoc[i] laø ñænh ñöùng tröôùc ñænh i trong ñöôøng ñi. Maûng Truoc[ ] ñöôïc khôûi ñoäng baèng 0 taát caû ñeå chæ raèng luùc ñaàu chöa coù ñænh naøo. Ñoà thò G ñöôïc bieåu dieãn baèng ma traän keà a= (auv)nxn ⎧1;(u,v) ∈ E; trong ñoù : auv = ⎨ ⎩0;(u,v) ∉ E; Haøng ñôïi queue ta caøi ñaët baèng maûng . Thuaät toaùn ñöôïc caøi ñaët nhö sau : BFS(s) ≡ int u, j, dauQ = 1, cuoiQ = 1; queue[cuoiQ] = s; Daxet[s] = 1; while ( dauQ <= cuoiQ) { u = queue[dauQ]; dauQ++; for ( j = 1; j <= n; j++) if( a[u][j] == 1 && !Daxet[j] ) { cuoiQ++; Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 66 - queue[cuoiQ] = j; Daxet[j] = 1; Truoc[j] = u; } } Nhaän xeùt : Ta coù theå thaáy moãi laàn goïi DFS(s), BFS(s) thì moïi ñænh cuøng thaønh phaàn lieân thoâng vôùi s seõ ñöôïc thaêm, neân sau khi thöïc hieän haøm treân thì : • Truoc[t] == 0 : coù nghæa laø khoâng toàn taïi ñöôøng ñi töø s ñeán t, • Ngöôïc laïi, coù ñöôøng ñi töø s ñeán t. Khi ñoù lôøi giaûi ñöôïc cho bôûi : t ← p1 = Truoc[t] ← p2 = Truoc[p1] ← ← s . BAØI TAÄP Baøi 1: Caøi ñaët caùc thuaät toaùn : 1. Lieät keâ taát caû caùc daõy nhò phaân ñoä daøi n. 2. Lieät keâ taát caû caùc hoaùn vò cuûa n soá nguyeân döông ñaàu tieân. 3. Lieät keâ taát caû caùc toå hôïp chaëp k trong taäp goàm n soá nguyen döông ñaàu tieân. 4. Giaûi baøi toaùn ngöïa ñi tuaàn. 5. Giaûi baøi toaùn n haäu. 6. DFS. 7. BFS. Baøi 2 : Cho daõy a = (a1, a2, . . ., an ) goàm caùc soá ñoâi moät khaùc nhau. 1. Lieät keâ taát caû caùc hoaùn vò cuûa daõy n phaàn töû cuûa a. 2. Lieät keâ taát caû caùc toå hôïp chaëp k trong taäp goàm n phaàn töû cuûa a. Baøi 3 : Giaû söû oå khoùa coù n coâng taéc. Moãi coâng taéc coù moät trong 2 traïng thaùi “ñoùng” hay “môû”. Khoùa môû ñöôïc neáu coù ít nhaát [n/2] coâng taéc coù traïng thaùi môû. Lieät keâ taát caû caùc caùch môû khoùa. Baøi 4 ( Ngöïa ñi tuaàn ). Cho baøn côø n x n oâ. Moät con ngöïa ñöôïc pheùp ñi theo luaät côø vua. Tìm haønh trình cuûa ngöïa, baét ñaàu töø oâ ñi qua taát caû caùc oâ cuûa baøn côø, moãi oâ ñuùng moät laàn. Lieät keâ taát caû caùc haønh trình. Baøi 5 : Cho baøn côø n x n oâ. Moät con ngöïa ñöôïc pheùp ñi theo luaät côø vua. Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn
Thieát keá vaø ñaùnh giaù thuaät toaùn - 67 - Tìm haønh trình cuûa ngöïa, baét ñaàu töø oâ , oâ keát thuùc , moãi oâ trong haønh trình ngöïa ñi qua ñuùng moät laàn. 1. Lieät keâ taát caû caùc haønh trình. 2. Chæ ra haønh trình ngaén nhaát ( coù soá oâ trong haønh trình ít nhaát ) Baøi 6 ( Ngöïa ñi tuaàn ). Cho baøn côø n x n oâ. Moät con ngöïa ñöôïc pheùp ñi theo luaät côø töôùng. Tìm haønh trình cuûa ngöïa, baét ñaàu töø oâ ñi qua taát caû caùc oâ cuûa baøn côø, moãi oâ ñuùng moät laàn. Lieät keâ taát caû caùc haønh trình. Baøi 7 : Moät ngöôøi du lòch muoán tham quan n thaønh phoá T1, T2, . ., Tn . Xuaát phaùt töø moät thaønh phoá naøo ñoù, ngöôøi du lòch muoán ñi qua taát caû caùc thaønh phoá coøn laïi, moãi thaønh phoá ñi qua ñuùng moät laàn roài quay trôû laïi thaønh phoá xuaát phaùt. Goïi Cij laø chi phí ñi töø thaønh phoá Ti ñeán thaønh phoá Tj . 1. Lieät keâ taát caû caùc haønh trình ñi töø thaønh phoá Ti ñeán thaønh phoá Tj thoûa yeâu caàu baøi toaùn vaø chi phí töông öùng. 2. Chæ ra haønh trình ñi töø thaønh phoá Ti ñeán thaønh phoá Tj thoûa yeâu caàu baøi toaùn (neáu coù) sao cho coù chi phí ít nhaát. Baøi 8 : Cho moät ma traän vuoâng caáp n, caùc phaàn töû cuûa ma traän laø caùc soá töï nhieân. Ta noùi ñöôøng ñi trong ma traän laø moät ñöôøng gaáp khuùc khoâng töï caét xuaát phaùt töø moät oâ naøo ñoù cuûa ma traän, sau ñoù coù theå ñi theo caùc höôùng : leân treân, xuoáng döôùi, reõ traùi, reõ phaûi. Ñoä daøi cuûa ñöôøng ñi laø soá oâ naèm trong ñöôøng ñi. Vôùi oâ xuaát phaùt cho tröôùc : 1. Tìm moät ñöôøng ñi daøi nhaát trong ma traän, theo nghóa coù nhieàu oâ nhaát trong ñöôøng ñi. 2. Tìm ñöôøng ñi daøi nhaát trong ma traän sao cho caùc oâ treân ñöôøng ñi laäp thaønh moät daõy soá khoâng giaûm. Baøi 9 : Cho G = (V,E) laø moät ñôn ñoà thò, khoâng coù troïng soá, trong ñoù V= {1, , n} laø taäp ñænh, E laø taäp caïnh ( hay cung). 1. Xaùc ñònh soá thaønh phaàn lieân thoâng cuûa G. 2. Xuaát caùc ñænh naèm trong trong moãi thaønh phaàn lieân thoâng. Baøi 10 : Treân moät maûnh ñaát hình vuoâng, ta chia thaønh n x n oâ, moãi oâ ta ghi moät soá laø 0 hoaëc 1. OÂ mang soá 0 ta ñaøo ao, mang soá 1 ta troàng coû. Hai oâ troàng coû coù caïnh lieàn nhau ñöôïc xem laø cuøng naèm trong boàn coû. Haõy xaùc ñònh dieän tích cuûa boàn coû lôùn nhaát ( theo nghóa coù soá oâ nhieàu nhaát ). Traàn Tuaán Minh Khoa Toaùn-Tin Sưu tầm bởi: www.daihoc.com.vn