Tài liệu Giáo trình kỹ thuật lập trình nâng cao

GIÁO TRÌNH KỸ THUẬT LẬP TRÌNH NÂNG CAO

TRẦN HOÀNG THỌ



MỤC LỤC

LỜI NÓI ĐẦU 4

PHẦN I .5

CHƯƠNG I .5

I. MỞ ĐẦU .5

1. Mô tả đệ quy 5

2. Các loại đệ quy 6

II. MÔ TẢ ĐỆ QUY CÁC CẤU TRÚC DỮ LIỆU .7

III. MÔ TẢ ĐỆ QUY GIẢI THUẬT 7

1. Giải thuật đệ quy 7

2. Chương trình con đệ quy 8

3. Mã hóa giải thuật đệ qui trong các ngôn ngữ lập trình 11

4. Một số dạng giải thuật đệ quy đơn giản thường gặp .13

CHƯƠNG II .16

I. CÁC NỘI DUNG CẦN LÀM ĐỂ TÌM GIẢI THUẬT ĐỆ QUY CHO MỘT BÀI TOÁN 16

1. Thông số hoá bài toán .16

2. Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.16

3. Phân rã bài toán tổng quát theo phương thức đệ quy .16

II. MỘT SỐ BÀI TOÁN GIẢI BẰNG GIẢI THUẬT ĐỆ QUY ĐIỂN HÌNH .17

1. Bài toán tháp Hà Nội 17

2. Bài toán chia thưởng 19

3. Bài toán tìm tất cả các hoán vị của một dãy phần tử .21

4. Bài toán sắp xếp mảng bằng phương pháp trộn (Sort-Merge) 24

5. Bài toán tìm nghiệm xấp xỉ của phương trình f(x)=0 25

CHƯƠNG III 28

I. CƠ CHẾ THỰC HIỆN GIẢI THUẬT ĐỆ QUY 28

II. TỔNG QUAN VỀ VẤN ĐỀ KHỬû ĐỆ QUY .32

III. CÁC TRƯỜNG HỢP KHỬ ĐỆ QUY ĐƠN GIẢN 33

1. Các trường hợp khử đệ quy bằng vòng lặp .33

2. Khử đệ quy hàm đệ quy arsac 41

3. Khử đệ quy một số dạng thủ tục đệ quy thường gặp 45

Phần II .52

CHƯƠNG IV 52

I. CÁC GIAI ĐOẠN TRONG CUỘC SỐNG CỦA MỘT PHẦN MỀM .52

1) Đặc tả bài toán 52

2) Xây dựng hệ thống 52

3) Sử dụng và bảo trì hệ thống 53

II. ĐẶC TẢ .53

1. Đặc tả bài toán .53

2. Đặc tả chương trình (ĐTCT) .54

3. Đặc tả đoạn chương trình 55

III. NGÔN NGỮ LẬP TRÌNH 57

CHƯƠNG V 59

I. CÁC KHÁI NIỆM VỀ TÍNH ĐÚNG .59

II. HỆ LUẬT HOARE (HOARES INFERENCE RULES) 59

1. Các luật hệ quả (Consequence rules) .60 Trần Hoàng Thọ Khoa Toán - Tin

Kỹ thuật lập trình nâng cao - 3 -

2. Tiên đề gán (The Assignement Axiom) .61

3. Các luật về các cấu trúc điều khiển .61

III. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH KHÔNG CÓ VÒNG LẶP 64

IV. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH CÓ VÒNG LẶP 68

1. Bất biến 68

2. Lý luận quy nạp và chứng minh bằng quy nạp 70

3. Kiểm chứng chương trình có vòng lặp while 71

CHƯƠNG VI .76

I. CÁC KHÁI NIỆM .76

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

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

3. Hệ quả của định nghĩa .76

4. Các ví dụ 77

II. TÍNH CHẤT CỦA WP 77

III. CÁC PHÉP BIẾN ĐỔI TÂN TỪ 78

1. Toán tử gán (tiên đề gán) 78

2. Toán tử tuần tự .78

3. Toán tử điều kiện .79

4. Toán tử lặp .80

IV. LƯỢC ĐỒ KIỂM CHỨNG HỢP LÝ VÀ CÁC ĐIỀU KIỆN CẦN KIỂM CHỨNG 84

1. Lược đồ kiểm chứng 84

2. Kiểm chứng tính đúng 85

3. Tập tối tiểu các điều kiện cần kiểm chứng 93

PHU LỤC .96

I. LOGIC TOÁN 96

II. LOGIC MỆNH ĐỀ 96

1. Phân tích 96

2. Các liên từ logic .97

3. Ýnghĩa của các liên từ Logic. Bảng chân trị 97

4. Lý luận đúng 98

5. Tương đương (Equivalence) 99

6. Tính thay thế, tính truyền và tính đối xứng .100

7. Bài toán suy diễn logic .100

8. Các luật suy diễn (rules of inference) 102

III. LOGIC TÂN TỪ 103

1. Khái niệm .103

2. Các lượng từ logic 105

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

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

Trần Hoàng Thọ Khoa Toán - Tin

Kỹ thuật lập trình nâng cao - 4 -

LỜI NÓI ĐẦU

Giáo trình được viết theo nội dung môn học “ Kỹ thuật lập trình nâng cao” với mục đích làm tài liệu tham khảo chính cho môn học.

Giáo trình gồm 2 phần chính và 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