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

ĐỀ TÀI : Giáo trình kỹ thuật 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 Trần Hoàng Thọ Khoa Toán - Tin
Kỹ thuật lập trình nâng cao - 3 -
2. Tiên đề gán (The Assignement Axiom) .61
3. Các luật về các cấu trúc điều khiển .61
III. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH KHÔNG CÓ VÒNG LẶP 64
IV. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH CÓ VÒNG LẶP 68
1. Bất biến 68
2. Lý luận quy nạp và chứng minh bằng quy nạp 70
3. Kiểm chứng chương trình có vòng lặp while 71
CHƯƠNG VI .76
I. CÁC KHÁI NIỆM .76
1. Đặt vấn đề .76
2. Định nghĩa WP(S,Q) .76
3. Hệ quả của định nghĩa .76
4. Các ví dụ 77
II. TÍNH CHẤT CỦA WP 77
III. CÁC PHÉP BIẾN ĐỔI TÂN TỪ 78
1. Toán tử gán (tiên đề gán) 78
2. Toán tử tuần tự .78
3. Toán tử điều kiện .79
4. Toán tử lặp .80
IV. LƯỢC ĐỒ KIỂM CHỨNG HỢP LÝ VÀ CÁC ĐIỀU KIỆN CẦN KIỂM CHỨNG 84
1. Lược đồ kiểm chứng 84
2. Kiểm chứng tính đúng 85
3. Tập tối tiểu các điều kiện cần kiểm chứng 93
PHU LỤC .96
I. LOGIC TOÁN 96
II. LOGIC MỆNH ĐỀ 96
1. Phân tích 96
2. Các liên từ logic .97
3. Ýnghĩa của các liên từ Logic. Bảng chân trị 97
4. Lý luận đúng 98
5. Tương đương (Equivalence) 99
6. Tính thay thế, tính truyền và tính đối xứng .100
7. Bài toán suy diễn logic .100
8. Các luật suy diễn (rules of inference) 102
III. LOGIC TÂN TỪ 103
1. Khái niệm .103
2. Các lượng từ logic 105
3. Tập hợp và tân tưØ .107
4. Các lượng từ số học .107
Trần Hoàng