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

87 trang vanle 2930

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình môn Kỹ thuật lập trình nâng cao", để 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_mon_ky_thuat_lap_trinh_nang_cao.doc

Nội dung text: Giáo trình môn Kỹ thuật lập trình nâng cao

TRƯỜNG ĐẠI HỌC ĐÀ LẠT TRUNG TÂM TIN HỌC B&T SƯU TẦM GIÁO TRÌNH KỸ THUẬT LẬP TRÌNH NÂNG CAO TRẦN HOÀNG THỌ 2002 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 1 - 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 1 LỜI NÓI ĐẦU Giáo trình được viết theo nội dung môn học “ 1” 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à một phụ lục : Phần I. Đệ quy. Trình bày về chủ đề đệ quy trong lập trình bao gồm các nội dung sau : - Khái niệm đệ quy và vai trò của nó trong lập trình. - Cách xây dựng một giải thuật cho một bài toán bằng phương pháp đệ quy. - Cơ chế thực hiện một giải thuật đệ quy. - Khử đệ quy. Phần II. Kiểm chứng chương trình. Trình bày về chủ đề kiểm chứng tính đúng của chương trình bao gồm các nội dung sau: - Vai trò của vấn đề kiểm chứng trong lập trình. - Các phương pháp dùng để kiểm chứng tính đúng . - Hệ luật Hoare và áp dụng của nó vào kiểm chứng tính đúng có điều kiện. - Hệ luật Dijkstra và áp dụng của nó vào kiểm chứng tính đúng đầy đủ. - Dạng tổng quát của bài toán kiểm chứng và phương pháp kiểm chứng. Các lược đồ kiểm chứng và tập tối thiểu các điều kiện cần kiểm chứng. Phụ lục . Các kiến thức chung về logic. Trình bày các kiến thức ban đầu về logic mệnh đề và logic tân từ. Phụ lục cung cấp một một tài liệu cô đọng về các kiến thức logic áp dụng trực tiếp trong phần I và phần
II ( nó là một phần nôi dung của giáo trình nhập môn toán) người học cần dành thời gian thích hợp ôn lại để có thể theo kịp hướng tiếp cận của giáo trình. Cùng với những trình bày lý thuyết tổng quát, tác gỉa đưa vào một số thỏa đáng các ví dụ chọn lọc nhằm giúp người học nắm bắt được bản chất của các khái niệm, các phương pháp mới và làm quen với cách sử dụng các kết qủa mới. Khi học trước khi tìm cách giải các bài tập của thầy gíao cung cấp các bạn cố gắng đọc và hiểu hết các ví dụ minh họa. Vì nhiều lẽ chắc chắn giáo trình còn nhiều khiếm khuyết. Rất mong tất cả mọi người sử dụng chân thành góp ý. Tác giả chân thành cảm ơn các đồng nghiệp trong khoa Toán_Tin đã đóng góp nhiều ý kiến quý báu cho việc hình thành cấu trúc chi tiết cho nội dung giáo trình, chân thành cảm ơn thạc sỹ Võ Tiến đã đóng góp nhiều ý kiến quý báu trong cấu trúc giáo trình, giúp chỉnh lý nhiều khiếm khuyết trong bản thảo. ĐaLat ngày 01 tháng 12 năm 2002 TRẦN HOÀNG THỌ 1 - 5 - PHẦN I ĐỆ QUY CHƯƠNG I KHÁI NIỆM ĐỆ QUY I. MỞ ĐẦU 1. Mô tả đệ quy Trong nhiều tình huống việc mô tả các bài toán, các giải thuật, các sự kiện, các sự vật các quá trình, các cấu trúc, . . . sẽ đơn giản và hiệu quả hơn nếu ta nhìn được nó dưới góc độ mang tính đệ qui. Mô tả mang tính đệ qui về một đối tượng là mô tả theo cách phân tích đối tượng thành nhiều thành phần mà trong số các thành phần có thành phần mang tính chất của chính đối tượng được mô tả. Tức là mô tả đối tượng qua chính nó. Các ví dụ : - Mô tả đệ quy tập số tự nhiên N : + Số 1 là số tự nhiên ( 1 . N) . + Số tự nhiên bằng số tự nhiên cộng 1 . ( n . N . ( n +1 ) . N ) - Mô tả đệ quy cấu trúc xâu (list) kiểu T : + Cấu trúc rỗng là một xâu kiểu T. + Ghép nối một thành phần kiểu T(nút kiểu T ) với một xâu kiểu T ta có một xâu kiểu T. - Mô tả đệ quy cây gia phả : Gia phả của một người bao gồm mgười đó và gia phả của cha và gia phả của mẹ. - Mô tả đê quy thủ tục chọn hoa hậu : + Chọn hoa hậu của từng khu vực. + Chọn hoa hậu của các hoa hậu. - Mô tả đệ quy thủ tục sắp tăng dãy a[m:n] ( dãy a[m], a[m+1], . . . , a[n] ) bằng phương pháp Sort_Merge (SM) :
SM (a[m:n]) = Merge ( SM(a[m : (n+m) div 2]) , SM (a[(n+m) div 2 +1 : n] ) Với : SM (a[x : x]) là thao tác rỗng (không làm gì cả ). Merge (a[x : y] , a[(y+1) : z]) là thủ tục trộn 2 dãy tăng a [x : y] , a[(y+1) : z] để được một dãy a[x : z] tăng. - Đinh nghĩa đệ quy hàm giai thừa FAC( n) = n ! 0 ! = 1 n ! = n * ( n - 1 ) ! 1 Phương pháp đệ quy mạnh ở chổ nó cho phép mô tả một tập lớn các đối tượng chỉ bởi một số ít các mệnh đề hoặc mô tả một giải thuật phức tạp bằng một số ít các thao tác (một chương trình con đệ quy). Một mô tả đệ quy đầy đủ gồm 2 phần : - Phần neo : mô tả các trường hợp suy biến của đối tượng (giải thuật) qua một cấu trúc (thao tác) cụ thể xác định . ví dụ: 1 là số tự nhiên, cấu trúc rỗng là một xâu kiểu T, 0 ! = 1 , SM (a[x:x]) là thao tác rỗng. - Phần quy nạp: mô tả đối tượng (giải thuật) trong trường hợp phổ biến thông qua chính đối tượng (giải thuật ) đó một cách trực tiếp hoặc gián tiếp. Ví dụ : n! = n * (n – 1) ! SM (a[m:n]) = Merge (SM (a[m:( m+n) div 2] , SM (a[(m+n) div 2 +1 : n]) ) Nếu trong mô tả không có phần neo thì đối tượng mô tả có cấu trúc lớn vô hạn, giải thuật mô tả trở thành cấu trúc lặp vô tận. 2. Các loại đệ quy Người ta phân đệ quy thành 2 loại : Đệ quy trực tiếp, đệ quy gián tiếp. - Đệ quy trực tiếp là loại đệ quy mà đối tượng được mô tả trực tiếp qua nó : A mô tả qua A, B, C, trong đó B, C, không chứa A. (các ví dụ trên). - Đệ quy gián tiếp là loại đệ quy mà đối tượng được mô tả gián tiếp qua nó : A mô tả qua A1 ,A2 , , An .Trong đó có một Ai được mô tả qua A. Ví dụ 1: Mô tả dạng tổng quát một chương trình viết trên NNLT Pascal : Một Chương trình Pascal gồm : a) Đầu chương trình (head) gồm: Program Tên ; b) Thân chương trình (blok) gồm : b1) Khai báo unit, định nghĩa hằng, nhãn, kiểu dữ liệu, khái báo biến. b2) Định nghĩa các chương trình con gồm : b2.1) Đầu chương trình con : Procedure Tên thủ tục ( danh sách thông số hình thức ) ; hoặc Function Tên hàm ( danh sách thông số hình thức ) : Kiểu ; b2.2) Thân chương trình con ( Blok ) b2.3) Dấu ‘ ; ‘ b3) Phần lệnh : là một lệnh ghép dạng : Begin S1 ; S2 ; . . . ; Sn End ; c) Dấu kết thúc chương trình : ‘.’ Ví dụ 2 : Mô tả hai dãy số {Xn},{Yn} theo luật đệ quy hổ tương như sau : X0 = 1 ; Xn = Xn-1 + Yn-1 ; Y0 = 1 ; Yn =n2 Xn-1 + Yn-1 ;
1 - 7 - II. MÔ TẢ ĐỆ QUY CÁC CẤU TRÚC DỮ LIỆU Trong toán học , trong lập trình người ta thường sử dụng đệ quy để mô tả các cấu trúc phức tạp, có tính đệ quy . Bởi mô tả đệ quy không chỉ là cách mô tả ngắn gọn các cấu trúc phức tạp mà còn tạo khả năng để xây dựng các thao tác xử lý trên các cấu trúc phức tạp bằng các giải thuật đệ qui . Một cấu trúc dữ liệu có tính đệ quy thường gồm một số thành phần dữ liệu cùng kiểu được ghép nối theo cùng một phương thức . Ví dụ 1: Mô tả đệ quy cây nhi phân : Cây nhi phân kiểu T : + Hoặc là một cấu trúc rỗng (phần neo). + Hoặc là một nút kiểu T (nút gốc) và 2 cây nhị phân kiểu T rời nhau (cây con nhị phân phải, cây con nhị phân trái) kết hợp với nhau . Ví dụ 2: Mô tả đệ quy mảng nhiều chiều : + Mảng một chiều là dãy có thứ tự các thành phần cùng kiểu . + Mảng n chiều là mảng 1 chiều mà các thành phần có kiểu mảng n-1 chiều . III. MÔ TẢ ĐỆ QUY GIẢI THUẬT 1. Giải thuật đệ quy. Giải thuật đệ quy là giải thuật có chứa thao tác gọi đến nó . Giải thuật đệ quy cho phép mô tả một dãy lớn các thao tác bằng một số ít các thao tác trong đó có chứa thao tác gọi lại giải thuật (gọi đệ quy) . Một cách tổng quát một giải thuật đệ quy được biểu diễn như một bộ P gồm mệnh đề S (không chứa yếu tố đệ quy ) và P : P = P[ S , P ] . Thực thi giải thuật đệ quy có thể dẫn tới một tiến trình gọi đê quy không kết thúc khi nó không có khả năng gặp trường hợp neo, vì vậy quan tâm đến điều kiện dừng của một giải thuật đệ quy luôn được đặt ra . Để kiểm soát qúa trình gọi đệ quy của giải thuật đệ quy P người ta thường gắn thao tác gọi P với việc kiểm tra một điều kiện B xác định và biến đổi qua mỗi lần gọi P , qúa trình gọi P sẻ dừng khi B không con thỏa. Mô hình tổng quát của một giải thuật đệ quy với sự quan tâm đến sự dừng sẻ là : P if B then P[ S , P ] = hoặc P P[ S , if B then P ] = Thông thường với giải thuật đệ quy P , để đảm bảo P sẻ dừng sau n lần gọi ta chọn B là ( n >0 ) . Mô hình giải thuật đệ quy khi đó có dạng : P(n) If ( n > 0 ) then P[ S , P(n - 1)] ; = hoặc P(n) P[ S , if (n >0) then P(n - 1) ] ; = 1 - 8 - Trong các ứng dụng thực tế số lần gọi đệ quy (độ sâu đệ quy) không những phải hữu hạn mà còn phải đủ nhỏ . Bởi vì mỗi lần gọi đệ quy sẽ cần một vùng nhớ mới trong khi vùng nhớ cũ vẫn phải duy trì . 2. Chương trình con đệ quy. a) Các hàm đệ quy. Định nghĩa hàm số bằng đệ quy thường gặp trong toán học, điển hình là các hàm
nguyên mô tả các dãy số hồi quy . Ví dụ 1 . Dãy các giai thừa : { n! } = 1 ,1 , 2 , 6 , 24 , 120 , 720 , 5040 , . . . Ký hiệu FAC(n ) = n ! . Ta có : + FAC(0 ) = 1 ; ( 0 ! = 1 ) + FAC(n ) = n * FAC(n - 1 ) ; ( n ! = n * (n - 1 ) ! ) với n >= 1 Giải thuật đệ quy tính FAC(n ) là : FAC(n ) if (n = 0 ) then return 1 ; = else return (n * FAC(n - 1 )) ; Ví dụ 2 . Dãy số Fibonaci(FIBO) : { FIBO (n) } = 1 ,1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , . . . + FIBO(0 ) = FIBO (1 ) = 1 ; + FIBO(n ) = FIBO (n - 1 ) + FIBO ( n - 2 ) ; với n > = 2 Giải thuật đệ quy tính FIBO ( n ) là : FIBO(n) if ((n = 0 ) or ( n = 1 )) then return 1 ; = else return ( FIBO (n - 1) + FIBO (n - 2)) ; Ví dụ 3 . Dãy các tổ hợp : 1 1 2 1 1 3 3 1 1 4 6 4 1 C = 1 với n > = 0 n 0 = 0 với m > n > 0 Cn m với n > m > 0 C C C n m n m n m = + - - - 1 1 1 Giải thuật đệ quy tính là : Cn m if ( m = 0 ) then return 1 ; else if (m > n ) then return 0 ; else return ( ) ; C C n m n m - - - + 1 1 1 Nhận xét : Một định nghĩa hàm đệ quy gồm :
1 - 9 - + Một số các trường hợp suy biến mà gía trị hàm tại đó đã được biết trước hoặc có thể tính một cách đơn giản (không đệ quy ) . Như : FAC(0 ) = 1 , FIBO(0) = FIBO(1) = 1 , = 1 , = 0 với m > n > 0 . Cn 0 Cn m + Trường hợp tổng quát việc tính hàm sẻ đươc đưa về tính hàm ở giá trị “ bé hơn” (gần với giá trị neo) của đối số . Như : FAC(n ) = n * FAC(n - 1 ) ; FIBO(n) = FIBO(n -1) + FIBO( n - 2 ) . Trong tập biến của hàm có một nhóm mà độ lớn của nó quyết định độ phức tạp của việc tính gía trị hàm . Nhóm biến đó gọi là nhóm biến điều khiển . Gía trị biên của nhóm biến điều khiển ứng với trường hợp suy biến . Gía trị của nhóm biến điều khiển sẻ thay đổi qua mỗi lần gọi đệ quy với xu hướng tiến đến gía trị biên ( tương ứng với các trường hợp suy biến của hàm ). b) Các thủ tục đệ quy. Thủ tục đệ quy là thủ tục có chứa lệnh gọi đến nó . Thủ tục đệ quy thường được sử dụng để mô tả các thao tác trên cấu trúc dữ liệu có tính đệ quy Ví dụ 1 : Xem dãy n phần tử a[1:n] là sự kết hợp giữa dãy a[1:n-1] và a[n] . Do đo : - Thủ tục tìm max trong dãy a[1:n] ( thủ tục TMax) có thể thực hiện theo luật đệ qui : + Tìm max trong dãy con a[1:n] (gọi đệ quy Tmax(a[1:n-1] ) ). + Tìm max của 2 số : Tmax(a[1:n-1]) và a[n] (giải thuật không đệ quy). Tức là : TMax(a[1:n]) = max(TMax(a[1:n-l]) , a[n] ) với TMax(a[m:m] = a[m] ; ( trường hợp neo ) max(x,y) = x > y ? x : y ; ( giải thuật tính max 2 số : if (x>y) then max(x ,y) = x else max(x ,y) = y ) - Thủ tục tính tổng các phần tử ( thủ tục TSUM ) có thể thực hiện theo luật đệ quy : + Tìm tổng dãy con a[1:n] (gọi đệ quy TSUM(a[1:n-1]) ). + Tìm tổng của 2 số : TSUM(a[1:n-1]) và a[n] (giải thuật không đệ quy). Tức là : TSUM(a[1:n]) = a[n] + TSUM(a[1:n-1] với TSUM(a[m:m]) = a[m] Ví dụ 2 : Xem dãy a[m : n] là sự kết nối giữa hai dãy: dãy a[m:((m+n) div 2)] và dãy a[(((m+n) div 2)+1) :n] . 1 - 10 - Do đo : - Thủ tục tìm max trong dãy a[1:n] ( thủ tục Tmax1) có thể thực hiện theo luật
đệ qui : + Tìm max trong dãy con trái a[m:((m+n) div 2)] (gọi đệ quy Tmax1(a[m:((m+n) div 2)] ) ). + Tìm max trong dãy con phải a[(((m+n) div 2)+1) :n] . (gọi đệ quy Tmax1(a[(((m+n) div 2)+1) :n] ). + Tìm max của 2 số : Tmax1(a[m:((m+n) div 2)] ) và Tmax1(a[(((m+n) div 2)+1) :n] ). (giải thuật không đệ quy). Tức là :Tmax1(a[m:n]) = max(Tmax1(a[m:((m+n) div 2)] ) ,Tmax1(a[(((m+n) div 2)+1) :n]) ). với Tmax1(a[m:m] = a[m] ; ( trường hợp neo ) max(x,y) = x > y ? x : y ; - Thủ tục tính tổng các phần tử ( TSUM1 ) có thể thực hiện theo luật đệ quy : + Tìm tổng dãy con trái a[m:((m+n) div 2)] (gọi đệ quy TSUM1 (a[m:((m+n) div 2)] ) ). + Tìm tổng dãy con phải a[(((m+n) div 2)+1) :n] . (gọi đệ quy TSUM1 (a[(((m+n) div 2)+1) :n] ) ). + Tìm tổng của 2 số : TSUM1 (a[m:((m+n) div 2)] ) và TSUM1 (a[(((m+n) div 2)+1) :n] ). Tức là : TSUM1 (a[m:n]) = TSUM1 (a[m:((m+n) div 2)]) + TSUM1 (a[(((m+n) div 2)+1) :n] ) với TSUM1 (a[m:m]) = a[m] Ví dụ 3 : Cây nhị phân tìm kiếm kiểu T(BST) là một cấu trúc gồm : một nút kiểu T kết nối với 2 cây con nhi phân tìm kiếm kiểu T nên : - Thụ tục quét cây nhi nhân tìm kiếm theo thứ tự giữa (LNF) là : + Quét cây con trái theo thứ tự giữa ; + Thăm nút gốc ; + Quét cây con phải theo thứ tự giữa ; - Thủ tục tìm kiếm giá tri o trên cây nhị phân tìm kiếm Root là : Nếu Root = . thì thực hiện thao tác rỗng (không làm gì ) Con không nếu giá trị tại nút gốc = o thì thông báo tìm thấy và dừng Còn không nếu giá trị tại nút gốc < o thì tìm ở cây con trái Còn không thì tìm ở cây con phải . Nhận xét : 1 - 11 - Trong một thủ tục đệ qui, để cho việc gọi đệ quy dừng lại sau hữu hạn lần gọi nó cần chứa điều kiện kiểm tra (một biểu thức boolean B trên một nhóm biến ) , để khi điều kiện này không còn thỏa thì việc gọi đệ qui kết thúc . Dạng thường gặp của thủ tục đệ qui là : S1 ; ( không chứa yếu tố đệ qui ) if B then S2 ( phần lệnh trực tiếp , không có lệnh gọi đệ qui ) else Sdq ; ( phần lệnh có lệnh gọi đệ qui ) S3 ; (không có gọi đệ qui ) 3. Mã hóa giải thuật đệ qui trong các ngôn ngữ lập trình.
a) Tổng quan. Không phải mọi ngôn ngữ lập trình hiện có đều có thể mã hóa được giải thuật đệ quy, chỉ một số những ngôn ngữ lập trình có khả năng tổ chức vùng nhớ kiểu stack mới có khả năng mã hóa được giải thuật đệ quy . Các ngôn ngữ lập trình hiện nay đều mã hóa giải thuật đệ quy bằng cách tổ chức các chương trình con đệ quy tương ứng . b) Thể hiện đệ qui trong NNLT PASCAL và C++ NN LT Pascal và C++ đều cho phép mã hóa giải thuật đệ quy bằng cách tổ chức chương trình con đê quy nhờ vào cơ chế tạo vùng nhớ Stak của phần mềm ngôn ngữ . b1) Trong NNLT C++. NNLT C++ cho phép mã hóa giải thuật đệ quy một cách thuận lợi nhờ vào kỹ thuật khai báo trước tiêu đề nên không có sự phân biệt hình thức nào trong việc khai báo giữa hàm con đệ quy và hàm con không đệ quy. b2) Trong NN LT Pascal . Đối với chương trình con đệ quy trực tiếp thì hình thức khai báo cũng giống như đối với chương trình con không đệ quy. Đối với chương trình con đệ quy gián tiếp thì hình thức khai báo có thay đổi ít nhiều nhằm thỏa quy tắc tầm vực của ngôn ngữ ( trong phần lệnh của một chương trình con chỉ được gọi những chương trình con cùng cấp đã được khai báo trước ). Ví dụ : Với mô hình chương trình sau : Trong phần lệnh của khối A có thể gọi đến : 1 - 12 - + Gọi các chương trình con trực tiếp của nó gọi được B nhưng không gọi được C + Gọi chính nó ( gọi đệ quy ). + Gọi chương trình con cùng cấp nhưmg phải khai báo trước gọi được E nhưng không gọi được D , Muốn gọi D phải khai báo trước ( khai báo FORWARD) Khai báo trước FORWARD . D A B C Program E Để từ thủ tục hàm A có thể gọi đến D là thủ tục hàm cùng cấp nhưng được mô tả sau A, ta cần có một khai báo trước của D ở phía trước của A . Khai báo này gồm : tiêu đề của D, với danh sách thông số của D, tiếp theo là từ khoá FORWARD . Sau đó lúc mô tả lại D thì chỉ cần khai báo từ khoá PROCEDURE ( hoặc FUNCTION ) , tên của D ( không có danh sách thông số ) , phần thân của D. Ví dụ : Với 2 thủ tục gọi đệ quy hỗ tương nhau FIRST,SECOND sẽ được khai báo như sau : procedure SECOND (i : integer ) ; Forward ; procedure FIRST (n : integer ; var X : real);
var j, k : interger ; begin for j := 1 to n do begin writeln(‘ j = ‘, j ) ; k := n – 2* j ; SECOND( k ); end ; end ; procedure second ; begin if ( i > 0 ) then begin writeln(‘ i= ‘, i ); FIRST( i – 1 ) ; end ; end ; 1 - 13 - 4. Một số dạng giải thuật đệ quy đơn giản thường gặp . a) Đệ quy tuyến tính. Chương trình con đệ quy tuyến tính là chương trình con đệ quy trực tiếp đơn giản nhất có dạng : P = { NẾU thỏa điều kiện dừng thì thực hiện S ; Còn không begin { thực hiện S* ; gọi P } } Với S , S* là các thao tác không đệ quy . Ví dụ 1 : Hàm FAC(n) tính số hạng n của dãy n! + Dạng hàm trong ngôn ngữ mã giả : { Nếu n = 0 thì FAC = 1 ; /* trường hợp neo */ Còn không FAC = n*FAC(n-1) } + Dạng hàm trong ngôn ngữ Pascal : Function FAC(n : integer) : integer; begin if( n = 0 ) then FAC := 1 else FAC := n*FAC(n-1) ; end; + Dạng hàm trong C++ : int FAC( int n ) { if ( n == 0 ) return 1 ; else return ( n * FAC(n-1 )) ; } Ví dụ 2 : Chương trình con tính USCLN của 2 số dựa vào thuật toán Euclide : + Dạng hàm trên ngôn ngữ toán học : USCLN(m , n ) = USCLN(n , m mod n ) khi n . 0 USCLN(m , 0) = m + Dạng hàm trong ngôn ngữ mã giả : Nếu n = 0 thì USCLN = m
Còn không USCLN = USCLN( n , m mod n ) ; + Dạng hàm trong Pascal : Function USCLN(m , n : integer ) : integer ; begin if (n = 0 ) then USCLN := m else USCLN := USCLN( n , m mod n ) ; end ; +Dạng hàm trong C++ : int USCLN( int m , int n ) 1 - 14 - { if(n == 0 ) return (m) ; else return ( USCLN( n , m mod n)) ; } b) Đệ quy nhị phân. Chương trình con đệ quy nhị phân là chương trình con đệ quy trực tiếp có dạng : P = { NẾU thỏa điều kiện dừng thì thực hiện S ; Còn không begin { thực hiện S* ; gọi P ; gọi P } } Với S , S* là các thao tác không đệ quy . Ví dụ 1 : Hàm FIBO(n) tính số hạng n của dãy FIBONACCI + Dạng hàm trong Pascal: Function F(n : integer) : integer; begin if( n < 2 ) then F := 1 else F := F(n-1) + F(n-2) end; + Dạng hàm trong C++ : int F(int n) { if ( n < 2 ) return 1 ; else return (F(n -1) + F(n -2)) ; } c) Đệ quy phi tuyến. Chương trình con đệ quy phi tuyến là chương trình con đệ quy trực tiếp mà lời gọi đệ quy được thực hiện bên trong vòng lặp . Dạng tổng quát của chương trình con đệ quy phi tuyến là : P = { for giá tri đầu to giá trị cuối do begin thực hiện S ; if ( thỏa điều kiện dừng ) then thực hiện S* else gọi P end ; } Với S , S* là các thao tác không đệ quy . Ví dụ : Cho dãy { Xn } xác định theo công thức truy hồi : X0 = 1 ; Xn = n2 XO +(n-1)2 X1 + . . . + 2 2 Xn-2 + 1 2 Xn-1 + Dạng hàm đệ quy tính Xn trên ngôn ngữ mã giả là :
Xn = if ( n= 0 ) then return 1 ; 1 - 15 - else { tg = 0 ; for i = 0 to n-1 do tg = tg + (n-i)2 Xi ; return tg ; } + Dạng hàm đệ quy tính Xn trên ngôn ngữ Pascal là : function X( n :integer) : integer ; var i , tg : integer ; begin if ( n= 0 ) then X := 1 else begin tg = 0 ; for i: = 0 to n-1 do tg : = tg + sqr(n-i) *X(i) ; X := tg ; end ; end ; + Dạng hàm đệ quy tính Xn trên ngôn ngữ C++ là : int X( int n ) ; { if ( n == 0 ) return 1 ; else { int tg = 0 ; for (int i = 0 ; i<n ; i++ ) tg = tg + sqr(n-i) *X(i); return ( tg ) ; } 1 - 16 - CHƯƠNG II BÀI TOÁN ĐỆ QUY I. CÁC NỘI DUNG CẦN LÀM ĐỂ TÌM GIẢI THUẬT ĐỆ QUY CHO MỘT BÀI TOÁN. Để xây dựng giải thuật giải một bài toán có tính đệ quy bằng phương pháp đệ quy ta cần thực hiện tuần tự 3 nội dung sau : - Thông số hóa bài toán . - Tìm các trường hợp neo cùng giải thuật giải tương ứng . - Tìm giải thuật giải trong trường hợp tổng quát bằng phân rã bài toán theo kiểu đệ quy. 1. Thông số hoá bài toán. Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng quát (một họ các bài toán chứa bài toán cần giải ),tìm ra các thông số cho bài toán tổng quát đặc biệt là nhóm các thông số biểu thị kích thước của bài toán – các thông số điều khiển ( các thông số mà độ lớn của chúng đặc trưng cho độ phức tạp của bài toán , và giảm đi qua mỗi lần gọi đệ qui ) . Ví dụ : n trong hàm FAC(n) ; a , b trong hàm USCLN(a,b) . 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. Đây là các trường hợp suy biến của bài toán tổng quát , là các trương hợp tương ứng với các gía trị biên của các biến điều khiển (trường hợp kích thước bài toán nhỏ nhất), mà giải thuật giải không đệ qui (thường rất đơn giản). Ví dụ : FAC(1) =1 , USCLN(a,0) = a , SM(a[x:x] = ,TSUM(a[m:m]) = a[m] 3. Phân rã bài toán tổng quát theo phương thức đệ quy. Tìm phương án (giải thuật ) giải bài toán trong trường hợp tổng quát bằng cách phân chia nó thành các thành phần mà hoặc có giải thuật không đệ quy hoặc là bài toán trên nhưng có kích thước nhỏ hơn. Ví dụ : FAC(n) = n * FAC(n -1) . Tmax(a[1:n]) = max(Tmax(a[1:(n-1)]) , a[n] ) 1 - 17 - II. MỘT SỐ BÀI TOÁN GIẢI BẰNG GIẢI THUẬT ĐỆ QUY ĐIỂN HÌNH. 1. Bài toán tháp Hà Nội . Truyền thuyết kể rằng : Một nhà toán học Pháp sang thăm Đông Dương đến một ngôi chùa cổ ở Hà Nội thấy các vị sư đang chuyển một chồng đĩa qúy gồm 64 đĩa với kích thước khác nhau từ cột A sang cột C theo cách : - Mỗi lần chỉ chuyển 1 đĩa . - Khi chuyển có thể dùng cột trung gian B . - Trong suốt qúa trình chuyển các chồng đĩa ở các cột luôn được xếp đúng (đĩa có kích thước bé được đặt trên đĩa có kích thước lớn ) . Khi được hỏi các vị sư cho biết khi chuyển xong chồng đĩa thì đến ngày tận thế !. Như sẽ chỉ ra sau này với chồng gồm n đĩa cần - 1 lần chuyển cơ bản (chuyển 1 đĩa ). 2n Giả sử thời gian để chuyển 1 đỉa là t giây thì thời gian để chuyển xong chồng 64 đĩa sẽ là : T = ( 2 ) * t S = 18 1 64 - 4 1019 . * *t S Với t = 1/100 s thì T = 5.8*109 năm = 5.8 tỷ năm . Ta có thể tìm thấy giải thuật (dãy các thao tác cơ bản ) cho bài toán một cách dễ dàng ứng với trường hợp chồng đĩa gồm 0, 1, 2, 3 đĩa . Với chồng 4 đĩa giải thuật bài toán đã trở nên phức tạp . Tuy nhiên giải thuật của bài toán lại được tìm thấy rất dễ dàng nhanh chóng khi ta khái quát số đĩa là n bất kỳ và nhìn bài toán bằng quan niệm đệ quy . a) Thông số hóa bài toán . Xét bài toán ở mức tổng quát nhất : chuyển n (n>=0) đĩa từ cột X sang cột Z lấy cột Y làm trung gian . Ta gọi giải thuật giải bài toán ở mức tổng quát là thủ tục THN(n ,X ,Y,Z) chứa 4 thông số n,X,Y,Z ; n thuộc tập số tự nhiên N (kiểu nguyên không dấu ); X ,Y,Z thuộc tập các ký tự (kiểu ký tự ). Bài toán cổ ở trên sẻ được thực hiện bằng lời gọi THN(64,A,B,C) . Dễ thấy rằng : trong 4 thông số của bài toán thì thông số n là thông số quyết định độ phức tạp của bài toán ( n càng lớn thì số thao tác chuyển đỉa càng nhiều và thứ tự thực
hiện chúng càng khó hình dung ) , n là thông số điều khiển . b) Trường hợp suy biến và cách giải . Với n =1 bài toán tổng quát suy biến thành bài toán đơn giản THN (1,X,Y,Z) : tìm dãy thao tác để chuyển chồng 1 đĩa từ cột X sang cột Z lấy cột Y làm trung gian . Giải thuật giải bài toán THN (1,X,Y,Z) là thực hiện chỉ 1 thao tác cơ bản : Chuyển 1 đĩa từ X sang Z ( ký hiệu là Move (X , Z) ) . 1 - 18 - THN(1,X,Y,Z) = { Move( X, Z ) } Chú ý : Hoàn toàn tương tự ta cũng có thể quan niện trường hợp suy biến là trường hợp n= 0 tương ứng với bài toán THN(0,X,Y,Z) : chuyển 0 đĩa từ X sang Z lấy Y làm trung gian mà giải thuật tương ứng là không làm gì cả ( thực hiện thao tác rỗng ) . THN(0,X,Y,Z) = { ư } c) Phân rã bài toán : Ta có thể phần rã bài toán TH N (k,X,Y,Z) : chuyển k đĩa từ cột X sang cột Z lấy cột Y làm trung gian thành dãy tuần tự 3 công việc sau : + Chuyển (k -1) đĩa từ cột X sang cột Y lấy cột Z làm trung gian : THN (k -1,X,Z,Y) (bài toán THN với n = k-1,X= X , Y = Z , Z = Y ) + Chuyển 1 đĩa từ cột X sang cột Z : Move ( X, Z ) (thao tác cơ bản ). + Chuyển (k - 1 ) đĩa từ cột Y sang cột Z lấy cột X làm trung gian : THN( k -1,Y,X,Z) ( bài toán THN với n = k-1 , X = Y , Y = X , Z = Z ) . Vậy giải thuật trong trường hợp tổng quát (n > 1) là : THN(n,X,Y,Z) = { THN (n -1,X,Z,Y) ; Move ( X, Z ) ; THN (n -1,Y,X,Z) ; } Với n đĩa thì cần bao nhiêu bước chuyển 1 đĩa? Thực chất trong thủ tục THN các lệnh gọi đệ qui chỉ nhằm sắp sếp trình tự các thao tác chuyển 1 đĩa Số lần chuyển 1 đĩa được thực hiện là đặc trưng cho độ phức tạp của giải thuật . Với n đĩa , gọi f(n) là số các thao tác chuyển _một_đĩa . Ta có : f(0) = 0 . f(1) =1 . f(n) = 2f(n -1) + 1 với n > 0 Do đo : f(n) = 1+ 2 + 2 2 + + 2 n-1 = 2 n - 1 Để chuyển 64 đĩa cần 2 64 - 1 bước hay xấp xỉ 10 20 bước . Cần khoảng 10 triệu năm với một máy tính nhanh nhất hiện nay để làm việc này . d) Chương trình con mã hóa giải thuật THN trong NNLT Pascal : procedure THN (n : integer ; X,Y,Z : char) begin if n > 0 then begin THN (n-1 ,X,Z,Y) ; Move( X, Z); THN (n-1 ,Y,X,Z); end ; end ; ( Lấy trường hợp chuyển n = 0 làm trường hợp neo )
1 - 19 - Hoặc : procedure THN (n : integer ; X,Y,Z : char) begin if (n = 1) then Move(X, Z) else begin THN (n-1 ,X,Z,Y ) ; Move(X, Z ); THN (n -1 ,Y,X,Z ); end ; end; ( Lấy trường hợp chuyển n = 1 làm trường hợp neo ) Với thủ tục Move(X, Y) mô tả thao tác chuyển 1 đĩa từ cột X sang cột Y được viết tuỳ theo cách thể hiện thao tác chuyển . e) Chương trình con mã hóa giải thuật THN trong NNLT C++ : Trong C++ hàm con thực hiện giải thuật THN có dạng : void THN( int n , char X,Y,Z) { if(n > 0) { THN(n -1,X,Z,Y ) ; Move ( X , Z ) ; THN(n - 1,Y,X,Z ) ; } return ; } hoặc : void THN( int n , char X,Y,Z) { if(n = = 1) Move ( X , Z ) ; else { THN(n -1,X,Z,Y ) ; Move ( X, Z ) ; THN(n - 1,Y,X,Z ) ; } return ; } 2. Bài toán chia thưởng. Có 100 phần thưởng đem chia cho 12 học sinh giỏi đã được xếp hạng. Có bao nhiêu cách khác nhau để thực hiện cách chia? Ta thấy ngay rằng việc tìm ra lời giải cho bài toàn sẻ không dễ dàng nếu ta không tìm ra cách thích hợp để tiếp cận với nó. Ta sẽ tìm giải thuật giải bài toàn bằng phương pháp đệ quy. 1 - 20 - a) Thông số hóa. Ta sẽ giải bài toán ở mức độ tổng quát : Tìm số cách chia m vật (phần thưởng ) cho n đối tượng (học sinh ) có thứ tự . Gọi PART là số cách chia khi đó PART là hàm của 2 biến nguyên m , n ( PART(m ,n )) . Ta mã hoá n đối tượng theo thứ tự xếp hạng 1, 2 , 3 , . . . n ; Si là số phần thưởng mà
học sinh i nhận được . Khi đó các điều kiện ràng buộc lên cách chia là : Si >= 0 S1 >= S2 >= >= Sn . S1 + S2 + + Sn = m Ví dụ : Với m = 5 , n = 3 ta có 5 cách chia sau : 5 0 0 4 1 0 3 2 0 3 1 1 2 2 1 Tức là PART(5,3 ) = 5 b) Các trường hợp suy biến : + m = 0 thì sẻ có duy nhất 1 cách chia : mọi học sinh đều nhận được 0 phần thưởng . Vậy : PART(0 , n ) = 1 với mọi n + n = 0 , m 0 . ( ta có thể thay trường hợp neo PART(m ,0) = 0 hoặc trường hợp neo PART(m , 1) = 1 ) c ) Phân rã bài toán trong trường hợp tổng quát : + m m thì PART(m , n ) = PART(m , m ) . + Trong trường hợp m >= n : số vật chia (phần thưởng ) lớn hơn hoặc bằng số học sinh (đối tượng ) ta phân các cách chia làm 2 nhóm : * Nhóm thứ nhất không dành cho học sinh xếp cuối cùng phần thưởng nào cả ( Sn = 0 ) . Số cách chia này sẽ bằng số cách chia m phần thương cho n -1 học sinh . Tức là : Số cách chia trong nhóm thứ nhất = PART(m , n -1 ) . 1 - 21 - * Nhóm thứ 2 có phần cho người cuối cùng ( Sn > 0 ) . Dễ thấy rằng số cách chia của nhóm này bằng số cách chia m - n phần thương cho n học sinh ( vì phương thức chia mà tất cả học sinh đều nhận được phần thưởng có thể thực hiện bằng cách : cho mỗi người nhận trước 1 phần thưởng rồi mới chia ). Tức là : Số cách chia trong nhóm thứ 2 = PART(m - n , n ) . Vậy : với m>= n PART(m , n ) = PART(m , n -1 ) + PART(m - n , n ) d ) Dạng mã giả của hàm PART(m , n ) PART(m , n ) = if(m = 0 ) then return 1 ; else if( n = 1 ) then return 1 ; else if(m < n ) then return PART(m , m) ; else return ( PART(m , n -1) + PART(m - n , n )) e) Dạng hàm PART trong NNLT Pascal Function PART(m , n : integer ) : integer ;
Begin if ( (m = 0) or ( n = 1) ) then PART := 1 else if(m < n) then PART := PART(m , m ) else PART := PART(m , n -1 ) + PART(m - n , n) ; End ; g) Dạng hàm PART trong NN LT C++ int PART( int m , int n ) { if ((m == 0 ) || (n == 0) ) return 1 ; else if(m < n ) retrun ( PART(m , m )) ; else return ( PART(m , n -1 ) + PART( m -n , n ) ) ; } 3. Bài toán tìm tất cả các hoán vị của một dãy phần tử. Bài toán : Xuất tất cả các hoán vị của dãy A . Ví dụ : Với dãy A gồm N = 3 phần tử A[1] = a , A[2] = b , A[3] = c thì bài toán bắt phải xuất 6 hoán vị có thể của A : a b c a c b c b a b a c c a b b c a Với dãy A gồm N = 4 phần tử A[1] = 1 , A[2] = 2 , A[3] = 3 , A[4] =4 thì bài toán bắt phải xuất 24 hoán vị có thể của A : 1 2 3 4 1 2 4 3 1 4 3 2 4 2 3 1 1 - 22 - 2 1 3 4 2 1 4 3 4 1 3 2 2 4 3 1 1 3 2 4 1 4 2 3 1 3 4 2 4 3 2 1 3 1 2 4 4 1 2 3 3 1 4 2 3 4 2 1 3 2 1 4 4 2 1 3 3 4 1 2 3 2 4 1 2 3 1 4 2 4 1 3 4 3 1 2 2 3 4 1 a) Thông số hóa bài toán . Gọi HV(v, m ) ( với v : array[1 . . N ] of T , m :integer ; m = N ; T là một kiểu dữ liệu đã biết trước ) là thủ tục xuất tất cả các dạng khác nhau của v có được bằng cách hoán vị m thành phần đầu của dãy v Ví dụ : N = 4 , A[1] = 1 , A[2] = 2 , A[3] = 3 , A[4] = 4 thì lời gọi HV(A ,3 ) xuất tất cả hoán vị của A có được bằng cách hoán vị 3 phần tử đầu ( có 6 h vị ) : 1 2 3 4 1 3 2 4 3 2 1 4 2 1 3 4 3 1 2 4 2 3 1 4 Để giải bài toán đặt ra ban đầu ta gọi HV(A,N) ). b) Trường hợp neo. Vơi m = 1 : HV(v,1) là thủ tục giải bài toán xuất tất cả các dạng của v có được bằng cách hoán vị 1 phần tủ đầu . Vậy HV(v,1) là thủ tục xuất v. HV(v,1) = print(v) = for k:= 1 to N do write(v[k]) c) Phân rã bài toán. Ta có thể tìm hết tất cả các hoán vị m phần tử đầu của vector V theo cách sau : - Giữ nguyên các phần tử cuối V[m] , . . . ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) . - Đổi chổ V[m] cho V[m-1] ,giữ nguyên các phần tử cuối V[m], ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) . - Đổi chổ V[m] cho V[m-2] ,giữ nguyên các phần tử cuối V[m], . ,V[N]
hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - Đổi chổ V[m] cho V[2] ,giữ nguyên các phần tử cuối V[m], . ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) . - Đổi chổ V[m] cho V[1] ,giữ nguyên các phần tử cuối V[m], . . . ,V[N] hoán vị m-1 phần tử đầu ( gọi đệ quy HV(V ,m - 1) . Vậy : HV(V,m) = { SWAP( V[m],V[m] ) ; HV(V,m – 1) ; SWAP( V[m],v[m-1] ) ; HV(V,m – 1) ; SWAP( V[m],v[m-2 ] ) ; HV(V,m – 1) ; 1 - 23 - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SWAP (V[m],v[2] ) ; HV(V,m – 1) ; SWAP( V[m],v[1] ) ; HV(V,m – 1) ; } ( SWAP(x , y ) là thủ tục hoán đổi giá trị của 2 đối tượng dữ liệu x ,y ) Vậy : HV(V , m ) = for k := m downto 1 do begin SWAP( V[m], V[k] ) ; HV(V,m – 1) ; end ; d) Thủ tục hoán vị trên NNLT Pascal. . . . . . . . . . . . . . . . . . . const size = Val ; (* Val là hằng gía trị *) type vector = array[1. . size] of typebase; (* typebase là một kiểu dữ liệu có thứ tự *) . . . . . . . . . . . . . . . . . . . . . . procedure Swap( var x , y : typebase ) ; var t : typebase ; begin t := x ; x := y ; y := t ; end ; . . . . . . . . . . . . . . . . . . . . . . . . . . procedure print( A : vector ) ; var i : integer ; begin for i:= 1 to size do write( A[i] : 3 ); writeln ; end ; . . . . . . . . . . . . . . . . . . . . . . . . . . Procedure HV( V : vec tor ; m :integer ) ; var k : integer ; begin if (m = 1 ) then print(V)
else for k := m downto 1 do begin Swap(V[m] , V[k]); HV(V , m – 1) ; end ; end ; 1 - 24 - e) Thủ tục hoán vị trên NNLT C++ . . . . . . . . . . . . . . . . . . . const size = Val ; // Val là hằng gía trị typedef typebase vector[size] ; // typebase là một kiểu dữ liệu có thứ tự . . . . . . . . . . . . . . . . . . . . . . void Swap( typebase & x , typebase& y) { typebase t ; t = x ; x = y ; y = t ; } . . . . . . . . . . . . . . . . . . . . . . . . . . void print( const vector &A) { for(int j= 0 ; j = 0 ; k ) { swap(V[m-1] ,V[k] ) ; HV(V,m-1) ; } } 4. Bài toán sắp xếp mảng bằng phương pháp trộn (Sort-Merge). Ý tưởng : Để sắp xếp 1 danh sách gồm n phần tử bằng phương pháp trộn người ta chia danh sách thành 2 phần (tổng quát là nhiều phần ) , sắp xếp từng phần, rồi trộn chúng . Bài toán : sắp theo thứ tự không giảm mảng a : VectorT bằng phương pháp trộn. ( VectorT = array[1 . . size] of T). a) Thông số hoá: Bài toán được khái quát thành sắp xếp một dãy con của dãy V : VectorT từ chỉ số m đến chỉ số n với 1 <= m <= n <= size . Ta đặt tên cho bài toán ở dạng tổng quát là : SM(V,m,n). Bài toán ban đầu : sắp dãy A sẻ được thực hiện bằng lời gọi : SM(A ,1,size). b) Trường hợp tầm thường: Đó là khi n = m (dãy sắp chỉ có 1 phần tử ), khi đó không cần làm gì cả (thao tác rỗng) . 1 - 25 -
c) Phân rã trường hợp tổng quát : Khi n > m ta thực hiện các công việc sau : + Chia dãy : a[m] ,a[m+1], . . . , a[n] thành 2 dãy con a[m] , . . , a[l] và a[l+1] , . . . , a[n] + Sắp xếp từng dãy con thành các dãy có thứ tự theo giải thuật SM . + Trộn 2 dãy con có thứ tự lại thành dãy a[m] ,. . . , a[n] mới có thứ tự . Để thực hiện việc trộn hai dãy có thứ tự thành một dãy có thứ tự ta sẽ dùng một thủ tục không đệ quy Merge(m , l , n) . Ta cần chọn l để được 2 dãy con giảm hẵn kích thước so với dãy ban đầu , tức là chọn l : m m then begin l := (m+n) div 2; SM (d,m,l) ; SM (d,l+1,n) ; Merge (d,m,l,n) ; end ; end ; Trong đó SM là thủ tục trộn 2 dãy tăng để được một dãy tăng. Để sắp mảng A (dãy A[1:size]) ta gọi SM(A ,1,size) 5. Bài toán tìm nghiệm xấp xỉ của phương trình f(x)=0 . Bài toán : Hàm f(x) liên tục trên đoạn [ao,bo] , tìm một nghiệm xấp xỉ với độ chính xác trên [ao,bo] của phương trình f(x) = 0. Ý tưởng của giải thuật : - Trường hợp neo : bo - ao 0 thì ta xem như không có nghiệm xấp xỉ trên đoạn xét. - Trương hợp bo - ao = thì chia đôi đoạn [ao,bo] rồi tìm lần lượt nghiệm trên từng đoạn con : đoạn con trái, đoạn con phải . Ta sẽ xây dựng một hàm đệ qui trả về giá trị là nghiệm xấp xỉ của f (nếu có),hay một hằng E ( đủ lớn) nếu f không có nghiệm xấp xỉ trên [ao,bo] . 1 - 26 - a) Thông số hoá: Xét hàm ROOT với 3 thông số là g , a,b ,(ROOT(g,a,b)) trả về giá trị nghiệm xấp xỉ của phương trình g(x) =0 trên đoạn [a,b] hoặc giá trị C nếu phương trình xét không có nghiệm xấp xỉ . Để giải bài toán ban đấu ta gọi hàm ROOT(f,ao,bo) . b) Trường hợp tầm thường: đó là khi b - a < epsilon . Khi đó : if ( g(a).g(b) ) <= 0 then ROOT(g,a,b) = a ; // a là nghiệm xấp xỉ
else ROOT(g,a,b) = E ; // không có nghiệm xấp xỉ c) Phân rã trường hợp tổng quát: khi b - a >= ta phân [a,b] làm 2 đoạn [a,c] và [c,b] với c = (a + b) / 2. - Nếu ROOT(g , a ,c) < E thì ROOT(g , a , b ) = ROOT(g ,a ,c) (bài toán tìm nghiệm trên đoạn [a,c] ) . - còn không thì ROOT(g , a , b ) = ROOT(g ,c ,b) (bài toán tìm nghiệm trên đoạn [c ,b] ) . d) Hàm tìm nghiệm xấp xỉ trên NN Pascal có dạng: const epsilon = ; E = ; Function ROOT(a,b :real ) :real ; var c , R : real ; begin if ((b-a) < epsilon ) then if ( f(a)*f(b) <= 0 ) then ROOT := a else ROOT := L else begin c := (a + b)/2 ; if ( ROOT(a ,c ) < E ) then ROOT := ROOT(a,c) else ROOT := ROOT(c,b) end; e) Chương trình con tìm nghiệm xấp xỉ trong NN LT C++ const double epsilon = ; const double E = ; double ROOT(double a , double b ) { if((b - a) < epsilon ) if(f(a)*f(b) <= epsilon return (a ) ; else return ( L ) ; else { double c = (a + b ) / 2 ; 1 - 27 - double R = ROOT(a,c) ; if( R< E ) return R ; else return ( ROOT(c , b) ) ; } } 1 - 28 - CHƯƠNG III KHỬ ĐỆ QUY I. CƠ CHẾ THỰC HIỆN GIẢI THUẬT ĐỆ QUY. Trạng thái của tiến trình xử lý một giải thuật ở một thời điểm được đặc trưng bởi nội dung các biến và lệnh cần thực hiện kế tiếp. Với tiến trình xử lý một giải thuật đệ qui ở từng thời điểm thực hiện, con cần lưu trữ cả các trạng thái xử lý đang còn dang dở . a) Xét giải thuật đệ quy tính giai thừa:
FAC ( n ) = if(n = 0 ) then retrun 1 ; else retrun ( n * FAC (n – 1)) ; Sơ đồ quá trình tính gía trị 3 ! theo giải thuật đệ quy : FAC(3 ) = 3 * FAC( 2 ) FAC( 0 ) = 1 FAC( 1 ) = 1 * FAC( 0 FAC( 2 ) = 2 * FAC( 1 Khi thực hiện lời gọi FAC (3 ) sẻ phát sinh lòi gọi FAC (2 ) , đồng thời phải lưu giữ thông tin trạng thái xử lý còn dang dỏ ( FAC ( 3 ) = 3 * FAC ( 2 ) ) . Đến lượt mình lời gọi FAC ( 2 ) lại làm phát sinh lời gọi FAC (1 ) ,đồng thời vẩn phải lưu trử thông tin trạng thái xử lý còn dang dở ( FAC (2 ) = 2 * FAC ( 1 ) ) , . Cứ như vậy cho tới khi gặp lời gọi trường hợp neo ( FAC (0 ) = 1 ) . Tiếp sau qúa trình gọi là một qúa trình xử lý ngược được thực hiện : - Dùng giá trị FAC ( 0 ) để tính FAC ( 1 ) theo sơ đồ xử lý còn lưu trử . - Dùng giá trị FAC ( 1 ) để tính FAC ( 2 ) theo sơ đồ xử lý còn lưu trử . - Dùng giá trị FAC ( 2 ) để tính FAC ( 3 ) theo sơ đồ xử lý còn lưu trử . 1 - 29 - Đồng thời với qúa trình xử lý ngược là qúa trình xóa bỏ các thông tin về giải thuật xử lý trung gian ( qúa trình thu hồi vùng nhớ ) . b) Xét giải thuật đệ quy tính giá trị hàm FIBONACCI . FIB(n) if ((n = 0 ) or ( n = 1 )) then return 1 ; = else return ( FIB(n - 1) + FIB(n - 2)) ; Sơ đồ tính FIB(5) : FIB(3) = FIB(1) + FIB(2) FIB(4) = FIB(2) + FIB(3) FIB(5) = FIB(3) + FIB ( ) FIB(2) = FIB(0) + FIB(1) FIB(0) = FIB(1) = FIB(2) = FIB(0) + FIB(1) FIB(0) = 1 FIB(1) = FIB(2) = FIB(0) + FIB(1) FIB(1) = FIB(1) = FIB(3) = FIB(2) + FIB(1) FIB(1) = FIB(0) = c) Xét thủ tục đệ quy tháp Hà Nội THN (n , X , Y , Z) THN (n : integer ; X ,Y , Z : char) = if (n > 0 ) then { THN(n-1,X ,Z ,Y) ; Move(X, Z) ; THN(n-1,Y,X,Z) ; } Để chuyển 3 đĩa từ cột A sang cột C dùng cột B làm trung gian ta gọi : THN (3,A,B,C)
Sơ đồ thực hiện lời gọi THN (3,A,B,C) là : 1 - 30 - Lời gọi c/0 Lới gọi c/1 Lời gọi c/2 Lời gọi c/3 THN(0,A,C,B) THN(1,A,B,C) A > C THN(0,B,A,C) THN(2,A,C,B) A > B THN(0,C,B,A) THN(1,C,A,B) C >B THN(0,A,C,B) THN(3,A,B,C) A > C THN(0,B,A,C) THN(1,B,C,A) B > A THN(0,C,B,A) THN(2,B,A,C) B > C THN(0,A,C,B) THN(1,A,B,C) A > C THN(0,B,A,C) Với THN(0 ,X , Y , Z ) là trường hợp neo tương ứng với thao tác rỗng . X > Y là thao tác chuyển 1 đĩa từ cột X sang cột Y (MOVE(X,Y)). Các bước chuyển đĩa sẻ là : A > C ; A > B ; C > B ; A > C ; B > A ; B > C ; A > C ; Lời gọi cấp 0 : THN(3 , A , B , C ) sẻ làm nảy sinh hai lời gọi cấp 1 : THN (2 ,A, C, B) ; THN (2 , B , A , C ) cùng với các thông tin của qúa trình xử lý còn dang dở . Các lời gọi cấp 1 : THN(2 , A , C , B ) , THN (2 , B , A ,C ) sẻ làm nảy sinh các lời gọi cấp 2 : THN (1 ,A, B, C) ; THN (1, C , A , B ) ; THN (1 ,B, C, A) ; THN (1, A , B , C ) ; cùng với các thông tin của qúa trình xử lý còn dang dở . Các lời gọi cấp 2 : THN(1 ,A, B, C) ; THN(1, C , A , B ) ; THN(1 ,B, C, A) ; THN(1, A , B , C ) ; sẻ làm nảy sinh các lời gọi cấp 3 dạng : THN(0 ,X, Y, Z) (thao tác rỗng tương ứng với trường hợp suy biến ); cùng với các thông tin của qúa trình xử lý còn dang dở . Quá trình gọi dừng lại khi gặp trường hợp suy biến . Qúa trình xử lý ngược với quá trình gọi bắt đầu khi thực hiện xong các trường hợp neo nhằm hoàn thiện các bước xử lý con dang dở song song với quá trình hoàn thiện các lời gọi là qúa trình loại bỏ các lưu trử thông tin giải thuật trung gian. 1 - 31 - Do đặc điểm của qúa trình xử lý một giải thuật đệ quy là : việc thực thi lời gọi đệ quy sinh ra lời gọi đệ quy mới cho đến khi gặp trường hợp suy biến (neo ) cho nên để thực thi giải thuật đệ quy cần có cơ chế lưu trử thông tin thỏa các yêu cầu sau : + Ở mỗi lần gọi phải lưu trữ thông tin trạng thái con dang dở của tiến trình xử lý ở thời điểm gọi. Số trạng thái này bằng số lần gọi chưa được hoàn tất . + Khi thực hiện xong (hoàn tất) một lần gọi, cần khôi phục lại toàn bộ
thông tin trạng thái trước khi gọi . + Lệnh gọi cuối cùng (ứng với trương hợp neo) sẽ được hoàn tất đầu tiên , thứ tự dãy các lệnh gọi được hoàn tất ngược với thứ tự gọi, tương ứng dãy thông tin trạng thái được hồi phục theo thứ tự ngược với thứ tự lưu trử . Cấu trúc dữ liệu cho phép lưu trữ dãy thông tin thỏa 3 yêu cầu trên là cấu trúc lưu trử thỏa luật LIFO (Last In Firt Out ) . Một kiểu cấu trúc lưu trử thường được sử dụng trong trường hợp này là cấu trúc chồng (stack). Với một chồng S thường cho phép chúng ta thực hiện các thao tác sau trên nó : - Thủ tục Creatstack(S) : Tạo chồng S rỗng . - Thủ tục Push(x,S) : Lưu trữ thêm dữ liệu x vào đĩnh stack S ( x là dữ liệu kiểu đơn giản giản hoặc có cấu trúc ) - Thủ tục Pop(x,S) : Lấy giá trị đang lưu ở đĩnh S chứa vào trong đối tượng dữ liệu x và loại bỏ giá trị này khỏi S ( lùi đỉnh S xuống một mức ) . - Hàm Empty(S) : ( kiểu boolean ) Kiểm tra tính rỗng của S : cho giá trị đúng nếu S rỗng , sai nếu S không rỗng . Cài đặt cụ thể của S có thể thực hiện bằng nhiều phương pháp phụ thuộc vào từng ngôn ngữ lập trình và từng mục đích sử dụng cụ thể . Ví dụ : Cài đặt ( bằng cấu trúc mảng ) chồng S mà mỗi phần tử là một đối tượng dữ liệu thuộc kiểu T trong PASCAL như sau : Const sizestack = . . . ; Type stackType = record St : array [1 . . sizestack ] of T ; Top : 0 . . sizestack ; end ; Thủ tục Creatstack(S) : tạo chồng S rỗng : Procedure Creatstack( var S : StackType ) Begin S.Top := 0 ; End; Thủ tục Push(x,S) : Chèn - Lưu trữ thêm dữ liệu x vào đĩnh stack S ( x là dữ liệu kiểu đơn giản giản hoặc có cấu trúc ) Procedure Push( var S : StackType ; x : T) ; Begin 1 - 32 - S.St[S.Top +1] := x ; S.Top := S.Top + 1 ; End; Thủ tục Pop(x,S) : Xóa - Lấy giá trị đang lưu ở đĩnh S chứa vào trong đối tượng dữ liệu x và loại bỏ giá trị này khỏi S ( lùi đỉnh S xuống một mức ) . Procedure Pop( var S : StackType ; var x : T ) ; Begin x := S.St[S.Top] ; S.Top := S.Top - 1 ; End; Hàm Empty(S) : ( Hàm boolean ) Kiểm tra tính rỗng của Stack S
Function Empty( S : StackType ) : boolean ; Begin Empty := ( S.Top = 0 ) ; End ; Mô hình stack S và tác dụng các thao tác trên nó . ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– ––––––––– 3 ––––––––– 3 ––––––––– 3 ––––––––– 3 ––––––––– 2 ––––––––– 2 ––––––––– 2 –– x 1 ––– 2 ––––––––– 1 ––––––––– 1 –––x o –– 1 –––x o –––– 1 –––x o –––– Createstack(S) ; Push(S, xo ) ; Push(S,x1 ) ; pop(S,y) ( S.top = 0 ) S.St[1] := xo S.St[2] := x1 y := x1 S.top := 1 S.top := 2 S.Top := 1 ; NNLT PASCAL và C++ thực hiện được cơ chế đệ qui nhờ trong quá trình biên dịch, phần mềm ngôn ngữ tự động phát sinh ra cấu trúc stack để quản lý các lệnh gọi chương trình con. Khi một lệnh gọi chương trình con thực hiện, các biến địa phương (gồm cả các thông số) sẽ được cấp phát vùng nhớ mới ở đỉnh stack. Nhờ vậy các tác động địa phương của thủ tục sẽ không làm thay đổi các trạng thái xử lý còn dang dở. II. TỔNG QUAN VỀ VẤN ĐỀ KHỬ ĐỆ QUY. Đệ quy là phương pháp giúp chúng ta tìm giải thuật cho các bài toán khó . Giải thuật giải bài toán bằng đệ quy thường rất đẹp (gọn gàng, dễ hiểu ,dễ chuyển thành 1 - 33 - chương trình trên các NNLT) . Nhưng như đã chỉ ra ở trên việc xử lý giải thuật đệ quy lại thường gây khó khăn cho máy tính (tốn không gian nhớ và thời gian xử lý), hơn nữa không phải mọi NNLT đều cho phép mã hóa giải thuật đệ quy (ví dụ : FORTRAN) . Vì vậy việc thay thế một chương trình đệ quy ( có chứa chương trình con đệ quy ) bằng một chương trình không đệ quy cũng là một vấn đề được quan tâm nhiều trong lập trình . Một cách tổng quát người ta đã chỉ ra rằng : Mọi giải thuật đệ quy đều có thể thay thế bằng một giải thuật không đệ quy . Vấn đề còn lại là kỹ thuật xây dựng giải thuật không đệ quy tương ứng thay thế giải thuật đệ quy . Rất đáng tiếc việc xậy dựng giải thuật không đệ quy thay thế cho một giải thuật đệ quy đã có lại là một việc không phải bao giờ cũng đơn giản và đến nay vẫn chưa có giải pháp thỏa đáng cho trường hợp tổng quát. Sơ đồ để xây dựng chương trình cho một bài toán khó khi ta không tìm được giải thuật không đệ quy thường là : + Dùng quan niệm đệ quy để tìm giải thuật cho bài toán . + Mã hóa giải thuật đệ quy . + Khử đệ quy để có được một chương trình không đệ quy . Tuy nhiên do việc khử đệ quy không phải bao giờ cũng dễ và vì vậy trong nhiều trường hợp ta cũng phải chấp nhận sư dụng chương trình đệ quy . III. CÁC TRƯỜNG HỢP KHỬ ĐỆ QUY ĐƠN GIẢN. 1. Các trường hợp khử đệ quy bằng vòng lặp . a) Hàm tính gía tri của dãy dữ liệu mô tả bằng hồi quy .
a1) Ý tưởng dẫn dắt : Xét một vòng lặp trong đó sử dụng 1 tập hợp biến W = (V , U ) gồm tập hợp U các biến bị thay đổi trong vòng lặp và V là các biến còn lại. Dạng tổng quát của vòng lặp là : W := Wo ; { Wo = ( Uo,Vo) } while C(U) do U := g(W) (3.1.1) Gọi Uo là trạng thái của U ngay trước vòng lặp , Uk với k >0 là trạng thái của U sau lần lặp thứ k (giả sử còn lặp đến lần k ) . Ta có : Uo mang các giá trị được gán ban đầu Uk = g(W) = g(Uk-1 , Vo ) = f(uk-1) với k = 1 n (3.1.2) Với n là lần lặp cuối cùng , tức C(Uk ) đúng với mọi k no Ví dụ : Hàm giai thừa FAC (n) = n ! = 1 khi n = 0 = n * FAC(n - 1) khi n > 0 Tổng n số đầu tiên của dãy đan dấu sau : Sn = 1 - 3 + 5 - 7 + (-1)n+1 * (2n-1) S(k) = 1 khi k =1 = S(k-1) + (- 1)k+1 *(2*k-1) với k > 1 - Giải thuật đệ quy tính giá trị f(n) f(n) = if(n = no) then return C ; else return (g(n,f(n -1)) ; - Giải thuật lặp tính giá tri f(n) k := no ; F := C ; { F = f(no) } While( k < n ) do begin k := k +1 ; F := g(k,F ) ; end ; } { F = f(n) } Hoặc : F := C ; For k := no to n -1 do begin k := k + 1 ; F := g(k,F) ; end ; Trong trường hợp này : W = U = ( k ,F ) Wo = Uo = ( no,C ) C(U) = ( k < n)
f(W) = f(U) = f(k,F) = (k+1,g(k,F))) Ví dụ 1: Hàm tính FAC(n) = n! không đệ quy + Trong NN LT PASCAL Function FAC ( n : integer ) : longint ; var k : integer ; F : longint ; Begin F := 1 ; k := 0 ; while (k < n ) do begin 1 - 35 - k := k + 1 ; F := F * k ; end ; FAC := F ; end ; hoặc : Function FAC ( n : integer ) : longint ; var k : integer ; F : longint ; Begin F := 1 ; For k:= 1 to n do F := F * k ; FAC := F ; end ; + Trong NN LT C++ long int FAC ( int n ) { int k = 0 ; long int F = 1 ; while ( k < n ) F = ++k * F ; return (F) ; } Hoặc : long int FAC ( int n ) { long int F = 1 ; for ( int k = 1; k <= n ; k++) F = k * F ; return (F) ; } Ví du 2 : Dạng hàm Sn không đệ quy + trên NN LT Pascal : Function S(n : integer ) : integer ; var k ,tg : integer ; Begin k := 1 ; tg := 1 ; while ( k < n ) do begin k := k + 1 ; if odd (k) then tg := tg + (2 * k - 1 )
else tg := tg - (2 * k - 1 ) ; end ; S := tg ; end ; 1 - 36 - + Trong NN LT C++ int S ( int n ) { int k = 1 , tg = 1 ; while ( k < n ) { k ++ ; if (k%2) tg + = 2 * k - 1 ; else tg - = 2 * k + 1 ; } return ( tg ) ; } b) Các thủ tục đệ qui dạng đệ qui đuôi. Xét thủ tục P dạng : P(X) = if B(X) then D(X) else { A(X) ; P(f(X)) ; } Trong đó : X là tập biến ( một hoặc một bộ nhiều biến ). P(X) là thủ tục đệ quy phụ thuộc X A(X) ; D(X) là các nhóm thao tác (lệnh ) không đệ quy f(X) là hàm biến đổi X Xét qúa trình thi hành P(X) : gọi Po là lần gọi P thứ 0 (đầu tiên ) P(X) P1 là lần gọi P thứ 1 (lần 2) P(f(X)) Pi là lần gọi P thứ i ( lần i + 1) P(f(f( f(X) ) ( P(fi(X)) hợp i lần hàm f ) Trong lần gọi Pi nếu B(fi(X)) không đúng (false) thì thi hành lệnh A và gọi Pi+1 ; nếu B(fi(X)) đúng (true) thì thi hành lệnh D và kết thúc qúa trình gọi . Giả sử P được gọi đúng n +1 lần . Khi đó ở trong lần gọi cuối cùng (thứ n ) Pn thì B(fn(X)) đúng , lệnh D được thi hành và chấm dứt thao tác gọi thủ tục P . Sơ đồ khối quá trình thực hiện lệnh gọi thủ tục P(X) có dạng sau : 1 - 37 - P(X) True False B(X) A(X) ; X : = f(X) END
D(X) Tương ứng với vòng lặp sau : While ( not B(X) ) do begin A(X) ; X := f(X) ; end ; D(X) ; Ví dụ 1 : Để đổi 1 số nguyên không âm y ở cơ số 10 sang dạng cơ số k ( 2 0 then Begin A[m] := n mod k ; Convert(n div k , m -1) ; End ; 1 - 38 - Lệnh gọi Convert(y,n) dùng để đổi số nguyên y trong cơ số 10 sang cơ số k lưu dãy ký số trong mảng A ; Trong ví dụ này ta có : X là ( n, m ) ; B(X) là biểu thức boolean not( n 0) then begin A[m] := n mod k ; { A(X) } n := n div k ; { X := f(X) } m := m - 1 ; end ; Ví dụ 2 : Tìm USCLN của 2 số nguyên dựa vào thuật toán Euclide . - Giải thuật đệ quy (dưới dạng thủ tục ) tìm USCLN(m,n) bằng thuật toán Euclide : USCLN(m , n , var us) = if ( n = 0 ) then us := m else USCLN(n , m mod n , us ) ; - Trong trường hợp này thì : X là ( m , n , us ) P(X) là USCLN(m ,n ,us) B(X) là n = 0 D(X) là lệnh gán us := m A(X) là lệnh rỗng f(X ) là f(m,n,us) = ( n , m mod n ,us )
- Đoạn lệnh lặp tương ứng là : While (n 0 ) do begin sd := m mod n ; m := n ; n := sd ; end ; us := m ; end ; - Hàm con không đệ quy tương ứng trong C++ void USCLN(int m , int n , int& us ) { while(n != 0 ) { int sd = m % n ; m = n ; n = sd ; } us = m ; } c) Các hàm đệ qui dạng đệ qui đuôi (tail-recusive). Xét hàm đệ qui dạng : f(g(X)) khi C (X) đúng f ( X ) = a (X ) khi C (X) sai Tức là : f ( X ) = if( C(X) ) then return( f(g(X)) else return( a(x)) Tính f(Xo ) . Ta có : f(Xo ) = f(g(Xo )) vơí C(Xo ) đúng . = f(g(g(Xo ))) với C(g(Xo )) đúng . = = f(gk (Xo )) với C(gk-1 (Xo )) đúng . = a(gk (Xo )) với C(gk (Xo )) sai. ( gk(xo) = g(g (g (xo))))) ) Đặt : Uo = Xo = go (Xo ) Ui = gi (Xo ) = g(gi-1 (Xo )) = g(Ui-1 ) với i >= 1 Ta có quan hệ sau :
1 - 40 - Uo = Xo Ui = g(Ui-1 ) i = 1 k . Với k là số nhỏ nhất mà C(Uk ) sai . Lúc đó : f(Xo ) = a(Uk ) Vậy đoạn chương trình tính f = f(Xo) là : U := Xo ; while C(U) do U := g(U) ; f := a(U) ; Ví dụ : Với m , n > = 0 ta có hàm đệ quy tính USCLN(m,n) là : USCLN(m ,n ) = if (m 0 ; g(X) = g(m ,n ) = (abs(m -n ) , min (m ,n ) ) ; a(x) = a(m ,n ) = n ; - Đoạn chương trình tính USCLN(a ,b) là : m := a ; n := b ; while ( m 0 ) do begin t1 := m ; t2 := n ; m := abs(t1 - t2 ) ; if(t1 < t2 ) then n := t1 else n := t2 ; end ; USCLN := m ; - Dạng hàm tương ứng trong C++ int USCLN(int m , int n) { while( n != 0) { int t1 = m ; int t2 = n ; 1 - 41 - m = abs(t1-t2) ; if(t1<t2) n = t1 ; else n = t2 ; } return(m) ;
} 2. Khử đệ quy hàm đệ quy arsac a) Dạng hàm đệ qui ARSAC. a1) Dạng toán học : DS(A(CS(X) ) , FS(CS(X) , X ) ) ) khi C(X) đúng A(X) = BS(X) khi C(X) sai a2) Dạng mã giả : A(X ) = if C(X) then return ( DS (A(CS(X)) ,FS(CS(X),X) ) else return (BS(X ) ) Với : BS , CS , DS , FS là các giải thuật không đệ qui . Trường hợp thường gặp là : BS(X) , CS(Y) , DS(U,V) , FS(U,V) là các thao tác đơn giản , không có lệnh gọi hàm con . X , Y ,U , V là biến đơn trị hoặc biến véc tơ . Đây là dạng tổng quát của hàm đệ quy chỉ gọi đến chính nó một lần . b) Sơ đồ tổng quát tính gía trị A(X) : Gọi Uo = X là gía trị đối số cần tính của hàm A . Việc tính A(Uo) sẽ phát sinh lệnh gọi tính A(U1) với U1 = CS(Uo) ( gỉa sử C(Uo) true ). Cứ như vậy , khi mà C(Ui ) còn đúng thì việc tính A(Ui ) sẽ phát sinh lệnh tính A(Ui+1) với Ui+1 = CS(Ui ). Với giả thiết là Uo = X thuộc miền xác định của A , thì quá trình lặp lại các lệnh gọi này phải dừng lại sau hữu hạn lần gọi . Tức là . k thỏa : C(Uo) = C(U1) = . . = C(Uk-1) = true , C(Uk) = false. Xét 2 dãy số : - Dãy : { Ui } = { CS(Ui) } ( 2.1) Uo = X { cho trước } Ui+1 = CS(Ui) i = 0 . . k-1 - Dãy : { Vi } = { A(Ui) } (2.2) Vo = A(Uo) = A(Xo) ( gía trị cần tính ). Vi = A(Ui) = DS(A(CS(Ui ), FS(CS(Ui), Ui ) ) 1 - 42 - = DS(A(Ui+1),FS(Ui+1,Ui)) = DS(Vi+1,FS(Ui+1,Ui)) với 0< i < k ( vì C(Ui) đúng ) Vk = BS(Uk) ( vì C(Uk) = false ) Dựa vào 2 dãy số {Ui } ,{Vi} ( mô tả bởi (2.1) và (2.2) ) ta tính A(X ) theo giải thuật sau : - Tính và ghi nhớ các Ui từ 0 đến k theo (2.1). ( Với C(Uo) = C(U1) = = C(Uk-1) = True , C(Uk) = False ) - Sử dụng dãy gía trị Ui để tính lần ngược Vi từ k xuống 0 theo (2.2) , Vo chính là gía trị cần tính ( Vo = A(X ) ). c) Giải thuật không đệ quy tính gía trị hàm Arsac bằng sử dụng cấu trúc Stack . Để thực hiện giải thuật trên thì dãy Ui phải được tính và lưu trử trong một cấu trúc dữ liệu thích hợp , để khi cần đến (khi tính Vi ) dễ lấy ra sử dụng . Đặc điểm quan trong của dãy Ui là thỏa luật LIFO : thứ tự sử dụng ngược với thứ tự tạo sinh . Cấu trúc dữ liệu cho phép lưu trữ thuận lợi dãy phần tử thỏa luật LIFO ( vào sau ra
trước - Last In First Out ) là câu trúc Stack . ( Trên cấu trúc Stack 2 thao tác cơ bản đặc trưng là : + Push(S,X) : Chèn phần tử dữ liệu X vào đĩnh Stack S . + Pop(S,X) : Lấy ra khỏi stack S phần tử dữ liệu ở đĩnh và chứa nó vào biến X ). Giải thuật không đệ qui tính Vo = A(X) dựa trên 2 công thức (2.1 ) , (2. 2 ) và sử dụng Stack S là : + Bước 1 : tính Ui bắt đầu từ Uo theo (2.1) lưu vào Stack S CreateStack(S) ; ( tạo stack rỗng S ) k := 0 ; U := X ; ( Uo = X ) push(S,U) ; ( chèn UO vào đĩnh stack S ) while C(U) do begin k := k+1 ; U := CS(U) ; ( Uk+1 = CS(Uk)) push (S,U) ; ( chèn Uk+1 vào đĩnh Stack S ) end ; + Bước 2 : Lấy dữ liệu trong Stack S tính Vi theo (2. 2) pop(S,U) ; ( U = Uk ) V := BS(U) ; ( C(Uk) sai ; V=Vk = BS (Uk)) for i := k -1 downto 0 do begin Y := U ; ( Y = Ui+1) 1 - 43 - pop(S,U) ; ( U = Ui ) V := DS(V,FS(Y,U)) ; ( C(Ui) đúng ; Vi = DS(Vi+1,FS(Ui+1,Ui)) ) end ; { V = A(Xo) } Hoặc : + Bước 1 : tính Ui bắt đầu từ Uo theo (2.1) lưu vào Stack S CreateStack(S) ; ( tạo stack rỗng S ) U := Xo ; ( Uo = Xo ) push(S,U) ; ( chèn UO vào đĩnh stack S ) while C(U) do begin U := CS(U) ; ( UK+1 = CS(UK)) push (S,U) ; ( chèn Uk+1 vào đĩnh Stack S ) end ; + Bước 2 : Lấy dữ liệu trong Stack S tính Vi theo (2. 2) pop(S,U) ; ( U = Uk ) V := BS(U) ; ( C(Uk) sai ; V=Vk = BS (Uk)) While(not emptystack(S)) do begin Y := U ; ( Y = Ui+1) pop(S,U) ; ( U = Ui ) V := DS(V,FS(Y,U)) ; ( C(Ui) đúng ; Vi = DS(Vi+1,FS(Ui+1,Ui)) )
end ; { V = A(Xo) } Cơ chế lưu trử dãy dữ liệu LIFO bằng Stack là một đặc trưng của quá trình xử lý giải thuật đệ quy điều cần quan tâm là cấu trúc stack thường chiếm nhiều bộ nhớ . Vì vậy người ta luôn tìm cách tránh dùng nó khi còn tránh được . d) Một số hàm Arsac đặc biệt mà việc khử đệ qui giải thuật tính gía trị hàm có thể không dùng Stack . d1) Trường hợp thủ tục CS là song ánh . Trường hợp CS là song ánh từ miền D lên miền D thì hàm CS có hàm ngược CS-1 . Gọi hàm ngược của hàm CS là hàm CSM1 . Ta có : CSM1(CS(X)) = CS-1(CS(X)) = X với . X . D . Nên : CSM1(Ui+1) = CS-1(CS(Ui)) = Ui với i = k-1, . . ,1,0 Khi đó ta không cần lưu giữ các giá trị trung gian của dãy { Ui } mà chỉ cần xuất phát từ Uk dùng hàm CSM1 để khôi phục lại các gía trị Ui vói i<k . Giải thuật tính A(X ) sẽ trở thành : + Bước 1 : Dựa vào (2.1) tính Uk 1 - 44 - U := X ; ( Uo = X ) k := 0 ; while C(U) do begin k := k+1 ; U := CS(U) ; ( UK+1 = CS(UK)) end ; + Bước 2 : Tính Vk , Vk-1, V1, Vo dựa vào Uk ,(2.2) và CSM1 V := BS(U) ; ( V=Vk = BS (Uk) ) for i := k -1 downto 0 do begin Y := U ; ( Y = Ui+1 ) U := CSM1(U) ; (Ui = CSM1(Ui+1) ) V := DS(V,FS(Y,U)) ; ( Vi = DS(Vi+1,FS(Ui+1,Ui) ) end ; { V = Vo = A(X )} d2) Trường hợp thủ tục DS có tính hoán vị . Xét công thức tính : Vi = DS(Vi+1,FS(Ui+1,Ui)) với mọi i<k Đặt : U’i = FS(Ui+1,Ui ) DS(Vi+1,U’i) = Vi+1 T U’i Ta có : Vo = DS(V1, FS(U1,Uo) = DS(V1,U’o) = V1 T U’0 V1 = DS(V2, FS(U2,U1) = DS(V2,U’1) = V2 T U’1 V2 = DS(V3, FS(U3,U2) = DS(V3,U’2) = V3 T U’2 Vi = DS(Vi+1, FS(Ui+1,Ui) = DS(Vi+1,U’i) = Vi+1 T U’i ( 3 - 1 )
Vk-1 = DS(Vk, FS(Uk,Uk-1) = DS(Vk,U’k-1) = Vk T U’k-1 Vk = BS(Uk) Khi DS có tính hoán vị tức : DS(DS(x,y),z) = DS(DS(x,z),y) ( Viết trên ký hiệu T : (x T y) T z = (x T z) T y Thực hiện thế lần lượt V1 rồi V2 trong công thức Vo. Ta có : 1 - 45 - Vo = V1 T U’0 = ( V2 T U’1) T Uo = ( V2 T U’0 ) T U’1 = ( ( V3 T U’2) T U’o) T U’1 = ((V3 T U’2) T U’o ) T U’1 = ( (V3 T U’o) T U’2 ) T U’1 = ( (V3 T U’o) T U’1 ) T U’2 V0 = ( ((( Vk T U’o) T U’1) T U’2 ) T T U’k-2) T U’k-1 (3 - 2 ) (3 - 2) là một dãy liên tiếp ( một tổng ) k phép toán T mà ta đã biết giải thuật tính. Thực vậy : Thiết lập dãy Wi như sau : W0 = Vk Wi = Wi-1 T U’i-1 với i = 1 k Tức là : Wo = Vk = BS(Uk ) (3 - 3 ) Wi = Wi-1 T U’i-1 = DS(Wi-1,FS(Ui,Ui-1)) i=1 k Wk chính là gía trị Vo cần tính . Như vậy giải thuật tính Wk ( Vo = A(X ) ) gồm 2 bước : Bước 1: Xác định k và Uk theo công thức ( 1 - 1 ) Bước 2: Tính dãy Wi , trong lúc tính thì phải tính lại dãy Ui ,theo ( 3 - 3) A(X ) = Vo = Wk . Giải thuật không đệ qui tương ứng dược xem như bài tập . 3. Khử đệ quy một số dạng thủ tục đệ quy thường gặp. a) Dẫn nhập. Để thực hiện một chương trình con đệ quy thì hệ thống phải tổ chức vùng lưu tr. thỏa quy tắc LIFO (vùng Stack). Vì vậy chỉ những ngôn ngữ lập trình có khả năng tạo vùng nhớ stack mới cho phép tổ chức các chương trình con đệ quy. Thực hiện một chương trình con đệ quy theo cách mặc định thường tốn bộ nhớ vì cách tổ chức Stack một cách mặc định thích hợp cho mọi trường hợp thường là không tối ưu trong từng trường hợp cụ thể. Vì vậy sẻ rất có ích khi người lập trình chủ động tạo ra cấu trúc dữ liệu stack đặc dụng cho từng chương trình con đệ quy cụ thể . Phần tiềp theo sẻ trình bày việc khử đệ quy một số dạng thủ tục đệ quy theo hướng thay giải thuật đệ quy bằng các vòng lặp và một cấu trúc dữ liệu kiểu stack thích hợp . b) Thủ tục đệ qui chi có một lệnh gọi đệ quy trực tiếp . Mô hình tổng quát của thủ tục đệ quy chỉ có một lệnh gọi đệ quy trực tiếp là : P(X) = if C(X) then D(X) 1 - 46 - else begin A(X) ; P(f(X)) ; B(X) ;
end ; Với : X là một bién đơn hoặc biến véc tơ. C(X) là một biểu thức boolean của X . A(X) , B(X) , D(X) là các nhóm lệnh không đệ quy ( không chứa lệnh gọi đến P ). f(X) là hàm của X . Tiến trình thực hiện thủ tục P(X) sẻ là : + Nếu C(X) đúng thì thực hiện D(X) . + Còn không ( C(X) sai ) thì thực hiện A(X) ; gọi P(f(X)) ; thực hiện B(X) . ( B(X) chỉ được thực hiện khi P(f(X)) thực hiện xong ) . Mỗi lần thành phần đệ quy P(Y) được gọi thì thông tin giải thuật B(Y) lại được sinh ra (nhưng chưa thực hiện ) . Gỉa sử qúa trình đệ quy kết thúc sau k lần gọi đệ quy thì ta phải thực hiện một dãy k thao tác B theo thứ tự : B(fk-1(X)) , B(fk-2(X)) , . . . ,B(f(f(X))) ,B(f(X)),B(X). Để thực hiện dãy thao tác { B(fi(X)) } theo thứ tự ngược với thứ tự phát sinh ta cần dãy dữ liệu {fi(X) } truy xuất theo nguyên tắc LIFO. Ta sẻ dùng một Stack để lưu trử dãy { fi(X) } = { X , f(X) , f(f(X)) , . . . , fi(X) , . . . , fk-1(X) } Trình tự thực hiện P(X) được diễn tả bằng mô hình sau : P(X) C(X) = False A(X) ; Push(S,X); U:=f(X) ; P(U) ; POP(S,U) ; B(U) ( U = X ) C(U) = False A(U) ; Push(S,U); U :=f(U)); P(U) ; POP(S,U) ; B(U) ( U = f(X)) C(U) = False A(U) ; Push(S,U) ; U : = f(U)); P(U ) ; POP(S,U) ; B(U) C(U) = False A(U) ; > Push(S,U) ; U : = f(U)); P(U ) ; POP(S,U) ; B(U) ( U=fk-1(X) ) C(U) = True D(U ) 1 - 47 - Giải thuật thực hiện P(X) với việc sử dụng Stack có dạng : P(X) = { Creat_Stack (S) ; ( tạo stack S ) While(not(C(X)) do begin A(X) ; Push(S,X) ; ( cất gía trị X vào stack S ) X := f(X) ; end ; D(X) ; While(not(EmptyS(S))) do begin POP(S,X) ; ( lấy dữ liệu từ S ) B(X) ; end ; } Ví dụ : Thủ tục đệ quy chuyển biểu diễn số từ cơ số thập phân sang nhị phân có dạng : Binary(m) = if ( m > 0 ) then begin
Binary( m div 2 ) ; write( m mod 2 ) ; end; Trong trường hợp này : X là m . P(X) là Binary(m) . A(X) ; D(X) là lệnh rỗng . B(X) là lệnh Write(m mod 2 ) ; C(X) là ( m 0 ) do begin sdu := m mod 2 ; Push(S,sdu) ; m := m div 2 ; end; While( not(EmptyS(S)) do begin POP(S,sdu) ; Write(sdu) ; end; } 1 - 48 - c) Nhiều lệnh gọi đệ quy trực tiếp. c1) Thủ tục đệ quy với 2 lần gọi trực tiếp Thủ tục đệ quy 2 lần gọi trực tiếp có dạng : P(X) = if C(X) then D(X) else begin A(X) ; P(f(X)) ; B(X) ; P(g(X)) ; end ; Qúa trình thực hiện thủ tục P(X) sẻ là : - Nếu C(X) đúng thì thực hiện D(X) . - Nếu C(X) sai thì thực hiện A(X) ; gọi P(f(X)) ; thực hiện B(X) ; gọi P(g(X)) , khi gọi P(g(X)) thì lại phát sinh lệnh A(g(X)) như vậy ngoài việc phải lưu vào stack các gía trị fi(X) ta con phải lưu vào stack các gía trị gi(X) tương ứng . Khi ta lấy dữ liệu từ stack để thực hiện lệnh B(U) mà chưa gặp điều kiện kết thúc thì ta thực hiện P(g(U)) và lại phải lưu gía trị g(U) vào stack , Điều kiện dừng là khi truy xuất tới phần tử lưu đầu tiên trong stack . Như vậy là ngoài dữ liệu X , con phải lưu vào ngăn xếp thêm thứ tự lần gọi ( cụm gọi ) Thuật toán khử đệ quy tương ứng với thủ tục đệ quy P(X) là : { Creat_Stact (S) : Push (S, (X,1)) ; Repeat While ( not C(X) ) do begin
A(X) ; Push (S, (X,2)) ; X := f(X) ; end ; D(X) ; POP (S, (X,k)) ; if ( k 0 ) then begin THN ( n - 1 , X , Z , Y ) ; Move ( X , Z ) ; THN ( n - 1 , Y , X , Z ) ; end ; Với n là số đĩa , X là cột đầu , Z là cột cuối , Y là cột giữa ,Move(X,Z) là thao tác chuyển 1 đĩa từ cột X tới cột Z . Trong trường hợp này : Biến X là bộ ( n , X , Y , Z ) . C(X) là biểu thức boolean ( n 0 ) do begin Push (S ,(n,X,Y,Z,2)) ; n := n - 1 ; Swap (Y,Z ) ; (* Swap(a,b) là thủ tục hoán end ; đổi nội dung 2 biến a ,b *) POP (S,(n,X,Y,Z,k)) ; if ( k <> 1 ) then begin Move (X ,Z ) ; n := n - 1 ; Swap (X ,Y ) ; end ; until ( k = 1 ) ; }
c2) Trường hợp n lần gọi đệ quy trực tiếp . Thủ tục đệ quy trong trường hợp này có dạng : 1 - 50 - P(X) = if C(X) then D(X) else begin A1(X) ; P(f1(X)) ; A2(X) ; P(f2(X)) ; Ai(X) ; P(fi(X)) ; An(X) ; P(fn(X)) ; An+1(X) ; end ; Cũng giống như trong trường hợp (3a) là khi quay trở lại sau khi thực hiện một lần đệ quy, cần biết đó là lệnh gọi thuộc nhóm thứ mấy trong dãy lệnh gọi để biết thao tác cần thực hiện tiếp. Vì vậy trong chồng cần giữ thêm vị trí nhóm lệnh gọi . Dạng lặp tương ứng là : { Creat_Stack (S) ; Push(S,(X,1)) ; Repeat While (not C(X) ) do begin A1(X) ; Push (S,(X,2)) ; X := f1(X) ; end ; D(X) ; POP(S,(X,k)) ; While( k = n+1 ) do begin An+1 ; POP(S,(X,k)) ; end ; if ( k > 0 ) then begin Ak(X) ; Push (S,(X,k+1)); X := f k (X) end ; until (k = 1 ) ; } Ví dụ : Khử đệ quy cho thủ tục hoán vị . + Thủ tục hoán vị dưới dạng đệ quy : 1 - 51 - HVI(V ,n) = if (n = 1 ) then Print ( V ) else for i := n downto 1 do begin
Swap (V[n],V[i] ) ; HVI(V ,n - 1) : end ; trong trường hợp này thì : X là bộ (V ,n ) . (* vector V và số nguyên n *) C(X) là ( n = 1 ) . D(X) là Print (V) . (* xuất vector V *) Ai(X) là thủ tục Swap(V[n] ,V[i] ) ( i = 1 n ) . An+1 là thao tác rỗng . fi(X) = f(V, n ) = ( V, n - 1) .( với i = 1 . . n ) Dạng lặp của thủ tục là : { Creat_Stack (S) ; Push (S,(V ,n ,1)) ; Repeat While ( n > 1 ) do begin Swap(V[n] ,V[1] ; Push (S ,V , n ,2) ; n := n -1 ; end ; Print (V) ; POP (S ,(V ,n ,k)) ; While ( k = n +1 ) do POP(S ,(V ,n ,k) ; if(k <> 1 ) then begin Swap(V[n] ,V[k]) ; Push (S ,(V ,n ,k+1) ; n := n - 1 ; end ; until(k = 1 ) ; 1 - 52 - PHẦN II KIỂM CHỨNG CHƯƠNG TRÌNH CHƯƠNG IV CÁC KHÁI NIỆM I. CÁC GIAI ĐOẠN TRONG CUỘC SỐNG CỦA MỘT PHẦN MỀM Việc sử dụng máy tính để giải một bài toán thực tế thường bao gồm nhiều việc. Trong các công việc đó công việc mà người ta quan tâm nhất là việc xây dựng các hệ thống phần mềm (các hệ thống chương trình giải bài toán ). Để xây dựng một hệ thống phần mềm , người ta thường thực hiện trình tự các công việc sau : Đặc tả bài toán, xây dựng hệ thống, sử dụng và bảo trì. 1) Đặc tả bài toán Gồm việc phân tích để nắm bắt rõ yêu cầu của bài toán và diễn đạt chính xác lại bài toán bằng ngôn ngữ thích hợp vừa thích ứng với chuyên ngành tin học vừa có tính đại chúng ( dễ hiểu đối với nhiều người). 2) Xây dựng hệ thống
Trong bước này sẻ tuần tự thực hiện các công việc sau : - Thiết kế : Xây dựng mô hình hệ thống phần mềm cần có. Trong bước này, công việc chủ yếu là phân chia hệ thống thành các module chức năng và xác định rõ chức năng của từng module cũng như mối tương tác giữa các module với nhau. Chức năng của mỗi module được định rõ bởi đặc tả của từng module tương ứng. - Triển khai từng module và thử nghiệm : Viết chương trình cho từng module (bài toán con) thỏa "đúng" đặc tả đã đặt ra. Tính đúng của chương trính được quan tâm bằng 2 hướng khác nhau : + Chứng minh tính đúng một cách hình thức (thường là một công việc khó khăn) . + Chạy thử chương trình trên nhiều bộ dữ liệu thử khác nhau mỗi bộ dữ liệu đại diện cho một lớp dữ liệu (thường là một công việc tốn kém ). Để có tính thuyết phục cao, người ta cần chạy thử trên càng nhiều bộ dữ liệu càng tốt. Khi thử nếu phát hiện sai thì phải sửa lại chương trình còn chưa phát hiện sai thì ta con tạm tin chương trình đúng (chạy thử chỉ có tác dụng phát hiện sai và tăng lòng tin vào tính đúng chứ không chứng minh được tính đúng ). 1 - 53 - - Thử nghiệm ở mức độ hệ thống : Sau khi từng module hoạt động tốt, ngưòi ta cần thử sự hoạt động phối hợp của nhiều module, thư nghiệm toàn bộ hệ thống phần mềm. Thử nghiệm tính đúng theo bất cứ cách nào thì cũng rất tốn thời gian và công sức nhưng lại là một việc phải làm của người lập trình vì người lập trình luôn luôn phải bảo đảm chương trình mình tạo ra thỏa đúng đặc tả. 3) Sử dụng và bảo trì hệ thống Sau khi hệ thống phần mềm hoạt động ổn định, người ta đưa nó vào sử dụng. Trong quá trình sử dụng có thể có những điều chỉnh trong đặc tả của bài toán, hay phát hiện lỗi sai của chương trình. Khi đó cần xem lại chương trình và sửa đổi chúng. Các yêu cầu sau cho qúa trình xây dựng phần mềm : a) Cần xây dựng các chương trình dễ đọc, dễ hiểu và dễ sửa đổi. Điều này đòi hỏi một phương pháp tốt khi xây dựng hệ phần mềm : phân rã tốt hệ thống , sử dụng các cấu trúc chuẩn và có hệ thống khi viết chương trình ,có sưu liệu đầy đủ . b) Cần đảm bảo tính đúng. Làm thế nào để xây dựng một chương trình "đúng" ? Một điều cần chú ý là: Phép thử chương trình chỉ cho khả năng chỉ ra chương trình sai nếu tình cờ phát hiện được chứ không chứng minh được chương trình đúng vì không thể thử hết được mọi trường hợp. Vì vậy người ta luôn cố gắng chứng minh chương trình đúng của chương trình bằng logic song song với chạy thử chương trình. Có 2 cách chính thường được sử dụng để đảm bảo tính đúng của phần mềm trong quá trình xây dựng hệ thống : - Viết chương trình rồi chứng minh chương trình đúng. - Vừa xây dựng vừa chứng minh tính đúng của hệ thống. Việc tìm kiếm những phương pháp xây dựng tốt để có thể vừa xây dựng vừa kiểm chứng được tính đúng luôn là một chủ đề suy nghĩ của những người lập trình . II. ĐẶC TẢ 1. Đặc tả bài toán a) Khái niệm.
Khi có một vấn đề ( một bài toán) cần được giải quyết , người ta phát biểu bài toán bằng một văn bản gọi là đặc tả bài toán (problem specification). Các bài toán đặt ra cho những người làm công tác tin học thường có dạng sau : Xây dựng một hệ thống xử lý thông tin mà hoạt động của nó : - Dựa trên tập dữ liệu nhập (thông tin vào) thoả mãn những điều kiện nhất định. - Xẩy ra trong một khung cảnh môi trường hạn chế nhất định. - Mong muốn sản sinh ra một tập dữ liệu xuất (thông tin ra ) được quy định trước về cấu trúc và có mối quan hệ với dữ liệu nhập và môi trường được xác định trước . 1 - 54 - Những khía cạnh trên được thể hiện trong đặc tả bài toán (ĐTBT) . b) Tác dụng của đặc tả bài toán . - Là cơ sở để đặt vấn đề, để truyền thông giữa những người đặt bài toán và những người giải bài toán . - Là cơ sở để những người giải bài toán triển khai các giải pháp của mình . - Là cơ sở để những người giải bài toán kiểm chứng tính đúng của phần mềm tạo ra . - Là phương tiện để nhiều người hiểu tính năng của hệ thống tin học mà không cần (thường là không có khả năng) đi vào chi tiết của hệ thống . Để đạt được 4 mục tiêu trên, ĐTBT cần gọn, rõ và chính xác . Để đạt được mục tiêu thứ 2, thứ 3 thì ngôn ngữ để viết ĐTBT cần phải có tính hình thức (formal) và trên ngôn ngữ này cần có các phương tiện để thực hiện các chứng minh hình thức . Ngôn ngữ thích hợp với yêu cầu này là ngôn ngữ toán học và hệ logic thích hợp là logic toán học. Người ta thường sử dụng ngôn ngữ bậc nhất (với các khái niệm và toán tử toán học) và logic bậc nhất . Tuỳ theo mức độ phức tạp của bài toán mà phương tiện diễn đạt ĐTBT có những mức độ phức tạp và mức độ hình thức khác nhau . Ở mức bài toán lớn, trong mối quan hệ giữa người sử dụng và người phân tích, người ta dùng : sách hợp đồng trách nhiệm (cahier des charges), sơ đồ tổ chức, biểu đồ luân chuyển thông tin Giữa những người phân tích, người ta dùng phiếu phân tích các đơn vị chức năng, biểu đồ chức năng Kết quả phân tích được chuyển thành yêu cầu với người lập trình bằng các đặc tả chương trình (ĐTCT - program specification) . 2. Đặc tả chương trình (ĐTCT). ĐTCT gồm các phần sau : - Dữ liệu nhập : Các dữ kiện mà chương trình sử dụng . Đặc trưng quan trọng là danh sách dữ liệu nhập và cấu trúc của chúng , có khi cần nêu nguồn gốc , phương tiện nhập của mỗi dữ liệu nhập . - Điều kiện ràng buộc trên dữ liệu nhập : là những điều kiện mà dữ liệu nhập phải thoả để hệ thống hoạt động đúng . Chương trình không bảo đảm cho kết quả đúng khi thực thi các bộ dữ liệu không thoả các điều kiện này . Trong phần mô tả dữ kiện nhập cần nêu lên : + Cấu trúc : kiểu dữ liệu ( các thành phần, sự kết nối các thành phần ). + Các ràng buộc trên gía trị của chúng . - Dữ liệu xuất : Các dữ liệu mà chương trình tạo ra . Cũng như phần dữ liệu nhập, cần nêu rõ danh sách dữ liệu xuất, cấu trúc của chúng, có khi cần nêu phương tiện xuất của từng dữ liệu xuất.
1 - 55 - - Điều kiện ràng buộc trên dữ liệu xuất: Những điều kiện ràng buộc mà dữ liệu xuất phải thoả. Chúng thể hiện yêu cầu của người sử dụng đối với chương trình. Các điều kiện này thường liên quan đến dữ liệu nhập . Ví dụ 1 : Viết chương trình đọc vào một số nguyên dương N rồi xuất ra màn hình N số nguyên tố đầu tiên. Đặc tả chương trình : + Dữ liệu nhập : một số nguyên N . + Điều kiện nhập : N > 0 , nhập vào từ bàn phím. + Dữ liệu xuất : một dãy gồm N số nguyên . + Điều kiện xuất : là dãy N số nguyên tố đầu tiên , xuất ra màm hình . Ví dụ 2 : Viết chương trình đọc vào một dãy N số nguyên , xuất ra màn hình dãy đã sắp xếp theo thứ tự không giảm. Đặc tả chương trình : + Dữ liệu nhập : một array A có N phần tử là số nguyên . + Điều kiện nhập : nhập từ bàn phím . + Dữ liệu xuất : array A' có N phần tử là số nguyên. + Điều kiện xuất : xuất ra màn hình ,A' là một hoán vị của A , A' là một dãy không giảm. ( 1 A'[i] 0) and (b > 0) } // ràng buộc trên trạng thái đầu .
x := a ; y := b ; u := 0 ; { ( x = a ) and (y = b ) and ( (u + x*y ) = (a*b) ) } // ràng buộc trung gian trên repeat {(u+x*y = a*b) and ( y>0 ) } trạng thái của CT. u := u + a ; y := y - 1 ; {(u+x*y = a*b) and (y >= 0) } // ràng buộc trung gian trên trạng thái until (y= 0) của chương trình. {u= a*b} // ràng buộc trên trạng thái xuất Mỗi tân từ trong ví dụ trên mô tả một tập các trạng thái có thể có ở điểm đó. Ví dụ 2 : Đoạn chương trình hoán đổi nội dung của 2 biến x và y, dùng biến t làm trung gian. {( x = xo) and (y = yo ) } // x , y mang giá trị ban đầu bất kỳ nào đó t := x ; x := y ; y := t { (x = yo ) and (y = xo ) } // x , y sau cùng mang giá trị hoán đổi của nhau. Trong ví dụ này để biểu diễn quan hệ giữa nội dung các biến với nội dung của một số biến bị gán trị, người ta cần phải dùng các biến giả (ghost variable). Ví dụ ở đây là xo và yo biểu thị nội dung của x và y trước khi thực hiện đoạn chương trình. Ví dụ 3 : Nhân 2 số nguyên dương x , y, kết quả chứa trong u . { (x = xo > 0) and (y = yo > 0 )} u := 0 ; repeat u := u + x ; y := y - 1 ; until (y = 0) { u = xo * yo } Thật ra ở đây tập hợp các trạng thái xuất thực sự là nhỏ hơn, biểu thị bởi một điều kiện chặt hơn, đó là : {( u = xo * yo ) and (y = 0) and (x = xo ) } Tổng quát ta cần khảo sát một đoạn chương trình S với 2 điều kiện đi trước P và đi sau Q . Cần chứng minh rằng nếu xuất phát từ trạng thái thoả P thi hành lệnh S thì 1 - 57 - cần đạt tới trạng thái thỏa Q . P được gọi là điều kiện đầu (precondition) , Q được gọi là điều kiện cuối (postcondition). Cặp tân từ (P,Q) , được gọi đặc tả của đoạn lệnh S. Bộ 3 S, P, Q tạo nên một đặc tả đoạn lệnh thường được mô tả hình thức bằng tập ký hiệu : { P } S { Q } ( { P } : tập trạng thái thỏa tân từ P , { Q } : tập trạng thái thỏa tân từ Q ) Việc thiết lập các khẳng định ở những điểm khác nhau trong chương trình nhằm để : + Hoặc là đặc tả một đoạn chương trình cần phải xây dựng : tìm S thỏa P, Q cho trước. + Hoặc là cơ sở để chứng minh tính đúng của đoạn chương trình S ( đoạn chương trình S thoả đặc tả ). + Hoặc để đặc tả ngữ nghĩa đoạn chương trình (thực hiện sưu liệu chương trình)
nhằm mục đích làm người đọc hiểu được ý nghĩa của đoạn chương trình III. NGÔN NGỮ LẬP TRÌNH. Để kiểm chứng tính đúng của một đoạn chương trình, đầu tiên cần trình bày đoạn chương trình đó trong một dạng ngôn ngữ lập trình chuẩn mực ở dạng cốt lõi. Ngôn ngữ lập trình ở dạng cốt lõi chỉ bao gồm các thao tác chuẩn : lệnh gán, lệnh điều kiện, lệnh lặp while và lệnh ghép (dãy tuần tự các lệnh ). Cú pháp của ngôn ngữ cốt lõi được định nghĩa trong dạng BNF như sau : ::= | dãy lệnh ::= | | ::= | ';' ::= | 'begin' 'end' ::= ':=' ::= 'if' 'then' 'else' | 'if' 'then' ::= 'while' 'do' Định nghĩa trên xác định rằng mỗi mà ta khảo sát có thể là : - : bao gồm các trường hợp : + Ví dụ : Y := ( X + Y ) * Z ; + mà sau 'then' hay 'else' có thể là một hay một được bắt đầu bởi 'begin' và chấm dứt bởi 'end'. Ví dụ : if (x > 0) then y := z else begin z := x * 2 ; if( z = y) then y := 0 end ; + với một biểu thị điều kiện lặp và 1 - 58 - Ví dụ : while (x > 0) do begin y := x ; while ( y > 0) do y := y -1 ; x := x - 1 ; end ; - chính là dãy tuần tự các ngăn cách bởi dấu ';' 1 - 59 - CHƯƠNG V KIỂM CHỨNG TÍNH ĐÚNG CÓ ĐIỀU KIỆN I. CÁC KHÁI NIỆM VỀ TÍNH ĐÚNG. Xét bộ 3 gồm : đọan lệnh S, các tân từ trên các biến của chương trình (có thể bao gồm các biến giả) P, Q ( P mô tả điều kiện đầu , Q mô tả điệu kiện cuối ). Bộ 3 : { P } S { Q } tạo nên đặc tả đoạn lệnh S . Đặc tả : { P } S { Q } được gọi là thỏa đầy đủ ( đúng đầy đủ – đ đ đ ) nếu xuất phát từ bất kỳ 1 trạng thái thỏa P thực hiện đoạn lệnh S thì việc xử lý sẻ dừng ở trạng thái thỏa Q . Đặc tả : { P } S { Q } được gọi là thỏa có điều kiện ( đúng có điều kiện – đcđk ) nếu xuất phát từ bất kỳ 1 trạng thái thỏa P thực hiện đoạn lệnh S nếu việc xử lý dừng thì trạng thái cuối thỏa Q ( tính dừng của S chưa được khẳng định ).
Khẳng định { P } S { Q } diễn đạt tính đúng có điều kiện (condition correctness) (tđcđk) của S. Tính đúng của S dựa trên đkđ P và đkc Q với giả định rằng tính dừng của S đã có. Ví dụ : a) { (x = xo ) and (y = yo ) } Nếu (x = xo ) và (y = yo ) trước khi t := x t := x được thi hành {( t = x = xo ) and (y = yo ) } Thì sau đó ( t = x = xo ) và (y = yo ) b) {( t = x = xo ) and (y = yo ) } Nếu (t = x = xo ) và ( y = yo) trước khi x := y x := y được thi hành { (t = xo ) and (x = y = yo ) } Thì sau đó ( t = xo ) và ( x = y = yo ) c) { (t = xo ) and (x = y = yo ) } Nếu (t = xo ) và (x = y = yo ) trước khi y := t y := t được thi hành {( y = xo ) and (x = yo ) } Thì sau đó ( y = xo ) và ( x = yo ) Các phát biểu a, b, c là đúng theo cảm nhận của ta về lệnh gán. d) { x > 0 } Nếu (x > xo ) trước khi x := x-1 x := x-1 được thực hiện { x > 0 } Thì sau đó ( x > 0 ) Phát biểu d là sai vì có một trạng thái ban đầu x = 1 thoả P ( x > 0 ) nhưng sau khi thi hành lệnh x := x -1 (x giảm 1) thì x = 0 không thoả Q ( x > 0 ) . II. HỆ LUẬT HOARE (HOARES INFERENCE RULES). 1 - 60 - Để có thể thực hiện chứng minh hình thức về tính đúng của các đoạn chương trình, ta cần có những tiền đề mô tả tác động của các thao tác xử lý cơ bản (lệnh cơ bản ) của ngôn ngữ dùng viết chương trình ( ở đây là ngôn ngữ cốt lõi đã được giới thiệu ơ IV.3 ). Một hệ tiên đề có tác dụng như thế của Ca. Hoare , được trình bày dưới dạng một hệ luật suy diễn (inference rules ) được xét dưới đây . 1. Các luật hệ quả (Consequence rules) 1a. P => Q , { Q } S { R } –––––––––––––––– (1a) { P } S { R } Nếu đkđ P mạnh hơn điều kiện Q .Tức là: P . Q hay { P } . { Q } ( tập hợp các trạng thái thoả P là tập con của các tập trạng thái thoả Q ) và mỗi trạng thái thoả Q đều đảm bảo trạng thái sau khi thi hành S (với giả định S dừng) thoả R thì mỗi trạng thái thoả P đều đảm bảo trạng thái sau khi thi hành S (với giả định S dừng) thoả R. Ví dụ 1 : Kiểm chứng tđcđk đặc tả sau : { x = 3 } x := 5 ; y := 2 { x = 5, y = 2 } Ta có : { true} x := 5 ; y := 2 { x = 5 ; y = 2 } (a) // tạm công nhận và ( x = 3 ) => true (b) // hiển nhiên Nên { x = 3 } x := 5 ; y := 2 { x = 5, y = 2 } // theo tiên đề (1a) Ví dụ 2 : Kiểm chứng tđcđk đặc tả sau : { x > 3 } x := x -1 { x > 0 } Ta có : { x > 1 } x := x-1 { x > 0 } (a) //tạm công nhận và ( x > 3 ) => ( x > 1) (b) // hiển nhiên Nên { x > 3 } x := x -1 { x > 0 } // theo tiên đề (1a) 1b.
Q => R , { P } S { Q } –––––––––––––––––– (1b) { P } S { R } Ví dụ 3 : Kiểm chứng tđcđk đặc tả sau : { true } x := 5 ; y := 2 { odd(x) and even(y) } Ta có : { true } x := 5 ; y := 2 { (x = 5) , ( y = 2 ) } (a) // tạm công nhận và ( (x = 5) and (y = 2)) => odd(x) and even(y) (b) // hiển nhiên Nên { true } x := 5 ; y := 2 { odd(x) and even(y) } //theo (1b) 1 - 61 - Ví dụ 4 : Kiểm chứng tđcđk đặc tả : { x > 1 } x := x -1 { x >= 1 } Ta có : { x > 1 } x := x-1 { x > 0 } (a) // tạm công nhận và ( x > 0 ) => ( x >= 1) // (b) // vì x là biến nguyên Nên { x > 1 } x := x -1 { x >= 1 } // theo (1b) Hai luật này cho phép liên kết các tính chất phát sinh từ cấu trúc chương trình với các suy diễn logic trên dữ kiện. 2. Tiên đề gán (The Assignement Axiom) { P(bt) } x := bt { P(x) } (2) Từ (2 ) ta suy ra nếu trước lệnh gán x := bt ; trạng thái chương trình làm P(bt) sai (thoả not P(bt) ) thì sau lệnh gán P(x) cũng sai (thỏa notP(x)). Lệnh gán x := bt xoá giá trị cũ của x , sau lệnh gán x mang giá trị mới là trị của biểu thức bt , còn tất cả các biến khác vẫn giữ giá trị như cũ. Ví dụ : Tính đúng có điều kiện của các đặc tả sau được khẳng định dựa vào tiên đề gán a) { x = x } y := x { x = y } b) { 0 ( 5 = 5 ) và ( x = 5) => ( (x = 5) and (2 = 2) ) (b) // hiển nhiên {true} x := 5 {( x = 5) and ( 2 = 2) } (c) //theo luật hệ qủa { x = 5 , 2 = 2 } y := 2 {( x = 5) and ( y = 2) } (d) // tiền đề gán
{true} x := 5 ; y := 2 { x = 5, y = 2 } // theo luật tuần tự b) Luật về điều kiện (chọn) (Rule for conditionals) b1) { P and B} S1 {Q }, { P and (not B)} S2 { Q } ––––––––––––––––––––––––––––––––––––– (3.2a) { P } if B then S1 else S2 { Q } Ý nghĩa luật này là : Nếu có : { P and B } + Nếu xuất phát từ trạng thái thỏa P and B S1 thi hành S1 thì sẻ tới trạng thái thỏa Q { Q } Và { P and notB } + Nếu xuất phát từ trạng thái thỏa P and not B S2 thi hành S2 thì sẻ tới trạng thái thỏa Q { Q } Thì suy ra : { P } Nếu xuất phát từ trạng thái thỏa P if B then S1 else S2 thi hành lệnh if B then S1 else S2 { Q } thì sẽ tới trạng thái thỏa Q . b2) { P and B} S { Q} , P and (not B ) => Q –––––––––––––––––––––––––––––––––––– (3.2b) { P } if B then S { Q} Ví dụ1 : Kiểm chứng tđcđk đặc tả : { i> 0 } if ( i= 0 ) then j := 0 else j := 1 {j=1} Ta có : ((i> 0) and (i = 0)) = false (a) //hiển nhiên { (i> 0 ) and (i = 0)} j := 0 {j=1} (b) //{false} S { Q } đúng với . S , Q ( (i> 0) and not(i = 0)) = true (c) // hiển nhiên 1 - 63 - {true } j := 1 { j=1 } (d) //tiên đề gán {(i >0) and not(i = 0)} j := 1 {j=1} (e) // c,d ,luật hệ qủa Từ b ,e và tiên đề 3.2a ta suy ra ĐPCM. Ví dụ2 : Kiểm chứng tđcđk đặc tả : {i >= j - 1} if ( i > j) then j := j+1 else i := i+1 {i >= j} Ta có : {i >= j+1} j := j+1 {i >= j} (a) //tiên đề gán ((i >= j-1) and (i > j)) ==> (i >= j+1) (b) // biến đổi với chú ý i , j nguyên {(i >= j-1) and (i > j)} j := j + 1 {i >= j} (c) // a,b ,luật hệ quả {i+1 >= j} i := i+1 {i >= j} (d) // tiên đề gán ((i >= j-1) and not(i > j)) ==> (i+1 >= j) (e) // biến đổi {(i >= j-1) and not(i > j)} i := i + 1 {i >= j} (g) // d ,e , luật hệ quả) Từ c , g dựa vào 3.2a suy ra ĐPCM. Ví du 3 : Kiểm chứng tđcđk đặc tả : {true} if odd(x) then x := x+1 {even(x)} Ta có : {even(x+1)} x := x+1 {even(x)} (a) //tiên đề gán
true and odd(x) ==> even(x+1) (b) // hiển nhiên {true and odd(x)} x := x+1 {even(x)} (c) // a ,b , luật hệ quả true and not odd(x) ==> even(x) (d) // hiển nhiên Từ (c) và (d) dựa vào 3.2b suy ra ĐPCM . b3) Luật về lệnh lặp While { I and B } S { I } ––––––––––––––––––––––––– (3.3) { I } while B do S { I and (not B ) } Luật này nói rằng nếu I không bị thay đổi bởi một lần thực hiện lệnh S thì nó cũng không bị thay đổi bởi toàn bộ lệnh lặp While B do S. Với ý nghĩa này I được gọi là bất biến (invariant) của vòng lặp. Chú ý rằng khẳng định : { P } while B do S { Q } thỏa dựa vào hệ luật Hoare chỉ xác định tđcđk (conditionnal correctness). Để chứng minh tính đúng (correctness) thực sự ta cần bổ sung chứng minh lệnh lặp dừng. Ví dụ1 : Kiểm chứng tính đúng có điều kiện của đặc tả : {i = n ) ==> i=n (c) = Từ b ,c , luật hệ qủa ta có ĐPCM. Ví dụ 2 : Kiểm chứng tính đúng có điều kiện của đặc tả : {sum = 0 , i = 0 , n > 0} while ( i n ) Ta có : {( sum = i*(i+1)/2 ) ,( i 0) ==> s = i*(i+1)/2 (c) //hiển nhiên ( s = i*(i+1)/2) and not(i s=n*(n+1)/2 (d) //hiển nhiên Từ b , c , d ta suy ra ĐPCM. III. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH KHÔNG CÓ VÒNG LẶP. Cho : P, Q là các tân từ trên các biến của chương trình , S là một lệnh tổ hợp từ các lệnh gán với cấu trúc điều kiện và tuần tự. Chứng minh đặc tả : { P } S { Q} đúng đầy đủ . Ở đây vì mỗi lệnh chỉ được thi hành một lần nên tính dừng của đoạn lệnh S được suy ra từ tính dừng của lệnh gán mà luôn được xem là hiển nhiên . Vì vậy trong trường hợp
này tính đúng có điều kiện trùng với tính đúng đầu đủ. 1) Bài toán 1 : S là dãy tuần tự các lệnh gán . Ví dụ1 : Kiểm chứng tính đúng của đoạn lệnh hoán đổi nội dung 2 biến x và y a) {(x=xo) and ( y = yo ) } t := x ; x := y ; y := t ; {(x=yo ) and (y = xo ) } Chứng minh {(x = yo ) and ( t = xo) } y := t {(x = yo ) and ( y = xo ) } (a) // tiên đề gán {(y = yo ) and ( t = xo ) } x := y {(x = yo ) and ( t = xo ) } (b ) // tiên đề gán {(y = yo ) and ( t = xo ) } x := y ; y := t {(x = yo) and ( y = xo ) } (c) // a , b , luật tuần tự {(y = yo ) and ( x = xo ) } t := x {(y = yo ) and ( t = xo ) } (d) // tiên đề gán ( (x = xo ) and (y = yo ) ) = ( ( y = yo ) and ( x = xo ) } (e ) // giao hoán {( x = xo ) and (y = yo ) } t := x {(y = yo ) and ( t = xo ) } (g) // d ,e, luật hệ quả 1 - 65 - {(x = xo ) and ( y = yo ) } t := x ; x := y ; y := t {(x = yo ) and ( y = xo ) (h) // c ,g , luật tuần tự Ví dụ1 : Kiểm chứng tính đúng của đặc tả : { (m :: k=2*m) and (y * zk = c)} k := k div 2 ; z := z * z ; { y * zk = c} Chứng minh : (a) {y * (z*z)k = c} z := z * z {y*zk = c} (tiên đề gán) (b) {y * (z*z)k div 2 = c} k := k div 2 {y*(z*z)k = c} (tiên đề gán) (c) {y * (z*z)k div 2 = c} k := k div 2 ; z := z*z {y*z)k = c} (a ,b , luật tuần tự) (d) (m :: k = 2*m) and ( y * zk = c ) ==> (y*z2m = c) and ( m = k div 2 ) ==> y * (z*z)k div 2 = c c ,d , luật hệ quả suy ra ĐPCM. Nhận xét : Với dẫy tuần tự các lệnh gán, việc chứng minh {P} S1; ;Sn {Q} thướng được bắt đầu từ lệnh cuối cùng, dùng tiên đề gán để được đkđ, rồi cứ thế lần ngược về đến S1. {Pn} Sn {Q} (n) tìm Pn từ Sn ,Q và tiên đề gán {Pn-1 } Sn-1 {Pn } (n-1) tìm Pn-1 từ Sn-1 , Pn và tiên đề gán {Pn-1 } Sn-1 ; Sn {Q} luật về dãy lệnh tuần tự {P1 } S 1 ; ; S n {Q} (1) sau n-1 lần tương tự như trên. Sau đó dùng các tính chất của dữ kiện chứng minh logic rằng : P ==> P1 (0) Từ (1) , (0) ,dựa vào luật hệ quả ta có : {P} S1 ; ; Sn {Q} ( ĐPCM ) 2) Bài toán 2 : a) Kiểm chứng đặc tả : {P} if B then S1 else S2 {Q} Với S1, S2 là nhóm các lệnh gán , B là biểu thức boolean.
Cách chứng minh : + Bước 1 : Tìm P1, P2 thỏa : {P1} S1 {Q} (1a) {P2} S2 {Q} (1b) + Bước 2 : Chứng minh ( dùng các tính chất logic và đại số ) P and B ==> P1 (2a) P and (not B) ==> P2 (2b) + Bước 3 : Dùng luật hệ quả suy ra : {P and B} S1 {Q} ( 3a) // 1a ,2a , và luật hệ qủa {P and (not B)} S2 {Q} ( 3b) // 1b ,2b , và luật hệ qủa + Bước 4 : Dũng (3a) , (3b) , luật điều kiện suy ra : 1 - 66 - {P} if B then S1 else S2 {Q} ( ĐPCM ) b) Kiểm chứng đặc tả : {P} S0 ; if B then S1 else S2 {Q} (*) với S1, S2, S0 là dẫy các lệnh gán Ví dụ : Kiểm chứng đặc tả : {y > 0} x := y-1 ; if (y > 3) then x := x*x else y := y-1 {x >= y} Để khẳng định được (*) ta cần chỉ ra 1 khẳng định R mà : {P} S0 {R} và {R} if B then S1 else S2 {Q} rồi dùng luật hệ quả để có (*) Làm thế nào để tìm được R ? Do S1 và S2 là nhóm lệnh gán tuần tự nên ta có thể tìm được (bằng tiên đề gán và luật về dãy lệnh tuần tự ) U và V để : {U} S2 {Q} và {V} S3 {Q} . Dĩ nhiên ta muốn U và V là các điều kiện tổng quát nhất có thể (ở đây là yếu nhất). R được xây dựng thế nào từ U và V ? Khả năng tổng quát nhất cho R để sau khi điểm điều kiện B sẽ có được U hoặc V là : R = (B ==> U) and (not B ==> V) Như sau này sẻ chỉ ra U , V , R được xây dựng như vậy là yếu nhất (weakest precondition) để đạt được Q tương ứng với lần lượt các lệnh S1 , S2 và if B then S1 else S2 , và được ký hiệu là : WP(S2,Q) ,WP(S3,Q) và WP(if B then S2 else S3, Q) tương ứng. Ví dụ 1 : Kiểm chứng đặc tả : { y > 0 } x := y - 1 ; if ( y > 3 ) then x := x * x else y := y - 1 ; { x >= y } Trong ví dụ này : P là tân từ : ( y > 0 ) ; Q là tân từ : ( x >= y ) B là biểu thức boolean : ( y > 3 ) S0 là lệnh gán : x := y - 1 ; Do S1 và S2 là lệnh gán : x := x * x ; S2 là lệnh gán : y := y - 1 ;
Ta có : {x2 >= y} x := x*x {x >= y} suy ra U = WP( S1 , Q ) x = 2 >= y (a) {x >= y-1} y := y-1 {x >= y} suy ra V = WP( S2 , Q ) x >= y-1 (b) = 1 - 67 - Đặt R (B ==> U) and (not B ==> V) = = ((y > 3) ==> (x2 >= y)) and ((y (x >= y-1)) Ta chứng minh được dễ dàng. R and (y>3) ==> (x2 >= y) (c) R and (not(y>3)) ==> (x >= y-1) (d) nên theo luật hệ quả {R and y>3} S2 {x >= y} ( {R and B} S2 {Q} ) (e) {R and not(y>3)} S3 {x >= y} ( {R and (not B)} S3 {Q} ) (g) Theo luật về lệnh chọn {R} if ( y>3) then x := x*x else y := y-1 {x >=y} (h) theo tiên đề gán. { ((y>3) ==> ((y-1) 2 >=y)) and ((y ((y-1) >= (y-1))) } x := y -1 { R } (i) Dễ kiểm chứng được (y>3) ==> ((y-1) 2 >= y = true (j) (y (y-1) >= y-1 = true (k) nên (y >0) ==> ((y>3) ==>((y-1)2 >=y)) and ((y ((y-1) >=(y-1))) (l) Theo luật hệ quả {y > 0} x := y-1; if (y>3) then x := x*x else y := y-1 { x >= y} (m) // ĐPCM Ví dụ 2 : kiểm chứng đặctả : { true } if ( i = i) and (m >= j) and (m >= k)} Đặt Q(m) ( m >= i) and (m >= j) and (m >= k) = Ta có : (a) {Q(i)} m := i {Q(m)} (tiên đề gán) (b) {Q(k)} m := k {Q(m)} (tiên đề gán) Đặt R1 ((i Q(k)) and ( (i >= k) ==>Q(i)) = dùng luật về lệnh chọn ta sẽ chứng minh được : {R1} if ( i ( Q(k) and (j >= k)) ==> Q(j) =
1 - 68 - Ta có: {R2} if (j R2 (e) ( true and ( i > j )) ==> R1 (g) Từ c , d, e ,g , theo luật về lệnh chọn ta có ĐPCM. Nhận xét : Để chứng minh đặc tả {P} S {Q} với S là tổ hợp lệnh gồm chỉ các lệnh gán và điều kiện đúng đầy đủ ,ta thực hiện công việc xây dựng điều kiện đầu yếu nhất P1 của S ứng với Q , sau đó bước kiểm chứng cuối cùng chỉ đơn giản là chứng minh : P ==> P1. Công việc trên được trình bày dưới dạng một hàm đệ quy như sau : function DKDYN (S : nhóm_lệnh ; Q : tân_từ ) : tân_từ ; var t : câu lệnh ; begin if (S DKDYN(phần_đúng(t),Q)) and not (điều_kiện(t)==>DKDYN(phần_khong đúng(t),Q)) end else DKDYN := Q end ; IV. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH CÓ VÒNG LẶP. 1. Bất biến Một tính chất đặc thù của trí tuệ là nó thoát khỏi công việc mà nó đang thực hiện, khảo sát kết quả mà nó đã làm và luôn luôn tìm kiếm, và thường phát hiện được, các khuôn mẫu (Douglas R. Hofstadter). Một bất biến là một tính chất không thay đổi tồn tại trong một khung cảnh, một sự kiện một quá trình thay đổi thường xuyên. Một điều có vẻ nghịch lý là trong một thế giới, thay đổi và cần thiết phải thay đổi nhanh chóng, các bất biến lại có ý nghĩa rất quan trọng đối với chúng ta. Một em bé trong một nước nói tiếng Anh học cách thành lập dạng số nhiều của danh từ : dogs, cats, hands, arms , cách thành lập dạng quá khứ của động từ : 1 - 69 - kicked, jumped, walked bằng học luật không đổi (thêm s, thêm ed), kèm theo với việc học thuộc một số trường hợp ngoại lệ. Hãy tượng tượng việc học sẽ khó như thế nào nếu không có các luật không đổi (bất biến ) này. Việc nhận thức được các bất biến thường dẫn tới những lời giải đơn giản cho các bài toán khó. Đầu óc con người dường như có một khả năng đặc biệt để nhận thức các bất biến hay các "khuôn mẫu".
Hãy quan sát 2 dãy các hình sau : (a) (b) Hình kế tiếp trong mỗi dãy hình trên là gì ? Tính chất bất biến của mỗi dãy là gì ? (a) Lặp lại bộ 3 hình vuông, tròn, tam giác. (b) Về dạng thì là sự lặp lại của cặp 2 hình vuông lớn và nhỏ. Về màu thì là sự lặp lại của một màu trắng và 2 màu sậm. Trong lĩnh vực chương trình cho máy tính, ta cũng cần nhận thức các sự việc bằng cách phát hiện các bất biến. Đối với một chương trình, ta có nhiều lần máy tính thi hành nó, mỗi lần thi hành được gọi là một quá trình (process) và tác động trên các dữ kiện khác nhau. Tính bất biến của các quá trình này chính là đặc tả của chương trình. Bên trong một chương trình có thể có các vòng lặp. Việc thực hiện vòng lặp làm biến thiên nhiều lần trạng thái các biến chương trình (các đối tương dữ liệu ) , mà số lần biến thiên thường không biết trước được. Làm thế nào để hiểu được tác động của vòng lặp và đi đến chứng minh vòng lặp thực hiện một tính chất (giữ một bất biến) nào đó thể hiện bởi đặc tả của nó. Mô hình biến đổi trạng thái chương trình của vòng lặp while B do S { P } { P1 } { P2 }. . . . . . . . { Pn } { Q } S S S S { P } là trạng thái trước vòng lặp . { Pi } là trạng thái sau lần lặp thứ i . 1 - 70 - { Q } là trạng thái sau vòng lặp . Việc nhận thức (tìm ra ) các tính chất bất biến của trạng thái chương trình trước và sau mỗi lần lặp có vai trò quyết định ở đây. Ví dụ : với vòng lặp : tg := 0 ; i := 0 ; while ( i <= n ) do begin i := i + 1 ; tg := tg + a[i] ; end ; Tính chất bất biến ở đây là : bất chấp i, sau lần lặp thứ i, tg sẽ chứa tổng i phần tử đầu tiên của array a(a[1], a[2], , a[i]). Tức là : tg = S(j: 1 <= j <=i : a[j]) = a j i [ ] 1 . 2. Lý luận quy nạp và chứng minh bằng quy nạp. Trong khoa học cũng như trong đời sống hàng ngày, người ta thường cần phải suy diễn từ các phát hiện riêng lẻ để đi đến các quy luật (bất biến) phổ dụng cho mọi( hay hầu hết) trường hợp có thể. Quá trình mà con người xác lập được một tính chất bất biến từ một tập hợp các quan sát được gọi là suy diễn quy nạp.
Suy diễn quy nạp xuất phát từ quan sát và kết quả là cho ra các giả thuyết cần chứng minh. Ví dụ 1 : từ các quan sát : 1 = 1 = 12 1 + 3 = 4 = 22 1 + 3 + 5 = 9 = 32 1 + 3 + 5 + 7 = 16 = 42 Bằng quy nạp người ta đặt giả thuyết : 1 + 3 + (2*n - 1) = n2 Ta có thể thử lại giả thuyết này với n = 5, 6 Tuy nhiên, để khẳng định rằng giả thuyết đúng với mọi n, ta cần có chứng minh. Phương pháp chứng minh thường dùng trong trường hợp này là chứng minh bằng quy nạp. a) Nguyên lý quy nạp toán học đơn giản . Để chứng minh một tân từ P(n) phụ thuộc vào số tự nhiên là đúng với mọi n . Ta cần chứng minh 2 điều sau : (i) P(0) là đúng (ii) Nếu P(n) được giả định là đúng thì sẽ suy ra P(n+1) cũng đúng. Khẳng định P(0) được gọi là cơ sở (basis) và bước chứng minh (ii) là bước quy nạp (inductive step). Khi có được 2 điều (i) và (ii), dựa vào nguyên lý quy nạp toán học, ta kết luận rằng P(n) đúng với mọi số tự nhiên n . Trên thực tế nguyên lý trên thường được áp dụng hơi khác. 1 - 71 - + Để chứng minh P(n) đúng với mọi số tự nhiên n >= m thì cơ sở của chứng minh quy nạp là P(m) chứ không phải P(0). + Để chứng minh P(n) đúng với mọi số tự nhiên n thoả m = 1 theo nguyên ly quy nạp toán học. b) Nguyên lý quy nạp mạnh (Strong induction principle) Để chứng minh P(n) đúng với mọi số tự nhiên n ta cần chứng minh hai điều sau : (i) P(0) đúng (ii) Nếu giả định là P(0), P(1), P(n) đều đúng thì P(n+1) cũng đúng Cũng như nguyên lý quy nạp đơn giản, người ta có thể dùng các biến dạng của nguyên lý quy nạp mạnh để chứng minh P(n) đúng với mọi số tự nhiên n >= m cho trước hay với mọi số tự nhiên n mà m < n <= p với m,p cho trước. 3. Kiểm chứng chương trình có vòng lặp while. a) Dạng tổng quát của bài toán . Cho W là một lệnh lặp while B do S và cặp đkđ P, đkc Q. Ta cần phải chứng minh rằng : đặc tả { P } W { Q } được thỏa đầy đủ .