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ÀITOÁ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ửđệquyhàmđệquyarsac.41

3. Khử đệ quymộ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ÁINIỆ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

2. Tiên đề gán (TheAssignement 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ÒNGLẶ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ÁINIỆM.76

1. Đặt vấn đề. .76

2. Địnhnghĩa WP(S,Q).76

3. Hệ quả của địnhnghĩ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ỢPLÝ 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 thaythế, 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ượngtừ logic.105

3. Tập hợp và tân tư.107

4. Các lượngtừ số học. .107