Giáo trình Công nghệ phần mềm - Phan Huy Khánh

155 trang phuongnguyen 3552

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Công nghệ phần mềm - Phan Huy Khánh", để 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_cong_nghe_phan_mem_phan_huy_khanh.pdf

Nội dung text: Giáo trình Công nghệ phần mềm - Phan Huy Khánh

Giáo trình Công nghệ phần mềm
Muûc luûc CHÆÅNG 1 ÂAÛI CÆÅNG VÃÖ CÄNG NGHÃÛ PHÁÖN MÃÖM 5 I. KHAÏI QUAÏT VÃÖ LËCH SÆÍ LÁÛP TRÇNH 5 I.1. Láûp trçnh tuyãún tênh 5 I.2. Láûp trçnh coï cáúu truïc 6 I.3. Láûp trçnh âënh hæåïng âäúi tæåüng (ÂHÂT) 6 I.4. Láûp trçnh træûc quan 7 I.5. Nhæîng tæ tæåíng caïch maûng trong láûp trçnh 7 II. CAÏC PHÆÅNG DIÃÛN CUÍA CÄNG NGHÃÛ PHÁÖN MÃÖM 8 II.1. Cäng nghãû pháön mãöm laì gç? 8 II.2. Nhæîng yãúu täú cháút læåüng bãn ngoaìi vaì bãn trong 8 II.3. Saín pháøm pháön mãöm laì gç ? 9 III. NHÆÎNG NÄÜI DUNG CÅ BAÍN CUÍA CNPM 11 III.1. Täøng quan vãö cäng nghãû pháön mãöm 11 III.2. Chu kyì säúng cuía pháön mãöm 12 CHÆÅNG 2 THIÃÚT KÃÚ PHÁÖN MÃÖM 18 I. NÃÖN TAÍNG CUÍA THIÃÚT KÃÚ PHÁÖN MÃÖM 18 II. PHÆÅNG PHAÏP LÁÛP TRÇNH CÁÚU TRUÏC 20 II.1. Khaïi niãûm vãö láûp trçnh cáúu truïc 22 II.2. Nhæîng yï tæåíng cå baín láûp trçnh cáúu truïc 22 II.3. Caïc cáúu truïc âiãöu khiãøn chuáøn 25 II.4. Mäüt säú vê duû viãút chæång trçnh theo så âäö khäúi 28 III. CÁÚU TRUÏC TÄÚI THIÃØU 29 III.1. Caïc cáúu truïc läöng nhau 31 IV. LÁÛP TRÇNH ÂÅN THÃ Ø 32 IV.1. Khaïi niãûm vãö âån thãø 32 IV.2. Mäúi liãn hãû giæîa caïc âån thãø 33 IV.2.1. Phán loaûi âån thãø 33 IV.2.2. Täø chæïc mäüt chæång trçnh coï cáúu truïc âån thãø 33 V. PHAÏT TRIÃØN CHÆÅNG TRÇNH BÀÒNG TINH CHÃÚ TÆÌNG BÆÅÏC 35 V.1. Näüi dung phæång phaïp 35 V.2. Vê duû minh hoaû 36 V.2.1. Vê duû 1 36 V.2.2. Baìi toaïn 8 quán háûu 38 TS. PHAN HUY KHAÏNH biãn soaûn i
ii Cäng nghãû Pháön mãöm V.3. Sæía âäøi chæång trçnh 42 VI. PHUÛ LUÛC - ÂÅN VË TRONG TURBO PASCAL 50 VI.1. Giåïi thiãûu Unit 50 VI.2. Cáúu truïc cuía Unit 50 VI.3. Caïch sæí duûng Unit 52 VI.4. Vê duû vãö Unit 53 VI.5. Baìi táûp 55 CHÆÅNG 3 HÅÜP THÆÏC HOÏA PHÁÖN MÃÖM 57 I. XAÏC MINH VAÌ HÅÜP THÆÏC HOÏA PHÁÖN MÃÖM 57 II. CHÆÏNG MINH SÆÛ ÂUÏNG ÂÀÕN CUÍA CHÆÅNG TRÇNH 58 II.1. Suy luáûn Toaïn hoüc 59 II.1.1. Caïc quy tàõc suy luáûn Toaïn hoüc 59 II.1.2. Khaïi niãûm vãö chæïng minh tênh âuïng âàõn cuía chæång trçnh 60 II.1.3. Tiãn âãö vaì quy tàõc suy diãùn 61 II.1.4. Quy tàõc âiãöu kiãûn if B then P 62 II.1.5. Quy tàõc âiãöu kiãûn if B then P else Q 63 II.1.6. Quy tàõc voìng làûp while 63 II.1.7. Caïc quy tàõc khaïc 64 II.2. Phæång phaïp cuía C.A.R. Hoare 66 II.2.1. Phaït biãøu 66 II.2.2. Chæïng minh tênh âuïng âàõn tæìng pháön cuía Div 66 II.3. Chæïng minh dæìng 69 II.3.1. Chæïng minh dæìng cuía mäüt chæång trçnh 69 II.3.2. Chæïng minh dæìng cuía Div 70 II.3.3. Âaïnh giaï mäüt chæång trçnh làûp 71 III. XÁY DÆÛNG CHÆÅNG TRÇNH 72 III.1. Måí âáöu 72 III.2. Baìi toaïn cåì tam taìi 73 III.2.1. Låìi giaíi thæï nháút 74 III.2.2. Låìi giaíi thæï hai 75 III.2.3. Chæïng minh tênh âuïng âàõn cuía chæång trçnh (I) 76 III.3. In ra mäüt danh saïch theo thæï tæû ngæåüc 80 III.3.1. TILDA1 81 IV. CAÏC TIÃN ÂÃÖ VAÌ QUY TÀÕC SUY DIÃÙN 82 IV.1. Âiãöu kiãûn træåïc yãúu nháút vaì âiãöu kiãûn sau maûnh nháút cuía mäüt daîy lãûnh 82 IV.1.1. Haìm fppre 83 IV.1.2. Haìm fppost 83 IV.1.3. Sæí duûng âiãöu kiãûn træåïc yãúu nháút vaì âiãöu kiãûn sau maûnh nháút âãø chæïng minh tênh âuïng âàõn cuía chæång trçnh 84 TS. PHAN HUY KHAÏNH biãn soaûn ii
Muûc luûc IV.2. Caïc tiãn âãö gaïn 86 IV.2.1. Âiãöu kiãûn træåïc yãúu nháút vaì âiãöu kiãûn sau maûnh nháút cuía lãûnh gaïn 86 IV.2.2. Quy tàõc tênh toaïn âiãöu kiãûn sau maûnh nháút cuía mäüt pheïp gaïn 87 V. BAÌI TÁÛP 89 CHÆÅNG 4 THÆÍ NGHIÃÛM CHÆÅNG TRÇNH 90 I. KHAÍO SAÏT PHÁÖN MÃÖM 90 II. CAÏC PHÆÅNG PHAÏP THÆÍ NGHIÃÛM 92 II.1. Âënh nghéa vaì muûc âêch thæí nghiãûm 92 II.2. Thæí nghiãûm trong chu kyì säúng cuía pháön mãöm 94 II.2.1. Thæí nghiãûm âån thãø 94 II.2.2. Thæí nghiãûm têch håüp 95 II.2.3. Thæí nghiãûm hãû thäúng 96 II.2.4. Thæí nghiãûm häöi quy 97 II.3. Dáùn dàõt caïc thæí nghiãûm 97 II.4. Thiãút kãú caïc pheïp thæí phaï huíy (Defect Testing) 98 II.4.1. Caïc phæång phaïp dæûa trãn chæång trçnh 98 II.4.2. Caïc phæång phaïp dæûa trãn âàûc taí 100 II.4.3. Kãút luáûn 101 II.4.4. Caïc tiãu chuáøn kãút thuïc thæí nghiãûm 101 II.5. Caïc pheïp thæí nghiãûm thäúng kã 102 II.5.1. Måí âáöu 102 II.5.2. Æåïc læåüng âäü äøn âënh cuía mäüt pháön mãöm 104 CHÆÅNG 5 ÂÀÛC TAÍ PHÁÖN MÃÖM 105 I. MÅÍ ÂÁÖU ÂÀÛC TAÍ PHÁÖN MÃÖM 105 I.1. Khaïi niãûm vãö âàûc taí 105 I.1.1. Âàûc taí laì gç ? 105 I.1.2. Caïc phæång phaïp âàûc taí 105 I.1.3. Caïc thê duû minh hoüa 106 I.2. Âàûc taí vaì láûp trçnh 107 II. ÂÀÛC TAÍ CÁÚU TRUÏC DÆÎ LIÃÛU 109 II.1. Khaïi niãûm vãö Cáúu truïc dæî liãûu cå såí vectå 109 II.1.1. Dáùn nháûp 109 II.1.2. Âàûc taí hçnh thæïc 110 II.2. Truy nháûp mäüt pháön tæí cuía vectå 110 II.3. Caïc thuáût toaïn xæí lyï vectå 111 II.3.1. Truy tçm tuáön tæû mäüt pháön tæí cuía vectå (sequential search) 111 II.3.2. Tçm kiãúm nhë phán (Binary search) 113 III. ÂÀÛC TAÍ ÂAÛI SÄÚ : MÄ HÇNH HOÏA PHAÏT TRIÃØN PHÁÖN MÃÖM 117 III.1. Måí âáöu 117 III.2. Phán loaûi caïc pheïp toaïn 119 III.3. Haûng vaì biãún 120 III.4. Pheïp thãú caïc haûng 120 TS. PHAN HUY KHAÏNH biãn soaûn iii
iv Cäng nghãû Pháön mãöm III.5. Caïc thuäüc tênh cuía âàûc taí 122 III.5.1. Mä hçnh láûp trçnh (triãøn khai) 122 III.5.2. Mä hçnh âàûc biãût 123 III.5.3. Mä hçnh âäöng dæ 123 III.6. Pheïp chæïng minh trong âàûc taí âaûi säú 123 III.6.1. Lyï thuyãúttæång âæång 124 III.6.2. Khaïi niãûm vãö lyï thuyãút quy naûp 125 III.6.3. Chæïng minh tæû âäüng båíi viãút laûi 126 III.6.4. Phán cáúp trong âàûc taí âaûi säú 128 IV. ÂÀÛC TAÍ HAY CAÏCH CUÛ THÃØ HOÏA SÆÛ TRÆÌU TÆÅÜNG 129 IV.1. Âàûc taí pheïp thay âäøi bäü nhåï 129 IV.2. Haìm 131 IV.3. Håüp thæïc hoïa vaì phuûc häöi 134 IV.4. Bàõt âáöu triãøn khai thæûc tiãùn 137 IV.5. Pheïp håüp thaình (cáúu taûo) 140 IV.6. Triãøn khai thæï hai 141 IV.7. Triãøn khai thæûc hiãûn láön thæï ba 146 IV.8. Âàûc taí laìm gç ? 149 TS. PHAN HUY KHAÏNH biãn soaûn iv
Âaûi cæång vãö cäng nghãû pháön mãöm 5 CHÆÅNG 1 Âaûi cæång vãö cäng nghãû pháön mãöm I. Khaïi quaït vãö lëch sæí láûp trçnh Láûp trçnh (programming), hay láûp chæång trçnh cho maïy tênh âiãûn tæí (MTÂT) laì mäüt ngaình coìn ráút måïi meí. MTÂT âáöu tiãn láûp trçnh âæåüc måïi chè xuáút hiãûn caïch âáy hån bäún mæåi nàm 1. Suäút hån bäún tháûp kyí qua, láûp trçnh khäng ngæìng âæåüc caíi tiãún vaì phaït triãøn, caìng ngaìy caìng hæåïng vãö nhu cáöu cuía ngæåìi láûp trçnh. Láûp trçnh laì mäüt cäng viãûc nàûng nhoüc, nàng suáút tháúp so våïi caïc hoaût âäüng trê tuãû khaïc. Vê duû nãúu mäüt saín pháøm pháön mãöm khoaíng 2000 − 3000 doìng lãûnh âoìi hoíi 3 ngæåìi láûp trçnh chênh trong voìng 6 thaïng thç nàng suáút mäùi ngæåìi chè dao âäüng trong khoaíng tæì 5 âãún 6 lãûnh mäùi ngaìy (?!). Chênh vç caïc saín pháøm pháön mãöm khi tung ra thë træåìng chæa thæûc sæû hoaìn haío ngay nãn ngæåìi ta thæåìng duìng meûo thæång maûi bàòng caïch gaïn cho saín pháøm mäüt caïi âuäi “phiãn baín” (version) âãø noïi ràòng phiãn baín ra sau âaî khàõc phuûc âæåüc nhæîng khiãúm khuyãút cuía phiãn baín træåïc âoï. Vê duû û 1 : Hãû âiãöu haình MS−DOS âaî coï caïc phiãn baín 1.0, 3.3, 5.0, 6.0, 7.0 v.v Microsoft Windows âaî coï caïc phiãn baín 1.0, 2.0, 3.0, 3.1, 3.11. Nay laì Windows 95, 97, 98 v.v Turbo Psacal cuía haîng Borland Inc. âaî coï caïc phiãn baín 5.0, 6.0, 7.0, 8.0 v.v I.1. Láûp trçnh tuyãún tênh Våïi nhæîng MTÂT âáöu tiãn, ngæåìi ta sæí duûng ngän ngæî maïy (machine language) hay ngän ngæî báûc tháúp (low level) âãø láûp trçnh vaì duìng caïc khoaï cå khê âãø naûp chæång trçnh vaìo maïy. Theo âaì phaït triãøn cuía caïc thiãút bë pháön cæïng, caïc ngän ngæî báûc cao (high level) våïi caïc doìng lãûnh tæûa tiãúng Anh bàõt âáöu âæåüc sæí duûng. Maïy seî dëch chæång trçnh âoï sang ngän ngæî maïy træåïc khi thæûc hiãûn. Våïi nhæîng ngän ngæî láûp trçnh ban âáöu, chæång trçnh viãút ra gäöm nhæîng doìng lãûnh coï khuynh hæåïng näúi nhau theo daîy daìi, khoï hiãøu vãö màût logic. Ngæåìi ta sæí 1 ENIAC (Electronic Numerical Integrator and Computer) laì chiãúc MTÂT âáöu tiãn ra âåìi nàm 1945 taûi træåìng Âaûi hoüc Täøng håüp Pensylvania, næåïc Myî. TS. PHAN HUY KHAÏNH biãn soaûn 5
6 Cäng nghãû Pháön mãöm duûng caïc lãûnh nhaíy (goto) âãø âiãöu khiãøn chæång trçnh mäüt caïch tuyì tiãûn. Chæång trçnh laì mäüt måï räúi ràõm khäng khaïc gç moïn mç såüi (spaghetti) cuía næåïc YÏ. Caïc ngän ngæî láûp trçnh tuyãún tênh khäng kiãøm soaït âæåüc nhæîng sæ thay âäøi cuía dæî liãûu. Moüi dæî liãûu sæí duûng trong chæång trçnh âãöu coï tênh toaìn cuûc vaì coï thãø bë thay âäøi vaìo báút cæï luïc naìo. Vaìo giai âoaûn naìy, ngæåìi ta xem viãûc láûp trçnh nhæ mäüt hoaût âäüng nghãû thuáût nhuäúm maìu sàõc taìi nghãû caï nhán hån laì khoa hoüc, våïi thuáût ngæî “the art of programming”. I.2. Láûp trçnh coï cáúu truïc Vaìo cuäúi nhæîng nàm 1960 vaì âáöu 1970, khuynh hæåïng láûp trçnh cáúu truïc (structured programming) ra âåìi. Theo phæång phaïp naìy, mäüt chæång trçnh coï cáúu truïc âæåüc täø chæïc theo caïc pheïp toaïn maì noï phaíi thæûc hiãûn. Chæång trçnh bao gäöm nhiãöu thuí tuûc, hay haìm, riãng reî. Caïc thuí tuûc hay haìm naìy âäüc láûp våïi nhau, coï dæî liãûu riãng, giaíi quyãút nhæîng váún âãö riãng, nhæng coï thãø trao âäøi qua laûi våïi nhau bàòng caïc tham biãún. Láûp trçnh cáúu truïc laìm cho viãûc kiãøm soaït chæång trçnh dãù daìng hån, vaì do váûy, giaíi quyãút baìi toaïn dãù daìng hån. Tênh hiãûu quaí cuía láûp trçnh cáúu truïc thãø hiãûn åí khaí nàng træìu tæåüng hoaï. Trong mäüt chæång trçnh coï cáúu truïc, ngæåiì ta chè quan tám vãö màût chæïc nàng : mäüt thuí tuûc hay haìm naìo âoï coï thæûc hiãûn âæåüc cäng viãûc âaî cho hay khäng ? Coìn viãûc thæûc hiãûn nhæ thãú naìo laì khäng quan troüng, chuìng naìo coìn âuí tin cáûy. Màûc duì kyî thuáût thiãút kãú vaì láûp trçnh cáúu truïc âæåüc sæí duûng räüng raîi nhæng váùn bäüc läü nhæîng khiãúm khuyãút. Khi âäü phæïc taûp tàng lãn thç sæû phuû thuäüc cuía chæång trçnh vaìo kiãøu dæî liãûu maì noï xæí lyï cuîng tàng theo. Cáúu truïc dæî liãûu trong mäüt chæång trçnh coï vai troì quan troüng cuîng nhæ caïc pheïp toaïn thæûc hiãûn trãn chuïng. Mäüt khi coï sæû thay âäøi trãn mäüt kiãøu dæî liãûu thç mäüt thuí tuûc naìo âoï taïc âäüng lãn kiãøu dæî liãûu naìy cuîng phaíi thay âäøi theo. Khiãúm khuyãút trãn cuîng aính hæåíng âãún tênh håüp taïc giæîa caïc thaình viãn láûp trçnh. Mäüt chæång trçnh coï cáúu truïc âæåüc giao cho nhiãöu ngæåìi thç khi coï sæû thay âäøi vãö cáúu truïc dæî liãûu cuía mäüt ngæåìi seî aính hæåíng âãún cäng viãûc cuía nhæîng ngæåìi khaïc. I.3. Láûp trçnh âënh hæåïng âäúi tæåüng (ÂHÂT) Láûp trçnh ÂHÂT (oriented-object programming) âæåüc xáy dæûng trãn nãön taíng cuía láûp trçnh cáúu truïc vaì træìu tæåüng hoaï dæî liãûu (data abstraction). Chæång trçnh ÂHÂT âæåüc thiãút kãú xung quanh dæî liãûu maì noï thao taïc chæï khäng baín thán caïc thao taïc. Tênh ÂHÂT laìm roî mäúi quan hãû giæîa dæî liãûu vaì thao taïc trãn dæî liãûu.
Âaûi cæång vãö cäng nghãû pháön mãöm 7 Træìu tæåüng hoaï dæî liãûu laì laìm cho viãûc sæí duûng caïc cáúu truïc dæî liãûu tråí nãn âäüc láûp âäúi våïi viãûc caìi âàût cuû thãø. Vê duû säú dáúu cháúm âäüng (floating point number) âaî âæåüc træìu tæåüng hoaï trong moüi ngän ngæî láûp trçnh. NSD thao taïc trãn caïc säú dáúu cháúm âäüng maì khäng quan tám âãún caïch biãøu diãùn nhë phán trong maïy cuía chuïng nhæ thãú naìo. Láûp trçnh ÂHÂT liãn kãút caïc cáúu truïc dæî liãûu våïi caïc pheïp toaïn. Mäüt cáúu truïc naìo âoï thç tæång æïng, ta coï nhæîng pheïp toaïn naìo âoï. Vê duû : mäüt baín ghi vãö nhán sæû coï thãø âæåüc âoüc, cáûp nháût sæû thay âäøi vaì âæåüc cáút giæî, coìn mäüt säú phæïc thç âæåüc duìng trong tênh toaïn. Khäng thãø viãút säú phæïc lãn tãûp nhæ mäüt baín ghi nhán sæû, cuîng khäng thãø cäüng træì nhán chia hai baín ghi nhán sæû våïi nhau nhæ caïch cuía säú phæïc. Láûp trçnh ÂHÂT âæa vaìo nhiãöu thuáût ngæî vaì khaïi niãûm måïi, chàóng haûn khaïi niãûm låïp (class), khaïi niãûm kãú thæìa (inheritence). Æu âiãøm cuía láûp trçnh ÂHÂT laì laìm cho viãûc phaït triãøn pháön mãöm nhanh choïng hån våïi khaí nàng duìng laûi caïc chæång trçnh cuî. Mäüt låïp måïi âæåüc xem nhæ låïp suy diãùn, coï thãø âæåüc kãú thæìa cáúu truïc dæî liãûu vaì caïc phæång phaïp cuía låïp gäúc hoàûc låïp cå såí. Mäüt trong nhæîng ngän ngæî láûp trçnh ÂHÂT âæåüc noïi âãún laì SMALLTALK, âæåüc phaït triãøn nàm 1980 taûi Xerox Palo Alto Recearch Center (PARC). Hiãûn nay, nhiãöu ngän ngæî láûp trçnh thäng duûng cuîng âæåüc trang bë thãm khaí nàng ÂHÂT, nhæ laì C++, Delphi, v.v I.4. Láûp trçnh træûc quan Láûp trçnh træûc quan (visual programming) âæåüc phaït triãøn trãn nãön taíng cuía láûp trçnh ÂHÂT. Khi thiãút kãú chæång trçnh, ngæåìi láûp trçnh nhçn tháúy ngay kãút quaí qua tæìng thao taïc vaì giao diãûn ngæåìi duìng (user interface) khi chæång trçnh âæåüc thæûc hiãûn. Ngæåìi láûp trçnh coï thãø dãù daìng chènh sæía vãö maìu sàõc, kêch thæåïc, hçnh daïng vaì caïc xæí lyï thêch håüp lãn caïc âäúi tæåüng coï màût trong giao diãûn. Caïc ngän ngæî láûp trçnh træûc quan thäng duûng hiãûn nay thæåìng âæåüc phaït triãøn trong mäi træåìng Microsoft Windows, nhæ Visual Basic, Visual C++, Visual Foxpro, Java. v.v I.5. Nhæîng tæ tæåíng caïch maûng trong láûp trçnh Láûp trçnh laì mäüt trong nhæîng lénh væûc khoï nháút cuía toaïn hoüc æïng duûng. Ngæåìi ta coi láûp trçnh laì mäüt khoa hoüc nhàòm âãö xuáút nhæîng nguyãn lyï vaì phæång phaïp âãø náng cao nàng suáút lao âäüng cuía láûp trçnh viãn. Nàng suáút åí âáy âæåüc hiãøu laì tênh âuïng âàõn cuía chæång trçnh, tênh dãù âoüc, dãù sæía, táûn duûng hãút khaí nàng cuía thiãút bë maì khäng phuû thuäüc vaìo thiãút bë. TS. PHAN HUY KHAÏNH biãn soaûn 7
8 Cäng nghãû Pháön mãöm Thæûc cháút cuía quaï trçnh láûp trçnh laì ngæåìi ta khäng láûp trçnh trãn mäüt ngän ngæî cuû thãø maì láûp trçnh hæåïng tåïi noï. Chæång trçnh phaíi âæåüc viãút dæåïi daûng caïc thao taïc coï cáúu truïc trãn caïc âäúi tæåüng coï cáúu truïc vaì caïc mãûnh âãö nhàòm khàóng âënh tênh âuïng âàõn cuía kãút quaí. Nhæîng tæ tæåíng caïch maûng trong láûp trçnh thãø hiãûn åí hai âiãøm sau : − Chæång trçnh vaì láûp trçnh viãn tråí thaình âäúi tæåüng nghiãn cæïu cuía lyï thuyãút láûp trçnh. − Laìm thãú naìo âãø laìm chuí âæåüc sæû phæïc taûp cuía hoaût âäüng láûp trçnh ? II. Caïc phæång diãûn cuía cäng nghãû pháön mãöm II.1. Cäng nghãû pháön mãöm laì gç? Theo tæì âiãøn Computer Dictionary cuía Microsoft Press® (1994), Software Engineering : The design and development of sofware (computer program), from concept through execution and documentation. Tæì âiãøn Larousse (1996) âënh nghéa chi tiãút hån : Cäng nghãû pháön mãöm laì táûp håüp caïc phæång phaïp, mä hçnh, kyî thuáût, cäng cuû vaì thuí tuûc liãn quan âãún caïc giai âoaûn xáy dæûng mäüt saín pháøm pháön mãöm. Caïc giai âoaûn âoï laì : âàûc taí (specifiction), thiãút kãú (design), láûp trçnh (programming), thæí nghiãûm (testing), sæía sai (debugging), caìi âàût (setup) âãø âem vaìo æïng duûng (application), baío trç (maintenance) vaì láûp häö så (documentation). Muûc âêch chênh cuía cäng nghãû pháön mãöm laì âãø saín xuáút ra nhæîng pháön mãöm coï cháút læåüng. Cháút læåüng pháön mãöm khäng laì mäüt khaïi niãûm âån giaín, bao gäöm nhiãöu yãúu täú. Chàóng haûn chæång trçnh chaûy nhanh, dãù sæí duûng, coï tênh cáúu truïc, dãù âoüc dãù hiãøu, v.v Ngæåìi ta thæåìng âaïnh giaï theo hai kiãøu cháút læåüng : nhæîng yãúu täú cháút læåüng bãn ngoaìi vaì nhæîng yãúu täú cháút læåüng bãn trong. II.2. Nhæîng yãúu täú cháút læåüng bãn ngoaìi vaì bãn trong Nhæîng yãúu täú cháút læåüng bãn ngoaìi ngæåìi duìng coï thãø nháûn biãút âæåüc, nhæ täúc âäü nhanh, chaûy äøn âënh, tênh dãù sæí duûng, dãù thêch nghi våïi nhæîng thay âäøi (tênh måí räüng), tênh cäng thaïi hoüc (ergonomy, human factor), v.v Nhæîng yãúu täú cháút læåüng bãn ngoaìi cuía mäüt saín pháøm pháön mãöm laì : Tênh âuïng âàõn Khaí nàng thæûc hiãûn chênh xaïc cäng viãûc âàût ra. Tênh bãön væîng Coï thãø hoaût âäüng trong nhæîng âiãöu kiãûn báút thæåìng. Tênh coï thãø måí räüng Khaí nàng dãù sæía âäøi âãø thêch nghi våïi nhæîng thay âäøi måïi
Âaûi cæång vãö cäng nghãû pháön mãöm 9 Tênh sæí duûng laûi Khaí nàng sæí duûng laûi toaìn bäü hay mäüt pháön cuía hãû thäúng cho nhæîng æïng duûng måïi. Tênh tæång thêch Coï thãø dãù daìng kãút håüp våïi caïc saín pháøm pháön mãöm khaïc. Caïc cháút læåüng khaïc Hiãûu quaí âäúi våïi nguäön taìi nguyãn cuía MTÂT nhæ bäü xæí lyï, bäü nhåï , dãù chuyãøn âäøi (khäng phuû thuäüc vaìo cáúu hçnh pháön cæïng), dãù kiãøm chæïng vaì an toaìn (âæåüc baío vãû quyãön truy nháûp), dãù sæí duûng, v.v Nhæîng yãúu täú cháút læåüng bãn trong laì laì tênh âån thãø, tênh dãù âoüc, dãù hiãøu maì chè nhæîng ngæåìi laìm Tin hocü chuyãn nghiãûp måïi biãútû âæåüc. Yãúu täú cháút læåüng bãn ngoaìi laì muûc âêch cuäúi cuìng nhæng yãúu täú cháút læåüng bãn trong laûi laì máúu chäút âãø âaût âæåüc nhæîng yãúu täú cháút læåüng bãn ngoaìi. II.3. Saín pháøm pháön mãöm laì gç ? Màûc duì ngæåìi ta khäng âënh nghéa nhæng khaïi niãûm saín pháøm pháön mãöm âæåüc hiãøu nhæ laì mäüt hãû thäöng chæång trçnh thæûc hiãûn mäüt nhiãûm vuû tæång âäúi âäüc láûp nhàòm phuûc vuû cho mäüt æïng duûng cuû thãø trong cuäüc säúng cuía con ngæåìi (vaì coï thãø âæåüc thæång maûi hoaï). Vê duû caïc saín pháøm pháön mãöm : Hãû âiãöu haình : MS − DOS, OS/2, Unix, MAC OS Hãû âiãöu haình maûng maïy tênh : Unix, Novell Netware, Windows NT vaì caïc æïng duûng trãn maûng LAN, WAN, Internet/Intranet (caïc Browsers, caïc dëch vuû khai thaïc Internet ). Caïc ngän ngæî láûp trçnh (chæång trçnh dëch) : Turbo Pascal, Turbo C, C++ Hãû quaín trë cå såí dæî liãûu : Microsoft Foxpro, Microsoft Access, Oracle, Paradox Microsoft Windows vaì caïc æïng duûng trãn Windows. Caïc troì chåi (games). Caïc pháön mãöm tråü giuïp thiãút kãú (CAD, Designers ), tråü giuïp giaíng daûy Caïc hãû chuyãn gia, trê tuãû nhán taûo, ngæåìi maïy, v.v Caïc chæång trçnh phoìng chäúng virus, v.v Dæåïi âáy laì baíng toïm tàõt quaï trçnh tiãún hoïa cuía saín pháøm pháön mãöm : Thåìi kyì âáöu tiãn Xæí lyï theo lä (Batch processing) 1950 − 1960 Pháön mãöm âæåüc viãút theo âån âàût haìng Thåìi kyì thæï hai Âa ngæåìi duìng (Multiusers) 1960 − 1970 Thåìi gian thæûc (Real time) Cå såí dæî liãûu (Database) Pháön mãöm saín pháøm TS. PHAN HUY KHAÏNH biãn soaûn 9
10 Cäng nghãû Pháön mãöm Thåìi kyì thæï ba Hãû thäúng xæí lyï phán bäø (Distributed processing system) 1970 − 1990 Thäng minh (Intelligence) Pháön cæïng giaï thaình haû Hiãûu quaí tiãu thuû Thåìi kyì thæï tæ Hãû thäúng âãø baìn (Desktop − Personal − Notebook computers) 1990 tråí âi Láûp trçnh hæåïng âäúi tæåüng (Object oriented programming) Láûp trçnh træûc quan (Visual programming) Hãû chuyãn gia (Expert system) Maûng thäng tin toaìn cáöu (Worldwide communication network) Xæí lyï song song (Paralell processing) Sau âáy laì mäüt tranh vui vãö quaï trçnh taûo ra mäüt saín pháøm pháön mãöm âaî khaï quen thuäüc âäúi våïi nhuîng ngæåìi laìm Tin hoüc tæì hån 20 nàm nay (theo J. CLAVIER, “Diriger un projet informatique”, Eïdition J. C. I. Inc, Canada 1993) : 1. Ngæåìi âàût haìng 2. Thiãút kãú cuía chuí trç âãö taìi 3. Saín pháøm cuía ngæåìi láûp trçnh Vê duû : Cäng ty Cäng viãn 4. Sau khi sæía sai våïi 5. Triãøn khai cho khaïch haìng 6. Æåïc må cuía ngæåìi sæí duûng ! nhiãöu saïng kiãún caíi tiãún Hçnh 1.1. Quaï trçnh taûo ra mäüt saín pháøm pháön mãöm
Âaûi cæång vãö cäng nghãû pháön mãöm 11 III. Nhæîng näüi dung cå baín cuía CNPM III.1. Täøng quan vãö cäng nghãû pháön mãöm Cäng nghãû pháön mãöm âàûc træng båíi táûp håüp caïc phæång phaïp âãø phaït triãøn mäüt chæång trçnh (pháön mãöm noïi chung). Sæû phaït triãøn mäüt chæång trçnh, hay tiãún trçnh pháön mãöm (software process), khäng chè nàòm åí chäù láûp trçnh theo nghéa heûp maì coìn laì viãûc triãøn khai caïc giai âoaûn dáùn âãún láûp trçnh. Táûp håüp caïc giai âoaûn naìy âæåüc goüi laì chu kyì säúng (hay voìng âåìi) cuía pháön mãöm (life cycle). Våïi mäüt dæû aïn Tin hoüc låïn, nhiãöu ngæåìi láûp trçnh tham gia âæåüc chia thaình nhoïm, mäùi nhoïm phuû traïch giaíi quyãút mäüt pháön cuía dæû aïn. Ngæåìi phuû traïch dæû aïn coï nhiãûm vuû phán bäø cäng viãûc cho tængì nhoïm, âaím baío mäúi liãn laûc giæîa caïc nhoïm, kiãøm tra tiãún trçnh phaït triãøn cuía dæû aïn, cháút læåüng cuía saín pháøm pháön mãöm khi hoaìn táút. Tiãún trçnh phaït triãøn pháön mãöm gäöm 3 giai âoaûn chênh laì xaïc âënh, phaït triãøn vaì baío trç, khäng phuû thuäüc vaìo miãún aïp duûng, âäü læïn vaì âäü phæïc taûp cuía dæû aïn phaït triãøn, cuîng nhæ mä hçnh âæåüc læûa choün. Giai âoaûn xaïc âënh : Giai âoaûn naìy traí låìi cáu hoíi laì caïi gç ? (What?) vaì khi naìo (When?) vãö dæî liãûu (thäng tin) cáön xæí lyï, muûc âêch chæïc nàng va ìmäi træåìng phaït triãøn. Gäöm 3 bæåïc : - Phán têch hãû thäúng. - Láûp kãú hoaûch dæû aïn pháön mãöm. - Phán têch yãu cáöu thæûc tiãùn. Giai âoaûn phaït triãøn : Giai âoaûn naìy traí låìi cáu hoíi laìm nhæ thãú naìo ? (How?). Gäöm 3 bæåïc : - Thiãút kãú pháön mãöm : Sæí duûng caïc cäng cuû âàûc taí vaì láûp trçnh cáúu truïc. - Choün cäng cuû hoàûc caïc ngän ngæî láûp trçnh âãø tiãún haình viãút chæång trçnh. - Kiãøm thæí (phaït hiãûn sai soït, nháöm láùn ). Giai âoaûn baío trç : Giai âoaûn naìy táûp trung vaìo caïc thay âäøi (Modify). Coï 3 kiãøu thay âäøi : - Sæía âäøi : Duì pháön mãöm coï cháút læåüng täút, váùn täön taûi nhæîng khiãúm khuyãút tæì viãcû sæí duûng cuía khaïch haìng (ngæåìi sæí duûng). Baío trç sæía âäøi laìm thay âäøi pháön mãöm, khàõc phuûc khiãúm khuyãút. - Thêch nghi : Nhàòm laìm pháön mãöm thêch nghi våïi mäi træåìng pháön cæïng, nhæ CPU, OS, caïc thiãút bë ngoaûi vi. TS. PHAN HUY KHAÏNH biãn soaûn 11
12 Cäng nghãû Pháön mãöm - Náng cao : Khaïch haìng tçm ra nhæîng chæïc nàng phuû cuía pháön mãöm. Baío trç hoaìn thiãûn âãø måí räüng pháön mãöm ra ngoaìi nhæîng chæïc nàng väún coï. III.2. Chu kyì säúng cuía pháön mãöm Coï nhiãöu mä hçnh khaïc nhau âãø thãø hiãûn mäüt chu kyì säúng (life cycle). Sau âáy laì mäüt chu kyì säúng kiãøu cäø âiãøn theo mä hçnh thaïc næåïc (“waterfall” model) gäöm caïc giai âoaûn nhæ sau : Tçm hiãøu vaì phán têch caïc yãu cáöu (RAD − Requirements analysis and definition) Thiãút kãú hãû thäúng vaì pháön mãöm (SSD − System and software design) Caìi âàût vaì kiãøm thæí tæìng pháön (IUT − Inplementtation and Unit testing) Têch håüp vaì kiãøm thæí hãû thäúng (IST − Integrgion and system testing) Tçm hiãøu vaì phán têch caïc yãu cáöu Thiãút kãú hãû thäúng vaì pháön mãöm Caìi âàût vaì kiãøm thæí tæìng pháön Têch håüp vaì kiãøm thæí hãû thäúng Hçnh 1.2. Mä hçnh thaïc næåïc Dáùu ràòng mä hçnh thaïc næåïc trãn âáy coï êch låüi trong viãûc quaín lyï (management), láûp kãú hoaûch vaì láûp baïo caïo tiãún âäü phaït triãøn pháön mãöm nhæng chè thêch håüp våïi mäüt låïp hãû thäúng pháön mãöm naìo âoï maì thäi, khäng phuì håüp våïi caïc hoaût âäüng âaî chè ra trong mä hçnh. Tiãún trçnh pháön mãöm gäöm caïc hoaût âäüng phæïc taûp vaì biãún âäüng maì khäng thãø biãøu diãùn trãn mäüt mä hçnh âån giaín. Nhæîng mä hçnh täút vãö tiãún trçnh pháön mãöm váùn coìn laì chæïng chuí âãö nghiãn cæïu. Hiãûn nay, caïc mä hçnh täøng quaït khaïc nhau hay tênh thæûc duûng cuía sæû phaït triãøn pháön mãöm, gàõn boï chàût cheî våïi nhau. Mä hçnh thaïc næåïc nguyãn thuyí (original) laì mäüt trong nhæîng mä hçnh täøng quaït mang tênh thæûc duûng sáu sàõc. Sau âáy laì mäüt säú tiãúp cáûn :
Âaûi cæång vãö cäng nghãû pháön mãöm 13 1. Tiãúp cáûn thaïc næåïc (the waterfall approach) : Bao gäöm caïc giai âoaûn âàûc taí yãu cáöu, thiãút kãú pháön mãöm, caìi âàût, kiãøm thæí, v.v , sau mäùi giai âoaûn laì sæû kãút thuïc (signed-off) vaì tiãúp tuûc giai âoaûn tiãúp theo. 2. Láûp trçnh thàm doì (exloratory programming) : Cho pheïp tàng nhanh quaï trçnh âãø dáùn âãún tênh thoía âaïng cuía hãû thäúng. Láûp trçnh thàm doì thæåìng âæåüc aïp duûng trong lénh væûc trê tuãû nhán taûo, khi NSD khäng thãø âënh hçnh âæåüc caïc âàûc taí yãu cáöu. NSD quan tám âãún tênh thoía âaïng cuía kãút quaí hån laì tênh chênh xaïc. 3. Baín máùu (prototyping) : Tæång tæû tiãúp cáûn láûp trçnh thàm doì. Pha âáöu tiãn bao gäöm phaït triãøn mäüt chæång trçnh cho pheïp thæí nghiãûm. Tuy nhiãn, muûc âêch cuía phaït triãøn laì thiãút láûp caïc yãu cáöu hãû thäúng. Sau âoï laì sæû caìi âàût laûi pháön mãöm âãø âæa âãún hãû thäúng cháút læåüng - saín pháøm. Bàõt âáöu Táûp håüp Kãút thuïc yãu cáöu vaì laìm mën Saín pháøm thiãút kãú nhanh Laìm mën xáy dæûng baín máùu baín máùu Âaïnh giaï cuía khaïch haìng vãö baín máùu Hçnh 1.3. Tiãúp cáûn kiãøu baín máùu 4. Biãún âoíi hçnh thæïc (formal transformation) : Laì sæû biãún âäøi caïc âàûc taí hçnh thæïc (formal specification) cuía hãû thäúng pháön mãöm âang xeït âãø thaình mäüt chæång trçnh khaí thi nhæng baío toaìn âæåüc tênh chênh xaïc (correctness - preserving transformations). 5. Làõp raïp hãû thäúng tæì caïc thaình pháön duìng laûi âæåüc (system assembly from reusable components). Kyî thuáût naìy cho pheïp xáy dæûng hãû thäúng tæì caïc thaình pháön âaî coï. Tiãún trçnh phaït triãøn hãû thäúng laì sæû làõp raïp hån laì sæ û saïng taûo. Hiãûn nay, caïc tiãúp cáûn 1, 2, 3 âæåüc æïng duûng nhiãöu trong thæûc tiãùn. Trãn thæûc tãú, caïc giai âoaûn phaït triãøn pháön mãöm khäng phaíi råìi riãng maì laì gäúi lãn nhau (overlap) vaì thäng tin âæåüc cung cáúp láùn nhau. Trong khi thiãút kãú, nhæîng váún âãö vaì caïc yãu cáöu gàõn boï våïi nhau, trong khi láûp trçnh, nhæîng váún âãö thiãút kãú âæåüc tçm tháúy, v.v Luïc naìy, tiãún trçnh pháön mãöm khäng âån giaín laì mäüt mä hçnh tuyãún tênh maì bao gäöm mäüt daîy caïc tæång taïc cuía caïc hoaût âäüng phaït triãøn. TS. PHAN HUY KHAÏNH biãn soaûn 13
14 Cäng nghãû Pháön mãöm Tuy nhiãn, mäüt mä hçnh chæïa caïc voìng làûp seî laìm khoï khàn cho viãûc quaín lyï vaì baïo caïo. Coï nhiãöu daûng mä hçnh trong tiãún trçnh pháön mãöm. Sau âáy laì mäüt säú mä hçnh : 1. Mä hçnh thaïc næåïc caíi tiãún Tçm hiãøu vaì phán têch caïc yãu cáöu Thiãút kãú hãû thäúng vaì pháön mãöm Caìi âàût vaì kiãøm thæí tæìng pháön Têch håüp vaì kiãøm thæí hãû thäúng Khai thaïc vaì baío trç Hçnh 1.4. Mä hçnh thaïc næåïc caíi tiãún 1. Tçm hiãøu vaì phán têch caïc yãu cáöu: NSD hãû thäúng vaì ngæåìi phaït triãøn hãû thäúng baìn baûc, trao âäøi (consultation) våïi nhau âãø thiãút láûp muûc âêch, raìng buäüc vaì caïc dëch vu cuía hãû thäúng pháön mãöm, lénh häüi âæåüc nhæîng âoìi hoíi cuía baìi toaïn. 2. Thiãút kãú hãû thäúng vaì pháön mãöm : Tiãún trçnh thiãút kãú hãû thäúng phán chia caïc yãu cáöu thaình caïc hãû thäúng pháön cæïng, pháön mãöm vaì thiãút láûp mäüt kiãún truïc hãû thäúng toaìn bäü (overall system architecture). Viãûc thiãút kãú pháön mãöm bao gäöm viãûc thãø hiãûn caïc chæïc nàng hãû thäúng pháön mãöm (software system functions) âãø biãún âäøi thaình caïc chæång trçnh khaí thi. 3. Caìi âàût vaì kiãøm thæí tæìng pháön : Trong giai âoaûn naìy, caïc âån vë chæång trçnh hay táûp håüp caïc chæång trçnh âæåüc kiãøm thæí láön læåüt sao cho thoía maîn caïc âàûc taí tæång æïng. 4. Têch håüp vaì kiãøm thæí hãû thäúng : Caïc âån vë chæång trçnh âæåüc têch håüp vaì kiãøm thæí nhæ laì mäüt hãû thäúng âáöy âuí âãø âaím baío caïc yãu cáöu âàût ra ban âáöu. Sau giai âoaûn naìy, hã û thäúng pháön mãöm âæåüc giao cho khaïch haìng. 5. Khai thaïc vaì baío trç (operation and maintenance) : Âáy laì mäüt pha daìi nháút cuía chu kyì säúng. Hãû thäúng âæåüc caìi âàût vaì âæa vaìo sæí duûng thæûc tãú. Viãûc baío trç bao gäöm viãûc khàõc phuûc nhæîng sai soït xaíy ra âaî khäng xuáút hiãûn trong caïc giao âoaûn træåïc âoï cuía chu kyì säúng. Viãûc täúi æu hoïa caïc dëch vuû cuía hãû thäúng âæåüc xem nhæ laì nhæîng yãu cáöu måïi âæåüc phaït hiãûn.
Âaûi cæång vãö cäng nghãû pháön mãöm 15 2. Mä hçnh xoàõn äúc Phaït triãøn trãn tênh æu viãût cuía voìng âåìi cäø âiãn vaì baín máùu, bäø sung nhuîng yãúu täú coìn thiãúu vaì thãm caïc yãúu täú måïi, phán têch ruíi ro. Kãú hoaûch : Phán têch ruíi ro : Dæûa trãn yãu cáöu ban âáöu Táûp håüp yãu cáöu ban âáöu va Dæûa trãn phaín æïng cuía kãú hoaûch dæû aïn khaïch haìng Quyãút âënh tiãúp tuûc Kãú hoaûch hay khäng ? dæûa trãn yï kiãún cuía khaïch haìng Hæåïng tåïi hãû thäúng hoaìn chènh Baín máùu ban âáöu Âaïnh giaï cuía khaïch haìng : Khàóng âënh kãút quaí cuía cäng nghãû Baín máùu táöng tiãúp theo . . . Hçnh 1.5. Mä hçnh xoàõn äúc Æu âiãøm : Caïc phiãn baín (hay saín pháøm) âæåüc hoaìn thiãûn dáön theo chiãöu xoaïy äúc tæì trong ra ngoaìi. Nhæåüc âiãøm : Khoï âaïnh giaï chênh xaïc, nháút laì khi gàûp ruíi ro, khoï kiãøm soaït. Do âoï khoï thuyãút phuûc âæåüc caïc khaïch haìng låïn Mä hçnh naìuy coìn måïi, chæa âæåüc kiãøm nghiãûm nhiãöu trong thæûc tiãùn. 3. Kyî thuáût thãú hãû 4 (4th Generation Technology) Bao gäöm caïc cäng cuû pháön mãöm trãn cå såí tæû âäüng saní sinh maî chæång trçnh gäúc theo nhu cáöu cuía ngæåìi phaït triãøn : Ngän ngæî phi thuí tuûc2 (non procedural language) âãø truy cáûp cå såí dæî liãûu. Bäü sinh baïo caïo. Bäü thao taïc dæî liãûu. 2 laì ngän ngæî láûp trçnh khäng tuán theo caïch goüi thuí tuûc hay goüi chæång trçnh con thäng thæåìng, khäng sæí duûng caïc cáúu truïc âiãöu khiãøn, tuáön tæû, maì dæûa trãn táûp håüp caïc yãúu täúï vaì quan hãû âãø dáùn vãö kãút quaí yãu cáöu. Vê duû ngän ngæî váún tin SQL thuäüc loaûi naìy. TS. PHAN HUY KHAÏNH biãn soaûn 15
16 Cäng nghãû Pháön mãöm Bäü tæång taïc vaì thiãút kãú maìn hçnh. Bäü sinh chæång trçnh. Baíng tênh. Cäng cuû âäö hoüa. Táûp håüp yãu cáöu Chiãún læåüc thiãút kãú Caìi âàût sæí duûng 4 GL Kiãøm thæí Hçnh 1.6. Kyî thuáût thãú hãû 4 Æu âiãøm : Thæåìng âæåüc sæí duûng âãø xáy dæûng caïc hãû thäng tin vaì tæång lai laì caïc æïng duûng kyî nghãû phaït triãøn pháön mãöm thåìi gian thæûc. Nhu Caïc PM sæí duûng kyî thuáût 4 GT cáöu (láúp chäù häøng) Nhu cáöu trung bçnh pháön mãöm Caïc phæång phaïp truyãön thäúng 1970 1980 1990 2000 Hçnh 1.7. Nhu cáöu pháön mãöm
Âaûi cæång vãö cäng nghãû pháön mãöm 17 5. Têch håüp caïc kyî thuáût Nhàòm tàng cæåìng tênh täúi æu trong phaït triãøn pháön mãöm, ngæåìi ta coï xu hæåïng têch håüp caïc kyî thuáût cäø âiãøn, xoaïy troìn äúc vaì 46T âaî nãu. Táûp håüp, hiãøu caïc yãu cáöu ban âáöu Phán têch yãu cáöu Laìm baín máuù 4 GT Mä hçnh xoaïy troìn äúc Thiãút kãú Baín máùu voìng thæï n 4 GT Maî hoaï 4 GT Mä hçnh voìng thæï n Kiãøm thæí Hãû thäúng hoaût âäüng Baío trç Hçnh 1.8. Têch håüp caïc kyî thuáût TS. PHAN HUY KHAÏNH biãn soaûn 17
CHÆÅNG 2 Thiãút kãú pháön mãöm I. Nãön taíng cuía thiãút kãú pháön mãöm TS. PHAN HUY KHAÏNH biãn soaûn 18
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 19 TS. PHAN HUY KHAÏNH biãn soaûn 19
20 Cäng nghãû Pháön mãöm II. Phæång phaïp láûp trçnh cáúu truïc
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 21 TS. PHAN HUY KHAÏNH biãn soaûn 21
22 Cäng nghãû Pháön mãöm II.1. Khaïi niãûm vãö láûp trçnh cáúu truïc Láûp trçnh cáúu truïc (Structured Programming) laì træåìng phaïi láûp trçnh xuáút hiãûn vaìo nhæîng nàm 70 vaì âæåüc duy trç phaït triãøn tæì âoï âãún nay. Láûp trçnh cáúu truïc phaín aïnh quan niãûm : láûp trçnh laì cäng viãûc saïng taûo nhæng coï tênh khoa hoüc vaì coï phæång phaïp, khäng phaíi laì ngáùu hæïng caï nhán. Tênh logic vaì trong saïng cuía chæång trçnh âaím baío âäü tin cáûy, dãù hiãøu, dãù sæía vaì dãù thæìa kãú chæång trçnh. II.2. Nhæîng yï tæåíng cå baín láûp trçnh cáúu truïc a) Chæång trçnh laì mäüt hãû thäúng phán cáúp tæì trãn xuäúng Trong láûp trçnh cáúu truïc, chæång trçnh laì mäüt hãû thäúng phán cáúp tæì trãn xuäúng, trong âoï caïc thaình pháön tæång taïc våïi nhau täúi thiãøu. Váún âãö cáön giaíi quyãút bao gäöm caïc váún âãö nhoí hån, mäùi váún âãö âoï laûi bao gäöm caïc váún âãö nhoí hån næîa, v.v cho âãún mæïc cuäúi cuìng laì nhæîng cäng viãûc âån giaín vaì dãù giaíi quyãút hoàûc âaî giaíi quyãút räöi. váún âãö viãûc 1 viãûc 2 viãûc 3 viãûc 1.1 viãûc 1.2 . . . viãûc 1.2.1 viãûc 1.2.2 viãûc 1.2.3 Hçnh 2.1. Chæång trçnh laì mäüt hãû thäúng phán cáúp
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 23 Vê duû 2 : Phán têch baìi toaïn cäüng hai phán säú âãø âæa vãö baìi toaïn tçm æåïc säú chung låïn nháút. Âãø cäüng hai phán säú, træåïc tiãn cáön æåïc læåüc chuïng, tiãúp âoï quy âäöng máùu säú âãø láúy máùu säú chung. Cuäúi cuìng tiãún haình cäüng hai tæí säú cuía hai phán säú âaî coï chung máùu säú. Viãûc æåïc læåüc phán säú âæåüc âæa vãö tçm æåïc säú chung låïn nháút cuía tæí säú vaì máùu säú (sæí duûng thuáût toaïn Euclide). Âãø quy âäöng máùu säú, cáön tçm bäüi säú chung nhoí nháút. Viãûc tçm bäüi säú chung nhoí nháút cuía hai säú laûi âæåüc âæa vãö tçm æåïc säú chung låïn nháút cuía chuïng : BSCNN(b’, d’) = b’ * d’ / ÆSCLN(b’,d’). ⎯a+ ⎯c b d ÆLPS(a/b) QÂMS(a’/b’, c’/d’) a”/M + b”/M ÆLPS(c/d) BSCNN(b’, d’) ÆSCLN(a/b) ÆSCLN(c/d) ÆSCLN(b’, d’) Hçnh 2.2. Phán têch baìi toaïn cäüng hai phán säú Nhæ váûy, chæång trçnh laì mäüt hãû thäúng gäöm nhiãöu thaình pháön phán cáúp, mäùi thaình pháön coï nhiãûm vuû giaíi quyãút mäüt váún âãö så cáúp vaì coï tênh âäüc láûp cao. Caïc thaình pháön nãn tæång taïc våïi nhau täúi thiãøu. Giæîa hai thaình pháön trong hãû thäúng chè nãn coï täúi âa mäüt âæåìng tæång taïc laì âæåìng trao âäøi thäng tin âãø dãù quaín lyï vaì dãù kiãøm soaït. • Giæîa chæång trçnh chênh vaì chæång trçnh con coï âæåìng giao tiãúp laì viãûc truyãön tham biãún. Khäng âæåüc goüi chæång trçnh con theo kiãøu væåüt cáúp. A B C TS. PHAN HUY KHAÏNH biãn soaûn 23
24 Cäng nghãû Pháön mãöm Hçnh 2.3. A goüi B, B goüi C, nhæng A khäng goüi âæåüc C • Haûn chãú duìng biãún toaìn cuûc (global variables) trong chæång trçnh con vç seî taûo thãm nhæîng âæåìng giao tiãúp khoï quaín lyï. Chàóng haûn, mäüt chæång trçnh con naìo âoï laìm thay âäøi mäüt biãún toaìn cuûc thç åí mäüt nåi khaïc, trong mäüt chæång trçnh con khaïc hoàûc ngay trong chæång trçnh chênh, cuîng seî khoï nháûn biãút sæû thay âäøi naìy. b) Khäng sæí duûng lãûnh nhaíy goto Lãûnh goto (jump statement) duìng âãø chuyãøn âiãöu khiãøn âãún mäüt âiãøm khaïc trong chæång trçnh. Lãûnh goto laìm khoï quaín lyï vaì khoï kiãøm soaït chæång trçnh nãn khoï âoüc, khoï sæía sai (räúi ràõm nhæ moïn mç såüi Spaghetti cuía YÏ). Caïc chæång trçnh viãút trãn ngän ngæî aassembly hoàûc trãn caïc ngän ngæî báûc cao nhæ Fortran, Algol, Cobol thæåìng sæí duûng lãûnh goto. Vê duû 3 : Chæång trçnh Algol sau âáy sæí duûng lãûnh goto âãø âiãöu khiãøn voìng làûp tênh täøng caïc pháön tæí cuía maíng a gäöm N säú thæûc : S := 0; I := 0; Start : S := S + a[I]; I := I + 1; if I <= N then goto Start; c) Chæång trçnh coï tênh cáúu truïc Chæång trçnh chè sæí duûng caïc cáúu truïc âiãöu kiãûn chuáøn, dãù hiãøu, dãù thãø hiãûn thuáût toaïn. Cáúu truïc cuía chæång trçnh phaín aïnh âæåüc cáúu truïc cuía váún âãö vaì caïch giaíi quyãút váún âãö (laìm nhæ thãú naìo ?). Phæång phaïp hay âæåüc sæí duûng âãø thiãút kãú chæång trçnh laì phán têch tæì trãn xuäúng (Top-Down Analysis) vaì täøng håüp tæì dæåïi lãn (Bottom up Synthesis). Näüi dung phæång phaïp phán têch tæì trãn xuäúng laì nhçn nháûn xem xeït täøng quaït toaìn bäü váún âãö, xuáút phaït tæì muûc tiãu (âènh) âi xuäúng caïc thaình pháön trong hãû thäúng, chia caïc thaình pháön thaình caïc thaình pháön nhoí hån theo mäüt cáúu truïc phán cáúp chàût cheî. Näüi dung phæång phaïp täøng håüp tæì dæåïi lãn laì xuáút phaït tæì caïc váún âãö cuû thãø vaì caïch giaíi quyãút cuû thãø, sau âoï têch håüp chuïng laûi thaình váún âãö låïn hån vaì caïch giaíi täøng quaït hån, hæåïng tæì dæåïi lãn trãn âãø nháûn âæåüc váún âãö cáön phaíi giaíi quyãút ban âáöu Caïch thiãút kãú naìy gáy khoï khàn vç khoï kiãøm soaït vaì dãù laûc hæåïng, khoï âaïp æïng âáöy âuí caïc yãu cáöu cuía váún âãö.
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 25 II.3. Caïc cáúu truïc âiãöu khiãøn chuáøn Trong chæång trçnh, chè nãn sæí duûng 7 cáúu truïc âiãöu khiãøn sau âáy våïi quy æåïc S laì mäüt lãûnh (Statement) vaì C laì mäüt biãøu thæïc âiãöu kiãûn (Condition) naìo âoï : Stt Cáúu truïc âiãöu khiãøn Læu âäö tæång âæång Mä taí 1 Tuáön tæû Âæåüc coi nhæ laì mäüt lãûnh (Sequential) S1 gheïp (khäúi), thæûc hiãûn begin tuáön tæû caïc lãûnh S1, S2, . . . S1 , Sn. . . . Sn Sn end 2 Reî nhaïnh False Nãúu C thoaí maîn (True) (Branching) C ? thç thæûc hiãûn S. True a) Reî nhaïnh thiãúu Nãúu C khäng thoaí maîn S if C then S (False) thç khäng laìm gç caí. 3 b) Reî nhaïnh âuí True False Nãúu C âuïng thç thæûc hiãûn if C then S1 C lãûnh S1. else S2 S1 S2 Nãúu C sai thç thæûc hiãûn S2. 4 Nãúu C1 âuïng thç thæûc Læûa choün True (Selection) False C1 ? S1 hiãûn S1. case True Nãúu khäng, nãúu C2 âuïng S2 C1 : S1 False C2 ? thç thæûc hiãûn S2, v.v . . . C2 : S2 . . . . . . Cuäúi cuìng, nãúu Cn âuïng True . . . thç thæûc hiãûn Sn. Cn : Sn False Cn ? Sn endcase Nãúu khäng thç thäi. 5 Cáúu truïc làûp Khi C coìn âuïng thç coìn (Iteration) False thæûc hiãûn S. C ? Kiãøm tra âiãöu kiãûn True Khi C sai thç dæìng. træåïc khi thæûc hiãûn S voìng làûp : TS. PHAN HUY KHAÏNH biãn soaûn 25
26 Cäng nghãû Pháön mãöm while C do S
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 27 Stt Cáúu truïc âiãöu khiãøn Læu âäö tæång âæång Mä taí 6 Làûp våïi kiãøm tra Coìn thæûc hiãûn S khi C coìn âiãöu kiãûn sau khi chæa thoaí maîn (sai). S thæûc hiãûn xong thán Êt nháút làûp âæåüc mäüt láön. voìng làûp : C ? False Dæìng khi C âuïng. do S until C True 7 Làûp hãút træåïc säú láön (for) i = i = False i ≤ False i ≥ True True S S i = i + Succ (i) i = i + Pred (i) for I ← Gt_Âáöu to Gt_Cuäúi do S for I ← Gt_Âáöu downto Gt_Cuäúi do S Ngoaìi caïc cáúu truïc làûp hay gàûp thäng thæåìng trãn âáy, ngæåìi ta coìn sæí duûng caïc cáúu truïc làûp coï thoaït (loop exit) nhæ sau : { sæí duûng khoaï key âãø âaïnh dáúu läúi thoaït, S1 key khäng xuáút hiãûn trong S vaì trong C } True C key := False False While not key do begin S2 S1 if C then key := True else S2 End TS. PHAN HUY KHAÏNH biãn soaûn 27
28 Cäng nghãû Pháön mãöm II.4. Mäüt säú vê duû viãút chæång trçnh theo så âäö khäúi Vê duû 4 : { Voìng làûp naìy duìng Repeat } S Repeat True S C1 Until C1 or not C2 False False C2 Chuï yï : Coï âiãöu kiãûn cuäúi voìng làûp coï thãø duìng Repeat True Vê duû 5 : True { Voìng làûp naìy duìng While } C1 False While C1 do False if C2 then S1 else S2 C2 True Chuï yï : Coï âiãöu kiãûn træåïc voìng làûp coï thãø duìng S1 S2 While Vê duû 6 : { Âáy laì cáúu truïc loop-exit, coï thãø duìng While S1 nhæ sau :} False C1 key := False True False While not key do begin C2 S1 True if not C1 then key := True S2 else if C2 then S2 End Cáúu truïc loop-exit trãn âáy co ï thãø duìng Repeat nhæ sau : key := False Repeat S1 if C1 then key := True else if C2 then S2 Until key
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 29 Vê duû 7 : { Træåìng håüp Loop-exit måí räüng. True C1 Duìng khoïa key âãø âaïnh dáúu läúi thoaït nhæ False sau :} S1 key := False True Repeat C2 If C1 then key := True False Else begin S2 S1 True C2 If C2 then key := True False Else begin S2 S3 If C3 then key := True True C4 Else begin False S3 S4 If C4 then key := True Else S4 End End End Until key III. Cáúu truïc täúi thiãøu Caïc cáúu truïc âiãöu khiãøn chuáøn laì kãút quaí cuía nhæîng cäú gàõng låïn trong cuäüc caïch maûng vãö láûp trçnh nhæîng nàm 60. Nhæîng nhaì tin hoüc coï tãn tuäøi âaî âoïng goïp cäng sæïc laì Bohm C. vaì Jacopini G., Dijkstra E.W. vaì Warier, v.v Âãø âaím baío tênh trong saïng, âån giaín vaì tæû nhiãn, ngæåìi ta khuyãn ràòng chè nãn xáy dæûng chæång trçnh våïi 3 cáúu truïc âiãöu khiãøn cå baín laì tuáön tæû, reî nhaïnh vaì làûp. Tuy nhiãn, Bohm vaì Jacopini âaî chæïng minh âæåüc ràòng chè cáön täúïi thiãøu hai cáúu truïc tuáön tæû vaì làûp laì âuí. Âënh lyï Bohm vaì Jacopini 1986 Våïi moüi chæång trçnh viãút dæåïi daûng så âäö khäúi P (Flowchart), âãöu täön taûi mäüt chæång trçnh Q tæång âæång våïi P theo nghéa sau : TS. PHAN HUY KHAÏNH biãn soaûn 29
30 Cäng nghãû Pháön mãöm Våïi moüi dæî liãûu vaìo X thuäüc miãön xaïc âënh X, ta coï P(x) = Q(x) : P vaì Q biãún âäøi nhæîng caïi vaìo giäúng nhau thaình caïc ra giäúng nhau. Caïc thao taïc trãn caïc biãún cuía Q laì giäúng nhæ cuía P. Caïc biãún cuía Q cuîng laì caïc biãún cuía P, coï thãø Q chæaï thãm mäüt säú biãún logic. Q sæí duûng hai cáúu truïc âiãöu khiãøn duy nháút laì tuáön tæû vaì voìng làûp while (SW: Sequence &While). Så âäö chuyãøn cáúu truïc nhæ sau : Case For Repeat Loop − Exit If Tuáön tæû While Hçnh 2.4. Chuyãøn vãö cáúu truïc tuáön tæû vaì làûp while (SW) Sau âáy laì caïch chuyãøn âäøi cuía caïc cáúu truïc Case, If, For, Repeat vaì Loop − Exit : 1. Case → if Case C of If C = C1 then S1 C1 : S1 else if C = C1 then S2 . . . → else if . . . Cn : Sn . . . End {Case} else if C = Cn then Sn 2. if → SW Duìng hai biãún phuû kiãøu logic âãø thæûc hiãûn voìng làûp While âuïng mäüt láön : Var p, q : Boolean If C then S p := C While p do begin → S ; p := not p End If C then S1 else S2 p := C ; q := p While p do begin → S1 ; p := not p
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 31 End; While not q do begin S2 ; q := not q End 3. Repeat → SW Repeat S until C → S ; While not C do S 4. For → SW For I:= GtÂáöu to GtCuäúi I := GtÂáöu do S → While i = GtCuäúi do do S begin S ; I := Pred (I) End III.1. Caïc cáúu truïc läöng nhau Baín thán lãûnh S trong mäùi cáúu truïc âiãöu khiãøn cå baín laûi coï thãø laì mäüt cáúu truïc âiãöu khiãøn khaïc. Vê duû 8 : Våïiï cáúuú truïcï âiãöuö kiãûnû If C then S1 else S2 Taûi S1 vaì S2, ta coï thãø âàût caïc cáúu truïc âiãöu khiãøn khaïc, chàóng hanû thãú S1 båíi : While C1 do S3 vaì thãú S2 båíi : Repeat S4 until C2 Ta coï : If C then While C1 do S3 Else Repeat S4 until C2 TS. PHAN HUY KHAÏNH biãn soaûn 31
32 Cäng nghãû Pháön mãöm Âãún læåüt S3 vaì S4 laûi coï thãø thay thãú båíi caïc cáúu truïc khaïc, v.v Våïi caïcc pheïp thãú nhæ váûy, cáúu truïc cuía chæång trçnh ngaìy caìng phæïc taûp vaì dáùn âãún khoï hiãøu vaì dãù sai soït. Chênh vç váûy maì ngæåìi ta chuï troüng triãøn khai chæång trçnh tæì trãn xuäúng vaì viãút caïc cáúu truïc theo tæìng khäúi. Caïc khäúi coï thãø thuût voìa, thuût ra âãø phaín aïnh tênh cáúu truïc vaì mæïc âäü läöng nhau cuía caïc cáúu truïc. Nguyãn tàõc : Cáúu truïc con âæåüc viãút loüt vaìo trong (thuût vaìo) cáúu truïc cha. Âiãøm vaìo vaì âiãøm ra cuía mäùi cáúu truïc phaíi nàòm trãn cuìng mätü haìng doüc. IV. Láûp trçnh âån thãø IV.1. Khaïi niãûm vãö âån thãø YÏ tæåíng cå baín cuía láûp trçnh cáúu truïc laì phán raîî váún âãö låïn thaình caïc váún âãö nhoí hån cho âãún khi nháûn âæåüc caïc váún âãö tæång âäúi âån giaín, mäùi váún âãö naìy âæåüc giaíi quyãút båíi mäüt âån thãø chæång trçnh (module). Mäùi âån thãø coï caïc tênh cháút nhæ sau : a) Tênh âån thuáön • Chè giaíi quyãút nhæîng âäúi tæåüng dæî liãûu coï liãn hãû våïi nhau trong phaûm vi cuía váún âãö. • Coï mäüt läúi vaìo vaì mäüt läúi ra, bãn trong chè duìng nhæîng cáúu truïc âiãöu khiãøn chuáøn. • Hoaût âäüng chè phuû thuäüc vaìo dæî liãûu âæa vaìo chæï khäng phuû thuäüc vaìo tçnh traûng træåïc âoï cuía noï. Mäùi âån thãø laì mäüt haìm dæî liãûu vaìo, kãút quaí tiãn âoaïn âæåüc. b) Tênh chuyãn biãût • Chè thæûc hiãûn mäüt chæïc nàng, nhiãûm vuû nháút âënh. • Khäng quaï daìi hoàûc quaï ngàõn (lyï tæåíng laì mäùi âån thãø coï tæì 60 âãún 70 doìng lãûnh væìa nàòm troün trong mäüt trang A4). • Chè âæåüc khåíi âäüng bàòng caïch goüi. c) Tênh âäüc láûp • Laì mäüt âån vë biãn dëch. Coï thãø viãút vaì chaûy thæí âäüc láûp. Caïc ngän ngæî láûp trçnh báûc cao nhæ Pascal (kyî thuáût duìng Unit), C, C++ (include caïc tãûp chæång trçnh ) vaì háöu hãû caïc cäng cuû láûp trçnh thæåìng gàûp hiãûn nay âãöu cho pheïp láûp trçnh theo âån thãø.
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 33 IV.2. Mäúi liãn hãû giæîa caïc âån thãø Caïc âån thãø näúi kãút våïi nhau thaình chæång trçnh, täø chæïc phán cáúp daûng cáy (tree). A B C D E F G Hçnh 2.5. Mäúi liãn hãû giæîa caïc âån thã ø IV.2.1.Phán loaûi âån thãø Coï 4 loaûi âån thãø : a) Âån thãø âiãöu khiãøn Âån thãø âiãöu khiãøn (Director Module) coï chæïc nàng goüi caïc âån thãø khaïc xæí lyï. b) Âån thãø xæí lyï Âån thãø xæí lyï (Pcocessing Module) chuyãn traïch mäüt nhiãûm vuû naìo âoï trãn vuìng dæî liãûu âäüc láûp. Âån thãø xæí lyï âæåüc âån thãø âiãöu khiãøn goüi tåïi vaì sau khi thæûc hiãûn xong chæïc nàng, âån thãø xæí lyï traí quyãön âiãöu khiãøn tråí laûi cho âån thãø âiãöu khiãøn. c) Âån thãø vaìo/ra Âån thãø vaìo/ra (IO Module) chuyãn traïch vaìo/ra dæî liãûu, coï sæû kiãøm tra vaì xæí lyï sai soït. Âån thãø cuîng do âån thãø âiãöu khiãøn goüi tåïi giäúng nhæ hoaût âäüng cuía âån thãø xæí lyï. d) Âån thãø chæång trçnh con (Subroutine Module) nhàòm giaíi quyãút mäüt nhiãûm vuû troün veûn nhæng coï quan hãû våïi caïc âån thãø khaïc. Âån thãø chæång trçnh con âæåüc goüi thæûc hiãûn nhiãöu láön trong chæång trçnh. IV.2.2. Täø chæïc mäüt chæång trçnh coï cáúu truïc âån thãø Cáúu truïc chæång trçnh gäöm : - Cáúu truïc näüi taûi cuía caïc âån thãø. - Mäúi liãn hãû giæîa caïc âån thãø. TS. PHAN HUY KHAÏNH biãn soaûn 33
34 Cäng nghãû Pháön mãöm Caïc âån thãø âæåüc täø chæïc phán cáúp daûng cáy nhæng phaíi thoía maîn tênh cuûc bäü tham chiãúu (locality of Reference) : chè coï âån thãø mæïc cao hån (cha) måïi coï quyãön tham chiãúu (goüi) âãún âån thãø mæïc tháúp hån kãö âoï (con). Nhæîng cáúu truïc cáy thoía maîn tênh cuûc bäü tham chiãúu âæåüc goüi laì cáúu truïc cáy thuáön tuïy (Pure tree Structure). Vê duû 9 : A − D chè phuûc vuû B, chè coï B måïi coï quyãön âiãöu khiãøn D, C khäng thãø goüi D. B C − Giæîa B vaì D chè coï mäüt âæåìng tæång taïc duy nháút laì trao âäøi D E tham biãún. Hçnh 2.6. Cáúu truïc cáy thuáön tuïy a) Âàûc âiãøm cuía cáúu truïc cáy thuáön tuïy − Mäùi âån thãø chè âæåüc quyãön âiãöu khiãøn âån thãø con træûc tiãúp, giaím âæåüc tênh phæïc taûp cuía chæång trçnh. − Caïc nhaïnh hoaìn toaìn taïch biãût nhau nãn coï tênh tæång taïc täúi thiãøu. Ngoaûi lãû : Nãúu mäüt cäng viãûc naìo âoï cáön thæûc hiãûn nhiãöu láön, nhiãöu chäù trong chæång trçnh thç nãn täø chæïc thaình mäüt âån thãø chæång trçnh con vaì veî riãng, khäng veî vaìo cáúu truïc cáy. Nhæ váûy, caïc âån thãø chæång trçnh con chè âoïng vai troì thæ viãûn, mäüt sæû måí räüng cuía ngän ngæî láûp trçnh. Træåìng håüp âån thãø chæång trçnh con phæïc taûp thç coï thãø täø chæïc theo cáúu truïc cáy thuáön tuïy. Nhæ váûy toaìn bäü chæång trçnh laì mäüt táûp håüp caïc cáúu truïc cáy thuáön tuïy. Vê du û 10 : A F G B C F1 F2 F3 G1 D E Caïc âån thãø chæång trçnh con Hçnh 2.7. Cáúu truïc cáy thuáön tuïy cuía chæång trçnh vaì chæång trçnh con
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 35 b) Thæí nghiãûm chæång trçnh trãn cáúu truïc cáy thuáön tuïy Quaï trçnh thæí nghiãûm mäüt chæång trçnh : − Thæí nghiãûm caïc âån thãø chæång trçnh con træåïc. − Thæí nghiãûm caïc âån thãø trong chæång trçnh chênh, tæì dæåïi lãn vaì riãng tæìng nhaïnh. Cáön phán biãût : − Caïc âån thãø xæí lyï phuû thuäüc vaìo ngæî caính (context) naìo, laì con cuía âån thãø naìo ? − Caïc âån thãø chæång trçnh con âäüc láûp våïi ngæî caính. Âãø thæí nghiãûm chæång trçnh cho trong hçnh veî trong vê duû åí trãn : − Thæí F vaì G træåïc (sau khi âaî thæí F1, F2, F3 vaì G1). − Thæí D vaì E räöi thæí B. − Thæí C. − Thæí caí chæång trçnh. V. Phaït triãøn chæång trçnh bàòng tinh chãú tæìng bæåïc V.1. Näüi dung phæång phaïp Nguyãn lyï phaït triãøn CHTR bàòng tinh chãú tæìng bæåïc (hay thiãút kãú tæì trãn xuäúng) do Niclaus Wirth (taïc giaí cuía ngän ngæî láûp trçnh Pascal) âãö xuáút vaìo nàm 1971, trong baìi baïo cuía mçnh "Program Development by Stepwise Refinement". Ban âáöu, CHTR laì nhæîng cáu âæåüc viãút bàòng ngän ngæî tæû nhiãn (chàóng haûn tiãúng Viãût) thãø hiãûn sæû phán têch täøng thãø cuía ngæåìi láûp trçnh. Sau âoï, taûi mäùi bæåïc, mäùi cáu âæåüc phán têch chi tiãút hån thaình nhæîng cáu khaïc. Coï nghéa âaî phán têch mäüt cäng viãûc thaình nhæîng cäng viãûc beï hån. - Mäùi cáu âæåüc goüi laì mäüt âàûc taí (Specification). - Mäùi bæåïc phán têch âæåüc goüi laì âaî tinh chãú (refine) cáu (cäng viãûc) âoï. Sæû tinh chãú âæåüc hæåïng vãö phêa ngän ngæî láûp trçnh seî duìng. Nghéa laì caìng åí bæåïc sau, nhængî cáu chæî trãn ngän ngæî tæû nhiãn caìng âån giaín dãù hiãøu hån vaì âæåüc thay thãú bàòng caïc cáu lãûnh cuía ngän ngæî láûp trçnh. Nãúu cáu coìn toí ra phæïc taûp, coï thãø coi âoï laì mäüt CHTR con vaì tiãúp tuûc tinh chãú noï. TS. PHAN HUY KHAÏNH biãn soaûn 35
36 Cäng nghãû Pháön mãöm Trong quaï trçnh tinh chãú, cáön âæa ra caïc cáúu truïc dæî liãûu tæång æïng våïi tæìng bæåïc. Nhæ váûy sæû tinh chãú caïc âàûc taí CHTR vaì dæî liãûu laì song song. Phæång phaïp tinh chãú tæìng bæåïc thãø hiãûn tæ duy giaíi quyãút váún âãö tæì trãn xuäúng, trong âoï sæû phaït triãøn cuía caïc bæåïc laì hæåïng vãö ngän ngæî láûp trçnh seî sæí duûng. Âaïy cuía sæû âi xuäúng trong hoaût âäüng phán têch laì caïc cáu lãûnh vaì caïc mä taí dæî liãûu viãút bàòng ngän ngæî láûp trçnh. YÏ nghéa : Viãûc láûp trçnh coï sæû âënh hæåïng vaì coï sæû ngàn nàõp trãn giáúy nhaïp, traïnh moì máùm thæí nghiãûm mang tênh træûc giaïc. V.2. Vê duû minh hoaû V.2.1. Vê duû 1 Nháûp vaìo daîy caïc kyï hiãûu liãn tiãúp tæì baìn phêm cho âãún khi kê tæû dáúu cháúm (.) âæåüc goî. In ra säú læåüng tæìng chæî säú tæì 0 9 âaî âoüc. Chàóng haûn, nãúu nháûp vaìo daîy : Kiki1t2047655kp412. thç in ra : säú chæî säú 0 âaî âoüc = 1, säú chæî säú 1 âaî âoüc = 2, säú chæî säú 2 âaî âoüc = 2 1. Phaïc thaío låìi giaíi Cáön in ra 10 giaï trë æïng våïi caïc chæî säú tæì 0 9. Coï thãø duìng 10 biãún âån ZERO, MOT, HAI, BA nhæng täút nháút nãn duìng mäüt maíng coï 10 pháön tæí : Säú ['0'] chæïa kê tæû '0' âaî âoüc; Säú ['1'] chæïa kê tæû '1' âaî âoüc; v.v Ta mä taí nhæ sau : Type daîy = array ['0' '9'] of integer; var sä ú = daîy; c: Char; {kyï tæû âæåüc âoüc } Tæì âoï låìi giaíi coï thãø âæåüc viãút nhæ sau : Repeat âoüc_mäüt_kê_tæû; {laì kyï tæû c } if kê_tæû_laì_chæî_säú then âãúm_chæî_säú_âoï; {vê duû, nãúu âoüc '2' thç tàng säú ['2'] lãn 1} Until c = dáúu cháúm;
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 37 for c := '0' to '9' do writeln('säú caïc chæî säú',c,'âaî âoüc =',säú [c]:2); Ta tinh chãú bæåïc kê_tæû_laì_chæî_säú bàòng caïch chuyãøn ra daûng biãøu thæïc Pascal nhæ sau : ('0' < c) and (c < = '9') Viãûc âoüc_mäüt_kê_tæû âæåüc viãút nhæ sau : Read (c); Dáúu cháúm coï thãø duìng hàòng : Const dáúu cháúm '='; Ta tháúy træåïc luïc âãúm, caïc pháön tæí cuía maíng säú phaíi bàòng 0. Ta coï : for c := '0' to '9' do säú [c] := 0; Báy giåì ta coï chæång trçnh hoaìn chènh nhæ sau : Program Âãúm chæî säú; Const dáúu cháúm = '.'; Type daîy = array ['0' '9'] of integer; Var säú: daîy; c: char; begin for c := '0' to '9' do säú [c] := 0; writeln ('Haîy goî vaìo caïc kê tæû'); writeln ('vaì kãút thuïc bàòng dáúu cháúm (.) :'); Repeat Read (c); if ('0' < = c) and (c < = '9') then säú [c] := säú [c] + 1; Until c = dáúu cháúm; for c := '0' to '9' do writeln ('Säú caïc chæî säú', c, ' âaî âoüc =', säú [c] : 2) Readln end. Cho chaûy chæång trçnh ta âæåüc kãút quaí nhæ sau : Haîy goî vaìo caïc kê tæû vaì kãút thuïc bàòng dáúu cháúm (.) : ytr7657g858450020820. Säú caïc chæî säú 0_âaî âoüc = 4 Säú caïc chæî säú 1_âaî âoüc = 0 Säú caïc chæî säú 2_âaî âoüc = 2 Säú caïc chæî säú 3_âaî âoüc = 0 Säú caïc chæî säú 4_âaî âoüc = 1 Säú caïc chæî säú 5_âaî âoüc = 3 TS. PHAN HUY KHAÏNH biãn soaûn 37
38 Cäng nghãû Pháön mãöm Säú caïc chæî säú 6_âaî âoüc = 1 Säú caïc chæî säú 7_âaî âoüc = 2 Säú caïc chæî säú 8_âaî âoüc = 3 Säú caïc chæî säú 9_âaî âoüc = 0 V.2.2. Baìi toaïn 8 quán háûu Haîy âàût 8 quán háûu lãn baìn cåì vua (coï 8 x 8 ä) sao cho khäng coï quán naìo àn âæåüc quán naìo ? Mäüt quán háûu coï thãø àn âæåüc bàõt cæï quán naìo nàòm trãn cuìng cäüt, cuìng haìng hay cuìng âæåìng cheïo thuáûn nghëch våïi noï. Baìi toaïn naìy do Call Friedrich Gauss âæa ra vaìo nàm 1850 nhæng khäng coï låìi giaíi hoaìn toaìn theo phæång phaïp giaíi têch. Lyï do laì loaûi baìi toaïn naìy khäng phuì håüp våïi caïc phæång phaïp giaíi têch maì phaíi tçm caïch khaïc âãø giaíi trãn MTÂT, coï thãø thæí âi thæí laûi nhiãöu láön. Niclaus Wirth trçnh baìy phæång phaïp thæí-sai (trial-and-error) nhæ sau : Âàût mäüt quán háûu vaìo cäüt 1 (trãn mäüt haìng tuyì yï); Âàût tiãúp mäüt quán háûu thæï hai sao cho 2 quán khäng àn nhau; Tiãúp tuûc âàût quán thæï 3, v.v Låìi giaíi coï daûng mäüt voìng làûp nhæ sau : Xeït-cäüt-âáöu; Repeat Thæí_cäüt; if an_toaìn then begin Âàût_quán_háûu_vaìo; Xeït_cäüt_kãú_tiãúp; end else Quay_laûi; until Âaî_xong_våïi_cäüt_cuäúi or Âaî_quay_laûi_quaï_cäüt_âáöu; Caïc cäng viãûc âæåüc tinh chãú dáön dáön bàòng caïch choün caïc viãûc âån giaín, coï caïch giaíi ngay âãø tiãún haình træåïc nhæ sau : Goüi baìn cåì vua 8 × 8 gäöm caïc ä (i, j) åí cäüt j, haìng i våïi j=1 8 vaì i=1 8, ta coï : Xeït_cäüt_âáöu : Bàõt âáöu våïi cäüt j=1. Xeït_cäüt_kãú_tiãpú : Tæïc laì chuyãøn qua xeït cäüt kãú tiãúp vaì chuáøn bë xeït haìng âáöu tiãn : j:= j+1; i:= 0; Âaî_xong_våïi_cäüt_cuäúi : Luïc naìy âaî xong caí 8 cäüt, quán háûu cuäúi cuìng âaî âæåüc âàût vaìo baìn cåì : thaình cäng, ta coï biãøu thæïc : j > 8
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 39 Âaî_quay_laûi_quaï_cäüt_âáöu: Tæïc laì âaî luìi quaï cäüt âáöu tiãn : tçnh traûng bãú tàõc xaíy ra : khäng tçm ra låìi giaíi ! j < 1 Thæí_cäüt : Tçm xem coï thãø âàût quán háûu taûi haìng naìo åí cäüt âang xeït. Bæåïc Thæí_cäüt seî coï daûng : repeat Xeït_mäüt_haìng ; {laì haìng thæï i } Kiãøm_tra_an_toaìn ; {khi âàût quán háûu vaìo haìng naìy } Until An_toaìn or Âaî_xeït_âãún_haìng_cuäúi; Luïc âáöu I=0, viãûc Xeït_mäüt_haìng tæïc : i:= i+1 Tæì âoï ta coï ngay Âaî_xeït_âãún_haìng_cuäiú tæïc laì : i = 8 Luïc naìy ngæåìi ta tçm caïch biãøu diãùn dæî liãûu tæång æïng vç caïc cäng viãûc âaî coï veí “mën” räöi. Theo låìi khuyãn cuía Niclaus Wirth, sæû biãøu diãùn dæî liãûu caìng trç hoaîn láu caìng täút (âãún khi khäng thãø trç hoaîn âæåüc næîa) ! Vç baìn cåì coï 8 x 8 ä nãn coï thãø nghé ngay âãún viãûc sæí duûng mäüt ma tráûn Boolean hai chiãöu âãø biãùu diãùn : Var B : array [1 8, 1 8] of Boolean; B [i, j] coï giaï trë true nãúu coï quán háûu åí haìng i, cäüt j. Tuy nhiãn, caïch biãøu diãùn naìy gáy khoï khàn cho viãûc kiãøm tra hai âæåìng cheïo coï 2 quán háûu naìo àn nhau khäng theo luáût cåì vua ? Báy giåì ta duìng 3 daîy Boolean a, b, c våïi : a [i] = true nãúu khäng täön taûi quán háûu naìo nàòm trãn haìng i. b [k] = true nãúu khäng täön taûi quán háuû naìo nàòm trãn âæåìng cheïo thuáûn thæï k. c [l] = true nãúu khäng täön taûi quán háûu naìo nàòm trãn âæåìng cheïo nghëch thæï l. Våïi mäùi ä (i, j) haìng i cäüt j, ta coï quan hãû nhæ sau : −âæåìng cheïo thuáûn thæï k thoaí maîn i + j = k; −âæåìng cheïo nghëch thæï l thoaí maîn i - j = l; Vç váûy, nãúu : 1 ≤ i, j ≤ 8 thç : 2 ≤ k ≤ 16 vaì : -7 ≤ l ≤ 7. Ta coï caïc maíng a , b , c nhæ sau : var a : array [1 8] of boolean; b : array [2 16] of boolean; c : array [-7 7] of boolean; TS. PHAN HUY KHAÏNH biãn soaûn 39
40 Cäng nghãû Pháön mãöm Âãø biãøu diãùn sæû kiãûn âàût quán háûu taûi cäüt j vaìo haìng i, ta duìng daîy nguyãn x sao cho x [j] = i nãúu nhæ coï mäüt quán háûu åí ä (i, j) : var x : array [1 8] of integer; Viãûc âàût quán háûu vaìo ä (i, j) seî laìm cho : a [i] = b [i+j] = c [i-j] = false Kiãøm_tra_an_toaìn : Cho âãún luïc naìy, chæa coï hai quán háûu naìo trong säú nhæîng quán âaî âàût lãn baìn cåì coï thãø àn láùn nhau. Âiãöu kiãûn An_toaìn âãø âàût quán háûu vaìo ä (i, j) laì : a [i] = b [i+j] = c [i-j] = true; Bàòng caïch sæí duûng mäüt biãún logic : Var Antoan: Boolean; Viãûc Kiãøm_tra_an_toaìn âæåüc dëch ra Pascal nhæ sau : An toaìn := a [i] and b [i + j] and c [i - j]; b[2] = b[i+j] c[-6] = c[i-j] 1 . . . 8 a[i], i = 1 • • 2 . . . 8 Hçnh 2.8. Baìn cåì vua cho baìi toaïn taïm quán háûu Âàût quán háûu vaìo ä (i, j) Âàût_quán_háûu_vaìo seî laì : x[j]:= i; a [i]:= false; b [i+j]:= false; c [i-j]:= false; Tiãúp tuûc tinh chãú bæåïc phæïc taûp nháút laì Quay_laûi : Quay_laûi : laì quay laûi mäüt cäüt åí træåïc cäüt âang xeït âãø âàût laûi quán háûu cho cäüt âoï khi tçnh thãú hiãûn traûng laì bãú tàõc. Bæåïc Quay_laûi coï daûng : Xeït_laûi_cäüt_træåïc; if not Âaî_quay_laûi_quaï_cäüt_âáöu then begin Boí_quán_háûu_åí_cäüt_âoï; {tæïc cäüt træåïc cäüt âang xeït, ä (i, j) } if Âang_åí_haìng_cuäúi_cuìng then begin
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 41 Xeït_laûi_cäüt_træåïc ; if not Âaî_quay_laûi_quaï_cäüt_âáöu then Boí_quán_háûu_åí_cäüt_âoï end end; Dãù daìng ta tháúy Xeït_laûi_cäüt_træåïc tæïc laì : j = j - 1; Coìn Âaî_quay_laûi_quaï_cäüt_âáöu thç âaî xeït træåïc âáy, tæïc laì : j =1 then begin i:=x[j]; a[i]:=true; b[i+j]:=true; c[i-j]:=true; if i=8 then begin TS. PHAN HUY KHAÏNH biãn soaûn 41
42 Cäng nghãû Pháön mãöm j:=j-1; if j>=1 then begin i:=x[j]; a[i]:=true; b[i+j]:=true; c[i-j]:=true end end end end until (j>8) or (j<1); if j<1 then writeln('Khong co loi giai!') else for i:=1 to 8 do begin for j:=1 to 8 do if x[j]=i then write(Hau) else write(ov); writeln end; readln end. Kãút quaí chaûy chæång trçnh nhæ sau : Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International Q # # # # # # # # # # # # # Q # # # # # Q # # # # # # # # # # Q # Q # # # # # # # # # Q # # # # # # # # # Q # # # # Q # # # # # V.3. Sæía âäøi chæång trçnh Chæång trçnh viãút xong chaûy täút chæa coï nghéa quaï trçnh láûp trçnh âaî xong. Do nhu cáöu, coï thãø cáön sæía âäøi laûi theo mäüt caïch naìo âoï cho phuì håüp. Nhåì phæång phaïp tinh chãú tæìng bæåïc maì ngæåìi láûp trçnh coï thãø dãù daìng nhçn tháúy nhæîng chäù cáön chènh sæía trong chæång trçnh. Âáy laì khaí nàng duy trç (Maintainability) cuía phæång phaïp. Mäüt âàûc tênh khaïc cuía phæång phaïp tinh chãú tæìng bæåïc laì tênh phäø cáûp (portability)) cuía chæång trçnh : ta dãù daìng chuyãøn âäøi sang mäüt mäi træåìng khaïc, tæïc laì chuyãøn sang mäüt ngän ngæî láûp trçnh khaïc, hoàûc mäüt hãû thäúng maïy tênh khaïc. Âãø minh hoaû, ta xeït baìi toaïn 8 quán háûu täøng quaït nhæ sau : Tçm táút caí caïc phæång aïn coï thãø âàût 8 quán háûu lãn baìn cåì sao cho khäng coï hai quán naìo àn láùn nhau. Tæì tinh chãú láön 1 trong muûc træåïc, ta cáön coï hai sæía âäøi nhæ sau :
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 43 − Khi âaî âãún cäüt cuäúi cuìng vaì âàût quán háûu cuäúi cuìng vaìo baìn cåì, ta in låìi giaíi ra nhæng chæa kãút thuïc chæång trçnh ngay maì tiãúp tuûc quay tråí laûi âãø tçm låìi giaíi khaïc. − Chæång trçnh ngæìng khi sæû quay laûi âaî quaï cäüt âáöu. TS. PHAN HUY KHAÏNH biãn soaûn 43
44 Cäng nghãû Pháön mãöm Låìi giaíi coï daûng phaïc thaío nhæ sau : Xeït_cäüt_âáöu; repeat Thæí_cäüt ; if An_toaìn then begin Âàût_quán_háûu_vaìo ; Xeït_cäüt_kãú ; if Cäüt_kãú_væåüt_quaï_cäüt_cuäúi_cuìng then begin In_ra_låìi_giaíi; Quay_laûi end end else Quay_laûi Until Âaî_quay_laûi_quaï_cäüt_âáöu; Tæì âáy, våïi caïc bæåïc laìm mën âaî giaíi quyãút åí muûc træåïc, ta coï thãø viãút laûi thaình chæång trçnh hoaìn chènh. Baìi toaïn maî âi tuáön Cho baìn cåì n × n ä vaì mäüt quán maî âang åí toaû âäü x0, y0. Haîy tçm caïch cho quán maî âi theo luáût cåì vua âãø qua hãút táút caí caïc ä cuía baìn cåì, mäùi ä âi qua âuïng mäüt láön ? Caïch giaíi quyãút âãø quán maî âi qua hãút n2 − 1 ä cuía baìn cåì laì taûi mäùi ä maì quán maî âang âæïng, haîy xaïc âënh xem coï thãø thæûc hiãûn mäüt næåïc âi kãú tiãúp næîa hay khäng ? Nhæ váûy thuáût toaïn âãø tçm næåïc âi kãú tiãúp coï thãø viãút thaình thuí tuûc âãû quy daûng phaïc thaío nhæ sau : Procedure Thæí_næåïc_âi_ kãú; Begin Khåíi âäüng_ næåïc_ âi_ coï_ thãø Repeat Choün_mäüt_næåïc_âi if OK then begin Thæûc_hiãûn_næåïc_âi if Chæa_hãút_næåïc then begin Thæí_næåïc_âi_kãú; if NotOK then Xoaï_næåïc_træåïc end else Thaình_cäng end Until Âi_âæåüc or (Hãút_næåïc_âi); Kãút_thuïc End;
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 45 Báy giåì ta cáön tçm cáúu truïc dæî liãûu âãø biãøu diãùn baìn cåì n × n ä, mäùi ä coï toaû âäü (i, j), våïi 1 ≤ i,j ≤ n. Dãù daìng ta tçm âæåüc mä taí nhæ sau : Type Idx = 1 n; Var H: Array[Idx, Idx] of Integer; Trong mä taí trãn, thay vç sæí duûng giaï trë kiãøu Bollean âãø âaïnh dáúu ä âoï âaî âæåüc âi qua chæa, ta âæa vaìo giaï trë kiãøu Integer âãø doì theo quaï trçnh di chuyãøn cuía quán maî theo quy æåïc nhæ sau : H[x, y] = 0 ä chæa âæåüc quán maî âi qua H[x, y] = i ä âaî âæåüc quán maî âi qua åí næåïc thæï i, 1 ≤ i ≤ n2 Âãø chè mäüt næåïc âi coï thaình cäng hay khäng, ta sæí duûng biãún Bollean q våïi quy æåïc nhæ sau : q = true næåïc âi thaình cäng q = false khäng coï næåïc âi Ta tháúy âiãöu kiãûn Chæa_hãút_næåïc âæåüc biãøu diãùn båíi biãøu thæïc : i ≤ n2 Giaí sæí goüi u, v laì toaû âäü næåïc âi kãú tiãúp cuía quán maî theo luáût cåì vua thç âiãöu kiãûn OK phaíi thoaí maîn : − Ä måïi phaíi thuäüc vaìo baìn cåì, nghéa laì 1 ≤ u ≤ n vaì 1 ≤ v ≤ n. − Quán maî chæa âi qua ä , nghéa laì H[u, v] = 0. Bàòng caïch xáy dæûng táûp håüp : Var s: set of Idx; biãøu thæïc âiãöu kiãûn OK báy giåì coï thãø viãút : (u in s) and (v in s) and H[u, v]=0 Âãø ghi nháûn næåïc âi håüp lãû Thæûc_hiãûn_næåïc_âi, ta sæí duûng pheïp gaïn : H[u, v] := i; Tæì âoï, viãûc Xoaï_næåïc_træåïc coï thãø sæí duûng pheïp gaïn : H[u, v] := 0 Âãø ghi nháûn kãút qua í låìi goüi âãû quy, ta sæí duûng biãún Bollean q1 cho biãøu thæïc âiãöu kiãûn Âi_âæåüc. Nhæ váûy, Thaình_cäng seî laì : q1 := true vaì Kãút_thuïc seî laì : q := q1 Báy giåì ta coï låìi giaíi mën hån nhæ sau : Procedure Try(i:Integer; x, y : Idx; Var q: Boolean); TS. PHAN HUY KHAÏNH biãn soaûn 45
46 Cäng nghãû Pháön mãöm Var u, v:Integer; q1: Boolean; Begin Khåíi âäüng_næåïc_âi_coï_thãø Repeat Choün mäüt_næåïc_âi if (u in s) and (v in s) and H[u, v]=0 then begin H[u, v] := i; if n cuía quán maî trãn baìn cåì, ta coï thãø coï taïm ä âæåüc âaïnh säú tæì 1 8 (theo chiãöu ngæåüc kim âäöng häö) maì quán maî coï thãø nhaíy âãún nhæ hçnh dæåïi âáy : y ⎯→ ↑ x Hçnh 2.9. Caïc vë trê khaïc nhau cuía quán maî Âãø coï âæåüc , tæì , ta cáön xaïc âënh giaï trë chãnh lãûch theo toaû âäü. Ta seî duìng hai maíng mäüt chiãöu a vaì b, mäùi maíng seî coï kêch thæåïc 8 pháön tæí, âãø læu giæî 8 giaï trë chãnh lãûch theo toaû âäü , våïi quy æåïc chiãöu âi ↑ vaì → mang dáúu +, chiãöu âi ← vaì ↓ mang dáúu −. Ta coï khai baïo nhæ sau : Var a, b: Array[1 8] of integer;
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 47 Chàóng haûn nãúu cho = våïi âiãöu kiãûn n−2 ≥ x0, y0 ≥ 3 thç ta coï thãø coï 8 càûp giaï trë nhæ sau : a[1]:= 2; b[1]:= 1; a[2]:= 1; b[2]:= 2; a[3]:= -1; b[3]:= 2; a[4]:= -2; b[4]:= 1; a[5]:= -2; b[5]:= -1; a[6]:= -1; b[6]:= -2; a[7]:= 1; b[7]:= -2; a[8]:= 2; b[8]:= -1; Báy giåì, âãø âaïnh säú caïc næåïc âi coï thãø, ta sæí duûng mäüt biãún k nguyãn, k seî nháûn giaï trë trong phaûm vi 1 8. Nhæ váûy, âáöu thuí tuûc, viãûc Khåíi âäüng_næåïc_âi_coï_thãø tæång æïng våïi lãûnh gaïn : k:= 0; Viãûc Choün mäüt_næåïc_âi tæång æïng våïi caïc lãûnh gaïn : k:= k + 1; q1:= false; u:= x + a[k]; v:= y + b[k]; Coìn biãøu thæïc âiãöu kiãûn Hãút_næåïc_âi seî tæång æïng våïi : k = 8 Thuí tuûc âãû quy âæåüc bàõt âáöu båíi toaû âäü = , kãø tæì næåïc âi k=2, caïc ä cuía baìn cåì âãöu coï thãø laì âêch cuía quán maî våïi khåíi âäüng : for i:=1 to n do for j:=1 to n do H[i, j]:= 0; Låìi goüi thuí tuûc nhæ sau : H[1, 1]:= 1; Try(2, 1, 1, q); Cuäúi cuìng laì mäüt thay âäøi nhoí bàòng caïch thãm biãún nguyãn nsq âãø tênh sqr(n) ngoaìi thuí tuûc. Chuï yï ràòng n ≥ 5. Sau âáy laì chæång trçnh hoaìn chènh : Chæång trçnh maî âi tuáön : PROGRAM KnightsTour; Uses CRT, Dos; Const NMax=50; Type Idx = 1 Nmax; Var i, j: Idx; N, Nsq: integer; q: Boolean; s: set of Idx; H: Array[Idx, Idx] of Integer; a, b: Array[1 8] of integer; gio, phut, giay, hund : Word; { Âãø tênh thåìi gian } Procedure Try(i:Integer; x, y : Idx; Var q: Boolean); TS. PHAN HUY KHAÏNH biãn soaûn 47
48 Cäng nghãû Pháön mãöm Var k, u, v:Integer; q1: Boolean; Begin k:= 0; Repeat k:= k + 1; q1:= false; u:= x + a[k]; v:= y + b[k]; if (u in s) and (v in s) and (H[u, v]=0) then begin H[u, v] := i; if i 1) and (N<Nmax) do begin { Giåì bàõt âáöu tênh } GetTime(gio, phut, giay, hund); Writeln(‘Bàõt âáöu =’, gio:2,':', phut:2,':', giay:2,':', hund); nsq:= sqr(N); s:=[1 n]; for i:=1 to n do for j:=1 to n do H[i, j]:= 0; H[1, 1]:= 1; Try(2, 1, 1, q); if q then for i:=1 to N do begin for j:=1 to N do write(h[i, j]:5); Writeln end else Writeln('Khäng coï låìi giaíi !'); { Giåì bàõt âáöu tênh } GetTime(gio, phut, giay, hund); Writeln(‘Kãút thuïc=’, gio:2,':', phut:2,':', giay:2,':', hund); Write('Cho N = '); Readln(N); End {While} End.
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 49 Sau âáy laì kãút quaí våïi N = 5 : Cho N = 5 Bàõt âáöu = 5:59:57:30 1 6 15 10 21 14 9 20 5 16 19 2 7 22 11 8 13 24 17 4 25 18 3 12 23 Kãút thuïc = 5:59:57:36 Kãút quaí våïi N = 6 : Cho N = 6 Bàõt âáöu = 6: 0:40:80 1 16 7 26 11 14 34 25 12 15 6 27 17 2 33 8 13 10 32 35 24 21 28 5 23 18 3 30 9 20 36 31 22 19 4 29 Kãút thuïc = 6: 0:41:79 TS. PHAN HUY KHAÏNH biãn soaûn 49
50 Cäng nghãû Pháön mãöm VI. Phuû luûc - Âån vë trong Turbo Pascal Âån vë (Unit) trong Turbo Pascal thãø hiãûn tênh cáúu truïc trong láûp trçnh : cho pheïp chia chæång trçnh låïn thaình mäüt hãû thäúng phán cáúp gäöm mäüt chæång trçnh chênh vaì nhiãöu âån vë chæång trçnh con. VI.1. Giåïi thiãûu Unit Unit laì táûp håüp khai baïo caïc hàòng, caïc kiãøu dæî liãûu, caïc biãún, caïc thuí tuûc vaì haìm coï quan hãû våïi nhau âãø âæa vaìo sæí duûng trong chæång trçnh chênh. Mäùi âån vë, âæåüc cáút giæî trãn thieït bë nhåï phuû (âéa tæì) dæåïi daûng mäüt tãûp chæång trçnh Pascal *.PAS vaì âæåüc dëch (compile) riãng reî. Kãút quaí dëch laì mäüt tãûp måïi coï pháön måí räüng laì *.TPU. Âãø goüi caïc Unit, trong pháön âáöu chæång trçnh sæí duûng lãûnh : USES trong pháön âáöu chæång trçnh. Thæ viãûn caïc chæång trçnh máùu Turbo Pascal coï 8 Unit chuáøn nhæ sau : System chæïa caïc haìm vaì thuí tuûc thæ viãûn thäng duûng mæïc hãû thäúng : xæí lyï tãûp, xæí lyï chuäùi, tênh caïc haìm toaïn hoüc. System âæåcü goüi màûc nhiãn maì khäng cáön khai baïo : USES System Dos cung cáúp caïc chæïc nàng cuía hãû âiãöu haình MS-DOS Crt âãø âiãöu khiãøn caïc thiãút bë vaìo (baìn phêm) vaì ra (maìn hçnh) : Goto XY, Clrscr Graph cung cáúp caïcc khaí nàng âäö hoüa (graphics) cho caïc loaûi maìn hçnh khaïc nhau : Hercule, CGA, EGA, VGA Turbo3 âãø tæång thêch våïi caïc chæång trçnh Turbo Pascal V3.0 âaî coï. Graph3 thæûc hiãûn caïc chæång trçnh con âäö hoaû theo kiãøu con ruìa (tortoise) cuía Turbo Pascal V3.0 VI.2. Cáúu truïc cuía Unit Unit do NSD taûo ra. Mäùi Unit âæåüc âàût trong mäüt tãûp chæång trçnh, gäöm nhæîng thaình pháön nhæ sau : a) Pháön tãn cuía Unit (Unit Heading) Unit
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 51 b) Pháön giao tiãúp (Interface Section) Interface { Caïc khai baïo sau âáy khäng bàõt buäüc phaíi coï } Uses Const Type Var Caïc khai baïo Const, Type vaì Var sau Interface cho Unit cuîng duìng âæåüc taûi nåi sæí duûng âån vë naìy. Ta noïi chuïng laì “tháúy âæåüc” (Visible). Danh saïch caïc tãn thuí tuûc vaì haìm âæåüc caïc Unit khaïc duìng âãún seî âæåüc khai baïo âáöy âuí trong pháön tiãúp theo : c) Pháön hiãûn thæûc (Implementation Section) Implementation { Caïc khai baïo sau âáy khäng bàõt buäüc phaíi coï } Uses Label Const Type Var Caïc mä taí haìm vaì/hoàûc thuí tuûc trong pháön naìy gäöm coï : • Caïc haìm vaì /hoàûc thuí tuûc âaî mä taí åí pháön giao tiãúp. • Caïc haìm vaì/hoàûc thuí tuûc näüi bäü duìng riãng trong pháön hiãûn thæûc (khäng khai baïo trong pháön giao tiãúp). Caïc mä taí nhaîn, hàòng, kiãøu dæî liãûu, biãún vaì caïc haìm, thuí tuûc näüi bäü trong pháön hiãûn thæûc cuía mäüt Unit laì khäng duìng âæåüc taûi nåi sæí duûng Unit naìy. Ta goüi chuïng laì “bë dáúu” (Hidden). d) Pháön khåíi âäüng (Initialization section) Begin Pháönnaìy coï thãø vàõng màût nhæng end. phaíi coï màût ! TS. PHAN HUY KHAÏNH biãn soaûn 51
52 Cäng nghãû Pháön mãöm end. Khi nåi sæí duûng mäüt Unit coï pháön khåíi âäüng Initialization thç pháön khåíi âäüng cuía Unit naìy seî âæåüc goüi chaûy træåïc khi thán cuía nåi sæí duûng chaûy. Nãúu coï mäüt nåi sæí duûng nhiãöu Unit thç pháön khåíi âäüng cuía caïc Unit âoï seî âæåüc chaûy theo thæï tæû xuáút hiãûn cuía tãn cuía caïc Unit trong khai baïo Uses cuía nåi goüi. Thæåìng thç trong pháön khåíi âäüng cuía mäüt âån vë, ngæåìi ta laìm caïc âäüng taïc chuáøn bë nhæ khåíi gaïn cho caïc biãún, måí caïc tãûp, thäng baïo chãú âäü chaûy chæång trçnh VI.3. Caïch sæí duûng Unit a) Mäüt chæång trçnh hay mäüt Unit coï thãø sæí duûng nhiãöu Unit khaïc Sæí duûng mäüt Unit coï nghéa laì âæåüc quyãön sæí duûng caïc hàòng, kiãøu dæî liãûu, biãún, caïc haìm vaì/hoàûc thuí tuûc âaî âæåüc khai baïo trong pháön giao tiãúp Interface cuía Unit âoï. Vê duû : Âãø sæí duûng caïc Units coï tãn láön læåüt laì U1, U2, , Un, duìng mãûnh âãö Uses âàût sau khai baïo Program trong chæång trçnh : Uses U1, U2, . . .,Un ; b) Khi coï mäüt sæía âäøi naìo âoï trong pháön Interface cuía mäüt Unit Khi âoï, nhæîng (tãûp) chæång trçnh hay (tãûp) Unit âoï cáön âæåüc dëch (Compile) laûi. Khi trong mäüt Unit chè coï sæû sæía âäøi åí pháön Implementation hay åí pháön Initialization thç khäng cáön dëch laûi nhæîng (tãûp) chæång trçnh hay (tãûp) Unit sæí duûng Unit âoï. Vê duû 11 : Giaí sæí chæång trçnh P goüi U1 vaì U1 sæí duûng U2 : Program P ; Unit U1 ; Unit U2 ; Uses U1 ; Interface Interface Const ⎯→ Uses U2 ; ⎯→ Const c = 10; a = b; Const b = c; Implementation Begin Implementation end. writeln (a); end. end. P.PAS U1.PAS U2.PAS Nãúu trong U2, âäøi c=5 chàóng haûn thç cáön phaíi dëch laûi U2.PAS vaì U1.PAS (vç U1 sæí duûng U2) vaì dëch laûi P.PAS.
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 53 c) Truìng tãn hàòng, biãún, kiãøu dæî liãûu vaì tãn CT con (haìm, thuí tuûc) Âãø pháön biãût, ngæåìi ta âàût træåïc tãn truìng âoï tãn Unit coï chæïa tãn naìy vaì caïch mäüt dáúu cháúm (.). Riãng chæång trçnh chênh (khai baïo Program) thç khäng cáön. Vê duû 12 : Giaí sæí chæång trçnh P sæí duûng caïc Unit U1 vaì U2. Nãúu trong P, trong Interface cuía U1 vaì U2 âãöu coï khai baïo biãún i thç âãø phán biãût i naìo laì cuía P, i naìo laì cuía U1 vaì U2 ngæåìi ta viãút : i {i cuía P} U1.i {i cuía U1} U2.i {i cuía U2} VI.4. Vê duû vãö Unit Viãút chæång trçnh tênh nhiãöu láön diãûn têch hçnh troìn våïi baïn kênh nháûp vaìo tæì baìn phêm, cho âãún khi baïn kênh nháûp vaìo laì 0 thç dæìng. Goüi chæång trçnh chênh laì HINHTRON vaì Unit sæí duûng âãø tênh diãûn têch hçnh troìn laì DTHTRON, ta coï : Program HINHTRON ; {Tãûp HINHTRON.PAS} Uses Crt, DTHTRON ; Var bk : Real ; Begin Write (‘Säú Pi = ‘, Pi) ; {hàòng Pi khai baïo trong Unit DTHTRON} Repeat Write (baïn kênh =) ; Readln (bk) ; if bk > 0 then Writeln (‘Diãûn têch = ‘, Dientich (bk) ) ; Until bk = 0 End. {HINHTRON} Unit DTHTRON ; {Tãûp DTHTRON.PAS} Interface Const Pi = 3.1415926535 ; {1/π = 0.318309886} Function Dientich (R : Real) : Real; Implementation Function Dientich; Begin Dientich := Pi * Sqr (R) End; Begin {pháön khåíi âäüng Inilialization} TS. PHAN HUY KHAÏNH biãn soaûn 53
54 Cäng nghãû Pháön mãöm Writeln (‘trong chæång trçnh chênh seî sæí duûng Unit DTHTRON !’) End.
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 55 VI.5. Baìi táûp 1. Sæí duûng caïc cáu lãûnh Pascal âãø viãút chæång trçnh theo så âäö khäúi dæåïi âáy bàòng caïch chè sæí duûng caïc cáúu truïc âiãöu khiãøn cå baín. Sau âoï haîy âäøi vãö daûng chæång trçnh chè sæí duûng ba cáúu truïc âiãöu khiãøn laì tuáön tæû, âiãöu kiãûn if then else vaì làûp While. 1. 2. True False C1 C1 False True S1 S1 S2 True False False C2 C2 C3 False True True 3. 4. True True S1 C1 C2 False False True C1 False S1 S2 S2 True C2 False 5. 6. S1 S1 True True C1 C1 False False S3 C2 S2 S2 True C3 S3 C2 False False True True S4 C3 False C4 False True TS. PHAN HUY KHAÏNH biãn soaûn 55
56 Cäng nghãû Pháön mãöm 7. 8. S1 S1 True C1 S2 False S2 S3 True True C2 C1 False False S3 S4 True False C3 C2 False True S4 S5 S6 2. Xæí lyï chuäùi (string) : Viãút chæång trçnh âoüc mäüt cáu (kãút thuïc båíi Enter ↵) sau âoï tiãún haình caïc cäng viãûc : • Thäúng kã säú tæì, säú kyï tæû trong cáu. • Taïch cáu ra thaình caïc tæì caïch nhau båíi dáúu caïch (space). In ra caïc tæì naìy. • Neïn cáu (boí caïc dáúu caïch giæîa caïc tæì). In kãút quaí. • Thay thãú nhæîng xuáút hiãûn cuía cáu con S1 thaình cáu con S2 vaì in kãút quaí. (S1 vaì S2 laì caïc cáu con nháûp vaìo) Yãu cáöu sæí duûng Unit cho mäùi viãûc. Chæång trçnh chênh duìng menu âãø goüi. 3. Viãút chæång trçnh xæí lyï ma tráûn vuäng A cáúp n x n dæåïi daûng menu, gäöm caïc viãûc sau : • Âoüc vaoì ma tráûn vuäng cáúp n x n. • Tênh âënh thæïc cuía ma tráûn. • Kiãøm tra tênh âäúi xæïng qua âæåìng cheïo chênh cuía ma tráûn. • Xaïc âënh xem ma tráûn coï daûng tam giaïc trãn khäng ? (caïc pháön tæì phêa dæåïi âæåìng cheïo chênh âãöu = 0) • Xaïc âënh xem ma tráûn coï daûng tam giaïc dæåïi khäng ? (caïc pháön tæì phêa trãn âæåìng cheïo chênh âãöu = 0) Yãu cáöu duìng Unit. Bäún viãûc sau cuìng chè coï hiãûu læûc khi ma tráûn âaî âæåüc âoüc.
Nãön taíng cuía thiãút kãú pháön mãöm Phæång phaïp láûp trçnh cáúu truïc 57 CHÆÅNG 3 Håüp thæïc hoïa pháön mãöm I. Xaïc minh vaì håüp thæïc hoïa pháön mãöm Ngæåìi ta thæåìng phán biãût 2 yãúu täú trong hoaût âäüng saín xuáút pháön mãöm : 1. Xáy dæûng âàûc taí, láûp trçnh vaì láûp häö så (viãút caïc hæåïng dáùn sæí duûng v.v ) Yãúu täú naìy taûo nãn giai âoaûn phaït triãøn chæång trçnh. 2. Xaïc minh (hay kiãøm tra) vaì håüp thæïc hoïa caïc saín pháøm pháön mãöm laì viãûc so saïnh caïc saín pháøm pháön mãöm âoï våïi caïc âàûc taí cuía chuïng sao cho coï quan hãû thoía maîn. Ngæåìi ta duìng thuáût ngæî xaïc minh (verification) khi so saïnh mäüt saín pháøm våïi mäüt âàûc taí chàût cheî (rigourous). Khi âàûc taí laì khäng hçnh thæïc (informal), ngæåìi ta duìng thuáût ngæî håüp thæïa hoïa (validation). Giai âoaûn xaïc minh vaì håüp thæïc hoïa, goüi tàõt laì giai âoaûn V & V (Verification and Validation) bao giåì cuîng coï màût trong moüi dæû aïn Tin hoüc. Sæû khaïc nhau cå baín giæîa V & V âæåüc Boehm B.W. (1979) toïm tàõt nhæ sau : Validation : Are we building the right product? Verification : Are we building the product right? Static verification Detailed Requirement High-level Formal Program verification design verification design Prototype Dynamic verification Hçnh 3.1. Kyî thuáût ténh vaì kyî thuáût âäüng cuía quaï trçnh V&V TS. PHAN HUY KHAÏNH biãn soaûn 57
58 Cäng nghãû Pháön mãöm Âãø thæûc hiãûn quaï trçnh V&V, ngæåìi ta sæí duûng caïc kyî thuáût ténh (static techniques) vaì âäüng (dynamic techniques) âãø kiãøm tra hãû thäúng. Kyî thuáût ténh nhàòm phán têch biãøu diãùn hãû thäúng qua viãûc phán têch yãu cáöu, phán têch thiãút kãú vaì hiãøn thë (listing) chæång trçnh. Kyî thuáût âäüng laì viãûc thæí nghiãûm(testing) chæång trçnh Kyî thuáût ténh bao gäöm viãûc thanh tra (inspection) chæång trçnh, phán têch vaì xaïc minh hçnh thæïc (formal verification) hay chæïng minh sæû âuïng âàõn (prouving) cuía chæång trçnh. II. Chæïng minh sæû âuïng âàõn cuía chæång trçnh Phæång phaïp chæïng minh laì sæí duûng caïc âënh lyï âãø minh hoüa tênh âuïng âàõn cuía saín pháøm cáön xaïc minh. Phæång phaïp naìy khäng coï khaí nàng håüp thæïc hoïa caïc âàûc taí phi hçnh thæïc, båíi vç khäng thãø chæïng minh mäüt caïch toaïn hoüc caïc tênh cháút khäng âæåüc âënh nghéa chàût cheî. Ngæåìi ta phán biãût caïc pheïp chæïng minh hçnh thæïc, âæåüc diãùn taí trong lyï thuyãút logic, vaì caïc chæïng minh phi hçnh thæïc nhæng chàût cheî, nhæ trong caïc cuäún saïch vãö Toaïn hoüc. Moüi pheïp chæïng minh hçnh thæïc tênh âuïng âàõn cuía chæång trçnh âæåüc xáy dæûng mäüt caïch tæåìng minh tæì caïc tiãn âãö vaì caïc quy tàõc suy diãùn logic. Thæûc tiãùn cho tháúy khäng thãø xáy dæûng mäüt pheïp chæïng minh nhæ váûy maì khäng sæí duûng âãún nhuîng cäng cuû nhæ laì caïc cäng cuû chæïng minh âënh lyï. Nhæîng pheïp chæïng minh hçnh thæïc cho caïc chæång trçnh cåî haìng ngaìn doìng lãûnh âaî âæåüc thæûc hiãûn. Chuïng cho pheïp khàóng âënh tênh âæåüc phã phaïn cuía chæång trçnh. Trong pheïp chæïng minh khäng hçnh thæïc, ngæåìi ta âënh nghéa kiãún truïc täøng quan cuía pheïp chæïng minh, xæí lyï nhæîng âiãøm khoï khàn, âãø laûi cho ngæåìi âoüc sæû chàm soïc chi tiãút âãún caïc âiãøm khaïc. Vê duû âãø chæïng minh khäng hçnh thæïc sæû âuïng âàõn cuía mäüt chæång trçnh, ngæåìi ta coï thãø diãùn taí caïc táút biãún cuía voìng làûp vaì cuía thuí tuûc âãû quy. Mäüt pheïp chæïng minh phi hçnh thæïc khäng cáön thiãút phaíi sæí duûng cacï cäng cuû, váún âãö laì ngæåìi âoüc seî tæû kiãøm chæïng thäng qua caïc cuäüc trao âäøi, thaío luáûn (chàóng haûn täø chæïc thanh tra càn cæï trãn viãûc xaïc minh). Ngæåìi ta coìn coï thãø thæí chæïng minh phi hçnh thæïc caïc tênh cháút âaî phaït biãøu êt nhiãöu coï tênh chàût cheî (chàóng haûn âãö cáûp âãún váún âãö håüp thæïc hoïa), khaïi niãûm chæïng minh tênh âuïng âàõn theo nghéa Toaïn hoüc âæåüc thay thãú båíi khaïi niãûm biãûn luáûn (reasonig - argumentation) nhàòm thuyãút phuûc caïc chuyãn gia Tin hoüc.
Error! Reference source not found. 59 II.1. Suy luáûn Toaïn hoüc Trong lénh væûc suy luáûn Toaïn hoüc, ngæåìi ta thæåìng âàût ra hai váún âãö : 1. Khi naìo thç mäüt suy luáûn laì âuïng ? 2. Coï thãø sæí duûng nhuîng phæång phaïp naìo âãø xáy dæûng caïc suy luáûn Toaïn hoüc ? Suy luáûn Toaïn hoüc laì mäüt hçnh thæïc tæ duy maì tæì mäüt hay nhiãöu mãûnh âãö logic âaî coï (phaïn âoaïn) ruït ra âæåüc mäüt mãûnh âãö logic måïi. Kãút quaí cuaí mäüt suy luáûn naìo âoï phaíi laì âuïng hoàûc laì sai. Trong Toaïn hoüc, âënh lyï laì mäüt phaït biãøu coï thãø chæïng minh âæåüc laì âuïng. Ngæåìi ta hay gàûp mä hçnh chæïng minh mäüt âënh lyï Toaïn hoüc (laì âuïng) nhæ sau : Âënh lyï Mãûnh âãö Hãû quaí Bäø âãö Âënh âãö, tiãn âãö Hçnh 3.2. Chæïng minh mäüt âënh lyï Toaïn hoüc II.1.1. Caïc quy tàõc suy luáûn Toaïn hoüc Âãø trçnh baìy caïc quy tàõc suy luáûn Toaïn hoüc, chuïng ta nhàõc laûi caïc pheïp toaïn logic sau : ¬ not (khäng) ∧ and (vaì) ∨ or (hoàûc) → implicate (keïo theo) ∼ equivalence (tæång âæång) Chuï yï : a → b tæång âæång våïi ¬a ∨ b, hay if a then b else true a ∼ b coï nghéa (a → b) ∧ (b → a). Thæï tæû æu tiãn cuía caïc pheïp toaïn logic laì ¬, ∧, ∨, →, ∼. Baíng logic nhæ sau : a b ¬a a ∧ b a ∨ b a → b a ∼ b 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 Âãø chæïng minh mäüt âënh lyï, ngæåìi ta sæí duûng mäüt säú tiãn âãö vaì quy tàõc suy luáûn, hay laì caïc hàòng âuïng. Baíng dæåïi âáy trçnh baìy caïc quy tàõc suy luáûn âæåüc sæí duûng trong chæïng minh tênh âuïng âàõn cuía chæång trçnh. TS. PHAN HUY KHAÏNH biãn soaûn 59
60 Cäng nghãû Pháön mãöm Stt Quy tàõc suy Tãn goüi Vê du û luáûn 1 p Luáût khàóng âënh Nhaûc cuía Trënh Cäng Sån hay. Váûy nhaûc ∴p ∨ q cuía Trënh Cäng Sån hay hoàûc ca sé Khaïnh Ly haït hay. 2 p ∧ q Luáût ruït goün Thaïng naìy tråìi nàõng haûn vaì säng Âaì thç caûn ∴p næåïc. Váûy tråìi nàõng haûn. 3 p → q Luáût taïch råìi Nãúu cåm chên thç cáön tàõt læía. p (Modus Ponens) Cåm âaî chên. ∴q Váûy cáön tàõt læía. 4 p → q Luáût phuí âënh Nãúu màût tråìi åí âènh âáöu thç boïng ngàõn nháút. ¬ q (Modus Tollens) Boïng khäng ngàõn nháút. ∴¬ p Váûy màût tråìi khäng åí âènh âáöu 5 p → q Tam âoaûn luáûn Nãúu tråìi mæa thç âæåìng HP bë ngáûp. q → r giaí âënh Nãúu âæåìng HP bë ngáûp thç phaíi xuäúng xe dàõt ∴p → r bäü. Váûy tråìi mæa thç phaíi xuäúng xe dàõt bäü. 6 p ∨ q Tam âoaûn luáûn Cu Tyï thuäüc baìi hoàûc laì cu Tyï ham chåi . ¬ p chuyãøn Maì Cu Tyï khäng thuäüc baìi. ∴ q Váûy cu Tyï ham chåi. Trong baíng trãn, dáúu ∴ âæåüc âoüc laì váûy thç. Mäùi luáût (cå såí cuía pheïp suy luáûn), chàóng haûn luáût taïch råìi (Modus Ponens), coï thãø viãút dæåïi daûng hàòng âuïng : (p ∧ (p → q)) → q II.1.2. Khaïi niãûm vãö chæïng minh tênh âuïng âàõn cuía chæång trçnh Mäüt chæång trçnh P xaïc âënh mäüt thuáût toaïn cho pheïp nháûn vaìo mäüt táûp håüp dæî liãûu L âãø âæa ra mäüt táûp håüp kãút quaí R. Noïi caïch khaïc, våïi moüi d ∈ L, chæång trçnh P xaïc âënh hoàûc mäüt daîy hæîu haûn caïc pheïp tênh âãø cho ra mäüt kãút quaí P(d) ∈ R, hoàûc mäüt daîy vä haûn caïc pheïp tênh : chæång trçnh bë “quáøn” våïi dæî liãûu d. Màût khaïc, P âæåüc viãút âãø tênh mäüt haìm f naìo âoï tæì D ⊆ L vaìo R. P âuïng nãúu vaì chè nãúu P tênh âuïng haìm f, nghéa laì nãúu ∀ d ∈ D, P(d) xaïc âënh (P khäng quáøn våïi dæî liãûu vaìo d) vaì bàòng f(d). Thäng thæåìng, âãø kiãøm tra tênh âuïng âàõn cuía chæång trçnh, ngæåìi ta duìng phæång phaïp thæí (test) : ngæåìi ta choün mäüt daîy caïc dæî liãûu máùu d1, d2, , dn, räöi cho P chaûy láön læåüt våïi mäùi dæî liãûu âãø kiãøm tra ràòng P(d1) = f(d1), P(d2) = f(d2), , P(dn) = f(dn).
Error! Reference source not found. 61 Tênh khäng âáöy âuí cuía phæång phaïp naìy thãø hiãûn åí chäù khäng thãø thæí hãút moüi dæî liãûu cuía D, duì D hæîu haûn : coï thãø xaíy ra P cho kãút quaí âuïng våïi moüi dæî liãûu máùu di âaî choün nhæng våïi mäüt dæî liãûu d ≠ di ∀ i, P cho mäüt kãút quaí sai. Hån næîa, phæång phaïp thæí khäng bao giåì chæïng minh âæåüc mäüt chæång trçnh laì âuïng âàõn, chè coï thãø chæïng minh âæåüc laì khäng âuïng, nãúu våïi mäüt giaï trë di naìo âoï âaî choün, thç P(d1) ≠ f(d1). Vãö màût lyï thuyãút, phæång phaïp chæïng minh tênh âuïng âàõn cuía chæång trçnh mang tênh Toaïn hoüc bàòng caïch chæïng minh mäüt âënh lyï tæång âæång : ∀d ∈ D, P(d) = f(d). II.1.3. Tiãn âãö vaì quy tàõc suy diãùn Mäüt caïch täøng quaït, caïc phaït biãøu cáön chæïng minh coï daûng E{P}S, trong âoï E vaì S laì caïc âiãöu kiãûn, P laì daîy caïc lãûnh (hay laì mäüt chæång trçnh) theo nghéa ràòng : nãúu E âuïng træåïc khi thæûc hiãûn P thç nãúu P dæìng, S âuïng sau khi thæûc hiãûn P. Ngæåìi ta goüi E laì âiãöu kiãûn træåïc (precondition) vaì S laì âiãöu kiãûn sau (postcondition) cuía chæång trçnh P. Caïc âiãöu kiãûn træåïc E vaì âiãöu kiãûn sau S âæåüc xáy dæûng tæì caïc biãøu thæïc logic coï thãø nháûn giaï trë âuïng (1) hoàûc sai (0), chuïng laì mäúi liãn hãû giæîa caïc biãún cuía chæång trçnh (vê duû caïc biãún a, b, c, p, q, r trong caïc biãøu thæïc a = bq + r, q ≥ 0, b2 − 4ac > 0, v.v ) cuìng caïc pheïp toaïn logic (nãúu coï). Tênh cháút : Våïi moüi chæång trçnh P vaì moüi âiãöu kiãûn C, ta âãöu coï : false {P} C vaì C {P} true Viãûc chæïng minh nãúu mäüt chæång trçnh P dæìng thç P seî cho kãút quaí âuïng âæåüc goüi laì chæïng minh tênh âuïng âàõn tæìng pháön. Trong caïc chæïng minh tênh âuïng âàõn tæìng pháön, caïc tiãn âãö vaì âënh lyï seî laì caïc phaït biãøu coï daûng E {P} S. Sau âáy laì danh saïch caïc tiãn âãö vaì caïc quy tàõc suy diãùn cho pheïp chæïng minh caïc âënh lyï daûng E {P} S. Âãø chæïng minh caïc quan hãû giæîa caïc âiãöu kiãûn (vê duû E1 ~ E2, E1 → E2, v.v ), ngæåìi ta sæí duûng caïc tênh cháút cuía âaûi säú Boole vaì miãön xaïc âënh caïc biãún chæång trçnh (säú nguyãn trong træåìng håüp Div). TS. PHAN HUY KHAÏNH biãn soaûn 61
62 Cäng nghãû Pháön mãöm a) Tiãn âãö vãö pheïp gaïn Cho pheïp gaïn x := vaì mäüt âiãöu kiãûn sau S, ta coï tiãn âãö : E {x := } S trong âoï E nháûn âæåüc tæì S bàòng pheïp thãú caïc biãún x båíi biãøu thæïc . E laì âiãöu kiãûn yãúu nháút phaíi laìm thoaí maîn caïc biãún træåïc khi thæûc hiãûn pheïp gaïn sao cho S laì âuïng sau âoï. Vê duû û 1 (xy ≥ 0) { z := x*y } (z ≥ 0) (q + 1 ≥ 0) { q := q + 1 } (q ≥ 0) ( (x+y)2 = y) { x := x + y } (x2 = y) Chuï yï quan troüng : Nhåì quy tàõc trãn âáy, ngæåìi ta coï thãø chæïng minh âiãöu kiãûn træåïc cuía mäüt lãûnh gaïn, bàòng caïch sæí duûng mäüt âiãöu kiãûn sau, nhæng ngæåüc laûi laì khäng thãø. Båíi váûy, âãø chæïng minh tênh âuïng âàõn cuía chæång trçnh, ngæåìi ta xuáút phaït tæì âiãøm kãút thuïc (âiãöu kiãûn sau) âãø tiãún haình ngæåüc lãn âiãøm bàõt âáöu (âiãöu kiãûn træåïc). b) Quy tàõc “;” hay täø håüp caïc lãûnh vaì lãûnh gheïp Goüi E, F, S laì caïc âiãöu kiãûn, P vaì Q laì caïc daîy lãûnh, ta coï : E {P} F E {P} S F {Q} S ∴ E { begin P end } S ∴ E {P ; Q} S Vê duû û 13 : Chæïng minh (x=1) { y:= 2; Z:= x + y} (Z=3) Laì âuïng âàõn våïi khàóng âënh âáöu E ≡ (x = 1) Vaì khàóng âënh cuäúi S ≡ (z = 3) Giaí sæí S âuïng, tæïc z = 3, khi âoï nháûn âæåüc x + y = 3, ta coï : (x+y=3) { Z:= x + y} (Z=3) (1) Do y âæåüc gaïn giaï trë 2, nãn nháûn âæåüc giaï trë cuía x laì 1, tæïc laì : (x=1) { y:= 2} (x+y=3) (2) Váûy theo quy tàõc “;”, tæì (1) vaì (2) ta coï P kãtú thuïc thç S âuïng (âpcm). II.1.4. Quy tàõc âiãöu kiãûn if B then P E ∧ B {P} S E ∧ ¬B → S ∴ E { if B then P } S
Error! Reference source not found. 63 Chuï yï : B phaíi âæåüc xem nhæ mäüt âiãöu kiãûn sao cho coï thãø æïng duûng mäüt trong nhæîng quy tàõc âæåüc trçnh baìy åí âáy. Âiãöu naìy coï nghéa ràòng viãûc tênh B khäng laìm thay âäøi caïc giaï trë cuía caïc biãún cuía chæång trçnh. Vê duû û 2 : Chæïng minh : E{if x>y then y:=x} (y ≥ x), våïi E laì âiãöu kiãûn âáöu naìo âoï. Khi E âuïng vaì x > y âuïng (âiãöu kiãûn B) thç y coï giaï trë x, váûy y ≥ x (S) , ta coï : E ∧ (x>y) { y:= x } (y ≥ x) (1) Khi E âungï vaì x > y sai (¬B) coï nghéa x ≤ y, váûy y ≥ x (S), tæïc laì : E ∧ (x ≤ y) → (y ≥ x) (2) Váûy tæì (1) vaì (2) ta coï nháûn âæåüc âpcm. II.1.5. Quy tàõc âiãöu kiãûn if B then P else Q E ∧ B {P} S E ∧ ¬B {Q} S ∴ E { if B then P else Q } S Vê duû û 3 : Chæïng minh : E {if x < 0 then abs:= -x els abs:= x}(abs = |x|) våïi E laì âiãöu kiãûn âáöu naìo âoï. Váûy chæång trçnh laì âuïng våïi âiãöu kiãûn âáöu E vaì âiãöu kiãûn sau abs = |x|. Khi E âuïng vaì x < 0 âuïng (B) thç abs coï giaï trë −x, tæïc abs = −x = |x| vaì âiãöu kiãûn sau S âuïng, ta coï : E ∧ x < 0 { abs:= -x }(abs = |x|) (1) Khi E âuïng vaì coï x < 0 sai (¬B) thç x ≥ 0, khi âoï abs coï giaï trë x tæïc abs = x = |x| vaì âiãöu kiãûn sau S âuïng, tæïc laì : E ∧ x < 0 { abs:= x }(abs = |x|) (2) Váûy tæì (1) vaì (2) ta coï nháûn âæåüc âpcm. II.1.6. Quy tàõc voìng làûp while E ∧ B { P } E ∴ E { while B do P } E ∧ ¬B ÅÍ âáy, E vaì B laì nhuîng âiãöu kiãûn. Riãng âiãöu kiãûn E âæåüc goüi laì báút biãún cuía voìng làûp. TS. PHAN HUY KHAÏNH biãn soaûn 63
64 Cäng nghãû Pháön mãöm Mäüt trong nhæîng khoï khàn cuía viãûc chæïng minh tênh âuïng âàõn cuía chæång trçnh laì tçm âæåüc báút biãún cho mäùi voìng làûp (nghéa laì mäüt báút biãún cho pheïp chæïng minh âuïng caïi yãu cáöu). Thæûc tãú khäng täön taûi mäüt phæång phaïp coï tênh hãû thäúng vaì täøng quan âãø tçm ra nhæîng báút biãún nhæ váûy. Vê duû û 4 : Sæí duûng báút biãún cuía voìng làûp, chæïng minh âoaûn chæång trçnh tênh fac = n!, våïi n ∈ Ν sau âáy : i := 1; fac := 1; while i < n do begin i := i + 1; fac := fac * i end; Goüi P ≡ {begin i:= i + 1; fac := fac * i end } Giaí sæí âiãuö kiãûn E ≡ (fac = i!) ∧ (i ≤ n), ta cáön chæïng minh E laì báút biãún cuía voìng làûp. Ta seî chæïng minh bàòng quy naûp : E âuïng træåïc khi vaìo voìng làûp, vç i = 1, fac = 1 = 1! Vaì 1 ≤ n. Giaí sæí E âuïng våïi i < n sau khi thæûc hiãûn voìng làûp vaì sau âoï, while coìn âæåüc thæûc thi mäüt láön næîa. Træåïc hãút i âæåüc tàng thãm 1 (våïi lãûnh gaïn i:= i + 1) vaì do váûy váùn coìn i ≤ n. Do giaí thiãút quy naûp fac = (i − 1) ! træåïc khi vaìo voìng làûp nãn fac seî coï giaï trë laì : fac = (i − 1)! * i = i! Tæì âoï E quaí tháût laì báút biãún cuía voìng làûp vaì mãûnh âãö : (E ∧ (i < n)) {P} E âuïng. Tæì âoï suy ra khàóng âënh : E { while i < n do P } E ∧ (i ≥ n) cuîng âuïng. Vç voìng làûp kãút thuïc sau khi làûp n − 1 láön, khi âoï i = n vaì fac = n!. II.1.7. Caïc quy tàõc khaïc Quy tàõc âiãöu kiãûn træåïc : Quy tàõc “vaì” : E {P} S E {P} S E’ → E E {P} S’ ∴ E’ {P} S ∴ E {P} S ∧ S’
Error! Reference source not found. 65 Quy tàõc âiãöu kiãûn sau : Quy tàõc “hoàûc” : E {P} S E {P} S S → S’ E’ {P} S ∴ E {P} S’ ∴ E ∨ E’ {P} S ∧ S’ Vê duû5û : Chæïng minh chæång trçnh con P tênh têch hai säú nguyãn m vaì n laì âuïng : P ≡ function product(m, n: Integer): Integer; begin {P1 ≡} if n < 0 then a:= −n else a:= n; {P2 ≡} k:= 0; x:= 0; {P3 ≡} while k < a do begin x:= x + m; k:= k + 1 end; {P4 ≡} if n < 0 then product:= −x else product:= x end; Ta seî chæïng minh ràòng sau khi thæûc hiãûn P thç haìm traí vãö giaï trë laì mn. Ta chia P gäöm bäún âoaûn CT laì {P1; P2; P3; P4} nhæ trãn. Goüi E laì âiãöu kiãûn âáöu E ≡ «m, n nguyãn» vaì S1 ≡ E ∧ (a = |n|). Khi âoï coï thãø chè ra E {P1} S1 laì âuïng. Goüi S2 ≡ S1 ∧ (k = 0) ∧ (x = 0). Dãù daìng kiãøm tra ràòng S1 {P2} S2 laì âuïng. Ta cuîng tháúy âiãöu kiãûn (x = mk) ∧ (k ≤ a) laì mäüt báút biãún trong voìng làûp P3 tæång tæû våïi lyï luáûn quy naûp trong voìng làûp tênh n!. Voìng làûp naìy kãút thuïc sau a bæåïc làûp khi k = a, tæïc x = ma taûi âiãøm naìy. Goüi S3 ≡ (x = ma) ∧ (a = [n]). Tæì âoï suy ra S2 {P3} S3 laì âuïng. Cuäúi cuìng coï thãø chè ra P4 laì âuïng våïi âiãöu kiãûn âáöu S3 vaì âiãöu kiãûn cuäúi S, våïi S ≡ product = mn. Váûy S3 {S4} S âuïng vaì haìm traí vãö giaï trë laì mn. Tæì caïc mãûnh âãö E {P1} S1, S1 {P2} S2, S2 {P3} S3 vaì S3 {S4} S laì âuïng, theo quy tàõc håüp thaình, ta coï P cuîng âuïng, tæïc E { P } S âuïng. Ngoaìi ra do caí P1, P2, P3 vaì P4 âãöu dæìng nãn P cuîng dæìng . (qed) TS. PHAN HUY KHAÏNH biãn soaûn 65
66 Cäng nghãû Pháön mãöm II.2. Phæång phaïp cuía C.A.R. Hoare II.2.1. Phaït biãøu Sau âáy laì mäüt vê duû sæí duûng phæång phaïp cuía C.A.R. Hoare : Div : r:=a; q:= 0; while r >= b do begin r:= r - b; q:= q + 1; end; a, b, q, r laì caïc biãún nguyãn, a vaì b âæåüc khåíi gaïn giaï trë âáöu láön læåüt laì A vaì B. Våïi A ∈ N vaì B ∈ N+, haìm Div tênh thæång q vaì säú dæ r cuía pheïp chia A cho B. Nhæ váûy våïi haìm Div ta coï : D = N × N+, R = N × N vaì f laì haìm xaïc âënh trãn N × N+ vaìo trong N × N, nghéa laì tæì càûp (A, B) ∈ N × N+, xaïc âënh càûp (q, r) ∈ N × N sao cho A = Bq + r vaì r 0) {Div} (A=Bq+r) ∧ (q≥0) ∧ (r≥0) ∧ (r 0) {Div} (A=Bq+r) ∧ (q≥0) ∧ (r≥0) ∧ (r 0) Q1 = (A=Bq+r) ∧ (q≥0) ∧ (r≥0) (r 0) vaì P1 ∧ (a=bq+r) ∧ (q≥0) ∧ (r≥0) ∧ (r<b) → Q1
Error! Reference source not found. 67 Theo caïc quy tàõc âiãöu kiãûn træåïc vaì âiãöu kiãûn sau, chè cáön chæïng minh : (I) P1 ∧ (a≥0) ∧ (b>0) {Div} P1 ∧ (a=bq+r) ∧ (q≥0) ∧ (r≥0) ∧ (r 0) {Div} (a=bq+r) ∧ (q≥0) ∧ (r≥0) ∧ (r 0) {Div} (a=bq+r) ∧ (q≥0) ∧ (r≥0) ∧ (r<b) Âàût : P3 = (a=bq+r) ∧ (q≥0) ∧ (r≥0) P4 = (a=b(q+1)+r) ∧ (q+1≥0) ∧ (r≥0) bàòng caïch thay q trong P3 båíi q+1 P5 = (a=b(q+1)+r−b) ∧ (q+1≥0) ∧ (r−b ≥0) bàòng caïch thay r trong P4 båíi r−b (2.1.) Ta xem ràòng P3 laì mäüt báút biãún cuía voìng làûp. Theo quy tàõc gaïn : P4 { q := q + 1 } P3 vaì P5 { r := r − b } P4 Tæì âoï theo quy tàõc täø håüp : (3) P5 { r := r − b ; q := q + 1 } P3 TS. PHAN HUY KHAÏNH biãn soaûn 67
68 Cäng nghãû Pháön mãöm Xeït âiãöu kiãûn træåïc, ta coï : (i) P5 ~ (a=bq+r) ∧ (q≥ −1) ∧ (r≥b) (ii) Vç ràòng : (q≥0) → (q≥ −1) vaì (r≥0) ∧ (r≥b) → (r≥b), ta coï : P3 ∧ (r≥b) → (a=bq+r) ∧ (q≥ −1) ∧ (r≥b) Theo quy tàõc âiãöu kiãûn træåïc, phaït biãøu (3) seî laì : P3 ∧ (r≥b) { r := r − b ; q := q + 1 } P3 Theo quy tàõc voìng làûp dáùn âãún : (4) P3 { while r≥b do begin r := r − b ; q := q + 1 end } P3 ∧ (r 0) {Div} P3 ∧ (r<b) Tæì vaì âaî chæïng minh, suy ra (I) theo quy tàõc “vaì”, âäöng thåìi kãút thuïc viãûc chæïng minh tênh âuïng âàõn tæìng pháön cuía Div.
Error! Reference source not found. 69 II.3. Chæïng minh dæìng II.3.1. Chæïng minh dæìng cuía mäüt chæång trçnh Mäüt chæång trçnh khäng laì âãû quy, khäng chæïa lãûnh goto seî chè coï thãø mäüt daîy vä haûn tênh toaïn nãúu noï thæûc hiãûn vä haûn láön thán mäüt voìng làûp. Viãûc chæïng minh mäüt chæång trçnh nhæ váûy dæìng våïi moüi dæî liãûu d ∈ D dáùn âãún viãûc chæïng minh ràòng mäùi voìng làûp cuía chæång trçnh chè coï thãø thæûc hiãûn mäüt säú hæîu haûn láön ∀ d∈D. Cho voìng làûp : while B do P våïi x1, x2, , xn laì caïc biãún cuía chæång trçnh. Goüi WE laì táûp håüp caïc giaï trë cuía vectå : w = sao cho caïc biãún thoaí maîn âiãöu kiãûn E. Giaí thiãút ràòng âiãöu kiãûn E laì báút biãún våïi voìng làûp âang xeït vaì thoaí maîn træåïc khi thæûc hiãûn voìng làûp naìy. Nãúu w = w1 ∈ WE ∧ B træåïc khi thæûc hiãûn voìng làûp, khi âoï w = w2 ∈ WE sau khi thæûc hiãûn thán voìng làûp P. Nãúu w2 ∈ WE ∧ ¬B, voìng làûp dæìng ; nãúu khäng w = w3 ∈ WE, sau khi thæûc hiãûn P, v.v Nhæ váûy âãø chæïng minh voìng làûp dæìng, chè cáön chè ra ràòng moüi daîy w1, w2, w3, âaî xáy dæûng laì hæîu haûn. Phæång phaïp âãø chæïng minh laì âënh nghéa mäüt haìm m tæì WE ∧ B vaìo N sao cho coï thãø chè ra ràòng : E ∧ B ∧ (m(w) = m0) { P } ¬B ∧ (m(w) < m0) ∀ m0 ∈ N Chuï yï : Phaït biãøu trãn coï nghéa ràòng nãúu w = wi træåïc khi thæûc hiãûn P, thç sau khi thæûc hiãûn P, hoàûc voìng làûp dæìng, hoàûc m(wi+1) < m(wi). Trong træåìng håüp naìy (âaî chæïng minh âæåüc P dæìng), ta coï thãø khàóng âënh ràòng våïi moüi daîy w1, w2, w3, , daîy m(w1), m(w)2, m(w)3 giaím dáön thæûc sæû trong N, laì hæîu haûn. Âiãöu âoï chæïng minh ràòng daîy w1, w2, w3, laì hæîu haûn, vaì voìng làûp dæìng. TS. PHAN HUY KHAÏNH biãn soaûn 69
70 Cäng nghãû Pháön mãöm II.3.2. Chæïng minh dæìng cuía Div Div chè chæïa mäüt voìng làûp : while r ≥ b do begin r := r − b ; q := q +1 end Voìng làûp naìy luän luän dæìng. Âiãöu kiãûn { b=B } laì mäüt báút biãún cuía voìng làûp naìy, âæåüc thoaí maîn træåïc khi thæûc thãø voìng làûp (xem chæïng minh âuïng tæìng pháön muûc ). Tæång tæû nhæ váûy âäúi våïi âiãöu kiãûn (r ≥ 0) (xem ). Ta xeït táûp håüp W1 = W(b = B) ∧ (r ≥ 0) ∧ (r ≥ b) vaì haìm m : W1 → N sao cho m(w) = r. Chuï yï : Viãûc choün haìm naìy dáùn viãûc chæïng minh dæìng âãún viãûc chæïng minh ràòng biãún r nháûn caïc giaï trë giaím ngàût vaì liãn tuûc. Âàût : P6 = (b=B) ∧ (r≥0) ∧ (r≥b) Tiãúp theo, ta coìn phaíi chæïng minh ràòng : (1) P6 ∧ (r=m0) { r := r − b ; q := q + 1 } (r 0) Âiãöu kiãûn B>0 luän luän âuïng vç ràòng (A, B) ∈ D = N × N+, nhæ váûy : (b=B) ∧ (r=m0) ∧ (r−b<m0) ~ (b=B) ∧ (r=m0) Tæì âoï dáùn âãún (1) xuáút phaït tæì (2). Viãûc chæïng minh Div dæìng âaî xong. Chuï yï : Âãø chæïng minh Div dæìng våïi ∀ d ∈ D, noïi chung khäng aïp duûng âæåüc cho ∀d∈L. Vê duû nãúu L = Z × Z, Div coï thãø quáøn våïi B = 0.
Error! Reference source not found. 71 II.3.3. Âaïnh giaï mäüt chæång trçnh làûp Âaïnh giaï mäüt chæång trçnh P laì xaïc âënh thåìi gian vaì kêch thæåïc bäü nhåï cáön thiãút âãø thæûc hiãûn chæång trçnh P : • mäüt haìm TP : L → R ∪ {+∞} sao cho, ∀ d ∈ L, TP(d) laì thåìi gian thæûc hiãûn P âäúi våïi dæî liãûu d (TP(d) = +∞ nãúu chæång trçnh quáøn). • mäüt haìm NP : L → N ∪ {+∞} sao cho, ∀ d ∈ L, NP(d) laì säú âån vë bäü nhåï cáön thiãút âãø thæûc hiãûn P âäúi våïi dæî liãûu d (NP(d) coï thãø vä haûn nãúu chæång trçnh quáøn). ÅÍ âáy, ta chè quan tám âãún viãûc xaïc âënh thåìi gian thæûc hiãûn chæång trçnh gäöm caïc lãûnh cå såí nhæ lãûnh gaïn (quy tàõc “;”), lãûnh âiãöu kiãûn vaì voìng làûp while. Ta seî goüi fP laì haìm riãng pháön (partial function) cuía L trong táûp håüp caïc kãút quaí R, âæåüc tênh båíi chæång trçnh P, vaì W laì táûp håüp Wtrue caïc giaï trë coï thãø cuía caïc biãún trong P. Haìm fP coï thãø måí räüng thaình mäüt haìm W → W. Tæång tæû, nãúu P’ laì mäüt daîy caïc lãûnh cuía P, haìm fPdc tênh båíi P coï thãø âæåüc âënh nghéa nhæ laì mäüt haìm cuía W → W. Vê duû û 14 : Trong træåìng håüp Div, nãúu L = D, W = N × N + × N × N = táûp håüp caïc giaï trë coï thãø cuía a, b, r, q. fDiv (a, b, r, q) = (a, b, thæång cuía a vaì b, pháön dæ cuía a chia cho b). Nãúu xeït lãûnh q := q + 1 cuía Div : fq := q+1 (a, b, r, q) = (a, b, q+1, r). Thåìi gian thæûc hiãûn mäüt chæång trçnh coï thãø âæåüc âënh nghéa nhæ sau : 1. Mäùi lãûnh cå såí vaì mäùi âiãöu kiãûn coï mäüt thåìi gian thæûc hiãûn âäüc láûp våïi giaï trë cuía caïc biãún. Nhæ váûy, ∀ w ∈ W : Våïi moüi pheïp gaïn x := y, Tx := y (w) = constant. Ta viãút Tx := y. Våïi moüi âiãöu kiãûn B, TB (w) = constant. Ta viãút TB. 2. TP ; Q (w) = TP (w) + TQ (fp(w)) 3. Tif B then P (w) = if B then (TB + TP(w)) else TB Tif B then P else Q (w) = if B then (TB + TP(w)) else (TB+ TQ(w)) n(w)−1 4. T (w) = (n(w) + 1) T + i while B do P B ∑ T(PPfw( )) i0= TS. PHAN HUY KHAÏNH biãn soaûn 71