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

TG : TRẦN HOÀNG THỌ


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.




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

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