Giáo trình kỹ thuật lập trình nâng cao

TRƯỜNG ĐẠI HỌC ĐÀ LẠT 
F 7 G 
GIÁO TRÌNH 
KỸ THUẬT LẬP TRÌNH 
 NÂNG CAO 
TRẦN HOÀNG THỌ 
2002 
 Kỹ thuật lập trình nâng cao - 2 - 
MỤC LỤC 
LỜI NÓI ĐẦU ........................................................................................................................4 
PHẦN I....................................................................................................................................5 
CHƯƠNG I .............................................................................................................................5 
I. MỞ ĐẦU ...........................................................................................................................5 
1. Mô tả đệ quy ................................................................................................................5 
2. Các loại đệ quy ............................................................................................................6 
II. MÔ TẢ ĐỆ QUY CÁC CẤU TRÚC DỮ LIỆU...................................................................7 
III. MÔ TẢ ĐỆ QUY GIẢI THUẬT........................................................................................7 
1. Giải thuật đệ quy..........................................................................................................7 
2. Chương trình con đệ quy..............................................................................................8 
3. Mã hóa giải thuật đệ qui trong các ngôn ngữ lập trình. .............................................11 
4. Một số dạng giải thuật đệ quy đơn giản thường gặp . ..............................................13 
CHƯƠNG II ...........................................................................................................................16 
I. CÁC NỘI DUNG CẦN LÀM ĐỂ TÌM GIẢI THUẬT ĐỆ QUY CHO MỘT BÀI TOÁN. .....16 
1. Thông số hoá bài toán. ..............................................................................................16 
2. Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.16 
3. Phân rã bài toán tổng quát theo phương thức đệ quy. ..............................................16 
II. MỘT SỐ BÀI TOÁN GIẢI BẰNG GIẢI THUẬT ĐỆ QUY ĐIỂN HÌNH. ..........................17 
1. Bài toán tháp Hà Nội . ...............................................................................................17 
2. Bài toán chia thưởng. .................................................................................................19 
3. Bài toán tìm tất cả các hoán vị của một dãy phần tử.................................................21 
4. Bài toán sắp xếp mảng bằng phương pháp trộn (Sort-Merge). .................................24 
5. Bài toán tìm nghiệm xấp xỉ của phương trình f(x)=0 . ...............................................25 
CHƯƠNG III ..........................................................................................................................28 
I. CƠ CHẾ THỰC HIỆN GIẢI THUẬT ĐỆ QUY................................................................28 
II. TỔNG QUAN VỀ VẤN ĐỀ KHỬû ĐỆ QUY.....................................................................32 
III. CÁC TRƯỜNG HỢP KHỬ ĐỆ QUY ĐƠN GIẢN. .........................................................33 
1. Các trường hợp khử đệ quy bằng vòng lặp . ............................................................33 
2. Khử đệ quy hàm đệ quy arsac..................................................................................41 
3. Khử đệ quy một số dạng thủ tục đệ quy thường gặp. ...............................................45 
Phần II ..................................................................................................................................52 
CHƯƠNG IV..........................................................................................................................52 
I. CÁC GIAI ĐOẠN TRONG CUỘC SỐNG CỦA MỘT PHẦN MỀM .................................52 
1) Đặc tả bài toán ..........................................................................................................52 
2) Xây dựng hệ thống ....................................................................................................52 
3) Sử dụng và bảo trì hệ thống ......................................................................................53 
II. ĐẶC TẢ .........................................................................................................................53 
1. Đặc tả bài toán...........................................................................................................53 
2. Đặc tả chương trình (ĐTCT).......................................................................................54 
3. Đặc tả đoạn chương trình ..........................................................................................55 
III. NGÔN NGỮ LẬP TRÌNH..............................................................................................57 
CHƯƠNG V..........................................................................................................................59 
I. CÁC KHÁI NIỆM VỀ TÍNH ĐÚNG. ................................................................................59 
II. HỆ LUẬT HOARE (HOARES INFERENCE RULES). ...................................................59 
1. Các luật hệ quả (Consequence rules) .......................................................................60 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 3 - 
2. Tiên đề gán (The Assignement Axiom) .....................................................................61 
3. Các luật về các cấu trúc điều khiển . ........................................................................61 
III. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH KHÔNG CÓ VÒNG LẶP. .............................64 
IV. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH CÓ VÒNG LẶP. ...........................................68 
1. Bất biến......................................................................................................................68 
2. Lý luận quy nạp và chứng minh bằng quy nạp. .........................................................70 
3. Kiểm chứng chương trình có vòng lặp while. .............................................................71 
CHƯƠNG VI.........................................................................................................................76 
I. CÁC KHÁI NIỆM. ..........................................................................................................76 
1. Đặt vấn đề. ................................................................................................................76 
2. Định nghĩa WP(S,Q)...................................................................................................76 
3. Hệ quả của định nghĩa...............................................................................................76 
4. Các ví dụ. ...................................................................................................................77 
II. TÍNH CHẤT CỦA WP....................................................................................................77 
III. CÁC PHÉP BIẾN ĐỔI TÂN TỪ....................................................................................78 
1. Toán tử gán (tiên đề gán). .........................................................................................78 
2. Toán tử tuần tự...........................................................................................................78 
3. Toán tử điều kiện. ......................................................................................................79 
4. Toán tử lặp. ................................................................................................................80 
IV. LƯỢC ĐỒ KIỂM CHỨNG HỢP LÝ VÀ CÁC ĐIỀU KIỆN CẦN KIỂM CHỨNG............84 
1. Lược đồ kiểm chứng. .................................................................................................84 
2. Kiểm chứng tính đúng. ...............................................................................................85 
3. Tập tối tiểu các điều kiện cần kiểm chứng. ...............................................................93 
PHU LỤC ..............................................................................................................................96 
I. LOGIC TOÁN..................................................................................................................96 
II. LOGIC MỆNH ĐỀ..........................................................................................................96 
1. Phân tích ....................................................................................................................96 
2. Các liên từ logic. ........................................................................................................97 
3. Ýnghĩa của các liên từ Logic. Bảng chân trị. .............................................................97 
4. Lý luận đúng. .............................................................................................................98 
5. Tương đương (Equivalence). .....................................................................................99 
6. Tính thay thế, tính truyền và tính đối xứng...............................................................100 
7. Bài toán suy diễn logic.........................................................................................100 
8. Các luật suy diễn (rules of inference). .....................................................................102 
III. LOGIC TÂN TỪ. .........................................................................................................103 
1. Khái niệm.................................................................................................................103 
2. Các lượng từ logic ....................................................................................................105 
3. Tập hợp và tân tưØ.....................................................................................................107 
4. Các lượng từ số học.................................................................................................107 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 4 - 
LỜI NÓI ĐẦU 
 Giáo trình được viết theo nội dung môn học “ Kỹ thuật lập trình nâng cao” với mục 
đích làm tài liệu tham khảo chính cho môn học. 
 Giáo trình gồm 2 phần chính và  ... hàng ngày . 
 Luật ==>E thường được gọi là modusponens (tam đoạn luận). Nó nói rằng có q 
nếu chứng minh được p và p ==> q . 
 Luật not_I nói rằng nếu xuất phát từ giả định p mà có mâu thuẫn thì cho ta kết 
luận not p . Cùng với luật này , cần bổ sung thêm luật về loại trừ trung gian true 
 p or not p 
 được phát biểu như tiên đề (tức là luật suy diễn không cần tiền đề). 
III. LOGIC TÂN TỪ. 
1. Khái niệm 
 Trong logic mệnh đề , mỗi mệnh đề có giá trị xác định hoặc là T (đúng) hoặc là 
F (sai) . Trong thực tế người ta hay gặp và cần làm việc với những khẳng định mà tính 
đúng sai của nó phụ thuộc vào các đối tượng thực sự được thay thế . 
 Ví dụ xét phát biểu sau : “ x là số nguyên tố “. 
 Gọi mệnh đề này là P(x), đây là một mệnh đề mà tính đúng sai của nó chỉ 
được xác định hoàn toàn khi ta "thế" một giá trị hằng cho "biến" x. 
 Ví dụ P(5) là T (dúng) , P(6) là F (sai) . 
 Trong logic tân từ , người ta phát biểu các mệnh đề bằng cách sử dụng những 
khái niệm sau: 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 104 - 
 a) Các hằng: là các đối tượng cụ thể tồn tại trong lĩnh vực mà người ta đang 
khảo sát . 
 Ví dụ : + Các hằng số 5,6,10.2,... 
 + Các hằng logic T(đúng) , F(sai) 
 Trong trường hợp tổng quát ,người ta thường đại diện cho các hằng bằng các 
chữ cái viết thường ỏ đầu bảng từ vựng: a,b,c...,a1 ,b1 , c1 ,... 
 b) Các biến (Variable): là các tên tượng trưng . Mỗi biến được ấn định một 
miền giá trị là tập các đối tượng mà nó có thể nhận. 
 Ví dụ: + Các biến số nguyên n, j , k ,. . . với các tập trị là các tập con của 
tập số nguyên Z . 
 + Các biến số thực x, y, z, . với các tập trị là các tập con của tập số 
thực R . 
 + Các biến véc tơ V, W, . . . với các tập trị là các tập con của tập tích 
ĐềCác R X R X R X ... X R ( Rn ) 
 Thường dùng các chữ cái viết thường ở cuối bảng từ vựng để biểu thị các biến : 
x,y,z,...,x1 ,y1 ,z1 ,... Từ dây về sau ,mỗi biến nếu không được nói rõ đều được xem là 
biến nguyên . 
 c) Các toán tử (Operotors , hay hàm (functions)) là các ánh xạ từ các tập hợp đối 
tượng vào các tập hợp đối tượng trong lĩnh vực đang khảo sát. Ta sẽ thường dùng 
các toán tử toán học sau : + , - , * , / , div , mod 
 Một toán tử có thể có một hay nhiều toán hạng (ngôi) . 
 Ví dụ : + Toán tử "đối" (biểu thị bởi -) là một ngôi : -x 
 + Toán tử - ,+, - , * , / , div, mod là hai ngôi : 2 + 3 , x * y 
 d) Các hàm logic hay các tân từ (predicates) . Đó là các ánh xạ từ tập hợp các 
đối tượng vào tập boolean {true,false}, ta sẽ thường dùng các tân từ là các quan hệ 
toán học như sau : 
 + Các quan hệ so sánh : = , , > , >= , < , <= 
 + Các quan hệ tập hợp : ⊆ , ⊇ , . . . 
 + Các quan hệ khác : odd(x) kiểm tra xem x có lẻ không ? 
 even(x) kiểm tra xem x có chẵn không ? 
 e) Các liên từ logic : đây là các toán tử trên tập boolean mà ta gặp trong logic 
mệnh đề: and , or , not , ==> , . 
 f) Các lượng từ phổ dụng ∀ và tồn tại ∃ (sẽ nói rõ ở mục sau) 
 Các biến logic , các tân từ trong đó có chứa các hằng hay biến hay hàm được gọi 
là các công thức cơ sở (formule elementaire) 
 Ví dụ : Các công thức cơ sở 
 - Biến logic : hôm-nay-trời-đẹp , tôi-về-lúc-8-giờ ,... 
 - tân từ : 5 > 2 
 x > 5 
 x + 5 > y - 3 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 105 - 
 Từ các công thức cơ sở này,người ta có thể thành lập các công thức phức hợp 
(formule complexe) bằng cách nối kết chúng dùng các liên từ logic và các lượng từ 
. Mỗi công thức phức hợp có thể xem là một tân từ mới. 
 Ví dụ : Công thức phức hợp 
 a) Hôm_nay_trời_đẹp and x > y 
 b) x > y ==> x > z 
2. Các lượng từ logic 
 Ngoài các liên từ logic , người ta có thể tạo ra các công thức phức hợp bằng cách 
gắn với các công thức các lượng từ logic . 
 a) Lượng từ phổ dụng. 
 Để nói rằng mỗi phần tử của một tập đều có tính chất P ta dùng lượng tử phổ 
dụng ( đọc là với mọi ) . ∀
 Ví dụ để nói rằng tất cả các phần tử của array a là không âm ta viết : 
 ( i : 0 = 0) ∀
 Biểu thức này được đọc như sau : 
 ∀ ( i Với mọi (số nguyên) i 
 : 0 <= i < n sao cho i nằm giữa 0 và n-1 
 : a[i] >= 0 thì a [i] là không âm 
 Dạng chung : (danh sách biến : R : P) ∀
 Với : R là tân từ hạn chế tập hợp được xét trong không gian định bởi danh sách 
biến , P là tân từ mà mỗi phần tử trong tập được xét phải thoả. 
Mệnh đề phổ dụng chỉ đúng khi mọi phần tử trong tập xác định bởi R đều thoả P. 
 Ví dụ : Cho a là array [0...n-1] of Integer 
 - Khẳng định : "a [k] là phần tử lớn nhất trong array" 
 ( i : 0 = a [i] ) ∀
 - Khẳng định : "các phần tử của a tạo thành cấp số cộng b,b+d, b+2d, . . 
 ( i : 0 <= i < n : a [i] = b + i*d) ∀
 - Khẳng định : "a dược sắp theo thứ tự không đơn giản" : 
 (i,j : 0 a[i] <= a [j]) ∀
 nếu R = true , ta có thể bỏ qua : ∀ (d :: 0 = d*0) 
 b) Lượng từ tồn tại. 
 Để khẳng định có một phần tử của tập hợp có tính chất P ta dùng lượng từ tồn tại 
 ( đọc là: “ có một “ hoặc “ tồn tại “). ∃
 Ví dụ : để khẳng định có gía tri x trong array a ta viết : 
 (i : 0 <= i < n : a [i] = x) ∃
 Biểu thức này được đọc như sau : 
 (i tồn tại một (số nguyên) i ∃
 : 0<= i < n sao cho i nằm giữa 0 và n-1 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 106 - 
 : a[i] = x thoả điều sau a[i] bằng x 
 Dạng chung là : ( danh sách biến : R : P ) ∃
 Mệnh đề tồn tại chỉ đúng khi có một phần tử trong miền xác định bởi R thoả P. 
 khi R = true thì ta có thể viết : ∃(danh sách biến :: P) 
 Ví dụ : cho hai array a và b 
 - Khẳng định :"trong array a không có thứ tự tăng" 
 ( i : 0 a [i+1]) ∃
 - Khẳng định : "có ít nhất một phần tử của a lớn hơn mọi phần tử của b" 
 ∃( i : 0 b[j] )) 
 - Khẳng định "n là chẵn" : ∃(m :: n = 2*m) 
 c) Một số tính chất: 
 - (i : R : P) ≡ (i :: R and P) 
 - (i : R : P) ≡ not (i :: R and not P) 
 - (i : R : P) ≡ not (i : R : not P) 
 d) Các biến tự do và bị buộc (free and band variables), phép thế(substitution) 
 Trong biểu thức Q(i: r(i) : p(i)) (ở đây ta xét Q là ∀ hay ∃ ) biến i được gọi 
là bị buộc (band) vào lượng từ Q . 
 Những xuất hiện của một biến i không bị buộc vào một lượng từ nào đó trong 
biểu thức R,được gọi là tự do (free) trong R. 
 Ví dụ trong biểu thức : (d : p = q*d) ∃
 các biến p và q là tự do , còn biến d là bị buộc . Các biến bị buộc chỉ đóng vai trò 
"giữ chỗ" và có thể được đổi tên , nếu tên này không trùng với một biến tự do đã có. 
Vì vậy , biểu thức trên tương đương với : 
 ∃(m :: p = q*m) nhưng hoàn toàn khác với : (p :: p = q*p) 
 Về nguyên tắc , một tên biến có thể vừa tự do và bị buộc trong cùng một biểu thức 
. 
 Ví dụ : Trong biểu thức ∀ ( 0<i ) and ( i : 0 <= i < n : a [i] = 0 ) 
 xuất hiện thứ nhất của i là tự do , còn xuất hiện còn lại là bị buộc. 
 Mặc dù ý nghĩa của biểu thức là rõ ràng nhưng nên tránh vì dễ gây nên lầm lẫn . 
 Xét một tân từ chứa biến tự do . 
 Ví dụ : is-divisor(q) ∃ (d :: p = q*d) 
 Ta có thể thay các xuất hiện tự do của một biến bằng một biểu thức để được một 
tân từ mới. 
 Ví dụ: thế 2*q cho q ta sẽ được tân từ is-divisor(2*q) mà dạng biểu thức của nó 
là : is-divisor(2*q) (d :: p = (2*q)*d) ∃
 Chú ý rằng trong ∃ (d :: p = q*d) biến p cũng tự do , nhưng vì ta không quan tâm 
đến phép thế cho p nên trong tân từ is-divisor(q) ta chỉ nêu q để giảm bớt đi các chi 
tiết không cần thiết trong diễn giải. 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 107 - 
3. Tập hợp và tân tưØ. 
 Mỗi biến có thể lấy giá trị trong một tập hợp xác định . Tập trị mà một dãy các 
biến có thể nhận được là tích Descarters các tập trị của từng biến . 
 Ưng với một tân từ P(i), với i là (danh sách) biến tự do mà mỗi phép thế i bằng 
một hằng sẽ cho giá trị đúng hay sai , ta có một tập hợp tất cả các hàm mà phép thế 
i trong P cho giá trị đúng . 
 ký hiệu tập đó là : { i : P(i) } 
 Ví dụ : { i : i >= 0 } "tập các (số nguyên) i sao cho i không âm " 
 { i,j : i < j } "tập các (số nguyên) i,j sao cho i nhỏ hơn j" 
 Ngược lại ứng với mỗi tập S , ta xây dựng tân từ đặc trưng cho S đó là: 
 P(i) = ( i ∈ S ) 
 Giữa các phép toán tập hợp và các phép toán logic có quan hệ chặt chẽ. 
 { i : P(i) or Q(i) } { i : P(i) } U { i : Q(i) } ≡
 { i : P(i) and Q(i) } ≡ { i : P(i) } ∩ { i : Q(i) } 
 Phần tử trung hoà của phép toán giao : tập vũ trụ (tích Descarters của các tập trị 
ứng với các biến trong danh sách biến) ứng với i chính là: { i : true } 
 Phần tử trung hoà của phếp toán hội là : { i : false } 
4. Các lượng từ số học. 
 sử dụng ý tưởng của ∀ và ∃ ta đặt thêm các lượng từ số học để dơn giản hoá 
cách viết và dễ dàng áp dụng các phép biến đổi . 
 Mỗi lượng từ sau sẽ biểu thị một hàm số học : 
 - Lượng từ tổng S (sumation) 
 S( i: r(i): f(i) ) chính là f i
i
( )∑ với i chạy trên tập hợp thoả r(i) 
 - Lượng từ tích P (product) 
 P( i: r(i): f(i) ) chính là f i
i
( )∏ với i chạy trên tập hợp thoả r(i) 
 Qui ước : 
 S( i: false: f(i) ) = 0 
 P( i: false: f(i) ) = 1 
 - Lượng từ MAX và MIN 
 MAX ( I: r(i): f(i)) là giá trị lớn nhất của f(i) trong các i thoả r(i). 
 MIN ( I: r(i):f(i) ) là giá trị nhỏ nhất của f(i) trong các i thoả r(i). 
 Qui ước : 
 MAX ( i: false: f(i) ) = - ∞ 
 MIN ( i: false: f(i) ) = ∞ 
 - Lượng từ N 
 N ( i:r(i): P(i)) số giá trị i trong miền r(i) thoả P(i) 
 Tức là : N ( i: r(i): P(i)) = S(i: r(i) and p(i): 1) 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 108 - 
 Mỗi lượng từ mà ta xét ngoại trừ N la ø sự khái quát của các phép toán hai ngôi 
có tính giao hoán và kết hợp thành phép toán trên một tập bất kỳ. 
 Ví dụ : 
 S là khái quát của phép công ( + ), P là khái quát của phép nhân ( * ). 
Trần Hoàng Thọ Khoa Toán - Tin