Giáo trình lập trình nâng cao

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