TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT
F7G
GIAÙO TRÌNH
KYÕ
THUAÄT
LAÄP
TRÌNH
NAÂNG
CAO
TRAÀN HOAØNG THOÏ
2002
Kyõ thuaät laäp trình naâng cao
- 2 -
MUÏC LUÏC
LÔØI NOÙI ÑAÀU........................................................................................................................4
PHAÀN I....................................................................................................................................5
CHÖÔNG I.............................................................................................................................5
I. MÔÛ ÑAÀU...........................................................................................................................5
1. Moâ taû ñeä quy................................................................................................................5
2. Caùc loaïi ñeä quy............................................................................................................6
II. MOÂ TAÛ ÑEÄ QUY CAÙC CAÁU TRUÙC DÖÕ LIEÄU...................................................................7
III. MOÂ TAÛ ÑEÄ QUY GIAÛI THUAÄT........................................................................................7
1. Giaûi thuaät ñeä quy..........................................................................................................7
2. Chöông trình con ñeä quy..............................................................................................8
3. Maõ hoùa giaûi thuaät ñeä qui trong caùc ngoân ngöõ laäp trình. .............................................11
4. Moät soá daïng giaûi thuaät ñeä quy ñôn giaûn thöôøng gaëp . ..............................................13
CHÖÔNG II...........................................................................................................................16
I. CAÙC NOÄI DUNG CAÀN LAØM ÑEÅ TÌM GIAÛI THUAÄT ÑEÄ QUY CHO MOÄT BAØI TOAÙN. .....16
1. Thoâng soá hoaù baøi toaùn...............................................................................................16
2. Phaùt hieän caùc tröôøng hôïp suy bieán (neo) vaø tìm giaûi thuaät cho caùc tröôøng hôïp naøy.16
3. Phaân raõ baøi toaùn toång quaùt theo phöông thöùc ñeä quy. ..............................................16
II. MOÄT SOÁ BAØI TOAÙN GIAÛI BAÈNG GIAÛI THUAÄT ÑEÄ QUY ÑIEÅN HÌNH...........................17
1. Baøi toaùn thaùp Haø Noäi . ...............................................................................................17
2. Baøi toaùn chia thöôûng..................................................................................................19
3. Baøi toaùn tìm taát caû caùc hoaùn vò cuûa moät daõy phaàn töû.................................................21
4. Baøi toaùn saép xeáp maûng baèng phöông phaùp troän (Sort-Merge)..................................24
5. Baøi toaùn tìm nghieäm xaáp xæ cuûa phöông trình f(x)=0 . ...............................................25
CHÖÔNG III..........................................................................................................................28
I. CÔ CHEÁ THÖÏC HIEÄN GIAÛI THUAÄT ÑEÄ QUY................................................................28
II. TOÅNG QUAN VEÀ VAÁN ÑEÀ KHÖÛû ÑEÄ QUY.....................................................................32
III. CAÙC TRÖÔØNG HÔÏP KHÖÛ ÑEÄ QUY ÑÔN GIAÛN. .........................................................33
1. Caùc tröôøng hôïp khöû ñeä quy baèng voøng laëp . ............................................................33
2. Khöû ñeä quy haøm ñeä quy arsac..................................................................................41
3. Khöû ñeä quy moät soá daïng thuû tuïc ñeä quy thöôøng gaëp. ...............................................45
Phaàn II ..................................................................................................................................52
CHÖÔNG IV..........................................................................................................................52
I. CAÙC GIAI ÑOAÏN TRONG CUOÄC SOÁNG CUÛA MOÄT PHAÀN MEÀM.................................52
1) Ñaëc taû baøi toaùn ..........................................................................................................52
2) Xaây döïng heä thoáng....................................................................................................52
3) Söû duïng vaø baûo trì heä thoáng......................................................................................53
II. ÑAËC TAÛ.........................................................................................................................53
1. Ñaëc taû baøi toaùn...........................................................................................................53
2. Ñaëc taû chöông trình (ÑTCT).......................................................................................54
3. Ñaëc taû ñoaïn chöông trình ..........................................................................................55
III. NGOÂN NGÖÕ LAÄP TRÌNH..............................................................................................57
CHÖÔNG V..........................................................................................................................59
I. CAÙC KHAÙI NIEÄM VEÀ TÍNH ÑUÙNG.................................................................................59
II. HEÄ LUAÄT HOARE (HOARES INFERENCE RULES)....................................................59
1. Caùc luaät heä quaû (Consequence rules).......................................................................60
Traàn Hoaøng Thoï
Khoa Toaùn - Tin
Kyõ thuaät laäp trình naâng cao
- 3 -
2. Tieân ñeà gaùn (The Assignement Axiom) .....................................................................61
3. Caùc luaät veà caùc caáu truùc ñieàu khieån . ........................................................................61
III. KIEÅM CHÖÙNG ÑOAÏN CHÖÔNG TRÌNH KHOÂNG COÙ VOØNG LAËP..............................64
IV. KIEÅM CHÖÙNG ÑOAÏN CHÖÔNG TRÌNH COÙ VOØNG LAËP............................................68
1. Baát bieán......................................................................................................................68
2. Lyù luaän quy naïp vaø chöùng minh baèng quy naïp..........................................................70
3. Kieåm chöùng chöông trình coù voøng laëp while..............................................................71
CHÖÔNG VI.........................................................................................................................76
I. CAÙC KHAÙI NIEÄM...........................................................................................................76
1. Ñaët vaán ñeà. ................................................................................................................76
2. Ñònh nghóa WP(S,Q)...................................................................................................76
3. Heä quaû cuûa ñònh nghóa...............................................................................................76
4. Caùc ví duï....................................................................................................................77
II. TÍNH CHAÁT CUÛA WP....................................................................................................77
III. CAÙC PHEÙP BIEÁN ÑOÅI TAÂN TÖØ....................................................................................78
1. Toaùn töû gaùn (tieân ñeà gaùn)..........................................................................................78
2. Toaùn töû tuaàn töï...........................................................................................................78
3. Toaùn töû ñieàu kieän.......................................................................................................79
4. Toaùn töû laëp.................................................................................................................80
IV. LÖÔÏC ÑOÀ KIEÅM CHÖÙNG HÔÏP LYÙ VAØ CAÙC ÑIEÀU KIEÄN CAÀN KIEÅM CHÖÙNG............84
1. Löôïc ñoà kieåm chöùng. .................................................................................................84
2. Kieåm chöùng tính ñuùng................................................................................................85
3. Taäp toái tieåu caùc ñieàu kieän caàn kieåm chöùng................................................................93
PHU LUÏC..............................................................................................................................96
I. LOGIC TOAÙN..................................................................................................................96
II. LOGIC MEÄNH ÑEÀ..........................................................................................................96
1. Phaân tích....................................................................................................................96
2. Caùc lieân töø logic. ........................................................................................................97
3. YÙnghóa cuûa caùc lieân töø Logic. Baûng chaân trò. .............................................................97
4. Lyù luaän ñuùng..............................................................................................................98
5. Töông ñöông (Equivalence)......................................................................................99
6. Tính thay theá, tính truyeàn vaø tính ñoái xöùng...............................................................100
7. Baøi toaùn suy dieãn logic.........................................................................................100
8. Caùc luaät suy dieãn (rules of inference)......................................................................102
III. LOGIC TAÂN TÖØ. .........................................................................................................103
1. Khaùi nieäm.................................................................................................................103
2. Caùc löôïng töø logic....................................................................................................105
3. Taäp hôïp vaø taân töØ.....................................................................................................107
4. Caùc löôïng töø soá hoïc.................................................................................................107
Traàn Hoaøng Thoï
Khoa Toaùn - Tin