Tài liệu Lập trình nâng cao

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