Toán rời rạc ứng dụng trong tin học

Toán rời rạc ứng dụng trong tin học

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (48.56 MB, 409 trang )

G]

& J

NHÀ XUẤT/BẢN GlÁCXm JC VIỆ

PGS. TS. ĐỖ ĐỨC GIÁO


Tái bản lần thứ hai

NHÀ XUẤT BẢN GIÁO DỤC VIỆT NAM

Công ty cổ phần Sách Đại học • Dạy nghề – Nhà xuất bản Giáo dục Việt Nam
giữ quyển công bố tác phẩm.

14 – 201 l/CXB/102 – 2075/GD

Mã số : 7B705y 1 – DAI

J lờ i nối đau
Dê nâng cao chất lượng giảng dạy và học tập môn Toán rời rạc
cho sinh viên và học viên ngành Công nghệ thông tin và các ngành
khoa học tự nhiên, chúng tôi biên soạn cuôh Toán rời rac ứng dung
trong tin hoc gồm:
Phần I. Kiến thức bổtrỢ;

– Phần II. Logic và ứng dụng;
– Phần III. Dồ thị và ứng dụng;
– Phần IV. Ngôn ngữ hình thức.
Cuốn Toán rời rac ứng dung trong tin hoc trình bày các vân dề
toán học cơ bản nhất, nhưng lại hết sức thiết yếu và cần thiết đối với
những ai m uôh có dược các kiến thức tin học vững chắc. Cuốn sách
giúp người học hiểu dược lý thuyết thấu dáo, rèn luyện tư duy khoa
học, k ỹ năng tính toán và khả năng vận dụng toán học vào giải quyết
vân dề, kích thích niềm say mê học tập và từ đó nâng cao k ỹ năng
thực hành, tư duy sáng tạo khi học các môn học cơ SỞ và chuyên
ngành Công nghệ thông tin tiếp theo. Cuốn sách này cũng rất bô ích
cho việc ôn thi tu vén sinh sau dại hoc ngành Công nghệ thông tin
dược tô chức hàng năm Ở Đại học Quốc gia Hà Nội.
Tác giả chân thành cảm ơn các bạn dồng nghiệp dã dộng viên tác
giả biên soạn cuốn sách này.
Cuốn sách xuất bản lần dầu, nôn khó tránh khỏi thiếu sót về hình
thức củng như nội dung. Vì vậy, tác giả m ong nhận dược sự góp ý
của bạn dọc dê cuốn sách ngày càng tốt hơn. Mọi góp ý xin gửi về:
Công ty Cô phần Sách Dại học và Dạy nghề: 25 Hàn Thuyên Hà Nộ i.
TÁC GIẢ

4

TOÁN RỜI RẠC ỨNG DUNG TRONG TIN HOC

MỤC LỤC
V

LỜI NÓI ĐẦU…………………………………………………………………………………………………. 3
Phẩn I. KIẾN THỬC B ổ TRỢ
Chương 1. CÁC KHÁI NIỆM c ơ BẢN CỦA THUẬT TOÁN
VÀ PHƯƠNG PHÁP ĐỆ Q UY……………………………………………………….. 9
§1. Khái niệm thuật toán………………………………………………………………………………..9
1.1. Thuật toán là gì………………………………………………………………………………… 9
1.2. Các đặc trưng của thuật toán……………………………………………………………….
1.3. Ngôn ngữ thuật toán………………………………………………………………………… 10
1.4. Độ phức tạp thuật to á n …………………………………………………………………….13
§2. Phương pháp đệ quy……………………………………………………………………………… 19
BÀI T Ậ P …………………………………………………………………………………………………….. 29
Chương 2. CÁC PHƯƠNG PHÁP Đ Ế M …………………………………………………………. 33
§1. Tập hợp và biểu diễn tập hợp trênmáy tính………………………………………………33
1.1. Các phép toán trên tập hợp………………………………………………………………33
1.2. Các tính chất của tập hợp…………………………………………………………………34
1.3. Lực lượng của tập h ợp………………………………………………………………………34
1.4. Tích Đề-các của các tập hợp và lực lượng của n ó ………………………………. 35
1.5. Biểu diễn các tập hợp trên máy tính…………………………………………………..35
§2. Hoán vị, chỉnh hợp và tổ hợp…………………………………………………………………..37
2.1. Hoán vị và chình hợp………………………………………………………………………..37
2.2. Tổ hợp và định lý nhị thức…………………………………………………………………38
§3. Các quy tắc đếm cơ bản……………………………………………..
43
3.1. Quy tắc cộng…………………………………………………………………………………… 43
3.2. Quy tắc nhân………………………………………………………………………………….. 44
3.3. Một số bài toán đếm kết hợp giữa quy tắc cộng và quy tắc nhâ n……….. 45
§4. Nguyên lý chuồng chim bồ câu ……………………………………………………………… 52
4.1. Nguyên lý chuồng chim bổ c ả u ……………………………………………………….. 52
4.2. Nguyên lý Dirichlet…………………………………………………………………………… 52

4.3. Các ví d ụ ………………………………………………………………………………………… 53
Chương 3. QUAN HỆ…………………………………………………………………………………… 57
§1. Quan hệ và biểu diễn quan h ệ ………………………………………………………………..57
1.1. Quan hệ và ví dụ về quan hệ……………………………………………………………. 57
1.2. Phương pháp biểu diễn quan hệ……………………………………………………….. 57
1.3. Tính chất của quan h ệ ………………………………………………………………………60
§2. Cung và đường trong đố thị của quan h ệ …………………………………………………63
2.1. Định nghĩa 1……………………………………………………………………………………. 63
2.2. Tính chất………………………………………………………………………………………… 63
§3. Quan hệ ngược và quan hệ hợp thành…………………………………………………….64
3.1. Quan hệ ngược……………………………………………………………………………….. 64
3.2. Quan hệ hợp thành………………………………………………………………………….. 65

MỤC L Ụ

C

_______ •________________________________________________________________5

• §4. Quan hệ tương đương…………………………………………………………………………….66
4.1. Định nghĩa quan hệ tương đương…………………………………………………….. 66
4.2. Phản hoạch tương đương và lớp tương đương trẽn tập hợp………………… 67
§5. Bao đóng bắc cáu của quan hệ……………………………………………………………….70
5.1. Bao đóng bắc cấu của quan hệ…………………………………………………………70
5.2. Xác định bao đóng bắc cầu của quan h ệ ………………………………………….. 70
§6. Thuật toán xác định bao đóng bắc cầu của quan h ệ ………………………………..73
BÀI TẬP ………………………… :………………………….. ……………………………………………. 74
Phán II. LOGIC VÀ ỨNG DỤNG
Chưưng 4. LOGIC MỆNH ĐỂ…………………………….. ………………………………………..78

§1. Các phép toán và công thức………………………………………………………………….. 78
1.1. Định nghĩa các phép toán trong đại số mệnh đ ề ………………………………..78
1.2. Định nghĩa công thức trong lỏgic mệnhđ ể …………………………………………. 79
1.3. Công thức đồng nhất bằng nhau và cốngthức đống nhất đúng……………80
1.4. Bảng công thức đồng nhất bằng nhau……………………………
80
1.5. Bảng công thức hằng đúng…………………………………………………………….. 81
1.6. Luật đối ngẫu…………………………………………………………………………………. 81
1.7. Luật thay th ế ………………………………………………………………………………….. 82
1.8. Luật kết lu ậ n ……………………………………………………….. i………………………. 83
§2. Điếu kiện đống nhất đúng (hằng đúng), điều kiện đồng nhất sai (hằng sai)…83
2.1. Tuyển và hội sơ cấp………………………………………………………………………. 83
2.2. Dạng chuẩn tắc tuyển và chuẩn tắc hội…………………………………………… 84
2.3. Thuật toán nhận biết hằng đúng, hằng sai và thực hiện được
của công thức trong lôgic mệnh đ ề …………………………………………………. 85
§3. Các quy tắc suy diễn trong lôgic mệnh đ ề ……………………………………………… 86
3.1. Các quy tắc suy diễn………………………… ……………………………………………87
3.2. Ví dụ minh hoạ việc áp dụng các quy tắc suy d iễ n …………………………….88
Chương 5. LOGIC VỊ TỪ …………………………………………………………………………… 102
§1. Định nghĩa vị từ ……………………………………………………………………………………102
§2. Khái niệm công thức đổng nhất bằng nhau, đổng nhất đúng
và đồng nhất s a l………………………………………………………………………….. …….104
§3. Ý nghĩa các vị từ theo lý thuyết tập hợp………………………………………………….106
3.1. Vị từ một ngôi………………………………………………………………………………..106
3.2. Mờ rộng cho vị từ n ngô i……………………………………………………………….. 107
§4. Dạng chuẩn tắc hội và dạng chuẩn tắc tuyển của công thức………………
108
4.1. Bảng các công thức đồng nhất bằng nhau trong lôgic vị từ cấp 1………. 110
4.2. Thuật toán tìm DCTH và DCTT của công thức A trong lôgic vị từ cấp 1…. 111
§5. Vấn đề về tính giải được………………………………………………………… ……………113

§6. Nguyên lý quy nạp………………………………….
118
§7. Quy tắc suy diễn trong lôgic vị từ cấp 1………………………………………………. ..124
7.1. Các lượng từ và các mệnh đề có lượng từ ……………………………………….. 124
7.2. Một số quy tắc suy diễn trong lôgic vị từ…………………………………………..124
7.3. Một sỏ ví dụ áp dụng………………………………… …………….. …………………. 125
BÀI TÂP …!………… ……………………… ……….. ……………… …………….. ,…………………129

6 ______________________________________________TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HOC

Chương 6. HỆ TOÁN MỆNH Đ Ể………………………………………………………………….140
§1. Hệ toán mệnh đ ề ………………………………………………………………………………… 141
1.1. Xây dựng hệ toán mệnh đề………………………………………………………………141
1.2. Các định nghĩa trong hệ toán mệnh đ ề ……………………………………………. 142
1.3. Một số ví dụ về định lý ……………
143
§2. Các tinh chất của hệ toán mệnh đế……………………………………………………….. 144
§3. Định lý tương đương…………………………………………………………………………….. 152
§4. Quan hệ giữa
Logic mệnh đề và hệ toán mệnhđ ề ……………………………. 169
§5. Tính phi mâu
thuẫn, tính đầy đủ, tính độc lập củahệ toán mệnh đé…… 180
5.1. Tính phi mâu thuẫn của hệ toán mệnh đ ề ………………………………………..180
5.2. Tính đầy đủ của hệ toán mệnh đ é …………………………………………………….180
5.3. Tính độc lập của hệ toán mệnh đ ề ……………………………………………………181

Phẩn III. ĐỒ THỊ VÀ ỨNG DỤNG
Chương 7. LÝ THUYẾT Đ ổ T H Ị………………………………………………………………….189
§1. Định nghĩa đồ thị, biểu diễn đồ thị và một số dạng đồ thị thường g ặ p ……… 189

1.1. Định nghĩa đố thị……………………………………………………………………………. 189
1.2. Biểu diễn đổ th ị……………………………………………………………………………… 190
1.3. Một số dạng đồ thị thường gặp…………………………………………………………193
§2. Một số thuật ngữ và tính chất của đố th ị………………………………………………….195
2.1. Một số thuật ngữ của dồ th ị……………………………………………………………..195
2.2. Một số tính chất của đồ th ị…………………………………………………………….. 197
§3. Số ổn định trong, số ổn định ngoài và nhân của đố th ị…………………………… 200
3.1. Sô ổn định tron g………………………………………………………….
200
3.2. Số ổn định ngoài……………………………………………………………………………. 200
3.3. Nhân của đồ thị……………………………………………………………………………… 201
3.4. Thuật toán tìm số ổn định ngoài……………………………………………………… 202
§4. Sắc sô của đô th ị………………….
204
4.1. Sắc số của đố thị đầy đ ủ ……………………………………………………………….. 204
4.2. Sắc số của đồ thị không có chu trình độ dài lẻ ………………………………….204
4 3 Quan hệ giữa sắc số và số ổn định trong………………………………………….205
4.4. Sắc số của đố thị có chu trình…………………………………………………………. 206
4.5. Sắc số của đồ thị đơn và đổ thị đơn phàn đôi…………………………………… 206
4.6. Bài toán tô màu bản đố……………………………………………………………………207
§5. Chu trình Euler và đường Euler……………………………………………………………..208
5.1. Chu trình Euler………………………………………………………………………………. 208
5.2. Thuật toán tìm chu trình Euler…………………………………………………………. 212
5.3. Đường Euler………………………………………………………………………………….. 213
5.4. Thuật toán tim đường Euler……………………………………………………………. 214
§6. Chu trình Hamilton và đường Hamilton………………………………………………….. 214
6.1. Chu trình Hamilton…………………………………………………………………………. 214
6.2. Đường Hamilton…………………………………………………………………………….. 216
§7. Đường đi ngắn nhất trong đổ th ị…………………………………………………………….218
7.1. Đường đi ngắn nhất trong đồ thị không trọng s ố ………………………………. 218

7.2. Đường đi ngắn nhất trong đồ thị có trọng s ố ……………………………………. 219

MỤC LỤC

_______ _______________________________________________________________ 7

§8. Một số tính chất của đố thị phảng…………………………………………………………. 224
8.1. Khái niệm diện hữu hạn và diện vô hạn của đố thị phảng………………………. 224
8.2. Chu sô’ của đò thị………….. ……………………………………………………………..225
8.3. Công thức Euler…………………………………………………………………………….. 226
BÀ. T Ậ P ……………………………………………………………………………………………………..226
Chương 8.

§2
§3.

§4

§5

§6

BAI

CÂYVÀ ỨNG DỤNG CỦA C Â Y ………………………………………………… 239

1.1. Cây.. . ………. ……………
1.2. Rừng cây………………………………………………………………………………………. 241
1.3. Cây có gốc……………………………………………………………………………………. 241

1.4. Cây m – phàn, cây m – phản đẩy đủ và cây nhị phản……………………….242
Một số tính chất của cây……………………………………………………………………… 243
ứng dụng của cây………………………………………………………………………………..246
3.1. Cày tìm kiếm nhị phân đối với bài toán 1…………………………………………..247
3.2. Cây quyết định đối với bàrtoán 2 ……………………………………………………248
3.3. Các mã tiền tố đối với bài toán 3 ……………………………………………………249
Các phương pháp duyệt cày………………………………………………………………… 252
4.1. Hệ địa chỉ phổ dụng………………………………………………………………………..252
4.2. Thuật toán duyệt câ y………………………………………………………………………253
Cây và các bài toán sắp x ế p ……………………………………………………………….. 258
5.1. Thuật toán sắp xếp nhị nguyên………………………………………………………. 258
5.2. Thuật toán sắp xếp kiểu nổi b ọ t……………………………………………………… 259
5.3. Thuật toán sắp xếp kiểu hoà nhập………………………………………………….. 261
Cày khung của đổ th ị………………………………………………….. :………………………266
6.1. Cây khung của đố thị không có trọng s ố ………………………………………… 266
6.2. Cây khung của đổ thị có trọng s ố ……………………………………………………275
T Ậ P …………………………………………………………………………………………………….. 282

Phấn IV. NGÔN NGỮ HỈNH THỨC
Chương 9. VĂN PHẠM VÀ NGÔN NGỮ SINH BỞI VĂN PHAM………………………. 298
§1 Khát niệm chung về ngốn ngữ……………………………………………………………….298
1.1. Bảng chữ c á i…………………………………………………………………………………. 298
1.2. Xâu ký tự ………………………………………………………………………………………. 299
1.3. Ngôn ngữ……………………………………………………………………………………… 299
§2 Văn phạm và ngôn ngữ sinh bởi văn phạm ……………………………………………..300
2.1. Định nghĩa văn phạm………………………………………………………………………300
2.2. Ngôn ngữ của văn phạm………………………………………………………………….301
§3 Phản loại văn phạm của chomsky…………………………………………………………302
§4. Một số ví dụ về văn phạm…………………………. ………………………………………… 304
§5. Một số tính chất của văn phạm………………………………………………………………308

BAI TẬP ……………………………………………………………………………………………………. 314
Chương 10. ÔTÔMAT HỮU HẠN VÀ NGÔN NGỬ-ĐOÁN NHẬN CỦA N Ó ……… 319
§1. Ôtômat hữu hạn (Finite Automata – FA)………………………………………………… 319
1.1. Định nghĩa ôtômat hữu hạn…………………………………………………………… 319

8_____________________________________________ TOÂN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC

1.2. Phương pháp biểu diễn ôtômat hữu hạn…………………………………………..320
1.3. Sự tương đương giữa ôtômat đơn định và không đơn định……………….. 327
§2. Ngôn ngữ chính quy và biểu thức chính quy……………………………………………328
2.1. Ngôn ngữ chính quy………………………………………………………………………..328
2.2. Biểu thức chính q u y ………………………………………………………………………..329
2.3. Thuật toán Thompson……………………………………………………………………. 329
2.4. Tính chất của ngôn ngữ chính quy…………………………………………………… 331
2.5. Quan hệ giữa ôtômat hữu hạn và ngôn ngữ chính quy……………………….332
BÀI T Ậ P ……………………………………………………………………………………………………335
Chương 11. ÔTÔMAT ĐẨY XUỐNG ĐOÁN NHẬN NGÔN NGỮ PHI NGỮ CẢNH ….345
§1. Văn phạm phi ngữ cảnh và cây dẫn xuất của n ó ……………………………………. 345
1.1. Định nghĩa văn phạm phi ngữ cảnh và quy tắc về ký h iệu………………… 345
1.2. Cây dẫn xuất đầy đủ trong văn phạm phi ngữ cảnh…………………………..346
1.3. Sự nhập nhằng trong ngôn ngữ phi ngữ cảnh………………………………….. 349
§2. Giản lược các văn phạm phi ngữ cảnh….. :……………………………………………. 350
2.1. Ký hiệu có ích và ký hiệu thừa……………………………………………………….. 350
2.2. Các A- quy tắc (a chỉ xâu rỗng)…………………………………………………….. 352
2.3. Các quy tắc đơn……………………………………………………………………………..353
§3. Văn phạm chuẩn của Chomsky……………………………………………………………. 354
§4. Ôtỏmat đẩy xuống (Pushdown Automata)………………………………………………356
4.1. Ôtômat đẩy xuống………………………………………………………………………….357
4.2. Ngôn ngữ đoán nhận của PA…… ……………………………………………………..360

§5. Phương pháp phân tích tất định trên lớp ngôn ngữ phi ngữ cảnh…………….. 366
5.1. Phản tích tất định……………………………………………………………………………366
5.2. Các hàm FIRST, FOLLOW……………………….
369
5.3. Điều kiện để văn phạm phi ngữ cảnh không nhập nhằng
và không đệ quy trái……………………………………………………………………….371
BÀI T Ậ P ………………………………………………………………..
374
Chương 12. MÁY TURING KHÔNG ĐƠN ĐỊNH ĐÀN HỔI ĐOÁN NHẬN
NGÔN NGỮVẢN PHẠM……………………….
391
§1. Máy
Turing đơn định…………………………………………………………………….. 391
§2. Máy Turing không đơn định đàn h ố i……………………………………………………… 393
2.1. Mô tả sự hoạt động của máy Turing đơn định không đàn h ồ i…………… 393
2.2. Mô hình máy một băng…………………………………………………………………..397
§3. Sự tương đương giữa máy Turing không đơn định đàn hổi
và văn phạm Chomsky……………’……………………………………………………………399
Phụ lục. MỘT s ố ĐỂ THI TUYỂN
TÀI LIỆU

s in h s a u đ ạ i h ọ c

(ĐHQGHN)………………. 401

THAM KHẢO …………………………………………………………………….. 407

PHẦN I

KIẾN THỨC BỔ TRỢ

_____________________________ ■

C hư ơn g 1
C Á C KHÁI NIỆM C O BẢN
CỦA THUẬT TOÁN VÀ PHƯONG PHÁP ĐỆ QUY
§1. KHÁI NIỆM THUẬT TOÁN
1.1. Thuật toán là gì
Thuật toán là một khái niệm quan trọng của toán học. Nói đến thuật
toán là nói đến một dãy các quy tắc, nhằm xác dinh một dãy các thao tác
trên các đôi tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác,
ta đạt dược mục tiêu cần làm.

1.2. Các độc trưng của thuột toán
– Tính dừng: Sau một số hữu hạn bước thuật toán phái dừng.
– Tính xác dinh: Ở mỗi bước, các thao tác phải rõ ràng, không gây nên
sự nhập nhằng. Nói rõ hơn, trong cùng một điểu kiện hai bộ xử lý cùng thực
hiện một bước của thuật toán phái cho những kết quá như nhau.
– Tính hiệu quá: Trước hết thuật toán phải dúng đắn, nghĩa là sau khi
dưa dữ liệu vào thuật toán hoạt dộng và đưa ra kết quả mong muốn.
– Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong
lớp các bài toán. Cụ thế là thuật toán có thê có các đầu vào là các bộ dữ liệu
khác nhau trong miên xác định.
– Yếu tố vào ra: Đối với một thuật toán luôn có một đối tượng vào
(input) và đối tượng ra (output).

10

“OÁN RỜI RAC ỨNG DUNG TRONG TIN HOC

1.3. Ngôn ngữ thuật ỉoán
– Ngôn ngữ dùng đe miêu ta thuật toán gọi là ngôn ngữ thuật toán.
– Thuật toán thường dược mò tá bàng một dãy các lệnh. Bộ xử lý sẽ
thực hiện các lệnh đó theo một trật tự nhất dinh cho đến khi gãp lệnh dừng
thì kết thúc.
– Ngôn ngữ thuật toán bao gồm:
+ Ngôn ngữ liệt kè tùng bước;
+ Sơ đồ khối;
+ Ngôn ngữ lập trình.
a) Ngôn ngữ liệt ké tùng bước bao gốm:
– Thuật toán: Tên thuật toán và chức nâng.
– Đầu vào: Các dữ liệu vào với tên, kiêu.
– Đầu ra: Các dữ liệu ra với tên, kiếu.
– Biến phụ (nếu có ) gồm tên, kiểu.
– Hành dộng là các thao tác với các lệnh có nhãn là các sô tự nhiên.
Ví dụ 1: Đế giái phương trình bậc hai ax2 + bx + c = 0 (a * 0), ta có thê
mô tá thuật toán bằng ngôn ngữ liệt kê như sau:
Bước l : Xác dinh các hệ sô a, b, c.
Bước 2: Kiểm tra xem hê sô a có khác 0 hay không? Nếu a = 0 quay lại
thực hiện bước 1.
Bước 3: Tính biểu thức A = b2 – 4ac.
Bước 4: Nếu A < 0 thông báo "phương trình vô nghiệm" và chuyển den
bước 8,
-b
Bước 5: Nếu A = 0. tinh X| = x2 = — và chuyên sang bước 7.
2a
Bước 6: Tính X, =

-b – VÃ
2a

– b + VÃ à.
chuyên sang bước 7.
, X-, = —————— vvà

2a

Bước 7: Thông báo các nghiệm X|, x2.
Bước S: Kết thúc thuât toán.
b) Sơ đổ khối

Đê mô tá thuật toán bàng sơ dổ khôi ta cần dựa vào các nút sau:

11

Phấn ĩ. KIẾN THỨC Bổ TRƠ

– NÚI thao tác: Biếu diễn bàng hình chữ nhật,
trong dó ghi câu lệnh cần thực hiện. Nếu có nhiều
câu lệnh liên tiếp cần được thực hiện thì chúng có
thế được viết chung trong nút thao tác;
– Nát điều kiện: Biểu diễn bằng hình thoi,
trong đó ghi điều kiện cần kiểm tra trong quá
trình tính toán;
– Nút khói dầu, kết thúc: Biểu diễn bằng hình
elip, the hiện sự bắt đầu hay kết thúc quá trình;
– Cung: Biểu diễn bằng đoạn thẳng có hướng,

dùng dể chỉ dường di của thuật toán.

Cung

Chẳng hạn, giải phương trình bậc hai ax2 + bx + c = 0 (a * 0) ta mò tả
thuật toán bằng phương pháp sơ đồ khối như sau:

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HOC

12

c) Ngôn ngữ lặp trình
Đê giải bài toán bằng máy tính, người ta thường sử dụng một loại ngôn
ngữ, gọi là ngôn ngữ lập trình, chẳng hạn như ngôn ngữ lập trình Cobol,
Algol, Pascal, … Chương trình chính là một dãy hữu hạn các câu lệnh được
viết theo một quy tắc nhất dinh trên một ngôn ngữ lập trình nào đó. Hay nói
cách khác, để giải một bài toán trước hết cần có một thuật toán để giải bài
toán đó; để máy tính hiểu được thuật toán, người ta sử dụng một ngón ngừ
lập trình cự thê đế diễn đạt thuật toán thông qua ngôn I*gữ đó.
Chảng hạn, giải phương trình bậc hai ax2 + bx + c = 0 (a * 0) ta mỏ tá
thuật toán bằng một chương trình Pascal như sau:
Program GIALPHUONG„TRINH_BAC_HAI ;
uses crt;
var a, b, c, delta, x1, x2: real;
BEGIN
clrscr;
write(‘Nhap he so
repeat
write(‘a =’); readln(a);

write(‘b =’); readln(b);
write(‘c =’); readln(c);
until a <> 0;
delta := sqr(b) – 4*a*c;
if delta < 0 then
begin
write(‘Phuong trinh vo nghiêm’);
halt;
end
else
if delta = 0 then
begin
write(‘Phuong trinh co nghiêm kep X=’, -b/(2*a));
exit;
end
else
begin
x1 ;= (—b – sqrt(delta))/(2*a);
x2:= (-b + sqrt(delta)ị/(2*a);
writeln(’Phuong trinh co hai nghiêm phan biet’);
write(‘x1 = ‘, x1,’x2 = ‘, x2);
exit;
end
readln;
END.

13

Phán ỉ. KIÉN THỨC Bổ TRỢ

1.4. Độ phức tạp thuật toán
Khi dề xuất một thuật toán, ngoài việc quan tâm đến tính đúng đắn,
thường phái quan tàm đến một số vấn đề như: ưu diêm, nhược điểm, tính phổ
dưng, thời gian tính toán, … Với các thuật toán được sử dụng có tần số cao
như các thuật toán sắp xếp, thuật toán tìm kiếm, … ta đặc biệt quan tâm dến
thời gian cần thiết cho việc thực hiện thuật toán dó.
Thông thường với mỗi thuật toán, dữ liệu vào sẽ có kích thước là một số
nào đó. Chảng hạn, khi sắp xếp một dãy số thì kích thước của dữ liệu có thê
xcm như là sô phần tứ n cúa dãy đó. Rõ ràng với n càng lớn thi thời gian cần
thiết cho việc sắp xếp sẽ càng lớn và nó là một hàm cúa đôi sô n. Ta ký hiệu
hàm dó là f(n). Trước khi dưa vào khái niệm dộ phức tạp của thuật toán, ta
dc cập tới một sô khái niệm sau:
a) Khái niệm vê độ táng của hàm
Một trong những khái niệm thường dùng để phân tích độ tăng của một
hàm là khái niệm “O” dược định nghĩa như sau:
Cho f(x) và g(x) là hai hàm từ tập các số nguyên dương hoặc tập các số
thực vào tập các số thực. Ta nói f(x) là ()(g(x)) nếu tồn tại hai hằng sô c và k
sao cho
lf(x)l < Clg(x)l với mọi X > k.
Cần lưu ý rằng, cặp các hằng số c và k thoả mãn điều kiện trên là không
duy nhất, dồng thời nếu f(x) là ()(g(x)) mà h(x) là hàm thoá mãn lg(x)l < lh(x)l
với X> k thì ta cũng có f(x) là ơ(h(x)).
Ví dụ 2: Cho f(x) = anxn + an_|Xn ‘ + … + a|X + a0, với a, là các sỏ’ thực
(i = 0, 1,…. n). Khi dó f(x) = 0(x”).
Thật vậy, với mọi X> 1 :
lf(x)l = lanxn + an-|Xn ‘ +. .. + aỊX + aDl
< lanlxn + I V | l x n 1+ ... + la,lx + lac +

= X
*
a n|

x n ( lan

M

‘ n -l I

a n-l|

+ … +

, n- 1

+ .•• + 1 a l| +

+

1a o | )

+

xYn /

+ 1a n – l 1 + – + 1a. 1+ 1a0| và k = 1, ta có
f(x)| < Cxn với mọi X > k, hay f(x) là 0 (x n).

TOÁN RỜI RẠC ỨNG DUNG TRONG TIN HOC

14

Ví dụ 3: Cho f(n) = 1 + 2 + 3 + … + n. Chỉ ra f(n) là C)(n2).
Thật vậy, f(n) < n + n + n + ... + n = n.n = n2, nên f(n) là C)(n2) với c = k = 1.
Ví dụ 4: Chỉ ra hàm n! là 0(nn) và logn! là O(nlogn).
Thật vậy, ta có n! < nn nên nl là 0 (n n) với c = k = 1.
Từ n! < nn => logn! < nlogn, vậy logn! là O(nlogn) với c = k = 1.
Ví dụ 5: Hãy chi ra hàm logn là O(n).
Thật vậy, ta có n < 2n với mọi n > 1, nên logn < n (lôgarit cơ số 2) và vì
vậy logn là 0(n) với c = k = 1.
b) Độ tăng của tổ hợp các hàm
Từ khái niệm về độ tãng của hàm ta có một số kết quá sau đây:
Ví dụ 6: Nếu f|(x) là 0(g|(x)) và f2(x) là 0(g2(x)) thì
(f|(x) + f2(x)) là 0(max|lg|(x)l, lg2(x)l|).
Thật vậy, theo giả thiết tồn tại Cj và k, sao cho
I fj(x)| < c, I g,(x)| với mọi X > kị, (i = 1, 2).
Ta lại có

I fị(x) + f2(x)| < I f|(x)| + I f2(x)|
< c, I g,(x)| + c 2|g 2(x)|
< c | g(x)| với mọi X > k,

ớđây k = max(k|, k2}; c = C| + c 2; g(x) = max{lg|(x)l, lg9(x)l}.

Ví dụ 7: Cho f|(x) và f2(x) đều là 0(g(x)). Khi dó
fị(x) + f2(x) là 0(g(x)) (hệ quả của ví dụ 6).
Ví dụ 8: Nếu f|(x) là 0(g|(x)) và f2(x) là 0(g2(x)) thì
fị(x).f2(x) là ũ(g,(x).g2(x)).
‘ITiật vậy, theo giả thiết I f|(x)|< C| I g|(x)| với mọi X > k|
và I f2(x)|< c 2 I g2(x)| với mọi X > k2.
Xét I f|(x).f2(x)| = |f|(x )|.| f2(x)| < C|C2|g |( x ) |.|g 2(x)|
= ClC2|g 1(x).g2(x)|.
Vậy f|(x). f2(x) là 0(g|(x).g2(x)), với c = C|C2, k = max(k,, k2}.

15

rh àn /. KIÊN THỨC Bổ TRƠ

Ví dụ 9: Cho f(n) = nlog(n!) + rrlogn, với n = 1, 2, 3, … Khi đó f(n) là
0 (n 2logn).
Thật vậy, ta có nlog(n!) là 0(n2logn), còn n2logn là 0(n2logn). Từ ví dụ 7
ta có f(n) là 0 (n 2logn).
Ví dụ 10: Chứng minh rằng, nếu f(x) là 0(g(x)) thì f”(x) là 0(gn(x)), ở
đâyffl(x )= |f(x ).f(x)…f(x)| = I f(x)|.| f(x)|…| f(x)| < c n gn(x)
‘———–„———– ‘
‘————– „————– n lán

n lán

với mọi X > k.

Hay f n(x) < c gn(x) với mọi X > k, c := C”.
Vậy f (X) là 0(gn(x)).

Ví dụ 11: Giả sử f(x) là 0(g(x)) với f(x), g(x) là các hàm đơn diệu tãng

và không giới nội. Chứng minh log(f(x)) là 0(log(g(x))).
Thật vậy, theo giá thiết ta có I f(x)| < C| I g(x)| với mọi X > k|. Ta có thê
giá thiết f(x) > 1, g(x) > 1 với X dủ lớn, hay f(x) < Cg(x) với X đủ lcớn.
Lỏgarit cơ sỏ 2 bất dảng thức trên ta có
log(f(x)) < log(C|g(x)) = logCị + log(g(x)) < 21og(g(x)) với X đủ lớn.
Hay log(f(x)) là 0(log(g(x)).
c) Độ phức tạp thuật toán
Ớ dày chúng ta chỉ để cập tới dộ phức tạp của thuật toán vé thời gian
tính toán mà không để cập tới dộ phức tạp về không gian cúa thuật toán.
Các phép toán dược dùng dế do dộ phức tạp thời gian của thuật toán là
phép so sánh sô nguyên; các phép cộng, trừ, nhàn, chia các số nguyên; hoặc
bất kỳ một phép tính sơ cấp nào khác xuất hiện trong quá trình tính toán.
Cần lưu ý các thuật ngữ dùng trong dộ phức tạp thuật toán thường gặp:
– Độ phức tạp 0( 1) gọi là độ phức tạp hằng số.
– Độ phức tạp O(logn) gọi là dộ phức tạp lôgarit.
– Độ phức tạp O(n) gọi là dộ phức tạp tuyến tính.
– Độ phức tạp O(nlogn) gọi là dộ phức tạp nlogn.- – Độ phức tạp 0 (n b) gọi là độ phức tạp da thức.
– Đ ộ phức tạp 0(bn) (b > 1) gọi là dộ phức tạp hàm mũ.
– Độ phức tạp 0(n!) gọi là độ phức tạp giai thừa.

TOAN RỜI RAC ỨNG DỤNG TRONG TIN HỌC

16

Để minh hoạ vể độ phức tap của thuật toán ta xét một sỏ VI du sau:
Ví dụ 12: Mô ta llliuật toán tìm phán tử lớn nhát của dãy hữu hạn các sô
nguvên và tìm độ phức tap cua thuật toán đó.

Bước I : Đặt giá trịi c ực dại tạm thời bằng sô nguyên đấu tiên của dãy.
Bước 2: So sánh sổ nguyên tiếp theo với giá trị tạm thời, nếu nó lớn hưn
giá trị cực dại tạm thời thì đặt cực đại tạm thời bằng số nguyên dó.
Bước 3: Lặp lại burớc 2 (nếu còn các sô nguyên trong dãy).
Bước 4: Dừng khi không còn số nguyên nào trong dãy. Khi dó cực dai
tạm thời chính là sô nguvôn lern nhất trong dãy.
Mô tá thuật toán tìm phần tứ lứn nhát trong dãy hữu hạn:
Procedure MAX(a,, a2, …. a„ : integer);
max := a,;
for i ;= 2 to n do
if max < a, then max := a,
{max là phấn tử hớn nhất}

Lưu ý: Mổi sô hạng của dãy dùng hai phép so sánh, một dô xác định
chưa đạt dến cuối dãy, một dế xác định có phải nó là giá trị lớn nhất tạm thời
hay không. Việc so sánh này dược dùng cho mỗi phần tứ a, trong dãv tù
phần tứ thứ hai trỏ di (i = 2, 3….. n). Sau dó là phép so sánh đế ra khói vòng
lặp, nên số phép so sánh cần dùng tất cả là 2(n – 1) + 1 dối với thuật toán
trên. Vậy thuật toán trên có dộ phức tạp thời gian là O(n) (dộ phức tạp

tuyên tính).
Ví dụ 13: Mô tả thuật toán xác dinh vị trí của một phần tử trong một
báng liệt kê sắp thứ tự. Bài toán tìm kiếm được phát biểu như sau:
Xác định vị trí của X trong bàng liệt kê các phần tử phân biệt: d|, a ,…..an.
Dưới đây ta đé cập tới thuật toán tìm kiếm tuyến tính:
Mô tả thuật toán: Trước hết ta so sánh X với a,, nếu X = a, thì \ ị trí là 1,
còn trường hợp X * a I ta so sánh tiếp X với a2. Nếu X = a2 thì vị trí của X là 2,
còn trường hợp X * a2 thi so sánh tiếp X với av Quá trình trôn được tiếp tục
cho đến khi nếu X = a, (i < n) thì vị trí là i, trường hợp X * a, (Vi < n) thì X
khòng có mặt trong bảng liệt kê.

17

Phàn /. KIỂN THỨC Bổ TRƠ

Mô tá thuật toán tìm kiếm tuyến tính:
Procedure TÌM KIỀM. TT (x: integer, a,, a2…. an: các số nguyên phản biệt);
i:= 1
while (I < n) and (x * a,) do i:=i + 1;
if ị < n then location := i
else location ;= o
{location là chỉ số của số hạng bằng X(location = 0 nếu không tim dược x)}.

Lito ý: Ở mỗi bước của vòng lập trong thuật toán trên có hai phép so
sánh: một dể xem đã tới cuối dãy chưa; một dể xem phần tử X có trùng với
một phần tứ của bảng liệt kê hay không. Cuối cùng là một phép so sánh
ngoài vòng lập.
Nếu X = a, thì có 2i + 1 phép so sánh dược sứ dụng. Số phép so sánh lớn
nhất là 2n + 1 (khi X * a¡, i = 1,2,
n). Sau dó cần một phép so sánh để
thoát khỏi vòng lặp. Vậy, khi X không có mặt trong bảng thì tống sô phép so
sánh trong thuật toán này là 2n + 2. Vậy độ phức tạp của thuật toán là 0(n).
Xét bài toán trên trong trường hợp các phần từ trong báng dược sắp theo
thứ tự tăng dần. Ví dụ, tìm số 19 trong báng liệt kê theo thứ tự tăng dần: 1, 2,
3, 4. 5, 6, 7, 8, 10. 12, 13, 15, 16, 17, 18, 19, 20, 22. Tổng quát: Tìm X trong
báng liệt kê a,, a2, …. an với dị < a2 Đé giái bài toán trên ta dùng thuật toán nhị phàn, được mô tả như sau: So sánh X với sô hạng am ở giữa dãy (m = l(n + 1>/21, ở dây ỊxỊ là phần
nguyên lớn nhất không vượt quá x). Nếu X > am thì việc tìm kiếm X trên dãy
gồm các số hạng am+1, am+, ……an; còn nếu X < am thì việc tìm kiếm sẽ thực hiện trên dãy gồm các sô ‘dị, a2….. am. Cả hai trường hợp đều dưa dến bài toán tìm kiếm trên báng khổng lớn hơn [n/2] phần tứ. Quá trình trên được
thực hiện cho tới khi bảng liệt kê chi còn một phần tử và so sánh X với chính
số hạng này.
Mô tả thuật toán tìm kiếm nhị phân:
Procedure TÌM KIẾM_NHLPHÂN (x : integer, a,, a2…. an: integer – tăng dấn)
i := 1 {i là diểm mut trái của khoảng tìm kiếm)
j := n {j lá diểm mút phải của khoảng tim kiếm)
while i begin

m := Ị(i + ])/2)
if X> amthen i := m + 1
else j := m
end
; -TOAN RỜI RAC

^ 8 ______________________ _____________________ TOAN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC

if X = a, then location := i

else location := 0
{location là chiỉ số của sõ hang bằng X (location = 0 nếu không tim thấy x)}.

Lưu ý: Độ phức tạp cùa thuật toán tìm kiếm nhị phán trên là O(logn) vì
nó phải dùng tới 2[logn] + 2 phép toán so sánh. Như vậy, trong trường hợp
báng liệt kê được sắp thứ tự thì thuật toán tìm kiếm nhị phân tốt hem thuật
toán tìm kiếm tuyến tính
Đê kết thúc phần nàv ta xét thêm thuật toán Euclid.
Trong lý thuyết sò n gười ta đã chứng minh dược rằng:
Nếu a = bq + r, trong dó a, b, q, r là các sô nguycn thì:
ƯCLN(a, b) = ƯCLN(b, r)

(*)

Giả sử a, b là các số nguyên dương, với a > b. Đặt r0 = a, Tj = b. Bằng
cách áp dụng kết quả trên ta có:
ro = r i‘l i + r2 •
r, = r2q2 + r3

(0 < r2< r,)
(0 < r3 < r2' rn-2 = *n-iqn-| + rn (0 < rn < rn_,) ®n—l – EiMrr
SỐ dư xuất hiện trong dãy các phép chia liên tiếp, vì dãy các số
a = rc > T| > r2 > … > 0 không thế chứa quá a sô hạng. Từ (*) ta suy ra:
ƯCLN(a, b) = ƯCLN(r0, r () = ƯCLN(r,, r2) = …

= ƯCLN(rn..2, rn_ I) = ƯCLN(rn-j, rn) = ƯCLN(rn, 0) = rn.
Vậy, ước chung lớn nhất là số dư khác 0 cuối cùng trong dãy các phép chia.
Ví dụ 14: Tim ƯCLN(414, 662).
Áp dụng thuật toán Euclid ta dược:
662 = 414.1 + 248
414 = 248.2+ 166
248 = 166.1 + 82
166 = 82.2 + 2
82 = 2.41
Do đó ƯC1 .N(414, 662) = 2 (2 là sô dư cuối cùng khác khống).

19

rh ấn l. KIẾN THỨC Bổ TRƠ

‘ITiuật toán Euclid dược mô tả như sau:
Procedure UCLN(a, b : integer);

X := a
y :=b
while y * 0
begin
r := X mod y

x:=y
y ;=r
end {UCLN(a, b) là x}

Lưu ỷ: Giá trị ban dầu cúa X, y tương ứng là a và b. Ó mỗi giai đoạn của

thú tục X dược thay bằng y và y được thay bởi X mod y (là số dư r trong phép
chia X cho y). Quá trình này dược lặp lại nếu y * 0 và thuật toán sẽ dừng khi
y = 0. Giá trị của X ớ thời điếm này là số dư khác 0 cuối cùng trong thú tục
và chính là ước số chung lớn nhất cần tìm.

§2. PHƯƠNG PHÁP ĐỆ QUY
Độ quy là một khái niệm tồn tại trong cuộc sống, trong toán học. trong
lập trình. Đệ quy cho một phương pháp ngăn gọn và sáng súa đe mô tá các
dõi tượng cũng như một sò quá trình. Như vậy, dệ quy là một phương pháp
xác dịnh tập hợp các dôi tượng thoá mãn một ycu cáu nào dó. Nó bao gồm
các quy tắc, trong dó một sô’ quy tắc dùng để xác định các dối tượng ban
đầu, còn quy tắc khác dùng để xác dịnh các đối tượng tiếp theo nhờ các đối
tượng ban đầu đã dược xác định.
= 2 -^ị + 3
với mọi n > 1. Khi dó ta có thê xác dịnh được số hạng an tống quát của dãy
sô trẽn như sau:
Ví dụ 1: Một dãy số a0, a,, a2….. a„, … có tính chất: an = 0,

Trước hết chọn các số ơị, a-, sao cho
(an – a, ) = a 2(an_ | – a, )
Từ (1) suy ra an = a ,a n^ I – a !.a 9 + a I.
Rõ ràng các số a I, a 2 phái thoá mãn hệ phương trình

(1)

TOÁN RỜI RẠC ỨNG DUNG TRONG TIN HOC

20

|« 2 = 2
Ịa, – a ,. a 2 = 3
Từ hệ trên ta có ngay ơ| = -3, a 2 = 2. Đặt qn = an – otị với n > 1. Suy ra
qn = a 2.qn_| với n > 1 và q! = 6, từ đó ta có qn = qj .a^-1.
Vậy a„ – aj = qj .aỊỊ-1, suy ra an = a, + qi .a”“1 = 6.2n 1- 3.
Chương trình con đệ quy để tính sô’ hạng tổng quát an được minh hoạ
như sau:
Function fn(n: integer): integer;
BIGIN
if n = 0 then fn := 0
else fn := 2*fn(n-1) + 3;
END;

Ví dụ 2: Một dãy a0, d ị, a2, …. an, … có tính chất: aQ = 0, d ị = 1,
an = an_j + an_2 với mọi n > 2, dược gọi là dãy Fibonacci. Như vậy, dãy
Fibonacci là dãy: 0, 1, 1, 2, 3, 5, 8, 13, 21,… và với n > 2 ta có thể tìm được
số Fibonacci thứ n nếu biết sô’ Fibonacci thứ n – 1 và thứ n – 2. Bàng quy
nạp toán học ta dễ dàng chứng minh được rằng, với n > 0
1 í 1+
a” = ^ l

n

>/5

2

1

1

J :j5

ịi-s íĩ)
K

2

y

Tuy nhiên công thức trên có thê tính trực tiếp như sau:
Trước hết hãy tìm một cặp sô’ (X|, ct2 sao cho:
a n – c t i V, = a 2(an_ 1- a, a n_2)

=>

an = (a, + a 2)an_1- a, a 2an_2

Rõ ràng các cặp sô’ CX|, a 2 thoả mãn hệ phương trình

Í

ơị + a 2 = 1
a ,a 2 = – l

Khi đó CX|, a 2 sẽ là nghiêm của phương trình X2 – X – 1 = 0, do dó ta

thê chọn

CX| =

,a2

= – —

. Đặt qn

qn = a 2qn-i với n > 2 và q, = 1. Ta có q n = a 2- 1 .

=

an

ơ ị a n„ | ,

khi dó

21

Phán l. KIÊN THỨC Bổ TRỢ

In_, = a n

2, suy ra an = a ^ – 1+ « r
a2 = a ^ ! + a 2
(1)
2
a3 —a |a 2 + a 2
(2)
3
a4 = a ,a 2 + a 2
(3)
an-l = aiV-2 + a 2~2

(n -2 )

^ = « 1 ^ -1 + « r 1

(n -1 )

Khi nhân hai vế của đẳng thức (n – 2) với

CX|,

đầng thức (n – 3) với

a 2,… đảng thức (1) với a ” -2 và cộng lại theo từng vế ta có:
t” ‘aị

vạy an =

.n-2

1 + \Í5
4~5

a2T

… +

1 ( 1-45
41 l

n-3

2 _

ỌỊĨ

ai

a, – a 2

với n > 2. Tuy nhiên công

2

thức này cũng đúng với n > 0.
Chương trình con để tính sô’ hạng tổng quát thứ n có thể được viết như sau:
Function fn(n : integer): integer;

BEGIN
if n <= 1 then fn := n else fn := fn(n – 1) + fn(n – 2); END;
Ví dụ 3: Có m phần thường được chia cho n học sinh giỏi được xếp
hạng từ 1, 2,…. n. Hỏi rằng có bao nhiêu cách chia phần thướng trên sao cho
các điểu kiện sau dược thoả mãn:
a) Nếu học sinh A giỏi hơn học sinh B thì sô’ phần thưởng của A sẽ lớn
hơn hoặc bằng sô’ phần thướng của B;
b) Tất cả m phần thướng đểu phải thướng hết cho học sinh.
Giả sứ rằng với i < j và 1 < i, j < n thì học sinh thứ i giỏi hơn học sinh
thứ j. Ký hiệu sổ phần thướng mà học sinh thứ i nhận dược là Tị. Từ giả thiết
của bài toán ta suy ra các diều kiện sau cần dược thoả mãn:
Tị + T2 + … + Tn = m;
T| > T2 > … > Tn > 0.

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC

22

Ký hiệu CHIA(m, n) là sô’ cách chia m phần thướng cho n học sinh theo
ycu cầu trên.
Nhận xét ràng:
– Khi m = 0, tức là không có phần thưởng nào thì khi dó rõ ràng chí có
duy nhất một cách chia: mỗi học sinh dược 0 phần thướng. Vậy CH1A(0, n) = 1
dối với mọi n.
– Khi có m phần thướng và không có học sinh giỏi, đưorng nhiên sẽ
không có cách chia nào. Vậy CHIA(m, 0) = 0 đối với mọi m * 0.
– Khi có m phần thướng, n học sinh giỏi và m < n, khi đó n - m học
sinh phía cuối sẽ không nhận dược phần thướng nào, do đó:

CHIA(m, n) = CHIA(m, m) khi m < n.
– Khi có m phần thưởng, n học sinh giỏi và m > n. Khi đó ta xét hai
trường hợp sau:
+ Khi học sinh cuối cùng không nhận được phần thướng nào, khi đó số
cách chia sẽ là CHIA(m, n – 1);
+ Khi học sinh cuối cùng nhận dược 1 phần thướng, khi đó tất cá các
học sinh giỏi sẽ nhận được ít nhất 1 phần thưởng, do đó số cách chia trong
trường hợp này sẽ là CHIA(m – n, n).
Tóm lại, khi có m phần thướng và n học sinh giỏi thì số cách chia sẽ là
CHIA(m, n – 1) + CHIA(m – n, n).
Trên cơ sớ dó ra có thê viết một chương trình con đệ quy thế hiện thuật

toán trên như sau:
Function CHIA(m, n : integer): integer;
BEGIN
if m = 0 then CHIA := 1
else if n = 0 then CHIA := CHIA(m, m)
else CHIA := CHIA(m, n – 1) + CHIA(m – n, n)
END;

Thuật toán quay lui

Bài toán: Hãy xây dựng các bộ giá trị gồm có n thành phấn (X|, x2, …, xn)
từ một tập hữu hạn cho trước, sao cho các bộ đó thoả mãn một yêu cầu B cho
trước nào đó.

Phấn /. KIỂN THỨC Bổ TRƠ

23

Phương pháp:
Xây dựng các phần tử Xị, x2, x n theo cách sau đây:
Giả sử đã xác định được k – 1 phần tử đầu tiên cúa dãy đó là X|, x2,
xk |. Cần xác dịnh tiếp phần tứ xk, phần tử này được xác định theo cách sau:
Giả sử Tk là tập tất cả các giá trị mà phần tứ xk có thể nhận dược. Vì tập
Tk là hữu hạn nên có thế đặt nk là số phần tứ của tập Tk. Khi đó có thế liệt kê
các phẩn tử của Tk theo một thứ tự nào đó. Tức là có thể thành lập một ánh
xạ 1 – 1 từ tập Tk lên tập {1, 2,…, nk}.
– Nếu k = n, khi đó bộ (X|, x2,
xk_ị, xk) có đủ n thành phần và thoả
mãn yêu cầu dặt ra, do dó bộ này được đưa vào quan hệ kết quả.
Xét j e 11, 2, …. nkỊ, ta nói rằng “j chấp nhận được” nếu có thế bổ sung
phần tứ thứ j trong Tk với tư cách là phần tử xk vào dãy X), x2, …, xk_ị, xk.
– Nếu k < n ta cần phái thực hiện tiếp quá trình trên, tức là phải bổ sung
tiếp phẩn tử xk+1 vào dãy Xị, x2, …, xk_| để được dãy Xị, x2, …, xk_|, xk.
Như vậy, nét đặc trưng của phương pháp quay lui là ớ chỗ có được lời
giải ta phái đi từng bước bằng phép thử. Khi một bước lựa chọn chấp nhận
cần ghi nhớ thông tin cần thiết và tiến hành bước tiếp theo. Ngược lại, khi
không có một lựa chọn nào được chấp nhận thì cần phải thực hiện lại bước
trước, xoá bớt ghi nhớ và thứ lại với những lựa chọn còn lại.
a) Thủ tục đệ quy cho thuật toán quay lui
Procedure THU (k: interger);
Var j: interger;
BEGIN
for j := 1 to nk do
if then
Begin

if k = n then

else THU(k +1);
End;
END;

Điều đáng quan tâm ờ đây là:
1) Làm thế nào để xác dịnh dược tập Tk, tức là tập tất cả các khả năng
mà phần tứ thứ k của dãy X|, x2….. xn có thể nhận được.

24

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC

2) Khi đã có tập Tk dê xác định xk, thấy ràng xk không những phụ thuộc
vào chí số j mà còn phụ thuộc vào các X|, x2……xk_ị. Vì vậy cần phải ghi
nhớ trạng thái cúa quá trình xác định dãy bằng một biến nhớ nào dó sau khi
xác định dược xk theo j và dồng thời phái trả lại trạng thái cũ sau lời gọi
T H U (k+ l).
Ngoài thủ tục THƯ(k) nên có một thú tục gọi là khới tạo, nhằm tạo ra
một sô giá trị cũng như những trạng thái cần thiết ban đầu.
b) Các ví dụ minh hoạ cho thuật toán quay lui
Trong các ví dụ dưới đây bộ giá trị (Xị, x2, …. xn) sẽ được lưu trữ dưới
dạng mảng một chiểu là x[ 1], x [ 2 ], x [ n ] .
Ví dụ 4: Liệt kê tất cả các hoán vị của n số tự nhiên dầu tiên.
Đặt N = {1,2,…, n }. Khi đó một hoán vị của n số tự nhiên đầu tiên sẽ là
một bộ x[ 1]» x[2], …. x[n]. Trong đó x[i] * x(j] với i * j và x[i] e N. Nhận
thấy Tị = N. Giả sử đã xác định được x[l], x[2J,…, x[k—1], khi đó:
Tk = N – {x[l], x[2],

,x [k -l]} .

Để ghi nhớ tập Tj (i = 1, …, n), ta cần sử dụng một mảng b[l..n] là các
giá trị boolean sao cho b[i] = true khi và chỉ khi i e Tk.
Sau dây là chương trình liệt kê tất cả các hoán vị của n số tự nhiên dầu tiên.
Program HOANVI;
uses crt;
type
mang = array[1 ..20] of interger;
Var
x: mang;
b: array[1 .20] of boolean;
n, d: interger;

(*•——- — *)
Procedure KHOLTAO;
Var
i: interger;
BEGIN
writefso phan tu =”); readln(n);
for i:= 1 to n do b[i] := true;
d := 0;
END;

(*— ————-■*)
Procedure INKQ;
Var
i: interger;

– Phần II. Logic và ứng dụng ; – Phần III. Dồ thị và ứng dụng ; – Phần IV. Ngôn ngữ hình thức. Cuốn Toán rời rac ứng dung trong tin hoc trình diễn những vân dềtoán học cơ bản nhất, nhưng lại rất là thiết yếu và thiết yếu đối vớinhững ai m uôh có dược những kiến thức và kỹ năng tin học vững chãi. Cuốn sáchgiúp người học hiểu dược lý thuyết thấu dáo, rèn luyện tư duy khoahọc, k ỹ năng thống kê giám sát và năng lực vận dụng toán học vào giải quyếtvân dề, kích thích niềm mê hồn học tập và từ đó nâng cao k ỹ năngthực hành, tư duy phát minh sáng tạo khi học những môn học cơ SỞ và chuyênngành Công nghệ thông tin tiếp theo. Cuốn sách này cũng rất bô íchcho việc ôn thi tu vén sinh sau dại hoc ngành Công nghệ thông tindược tô chức hàng năm Ở Đại học Quốc gia TP.HN. Tác giả chân thành cảm ơn những bạn dồng nghiệp dã dộng viên tácgiả biên soạn cuốn sách này. Cuốn sách xuất bản lần dầu, nôn khó tránh khỏi thiếu sót về hìnhthức củng như nội dung. Vì vậy, tác giả m ong nhận dược sự góp ýcủa bạn dọc dê cuốn sách ngày càng tốt hơn. Mọi góp ý xin gửi về : Công ty Cô phần Sách Dại học và Dạy nghề : 25 Hàn Thuyên Hà Nộ i. TÁC GIẢTOÁN RỜI RẠC ỨNG DUNG TRONG TIN HOCMỤC LỤCLỜI NÓI ĐẦU …………………………………………………………………………………………………. 3P hẩn I. KIẾN THỬC B ổ TRỢChương 1. CÁC KHÁI NIỆM c ơ BẢN CỦA THUẬT TOÁNVÀ PHƯƠNG PHÁP ĐỆ Q UY. ………………………………………………………. 9 § 1. Khái niệm thuật toán ……………………………………………………………………………….. 91.1. Thuật toán là gì ………………………………………………………………………………… 91.2. Các đặc trưng của thuật toán ………………………………………………………………. 1.3. Ngôn ngữ thuật toán ………………………………………………………………………… 101.4. Độ phức tạp thuật to á n ……………………………………………………………………. 13 § 2. Phương pháp đệ quy ……………………………………………………………………………… 19B ÀI T Ậ P …………………………………………………………………………………………………….. 29C hương 2. CÁC PHƯƠNG PHÁP Đ Ế M …………………………………………………………. 33 § 1. Tập hợp và trình diễn tập hợp trênmáy tính ……………………………………………… 331.1. Các phép toán trên tập hợp ……………………………………………………………… 331.2. Các đặc thù của tập hợp ………………………………………………………………… 341.3. Lực lượng của tập h ợp ……………………………………………………………………… 341.4. Tích Đề-các của những tập hợp và lực lượng của n ó ………………………………. 351.5. Biểu diễn những tập hợp trên máy tính ………………………………………………….. 35 § 2. Hoán vị, chỉnh hợp và tổng hợp ………………………………………………………………….. 372.1. Hoán vị và chình hợp ……………………………………………………………………….. 372.2. Tổ hợp và định lý nhị thức ………………………………………………………………… 38 § 3. Các quy tắc đếm cơ bản …………………………………………….. 433.1. Quy tắc cộng …………………………………………………………………………………… 433.2. Quy tắc nhân ………………………………………………………………………………….. 443.3. Một số bài toán đếm phối hợp giữa quy tắc cộng và quy tắc nhâ n ……….. 45 § 4. Nguyên lý chuồng chim bồ câu ……………………………………………………………… 524.1. Nguyên lý chuồng chim bổ c ả u ……………………………………………………….. 524.2. Nguyên lý Dirichlet …………………………………………………………………………… 524.3. Các ví d ụ ………………………………………………………………………………………… 53C hương 3. QUAN HỆ …………………………………………………………………………………… 57 § 1. Quan hệ và màn biểu diễn quan h ệ ……………………………………………………………….. 571.1. Quan hệ và ví dụ về quan hệ ……………………………………………………………. 571.2. Phương pháp trình diễn quan hệ ……………………………………………………….. 571.3. Tính chất của quan h ệ ……………………………………………………………………… 60 § 2. Cung và đường trong đố thị của quan h ệ ………………………………………………… 632.1. Định nghĩa 1 ……………………………………………………………………………………. 632.2. Tính chất ………………………………………………………………………………………… 63 § 3. Quan hệ ngược và quan hệ hợp thành ……………………………………………………. 643.1. Quan hệ ngược ……………………………………………………………………………….. 643.2. Quan hệ hợp thành ………………………………………………………………………….. 65M ỤC L Ụ_______ • ________________________________________________________________5 • § 4. Quan hệ tương tự ……………………………………………………………………………. 664.1. Định nghĩa quan hệ tương tự …………………………………………………….. 664.2. Phản hoạch tương tự và lớp tương tự trẽn tập hợp ………………… 67 § 5. Bao đóng bắc cáu của quan hệ ………………………………………………………………. 705.1. Bao đóng bắc cấu của quan hệ ………………………………………………………… 705.2. Xác định bao đóng bắc cầu của quan h ệ ………………………………………….. 70 § 6. Thuật toán xác lập bao đóng bắc cầu của quan h ệ ……………………………….. 73B ÀI TẬP ………………………… : ………………………….. ……………………………………………. 74P hán II. LOGIC VÀ ỨNG DỤNGChưưng 4. LOGIC MỆNH ĐỂ …………………………….. ……………………………………….. 78 § 1. Các phép toán và công thức ………………………………………………………………….. 781.1. Định nghĩa những phép toán trong đại số mệnh đ ề ……………………………….. 781.2. Định nghĩa công thức trong lỏgic mệnhđ ể …………………………………………. 791.3. Công thức như nhau bằng nhau và cốngthức đống nhất đúng …………… 801.4. Bảng công thức như nhau bằng nhau …………………………… 801.5. Bảng công thức hằng đúng …………………………………………………………….. 811.6. Luật đối ngẫu …………………………………………………………………………………. 811.7. Luật thay th ế ………………………………………………………………………………….. 821.8. Luật kết lu ậ n ……………………………………………………….. i ………………………. 83 § 2. Điếu kiện đống nhất đúng ( hằng đúng ), điều kiện kèm theo giống hệt sai ( hằng sai ) … 832.1. Tuyển và hội sơ cấp ………………………………………………………………………. 832.2. Dạng chuẩn tắc tuyển và chuẩn tắc hội …………………………………………… 842.3. Thuật toán phân biệt hằng đúng, hằng sai và triển khai đượccủa công thức trong lôgic mệnh đ ề …………………………………………………. 85 § 3. Các quy tắc suy diễn trong lôgic mệnh đ ề ……………………………………………… 863.1. Các quy tắc suy diễn ………………………… …………………………………………… 873.2. Ví dụ minh hoạ việc vận dụng những quy tắc suy d iễ n ……………………………. 88C hương 5. LOGIC VỊ TỪ …………………………………………………………………………… 102 § 1. Định nghĩa vị từ …………………………………………………………………………………… 102 § 2. Khái niệm công thức đổng nhất bằng nhau, đổng nhất đúngvà như nhau s a l ………………………………………………………………………….. ……. 104 § 3. Ý nghĩa những vị từ theo kim chỉ nan tập hợp …………………………………………………. 1063.1. Vị từ một ngôi ……………………………………………………………………………….. 1063.2. Mờ rộng cho vị từ n ngô i ……………………………………………………………….. 107 § 4. Dạng chuẩn tắc hội và dạng chuẩn tắc tuyển của công thức ……………… 1084.1. Bảng những công thức như nhau bằng nhau trong lôgic vị từ cấp 1 ………. 1104.2. Thuật toán tìm DCTH và DCTT của công thức A trong lôgic vị từ cấp 1 …. 111 § 5. Vấn đề về tính giải được ………………………………………………………… …………… 113 § 6. Nguyên lý quy nạp …………………………………. 118 § 7. Quy tắc suy diễn trong lôgic vị từ cấp 1 ………………………………………………. .. 1247.1. Các lượng từ và những mệnh đề có lượng từ ……………………………………….. 1247.2. Một số quy tắc suy diễn trong lôgic vị từ ………………………………………….. 1247.3. Một sỏ ví dụ vận dụng ………………………………… …………….. …………………. 125B ÀI TÂP … ! ………… ……………………… ……….. ……………… …………….., ………………… 1296 ______________________________________________TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HOCChương 6. HỆ TOÁN MỆNH Đ Ể …………………………………………………………………. 140 § 1. Hệ toán mệnh đ ề ………………………………………………………………………………… 1411.1. Xây dựng hệ toán mệnh đề ……………………………………………………………… 1411.2. Các định nghĩa trong hệ toán mệnh đ ề ……………………………………………. 1421.3. Một số ví dụ về định lý …………… 143 § 2. Các tinh chất của hệ toán mệnh đế ……………………………………………………….. 144 § 3. Định lý tương tự …………………………………………………………………………….. 152 § 4. Quan hệ giữaLogic mệnh đề và hệ toán mệnhđ ề ……………………………. 169 § 5. Tính phi mâuthuẫn, tính không thiếu, tính độc lập củahệ toán mệnh đé …… 1805.1. Tính phi xích míc của hệ toán mệnh đ ề ……………………………………….. 1805.2. Tính không thiếu của hệ toán mệnh đ é ……………………………………………………. 1805.3. Tính độc lập của hệ toán mệnh đ ề …………………………………………………… 181P hẩn III. ĐỒ THỊ VÀ ỨNG DỤNGChương 7. LÝ THUYẾT Đ ổ T H Ị …………………………………………………………………. 189 § 1. Định nghĩa đồ thị, trình diễn đồ thị và 1 số ít dạng đồ thị thường g ặ p ……… 1891.1. Định nghĩa đố thị ……………………………………………………………………………. 1891.2. Biểu diễn đổ th ị ……………………………………………………………………………… 1901.3. Một số dạng đồ thị thường gặp ………………………………………………………… 193 § 2. Một số thuật ngữ và đặc thù của đố th ị …………………………………………………. 1952.1. Một số thuật ngữ của dồ th ị …………………………………………………………….. 1952.2. Một số đặc thù của đồ th ị …………………………………………………………….. 197 § 3. Số không thay đổi trong, số không thay đổi ngoài và nhân của đố th ị …………………………… 2003.1. Sô không thay đổi tron g …………………………………………………………. 2003.2. Số không thay đổi ngoài ……………………………………………………………………………. 2003.3. Nhân của đồ thị ……………………………………………………………………………… 2013.4. Thuật toán tìm số không thay đổi ngoài ……………………………………………………… 202 § 4. Sắc sô của đô th ị …………………. 2044.1. Sắc số của đố thị đầy đ ủ ……………………………………………………………….. 2044.2. Sắc số của đồ thị không có chu trình độ dài lẻ …………………………………. 2044 3 Quan hệ giữa sắc số và số không thay đổi trong …………………………………………. 2054.4. Sắc số của đố thị có quy trình …………………………………………………………. 2064.5. Sắc số của đồ thị đơn và đổ thị đơn phàn đôi …………………………………… 2064.6. Bài toán tô màu bản đố …………………………………………………………………… 207 § 5. Chu trình Euler và đường Euler …………………………………………………………….. 2085.1. Chu trình Euler ………………………………………………………………………………. 2085.2. Thuật toán tìm quy trình Euler …………………………………………………………. 2125.3. Đường Euler ………………………………………………………………………………….. 2135.4. Thuật toán tim đường Euler ……………………………………………………………. 214 § 6. Chu trình Hamilton và đường Hamilton ………………………………………………….. 2146.1. Chu trình Hamilton …………………………………………………………………………. 2146.2. Đường Hamilton …………………………………………………………………………….. 216 § 7. Đường đi ngắn nhất trong đổ th ị ……………………………………………………………. 2187.1. Đường đi ngắn nhất trong đồ thị không trọng s ố ………………………………. 2187.2. Đường đi ngắn nhất trong đồ thị có trọng s ố ……………………………………. 219M ỤC LỤC_______ _______________________________________________________________ 7 § 8. Một số đặc thù của đố thị phảng …………………………………………………………. 2248.1. Khái niệm diện hữu hạn và diện vô hạn của đố thị phảng ………………………. 2248.2. Chu sô ‘ của đò thị ………….. …………………………………………………………….. 2258.3. Công thức Euler …………………………………………………………………………….. 226B À. T Ậ P …………………………………………………………………………………………………….. 226C hương 8. § 2 § 3. § 4 § 5 § 6BAIC ÂYVÀ ỨNG DỤNG CỦA C Â Y ………………………………………………… 2391.1. Cây. .. ………. …………… 1.2. Rừng cây ………………………………………………………………………………………. 2411.3. Cây có gốc ……………………………………………………………………………………. 2411.4. Cây m – phàn, cây m – phản đẩy đủ và cây nhị phản ………………………. 242M ột số đặc thù của cây ……………………………………………………………………… 243 ứng dụng của cây ……………………………………………………………………………….. 2463.1. Cày tìm kiếm nhị phân so với bài toán 1 ………………………………………….. 2473.2. Cây quyết định hành động so với bàrtoán 2 …………………………………………………… 2483.3. Các mã tiền tố so với bài toán 3 …………………………………………………… 249C ác giải pháp duyệt cày ………………………………………………………………… 2524.1. Hệ địa chỉ phổ dụng ……………………………………………………………………….. 2524.2. Thuật toán duyệt câ y ……………………………………………………………………… 253C ây và những bài toán sắp x ế p ……………………………………………………………….. 2585.1. Thuật toán sắp xếp nhị nguyên ………………………………………………………. 2585.2. Thuật toán sắp xếp kiểu nổi b ọ t ……………………………………………………… 2595.3. Thuật toán sắp xếp kiểu hoà nhập ………………………………………………….. 261C ày khung của đổ th ị ………………………………………………….. : ……………………… 2666.1. Cây khung của đố thị không có trọng s ố ………………………………………… 2666.2. Cây khung của đổ thị có trọng s ố …………………………………………………… 275T Ậ P …………………………………………………………………………………………………….. 282P hấn IV. NGÔN NGỮ HỈNH THỨCChương 9. VĂN PHẠM VÀ NGÔN NGỮ SINH BỞI VĂN PHAM. ……………………… 298 § 1 Khát niệm chung về ngốn ngữ ………………………………………………………………. 2981.1. Bảng chữ c á i …………………………………………………………………………………. 2981.2. Xâu ký tự ………………………………………………………………………………………. 2991.3. Ngôn ngữ ……………………………………………………………………………………… 299 § 2 Văn phạm và ngôn từ sinh bởi văn phạm …………………………………………….. 3002.1. Định nghĩa văn phạm ……………………………………………………………………… 3002.2. Ngôn ngữ của văn phạm …………………………………………………………………. 301 § 3 Phản loại văn phạm của chomsky ………………………………………………………… 302 § 4. Một số ví dụ về văn phạm …………………………. ………………………………………… 304 § 5. Một số đặc thù của văn phạm ……………………………………………………………… 308BAI TẬP ……………………………………………………………………………………………………. 314C hương 10. ÔTÔMAT HỮU HẠN VÀ NGÔN NGỬ-ĐOÁN NHẬN CỦA N Ó ……… 319 § 1. Ôtômat hữu hạn ( Finite Automata – FA ) ………………………………………………… 3191.1. Định nghĩa ôtômat hữu hạn …………………………………………………………… 3198 _____________________________________________ TOÂN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC1. 2. Phương pháp trình diễn ôtômat hữu hạn ………………………………………….. 3201.3. Sự tương tự giữa ôtômat đơn định và không đơn định ……………….. 327 § 2. Ngôn ngữ chính quy và biểu thức chính quy …………………………………………… 3282.1. Ngôn ngữ chính quy ……………………………………………………………………….. 3282.2. Biểu thức chính q u y ……………………………………………………………………….. 3292.3. Thuật toán Thompson ……………………………………………………………………. 3292.4. Tính chất của ngôn từ chính quy …………………………………………………… 3312.5. Quan hệ giữa ôtômat hữu hạn và ngôn từ chính quy ………………………. 332B ÀI T Ậ P …………………………………………………………………………………………………… 335C hương 11. ÔTÔMAT ĐẨY XUỐNG ĐOÁN NHẬN NGÔN NGỮ PHI NGỮ CẢNH …. 345 § 1. Văn phạm phi ngữ cảnh và cây dẫn xuất của n ó ……………………………………. 3451.1. Định nghĩa văn phạm phi ngữ cảnh và quy tắc về ký h iệu ………………… 3451.2. Cây dẫn xuất khá đầy đủ trong văn phạm phi ngữ cảnh ………………………….. 3461.3. Sự nhập nhằng trong ngôn từ phi ngữ cảnh ………………………………….. 349 § 2. Giản lược những văn phạm phi ngữ cảnh ….. : ……………………………………………. 3502.1. Ký hiệu có ích và ký hiệu thừa ……………………………………………………….. 3502.2. Các A – quy tắc ( a chỉ xâu rỗng ) …………………………………………………….. 3522.3. Các quy tắc đơn …………………………………………………………………………….. 353 § 3. Văn phạm chuẩn của Chomsky ……………………………………………………………. 354 § 4. Ôtỏmat đẩy xuống ( Pushdown Automata ) ……………………………………………… 3564.1. Ôtômat đẩy xuống …………………………………………………………………………. 3574.2. Ngôn ngữ đoán nhận của PA. ….. …………………………………………………….. 360 § 5. Phương pháp nghiên cứu và phân tích tất định trên lớp ngôn từ phi ngữ cảnh …………….. 3665.1. Phản tích tất định …………………………………………………………………………… 3665.2. Các hàm FIRST, FOLLOW. ……………………… 3695.3. Điều kiện để văn phạm phi ngữ cảnh không nhập nhằngvà không đệ quy trái ………………………………………………………………………. 371B ÀI T Ậ P ……………………………………………………………….. 374C hương 12. MÁY TURING KHÔNG ĐƠN ĐỊNH ĐÀN HỔI ĐOÁN NHẬNNGÔN NGỮVẢN PHẠM ………………………. 391 § 1. MáyTuring đơn định …………………………………………………………………….. 391 § 2. Máy Turing không đơn định đàn h ố i ……………………………………………………… 3932.1. Mô tả sự hoạt động giải trí của máy Turing đơn định không đàn h ồ i …………… 3932.2. Mô hình máy một băng ………………………………………………………………….. 397 § 3. Sự tương tự giữa máy Turing không đơn định đàn hổivà văn phạm Chomsky …………… ‘ …………………………………………………………… 399P hụ lục. MỘT s ố ĐỂ THI TUYỂNTÀI LIỆUs in h s a u đ ạ i h ọ c ( ĐHQGHN ) ………………. 401THAM KHẢO …………………………………………………………………….. 407PH ẦN IKIẾN THỨC BỔ TRỢ_____________________________ ■ C hư ơn g 1C Á C KHÁI NIỆM C O BẢNCỦA THUẬT TOÁN VÀ PHƯONG PHÁP ĐỆ QUY § 1. KHÁI NIỆM THUẬT TOÁN1. 1. Thuật toán là gìThuật toán là một khái niệm quan trọng của toán học. Nói đến thuậttoán là nói đến một dãy những quy tắc, nhằm mục đích xác dinh một dãy những thao táctrên những đôi tượng, sao cho sau một số ít hữu hạn bước triển khai những thao tác, ta đạt dược tiềm năng cần làm. 1.2. Các độc trưng của thuột toán – Tính dừng : Sau một số ít hữu hạn bước thuật toán phái dừng. – Tính xác dinh : Ở mỗi bước, những thao tác phải rõ ràng, không gây nênsự nhập nhằng. Nói rõ hơn, trong cùng một điểu kiện hai bộ giải quyết và xử lý cùng thựchiện một bước của thuật toán phái cho những kết quá như nhau. – Tính hiệu quá : Trước hết thuật toán phải dúng đắn, nghĩa là sau khidưa tài liệu vào thuật toán hoạt dộng và đưa ra tác dụng mong ước. – Tính phổ dụng : Thuật toán hoàn toàn có thể giải bất kể một bài toán nào tronglớp những bài toán. Cụ thế là thuật toán có thê có những nguồn vào là những bộ dữ liệukhác nhau trong miên xác lập. – Yếu tố vào ra : Đối với một thuật toán luôn có một đối tượng người dùng vào ( input ) và đối tượng người dùng ra ( output ). 10 ” OÁN RỜI RAC ỨNG DUNG TRONG TIN HOC1. 3. Ngôn ngữ thuật ỉoán – Ngôn ngữ dùng đe miêu ta thuật toán gọi là ngôn từ thuật toán. – Thuật toán thường dược mò tá bàng một dãy những lệnh. Bộ giải quyết và xử lý sẽthực hiện những lệnh đó theo một trật tự nhất dinh cho đến khi gãp lệnh dừngthì kết thúc. – Ngôn ngữ thuật toán gồm có : + Ngôn ngữ liệt kè tùng bước ; + Sơ đồ khối ; + Ngôn ngữ lập trình. a ) Ngôn ngữ liệt ké tùng bước bao gốm : – Thuật toán : Tên thuật toán và chức nâng. – Đầu vào : Các tài liệu vào với tên, kiêu. – Đầu ra : Các tài liệu ra với tên, kiếu. – Biến phụ ( nếu có ) gồm tên, kiểu. – Hành dộng là những thao tác với những lệnh có nhãn là những sô tự nhiên. Ví dụ 1 : Đế giái phương trình bậc hai ax2 + bx + c = 0 ( a * 0 ), ta có thêmô tá thuật toán bằng ngôn từ liệt kê như sau : Bước l : Xác dinh những hệ sô a, b, c. Bước 2 : Kiểm tra xem hê sô a có khác 0 hay không ? Nếu a = 0 quay lạithực hiện bước 1. Bước 3 : Tính biểu thức A = b2 – 4 ac. Bước 4 : Nếu A < 0 thông tin " phương trình vô nghiệm " và chuyển denbước 8, - bBước 5 : Nếu A = 0. tinh X | = x2 = — và chuyên sang bước 7.2 aBước 6 : Tính X, = - b - VÃ2a - b + VÃ à. chuyên sang bước 7., X -, = ------------------ vvà2aBước 7 : Thông báo những nghiệm X |, x2. Bước S : Kết thúc thuât toán. b ) Sơ đổ khốiĐê mô tá thuật toán bàng sơ dổ khôi ta cần dựa vào những nút sau : 11P hấn ĩ. KIẾN THỨC Bổ TRƠ - NÚI thao tác : Biếu diễn bàng hình chữ nhật, trong dó ghi câu lệnh cần thực thi. Nếu có nhiềucâu lệnh liên tục cần được thực thi thì chúng cóthế được viết chung trong nút thao tác ; - Nát điều kiện kèm theo : Biểu diễn bằng hình thoi, trong đó ghi điều kiện kèm theo cần kiểm tra trong quátrình giám sát ; - Nút khói dầu, kết thúc : Biểu diễn bằng hìnhelip, the hiện sự mở màn hay kết thúc quy trình ; - Cung : Biểu diễn bằng đoạn thẳng có hướng, dùng dể chỉ dường di của thuật toán. CungChẳng hạn, giải phương trình bậc hai ax2 + bx + c = 0 ( a * 0 ) ta mò tảthuật toán bằng chiêu thức sơ đồ khối như sau : TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HOC12c ) Ngôn ngữ lặp trìnhĐê giải bài toán bằng máy tính, người ta thường sử dụng một loại ngônngữ, gọi là ngôn từ lập trình, ví dụ điển hình như ngôn từ lập trình Cobol, Algol, Pascal, ... Chương trình chính là một dãy hữu hạn những câu lệnh đượcviết theo một quy tắc nhất dinh trên một ngôn từ lập trình nào đó. Hay nóicách khác, để giải một bài toán trước hết cần có một thuật toán để giải bàitoán đó ; để máy tính hiểu được thuật toán, người ta sử dụng một ngón ngừlập trình cự thê đế diễn đạt thuật toán trải qua ngôn I * gữ đó. Chảng hạn, giải phương trình bậc hai ax2 + bx + c = 0 ( a * 0 ) ta mỏ táthuật toán bằng một chương trình Pascal như sau : Program GIALPHUONG „ TRINH_BAC_HAI ; uses crt ; var a, b, c, delta, x1, x2 : real ; BEGINclrscr ; write ( ' Nhap he sorepeatwrite ( ' a = ' ) ; readln ( a ) ; write ( ' b = ' ) ; readln ( b ) ; write ( ' c = ' ) ; readln ( c ) ; until a < > 0 ; delta : = sqr ( b ) – 4 * a * c ; if delta < 0 thenbeginwrite ( ' Phuong trinh vo nghiêm ' ) ; halt ; endelseif delta = 0 thenbeginwrite ( ' Phuong trinh co nghiêm kep X = ', - b / ( 2 * a ) ) ; exit ; endelsebeginx1 ; = ( — b - sqrt ( delta ) ) / ( 2 * a ) ; x2 : = ( - b + sqrt ( delta ) ị / ( 2 * a ) ; writeln ( ’ Phuong trinh co hai nghiêm phan biet ' ) ; write ( ' x1 = ', x1, ' x2 = ', x2 ) ; exit ; endreadln ; END. 13P hán ỉ. KIÉN THỨC Bổ TRỢ1. 4. Độ phức tạp thuật toánKhi dề xuất một thuật toán, ngoài việc chăm sóc đến tính đúng đắn, thường phái quan tàm đến một số ít yếu tố như : ưu diêm, điểm yếu kém, tính phổdưng, thời hạn giám sát, ... Với những thuật toán được sử dụng có tần số caonhư những thuật toán sắp xếp, thuật toán tìm kiếm, ... ta đặc biệt quan trọng chăm sóc dếnthời gian thiết yếu cho việc thực thi thuật toán dó. Thông thường với mỗi thuật toán, tài liệu vào sẽ có size là một sốnào đó. Chảng hạn, khi sắp xếp một dãy số thì size của tài liệu có thêxcm như là sô phần tứ n cúa dãy đó. Rõ ràng với n càng lớn thi thời hạn cầnthiết cho việc sắp xếp sẽ càng lớn và nó là một hàm cúa đôi sô n. Ta ký hiệuhàm dó là f ( n ). Trước khi dưa vào khái niệm dộ phức tạp của thuật toán, tadc cập tới một sô khái niệm sau : a ) Khái niệm vê độ táng của hàmMột trong những khái niệm thường dùng để nghiên cứu và phân tích độ tăng của mộthàm là khái niệm " O " dược định nghĩa như sau : Cho f ( x ) và g ( x ) là hai hàm từ tập những số nguyên dương hoặc tập những sốthực vào tập những số thực. Ta nói f ( x ) là ( ) ( g ( x ) ) nếu sống sót hai hằng sô c và ksao cholf ( x ) l < Clg ( x ) l với mọi X > k. Cần quan tâm rằng, cặp những hằng số c và k thoả mãn điều kiện kèm theo trên là khôngduy nhất, dồng thời nếu f ( x ) là ( ) ( g ( x ) ) mà h ( x ) là hàm thoá mãn lg ( x ) l < lh ( x ) lvới X > k thì ta cũng có f ( x ) là ơ ( h ( x ) ). Ví dụ 2 : Cho f ( x ) = anxn + an_ | Xn ‘ + … + a | X + a0, với a, là những sỏ ‘ thực ( i = 0, 1, …. n ). Khi dó f ( x ) = 0 ( x ” ). Thật vậy, với mọi X > 1 : lf ( x ) l = lanxn + an – | Xn ‘ +. .. + aỊX + aDl < lanlxn + I V | l x n 1 + ... + la, lx + lac = Xa n | x n ( lan ‘ n - l Ia n-l | + ... +, n - 1 +. • • + 1 a l | + ... 1 a o | ) xYn / + 1 a n - l 1 + - + 1 a. 1 + 1 a0 | và k = 1, ta cóf ( x ) | < Cxn với mọi X > k, hay f ( x ) là 0 ( x n ). TOÁN RỜI RẠC ỨNG DUNG TRONG TIN HOC14Ví dụ 3 : Cho f ( n ) = 1 + 2 + 3 + … + n. Chỉ ra f ( n ) là C ) ( n2 ). Thật vậy, f ( n ) < n + n + n + ... + n = n. n = n2, nên f ( n ) là C ) ( n2 ) với c = k = 1. Ví dụ 4 : Chỉ ra hàm n ! là 0 ( nn ) và logn ! là O ( nlogn ). Thật vậy, ta có n ! < nn nên nl là 0 ( n n ) với c = k = 1. Từ n ! < nn => logn ! < nlogn, vậy logn ! là O ( nlogn ) với c = k = 1. Ví dụ 5 : Hãy chi ra hàm logn là O ( n ). Thật vậy, ta có n < 2 n với mọi n > 1, nên logn < n ( lôgarit cơ số 2 ) và vìvậy logn là 0 ( n ) với c = k = 1. b ) Độ tăng của tổng hợp những hàmTừ khái niệm về độ tãng của hàm ta có một số ít kết quá sau đây : Ví dụ 6 : Nếu f | ( x ) là 0 ( g | ( x ) ) và f2 ( x ) là 0 ( g2 ( x ) ) thì ( f | ( x ) + f2 ( x ) ) là 0 ( max | lg | ( x ) l, lg2 ( x ) l | ). Thật vậy, theo giả thiết sống sót Cj và k, sao choI fj ( x ) | < c, I g, ( x ) | với mọi X > kị, ( i = 1, 2 ). Ta lại cóI fị ( x ) + f2 ( x ) | < I f | ( x ) | + I f2 ( x ) | < c, I g, ( x ) | + c 2 | g 2 ( x ) | < c | g ( x ) | với mọi X > k, ớđây k = max ( k |, k2 } ; c = C | + c 2 ; g ( x ) = max { lg | ( x ) l, lg9 ( x ) l }. Ví dụ 7 : Cho f | ( x ) và f2 ( x ) đều là 0 ( g ( x ) ). Khi dófị ( x ) + f2 ( x ) là 0 ( g ( x ) ) ( hệ quả của ví dụ 6 ). Ví dụ 8 : Nếu f | ( x ) là 0 ( g | ( x ) ) và f2 ( x ) là 0 ( g2 ( x ) ) thìfị ( x ). f2 ( x ) là ũ ( g, ( x ). g2 ( x ) ). ‘ ITiật vậy, theo giả thiết I f | ( x ) | < C | I g | ( x ) | với mọi X > k | và I f2 ( x ) | < c 2 I g2 ( x ) | với mọi X > k2. Xét I f | ( x ). f2 ( x ) | = | f | ( x ) |. | f2 ( x ) | < C | C2 | g | ( x ) |. | g 2 ( x ) | = ClC2 | g 1 ( x ). g2 ( x ) |. Vậy f | ( x ). f2 ( x ) là 0 ( g | ( x ). g2 ( x ) ), với c = C | C2, k = max ( k, , k2 }. 15 rh àn /. KIÊN THỨC Bổ TRƠVí dụ 9 : Cho f ( n ) = nlog ( n ! ) + rrlogn, với n = 1, 2, 3, ... Khi đó f ( n ) là0 ( n 2 logn ). Thật vậy, ta có nlog ( n ! ) là 0 ( n2logn ), còn n2logn là 0 ( n2logn ). Từ ví dụ 7 ta có f ( n ) là 0 ( n 2 logn ). Ví dụ 10 : Chứng minh rằng, nếu f ( x ) là 0 ( g ( x ) ) thì f " ( x ) là 0 ( gn ( x ) ), ởđâyffl ( x ) = | f ( x ). f ( x ) ... f ( x ) | = I f ( x ) |. | f ( x ) | ... | f ( x ) | < c n gn ( x ) ' ----------- „ ----------- ' ' -------------- „ -------------- n lánn lánvới mọi X > k. Hay f n ( x ) < c gn ( x ) với mọi X > k, c : = C “. Vậy f ( X ) là 0 ( gn ( x ) ). Ví dụ 11 : Giả sử f ( x ) là 0 ( g ( x ) ) với f ( x ), g ( x ) là những hàm đơn diệu tãngvà không giới nội. Chứng minh log ( f ( x ) ) là 0 ( log ( g ( x ) ) ). Thật vậy, theo giá thiết ta có I f ( x ) | < C | I g ( x ) | với mọi X > k |. Ta có thêgiá thiết f ( x ) > 1, g ( x ) > 1 với X dủ lớn, hay f ( x ) < Cg ( x ) với X đủ lcớn. Lỏgarit cơ sỏ 2 bất dảng thức trên ta cólog ( f ( x ) ) < log ( C | g ( x ) ) = logCị + log ( g ( x ) ) < 21 og ( g ( x ) ) với X đủ lớn. Hay log ( f ( x ) ) là 0 ( log ( g ( x ) ). c ) Độ phức tạp thuật toánỚ dày tất cả chúng ta chỉ để cập tới dộ phức tạp của thuật toán vé thời giantính toán mà không để cập tới dộ phức tạp về khoảng trống cúa thuật toán. Các phép toán dược dùng dế do dộ phức tạp thời hạn của thuật toán làphép so sánh sô nguyên ; những phép cộng, trừ, nhàn, chia những số nguyên ; hoặcbất kỳ một phép tính sơ cấp nào khác Open trong quy trình đo lường và thống kê. Cần quan tâm những thuật ngữ dùng trong dộ phức tạp thuật toán thường gặp : - Độ phức tạp 0 ( 1 ) gọi là độ phức tạp hằng số. - Độ phức tạp O ( logn ) gọi là dộ phức tạp lôgarit. - Độ phức tạp O ( n ) gọi là dộ phức tạp tuyến tính. - Độ phức tạp O ( nlogn ) gọi là dộ phức tạp nlogn. - - Độ phức tạp 0 ( n b ) gọi là độ phức tạp da thức. - Đ ộ phức tạp 0 ( bn ) ( b > 1 ) gọi là dộ phức tạp hàm mũ. – Độ phức tạp 0 ( n ! ) gọi là độ phức tạp giai thừa. TOAN RỜI RAC ỨNG DỤNG TRONG TIN HỌC16Để minh hoạ vể độ phức tap của thuật toán ta xét một sỏ VI du sau : Ví dụ 12 : Mô ta llliuật toán tìm phán tử lớn nhát của dãy hữu hạn những sônguvên và tìm độ phức tap cua thuật toán đó. Bước I : Đặt giá trịi c ực dại trong thời điểm tạm thời bằng sô nguyên đấu tiên của dãy. Bước 2 : So sánh sổ nguyên tiếp theo với giá trị trong thời điểm tạm thời, nếu nó lớn hưngiá trị cực dại trong thời điểm tạm thời thì đặt cực lớn trong thời điểm tạm thời bằng số nguyên dó. Bước 3 : Lặp lại burớc 2 ( nếu còn những sô nguyên trong dãy ). Bước 4 : Dừng khi không còn số nguyên nào trong dãy. Khi dó cực daitạm thời chính là sô nguvôn lern nhất trong dãy. Mô tá thuật toán tìm phần tứ lứn nhát trong dãy hữu hạn : Procedure MAX ( a, , a2, …. a „ : integer ) ; max : = a, ; for i ; = 2 to n doif max < a, then max : = a, { max là phấn tử hớn nhất } Lưu ý : Mổi sô hạng của dãy dùng hai phép so sánh, một dô xác địnhchưa đạt dến cuối dãy, một dế xác lập có phải nó là giá trị lớn nhất tạm thờihay không. Việc so sánh này dược dùng cho mỗi phần tứ a, trong dãv tùphần tứ thứ hai trỏ di ( i = 2, 3 ..... n ). Sau dó là phép so sánh đế ra khói vònglặp, nên số phép so sánh cần dùng toàn bộ là 2 ( n - 1 ) + 1 dối với thuật toántrên. Vậy thuật toán trên có dộ phức tạp thời hạn là O ( n ) ( dộ phức tạptuyên tính ). Ví dụ 13 : Mô tả thuật toán xác dinh vị trí của một thành phần trong mộtbáng liệt kê sắp thứ tự. Bài toán tìm kiếm được phát biểu như sau : Xác định vị trí của X trong bàng liệt kê những thành phần phân biệt : d |, a, ..... an. Dưới đây ta đé cập tới thuật toán tìm kiếm tuyến tính : Mô tả thuật toán : Trước hết ta so sánh X với a, , nếu X = a, thì \ ị trí là 1, còn trường hợp X * a I ta so sánh tiếp X với a2. Nếu X = a2 thì vị trí của X là 2, còn trường hợp X * a2 thi so sánh tiếp X với av Quá trình trôn được tiếp tụccho đến khi nếu X = a, ( i < n ) thì vị trí là i, trường hợp X * a, ( Vi < n ) thì Xkhòng xuất hiện trong bảng liệt kê. 17P hàn /. KIỂN THỨC Bổ TRƠMô tá thuật toán tìm kiếm tuyến tính : Procedure TÌM KIỀM. TT ( x : integer, a, , a2 .... an : những số nguyên phản biệt ) ; i : = 1 while ( I < n ) and ( x * a, ) doi : = i + 1 ; if ị < n then location : = ielse location ; = o { location là chỉ số của số hạng bằng X ( location = 0 nếu không tim dược x ) }. Lito ý : Ở mỗi bước của vòng lập trong thuật toán trên có hai phép sosánh : một dể xem đã tới cuối dãy chưa ; một dể xem thành phần X có trùng vớimột phần tứ của bảng liệt kê hay không. Cuối cùng là một phép so sánhngoài vòng lập. Nếu X = a, thì có 2 i + 1 phép so sánh dược sứ dụng. Số phép so sánh lớnnhất là 2 n + 1 ( khi X * a ¡, i = 1,2, n ). Sau dó cần một phép so sánh đểthoát khỏi vòng lặp. Vậy, khi X không xuất hiện trong bảng thì tống sô phép sosánh trong thuật toán này là 2 n + 2. Vậy độ phức tạp của thuật toán là 0 ( n ). Xét bài toán trên trong trường hợp những phần từ trong báng dược sắp theothứ tự tăng dần. Ví dụ, tìm số 19 trong báng liệt kê theo thứ tự tăng dần : 1, 2,3, 4. 5, 6, 7, 8, 10. 12, 13, 15, 16, 17, 18, 19, 20, 22. Tổng quát : Tìm X trongbáng liệt kê a, , a2, .... an với dị < a2Đé giái bài toán trên ta dùng thuật toán nhị phàn, được diễn đạt như sau : So sánh X với sô hạng am ở giữa dãy ( m = l ( n + 1 > / 21, ở dây ỊxỊ là phầnnguyên lớn nhất không vượt quá x ). Nếu X > am thì việc tìm kiếm X trên dãygồm những số hạng am + 1, am +, …… an ; còn nếu X < am thì việc tìm kiếm sẽ thựchiện trên dãy gồm những sô'dị, a2 ..... am. Cả hai trường hợp đều dưa dến bàitoán tìm kiếm trên báng khổng lớn hơn [ n / 2 ] phần tứ. Quá trình trên đượcthực hiện cho tới khi bảng liệt kê chi còn một thành phần và so sánh X với chínhsố hạng này. Mô tả thuật toán tìm kiếm nhị phân : Procedure TÌM KIẾM_NHLPHÂN ( x : integer, a, , a2 .... an : integer - tăng dấn ) i : = 1 { i là diểm mut trái của khoảng chừng tìm kiếm ) j : = n { j lá diểm mút phải của khoảng chừng tim kiếm ) while ibeginm : = Ị ( i + ] ) / 2 ) if X > amthen i : = m + 1 else j : = mend ; – TOAN RỜI RAC ^ 8 ______________________ _____________________ TOAN RỜI RẠC ỨNG DỤNG TRONG TIN HỌCif X = a, then location : = ielse location : = 0 { location là chiỉ số của sõ hang bằng X ( location = 0 nếu không tim thấy x ) }. Lưu ý : Độ phức tạp cùa thuật toán tìm kiếm nhị phán trên là O ( logn ) vìnó phải dùng tới 2 [ logn ] + 2 phép toán so sánh. Như vậy, trong trường hợpbáng liệt kê được sắp thứ tự thì thuật toán tìm kiếm nhị phân tốt hem thuậttoán tìm kiếm tuyến tínhĐê kết thúc phần nàv ta xét thêm thuật toán Euclid. Trong kim chỉ nan sò n gười ta đã chứng tỏ dược rằng : Nếu a = bq + r, trong dó a, b, q, r là những sô nguycn thì : ƯCLN ( a, b ) = ƯCLN ( b, r ) ( * ) Giả sử a, b là những số nguyên dương, với a > b. Đặt r0 = a, Tj = b. Bằngcách vận dụng hiệu quả trên ta có : ro = r i ‘ l i + r2 • r, = r2q2 + r3 ( 0 < r2 < r, ) ( 0 < r3 < r2 ' rn-2 = * n-iqn - | + rn ( 0 < rn < rn_, ) ® n — l - EiMrrSỐ dư Open trong dãy những phép chia liên tục, vì dãy những sốa = rc > T | > r2 > … > 0 không thế chứa quá a sô hạng. Từ ( * ) ta suy ra : ƯCLN ( a, b ) = ƯCLN ( r0, r ( ) = ƯCLN ( r, , r2 ) = … = ƯCLN ( rn .. 2, rn_ I ) = ƯCLN ( rn-j, rn ) = ƯCLN ( rn, 0 ) = rn. Vậy, ước chung lớn nhất là số dư khác 0 ở đầu cuối trong dãy những phép chia. Ví dụ 14 : Tim ƯCLN ( 414, 662 ). Áp dụng thuật toán Euclid ta dược : 662 = 414.1 + 248414 = 248.2 + 166248 = 166.1 + 82166 = 82.2 + 282 = 2.41 Do đó ƯC1. N ( 414, 662 ) = 2 ( 2 là sô dư ở đầu cuối khác khống ). 19 rh ấn l. KIẾN THỨC Bổ TRƠ’ITiuật toán Euclid dược diễn đạt như sau : Procedure UCLN ( a, b : integer ) ; X : = ay : = bwhile y * 0 beginr : = X mod yx : = yy ; = rend { UCLN ( a, b ) là x } Lưu ỷ : Giá trị ban dầu cúa X, y tương ứng là a và b. Ó mỗi quá trình củathú tục X dược thay bằng y và y được thay bởi X mod y ( là số dư r trong phépchia X cho y ). Quá trình này dược tái diễn nếu y * 0 và thuật toán sẽ dừng khiy = 0. Giá trị của X ớ thời điếm này là số dư khác 0 sau cuối trong thú tụcvà chính là ước số chung lớn nhất cần tìm. § 2. PHƯƠNG PHÁP ĐỆ QUYĐộ quy là một khái niệm sống sót trong đời sống, trong toán học. tronglập trình. Đệ quy cho một chiêu thức ngăn gọn và sáng súa đe mô tá cácdõi tượng cũng như một sò quy trình. Như vậy, dệ quy là một phương phápxác dịnh tập hợp những dôi tượng thoá mãn một ycu cáu nào dó. Nó bao gồmcác quy tắc, trong dó một sô ‘ quy tắc dùng để xác lập những dối tượng banđầu, còn quy tắc khác dùng để xác dịnh những đối tượng người dùng tiếp theo nhờ những đốitượng khởi đầu đã dược xác lập. = 2 – ^ ị + 3 với mọi n > 1. Khi dó ta có thê xác dịnh được số hạng an tống quát của dãysô trẽn như sau : Ví dụ 1 : Một dãy số a0, a, , a2 ….. a „, … có đặc thù : an = 0, Trước hết chọn những số ơị, a -, sao cho ( an – a, ) = a 2 ( an_ | – a, ) Từ ( 1 ) suy ra an = a, a n ^ I – a !. a 9 + a I.Rõ ràng những số a I, a 2 phái thoá mãn hệ phương trình ( 1 ) TOÁN RỜI RẠC ỨNG DUNG TRONG TIN HOC20 | « 2 = 2 Ịa, – a ,. a 2 = 3T ừ hệ trên ta có ngay ơ | = – 3, a 2 = 2. Đặt qn = an – otị với n > 1. Suy raqn = a 2. qn_ | với n > 1 và q ! = 6, từ đó ta có qn = qj. a ^ – 1. Vậy a „ – aj = qj. aỊỊ-1, suy ra an = a, + qi. a ” “ 1 = 6.2 n 1 – 3. Chương trình con đệ quy để tính sô ‘ hạng tổng quát an được minh hoạnhư sau : Function fn ( n : integer ) : integer ; BIGINif n = 0 then fn : = 0 else fn : = 2 * fn ( n-1 ) + 3 ; END ; Ví dụ 2 : Một dãy a0, d ị, a2, …. an, … có đặc thù : aQ = 0, d ị = 1, an = an_j + an_2 với mọi n > 2, dược gọi là dãy Fibonacci. Như vậy, dãyFibonacci là dãy : 0, 1, 1, 2, 3, 5, 8, 13, 21, … và với n > 2 ta hoàn toàn có thể tìm đượcsố Fibonacci thứ n nếu biết sô ‘ Fibonacci thứ n – 1 và thứ n – 2. Bàng quynạp toán học ta thuận tiện chứng tỏ được rằng, với n > 01 í 1 + a ” = ^ l > / 5J : j5ịi-s íĩ ) Tuy nhiên công thức trên có thê tính trực tiếp như sau : Trước hết hãy tìm một cặp sô ‘ ( X |, ct2 sao cho : a n – c t i V, = a 2 ( an_ 1 – a, a n_2 ) => an = ( a, + a 2 ) an_1 – a, a 2 an_2Rõ ràng những cặp sô ‘ CX |, a 2 thoả mãn hệ phương trìnhơị + a 2 = 1 a, a 2 = – lKhi đó CX |, a 2 sẽ là nghiêm của phương trình X2 – X – 1 = 0, do dó tacóthê chọnCX | =, a2 = – —. Đặt qnqn = a 2 qn – i với n > 2 và q, = 1. Ta có q n = a 2 – 1. anơ ị a n „ |, khi dó21Phán l. KIÊN THỨC Bổ TRỢIn_, = a n2, suy ra an = a ^ – 1 + « ra2 = a ^ ! + a 2 ( 1 ) a3 — a | a 2 + a 2 ( 2 ) a4 = a, a 2 + a 2 ( 3 ) an-l = aiV-2 + a 2 ~ 2 ( n – 2 ) ^ = « 1 ^ – 1 + « r 1 ( n – 1 ) Khi nhân hai vế của đẳng thức ( n – 2 ) vớiCX |, đầng thức ( n – 3 ) vớia 2, … đảng thức ( 1 ) với a ” – 2 và cộng lại theo từng vế ta có : t ” ‘ aịvạy an =. n-21 + \ Í54 ~ 5 a2T … + 1 ( 1-4541 ln-32 _ỌỊĨaia, – a 2 với n > 2. Tuy nhiên côngthức này cũng đúng với n > 0. Chương trình con để tính sô ‘ hạng tổng quát thứ n hoàn toàn có thể được viết như sau : Function fn ( n : integer ) : integer ; BEGINif n < = 1 then fn : = nelse fn : = fn ( n - 1 ) + fn ( n - 2 ) ; END ; Ví dụ 3 : Có m phần thường được chia cho n học viên giỏi được xếphạng từ 1, 2, .... n. Hỏi rằng có bao nhiêu cách chia phần thướng trên sao chocác điểu kiện sau dược thoả mãn : a ) Nếu học viên A giỏi hơn học viên B thì sô ' phần thưởng của A sẽ lớnhơn hoặc bằng sô ' phần thướng của B ; b ) Tất cả m phần thướng đểu phải thướng hết cho học viên. Giả sứ rằng với i < j và 1 < i, j < n thì học viên thứ i giỏi hơn học sinhthứ j. Ký hiệu sổ phần thướng mà học viên thứ i nhận dược là Tị. Từ giả thiếtcủa bài toán ta suy ra những diều kiện sau cần dược thoả mãn : Tị + T2 + ... + Tn = m ; T | > T2 > … > Tn > 0. TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC22Ký hiệu CHIA ( m, n ) là sô ‘ cách chia m phần thướng cho n học viên theoycu cầu trên. Nhận xét ràng : – Khi m = 0, tức là không có phần thưởng nào thì khi dó rõ ràng chí códuy nhất một cách chia : mỗi học viên dược 0 phần thướng. Vậy CH1A ( 0, n ) = 1 dối với mọi n. – Khi có m phần thướng và không có học viên giỏi, đưorng nhiên sẽkhông có cách chia nào. Vậy CHIA ( m, 0 ) = 0 so với mọi m * 0. – Khi có m phần thướng, n học viên giỏi và m < n, khi đó n - m họcsinh phía cuối sẽ không nhận dược phần thướng nào, do đó : CHIA ( m, n ) = CHIA ( m, m ) khi m < n. - Khi có m phần thưởng, n học viên giỏi và m > n. Khi đó ta xét haitrường hợp sau : + Khi học viên ở đầu cuối không nhận được phần thướng nào, khi đó sốcách chia sẽ là CHIA ( m, n – 1 ) ; + Khi học viên ở đầu cuối nhận dược 1 phần thướng, khi đó tất cá cáchọc sinh giỏi sẽ nhận được tối thiểu 1 phần thưởng, do đó số cách chia trongtrường hợp này sẽ là CHIA ( m – n, n ). Tóm lại, khi có m phần thướng và n học viên giỏi thì số cách chia sẽ làCHIA ( m, n – 1 ) + CHIA ( m – n, n ). Trên cơ sớ dó ra có thê viết một chương trình con đệ quy thế hiện thuậttoán trên như sau : Function CHIA ( m, n : integer ) : integer ; BEGINif m = 0 then CHIA : = 1 else if n = 0 then CHIA : = CHIA ( m, m ) else CHIA : = CHIA ( m, n – 1 ) + CHIA ( m – n, n ) END ; Thuật toán quay luiBài toán : Hãy kiến thiết xây dựng những bộ giá trị gồm có n thành phấn ( X |, x2, …, xn ) từ một tập hữu hạn cho trước, sao cho những bộ đó thoả mãn một nhu yếu B chotrước nào đó. Phấn /. KIỂN THỨC Bổ TRƠ23Phương pháp : Xây dựng những thành phần Xị, x2, x n theo cách sau đây : Giả sử đã xác lập được k – 1 thành phần tiên phong cúa dãy đó là X |, x2, xk |. Cần xác dịnh tiếp phần tứ xk, thành phần này được xác lập theo cách sau : Giả sử Tk là tập tổng thể những giá trị mà phần tứ xk hoàn toàn có thể nhận dược. Vì tậpTk là hữu hạn nên có thế đặt nk là số phần tứ của tập Tk. Khi đó có thế liệt kêcác phẩn tử của Tk theo một thứ tự nào đó. Tức là hoàn toàn có thể xây dựng một ánhxạ 1 – 1 từ tập Tk lên tập { 1, 2, …, nk }. – Nếu k = n, khi đó bộ ( X |, x2, xk_ị, xk ) có đủ n thành phần và thoảmãn nhu yếu dặt ra, do dó bộ này được đưa vào quan hệ hiệu quả. Xét j e 11, 2, …. nkỊ, ta nói rằng ” j gật đầu được ” nếu có thế bổ sungphần tứ thứ j trong Tk với tư cách là thành phần xk vào dãy X ), x2, …, xk_ị, xk. – Nếu k < n ta cần phái triển khai tiếp quy trình trên, tức là phải bổ sungtiếp phẩn tử xk + 1 vào dãy Xị, x2, ..., xk_ | để được dãy Xị, x2, ..., xk_ |, xk. Như vậy, nét đặc trưng của giải pháp quay lui là ớ chỗ có được lờigiải ta phái đi từng bước bằng phép thử. Khi một bước lựa chọn chấp nhậncần ghi nhớ thông tin thiết yếu và triển khai bước tiếp theo. trái lại, khikhông có một lựa chọn nào được gật đầu thì cần phải thực thi lại bướctrước, xoá bớt ghi nhớ và thứ lại với những lựa chọn còn lại. a ) Thủ tục đệ quy cho thuật toán quay luiProcedure THU ( k : interger ) ; Var j : interger ; BEGINfor j : = 1 to nk doif

5/5 - (1 vote)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments