Bài giảng Toán rời rạc 1

119 trang huongle 6950

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 1", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_toan_roi_rac_1.pdf

Nội dung text: Bài giảng Toán rời rạc 1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG  KHOA CÔNG NGHỆ THÔNG TIN 1 BÀI GIẢNG TOÁN RỜI RẠC 1 PTIT Hà Nội 2013
LỜI GIỚI THIỆU Toán rời rạc là lĩnh vực nghiên cứu và xử lý các đối tượng rời rạc. Toán rời rạc dùng để đếm, quan sát, và xử lý mối quan hệ giữa các đối tượng trong các tập hợp khác nhau. Bản chất tính toán trên máy tính là rời rạc. Chính vì vậy, toán học rời rạc được xem là môn học kinh điển cho sinh viên các ngành Công nghệ thông tin và Điện tử Viễn thông. Tài liệu hướng dẫn môn học toán học rời rạc được xây dựng dựa trên cơ sở kinh nghiệm giảng dạy môn học và kế thừa những nội dung từ giáo trình “Toán học rời rạc ứng dụng trong tin học” của Kenneth Rossen. Tài liệu được trình bày thành hai phần: Lý thuyết tổ hợp (Toán rời rạc 1) và Lý thuyết đồ thị (Toán rời rạc 2). Phần I trình bày những kiến thức cơ bản về lý thuyết tổ hợp thông qua việc giải quyết bốn bài toán cơ bản đó là: Bài toán đếm, Bài toán tồn tại, Bài toán liệt kê và Bài toán tối ưu. Phần II trình bày những kiến thức cơ bản về Lý thuyết đồ thị: khái niệm, định nghĩa, các thuật toán trên đồ thị, đồ thị Euler, đồ thị Hamilton. Một số bài toán có ứng dụng thực tiễn quan trọng khác của lý thuyết đồ thị cũng được chú trọng giải quyết đó là Bài toán tô màu đồ thị, Bài toán tìm đường đi ngắn nhất và Bài toán luồng cực đại trong mạng. Trong mỗi phần của tài liệu, chúng tôi cố gắng trình bày ngắn gọn trực tiếp vào bản chất của vấn đề. Các thuật toán được trình bày và cài bằng ngôn ngữ lập trình C++. Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu không tránh khỏi những thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả đọc giả và các bạn đồng nghiệp. Hà nội, tháng 10 năm 2013 PTIT 2
MỤC LỤC CHƯƠNG 1. LOGIC, TẬP HỢP VÀ ỨNG DỤNG 5 1.1. Giới thiệu chung 5 1.2. Những kiến thức cơ bản về Logic mệnh đề 6 1.2.1. Định nghĩa & phép toán 6 1.2.2. Sự tương đương giữa các mệnh đề 7 1.2.3. Dạng chuẩn tắc 9 1.3. Vị từ và lượng từ 10 1.4. Một số ứng dụng trên máy tính 12 1.5. Những kiến thức cơ bản về lý thuyết tập hợp 15 1.5.1. Khái niệm & định nghĩa 15 1.5.2. Các phép toán trên tập hợp 16 1.5.3. Các hằng đẳng thức trên tập hợp 17 1.6. Biểu diễn tập hợp trên máy tính 18 1.7. Những nội dung cần ghi nhớ 19 BÀI TẬP CHƯƠNG 1 19 CHƯƠNG 2. BÀI TOÁN ĐẾM 21 2.1. Những nguyên lý đếm cơ bản 21 2.1.1. Nguyên lý cộng 21 2.1.2. Nguyên lý nhân 22 2.2. Nguyên lý bù trừ 24 2.3. Đếm các hoán vị và tổ hợp 27 2.3.1. Chỉnh hợp lặp 27 2.3.2. Chỉnh hợp không lặp 27 2.3.3. Hoán vị 28 2.3.4. Tổ hợp 28 2.3.5. Tổ hợp lặp PTIT 30 2.4. Hệ thức truy hồi 31 2.4.1. Định nghĩa và ví dụ 31 2.4.2. Giải công thức truy hồi tuyến tính thuần nhất với hệ số hằng số 34 2.5. Qui về các bài toán đơn giản 38 2.6. Phương pháp liệt kê 40 BÀI TẬP CHƯƠNG 2 43 CHƯƠNG 3. BÀI TOÁN LIỆT KÊ 45 3.1- Giới thiệu bài toán 45 3.2. Thuật toán và độ phức tạp tính toán 46 3.2.1. Ví dụ và Định nghĩa 46 3
3.2.2. Phương pháp biểu diễn thuật toán: 46 3.2.3. Độ phức tạp tính toán 48 3.2.4. Qui tắc xác định độ phức tạp thuật toán 51 3.3. Phương pháp sinh 52 3.4. Thuật toán quay lui (Back track) 63 3.5. Những nội dung cần ghi nhớ 69 BÀI TẬP CHƯƠNG 3 70 CHƯƠNG 4. BÀI TOÁN TỐI ƯU 73 4.1. Giới thiệu bài toán 73 4.2. Phương pháp duyệt toàn bộ 76 4.3. Thuật toán nhánh cận 79 4.4. Kỹ thuật rút gọn giải quyết bài toán người du lịch 90 4.4.1.Thủ tục rút gọn 91 4.4.2.Thủ tục chọn cạnh phân nhánh (r,c) 94 4.4.3.Thuật toán nhánh cận giải bài toán người du lịch 99 4.5. Những điểm cần ghi nhớ 100 BÀI TẬP CHƯƠNG 4 100 CHƯƠNG 5. BÀI TOÁN TỒN TẠI 103 4.1. Giới thiệu bài toán 103 5.2. Phương pháp phản chứng 106 5.3 Nguyên lý Dirichlet 107 5.4. Những nội dung cần ghi nhớ 108 BÀI TẬP 109 PTIT 4
CHƯƠNG 1. LOGIC, TẬP HỢP VÀ ỨNG DỤNG Nội dung chính của chương này đề cập đến những kiến thức cơ bản về logic mệnh đề, lý thuyết tập hợp và ứng dụng. Nội dung chính của chương bao gồm:  Logic mệnh đề và ứng dụng.  Logic vị từ và ứng dụng.  Lý thuyết tập hợp và ứng dụng.  Một số ứng dụng của logic và tập hợp trong tin học.  Bài tập chương 1. Bạn đọc có thể tìm thấy những kiến thức sâu hơn và chi tiết hơn trong các tài liệu [1] và [2] của tài liệu tham khảo. 1.1. Giới thiệu chung Tổ hợp là một lĩnh vực quan trọng của toán học rời rạc đề cập tới nhiều vấn đề khác nhau của toán học. Lý thuyết Tổ hợp nghiên cứu việc phân bố các phần tử vào các tập hợp. Thông thường các phần tử của tập hợp là hữu hạn và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó tuỳ theo yêu cầu của bài toán. Mỗi cách phân bố được coi là một “cấu hình của tổ hợp”. Các cấu hình tổ hợp được xem xét như một lời giải của bài toán đếm, bài toán liệt kê, bài toán tồn tại hay bài toán tối ưu. Bài toán đếm: đây là dạng bài toán nhằm trả lời câu hỏi “có bao nhiêu cấu hình thoả mãn điều kiện đã nêu?”. Bài toán đếm được áp dụng có hiệu quả vào những công việc mang tính chất đánh giá như xác suất xảy ra của một sự kiện, thời gian tính toán hay độ phức tạp của một chương trình máy tính. Bài toán liệt kê: bài toánPTIT liệt kê quan tâm đến tất cả các cấu hình có thể có được, vì vậy lời giải của nó được biểu diễn dưới dạng thuật toán “vét cạn” tất cả các cấu hình. Bài toán liệt kê thường được làm nền cho nhiều bài toán khác. Hiện nay, một số bài toán tồn tại, bài toán tối ưu, bài toán đếm vẫn chưa có cách nào giải quyết ngoài phương pháp liệt kê. Phương pháp liệt kê càng trở nên quan trọng hơn khi nó được hỗ trợ bởi các hệ thống máy tính. Bài toán tối ưu: khác với bài toán liệt kê, bài toán tối ưu chỉ quan tâm tới cấu hình “tốt nhất” theo một nghĩa nào đó. Đây là một bài toán có nhiều ứng dụng thực tiễn được giải quyết bằng lý thuyết tổ hợp. Bài toán tồn tại: nếu như bài toán đếm thực hiện đếm bao nhiêu cấu hình có thể có, bài toán liệt kê xem xét tất cả các cấu hình có thể có, bài toán tối ưu chỉ ra một cấu hình tốt nhất. Bài toán tồn tại hướng đến giải quyết những vấn đề còn nghi vấn. Điều này 5
có nghĩa là ngay kể cả vấn đề có hay không một cấu hình cũng chưa biết. Những bài toán này thường là những bài toán khó. Do vậy máy tính được xem là công cụ hữu hiệu nhất giải quyết bài toán tồn tại. 1.2. Những kiến thức cơ bản về Logic mệnh đề Các qui tắc cơ bản của Logic cho ta ý nghĩa chính xác của các mệnh đề. Những qui tắc của logic chính là công cụ cơ sở để chúng ta có thể xây dựng nên các ngôn ngữ lập trình, các bảng mạch máy tính, kiểm chứng tính đúng đắn của chương trình và nhiều ứng dụng quan trọng khác. 1.2.1. Định nghĩa & phép toán Đối tượng nghiên cứu của logic là các mệnh đề. Một mệnh đề được hiểu là một câu khẳng định hoặc đúng hoặc sai chứ không thể vừa đúng vừa sai. Ví dụ: Những câu khẳng định sau đây là một mệnh đề: “Hà nội là thủ đô của Việt nam.” 1 + 1 = 2 2 + 2 = 3 Các mệnh đề “ Hà nội là thủ đô của việt nam”, “ 1 +1 =2 “ là những mệnh đề đúng, mệnh đề “2 +2 =3” là sai. Nhưng những câu trong ví dụ sau sẽ không phải là một mệnh đề vì nó những câu đó không cho ta khẳng định đúng cũng chẳng cho ta khẳng định sai. “Bây giờ là mấy giờ ?” “Hãy suy nghĩ điều này cho kỹ lưỡng” x +1 =2 x + y = z Ta ký hiệu những chữ cáiPTIT A, B, C, D, p, q, r, s . . . là những mệnh đề. Giá trị của một mệnh đề đúng được ký hiệu là T, giá trị mệnh đề sai được ký hiệu là F. Tập giá trị T, F còn được gọi là giá trị chân lý của một mệnh đề. Định nghĩa 1. Cho p là một mệnh đề. Phép phủ định mệnh đề p cũng là một mệnh đề (ký hiệu là p hoặc p). Mệnh đề p có giá trị F khi và chỉ khi mệnh đề p nhận giá trị T, nhận giá trị F khi và chỉ khi p nhận giá trị T. Định nghĩa 2. Cho p và q là hai mệnh đề. Phép hội giữa mệnh đề p với mệnh đề q là một mệnh đề (ký hiệu p  q ). Mệnh đề p  q có giá trị T khi và chỉ khi p, q nhận giá trị T, có giá trị F khi và chỉ khi hoặc p, q, hoặc cả hai nhận giá trị F. 6
Định nghĩa 3. Cho p và q là hai mệnh đề. Phép tuyển giữa mệnh đề p với mệnh đề q là một mệnh đề (ký hiệu p p). Mệnh đề p p có giá trị T khi và chỉ khi ít nhất một trong hai mệnh đề p, q nhận giá trị T, có giá trị F khi và chỉ khi cả p, q đều nhận giá trị F. Định nghĩa 4. Cho p và q là hai mệnh đề. Phép tuyển loại giữa mệnh p với mệnh đề q (được ký hiệu là pq) là một mệnh đề. Mệnh đề pq chỉ đúng khi một trong p hoặc q đúng và sai trong các trường hợp khác còn lại. Định nghĩa 5. Cho p và q là hai mệnh đề. Phép kéo theo giữa mệnh đề p với mệnh đề q (ký hiệu p q) là một mệnh đề. Mệnh đề p q nhận giá T khi và chỉ khi p và q nhận giá trị F hoặc p và q cùng nhận giá trị T. Mệnh đề p q nhận giá trị F khi và chỉ khi p nhận giá trị T và q nhận giá trị F. Định nghĩa 6. Cho p và q là hai mệnh đề. Phép tương đương giữa mệnh đề p với mệnh đề q là một mệnh đề (ký hiệu p  q). Mệnh đề p  q có giá trị đúng khi p và q có cùng giá trị chân lý và sai trong các trường hợp khác còn lại. Các phép toán : , , , , ,  có thể được định nghĩa thông qua bảng giá trị chân lý sau: Bảng 1.1: Bảng giá trị chân lý của các phép toán , , , , ,  p q p pq pq pq p q p q T T F T T F T T T F F F T T F F F T T F T T T F F F T F F F T T 1.2.2. Sự tương đương giữa PTITcác mệnh đề Một vấn đề hết sức quan trọng trong lập luận toán học là việc thay thế một mệnh đề bằng một mệnh đề khác có cùng giá trị chân lý. Hai mệnh đề có cùng một giá trị chân lý chúng ta có thể hiểu theo cách thông thường là chúng tương đương nhau về ngữ nghĩa. Do vậy, ta sẽ tiếp cận và phân loại các mệnh đề phức hợp thông qua các giá trị chân lý của chúng. Định nghĩa 7. Một mệnh đề phức hợp luôn luôn đúng với bất kể các giá trị chân lý của các mệnh đề thành phần được gọi là hằng đúng (tautology). Một mệnh đề luôn luôn sai với mọi giá trị chân lý của các mệnh đề thành phần được gọi là mâu thuẫn. Ví dụ: mệnh đề phức hợp p  p là hằng đúng, p  p là mâu thuẫn vì giá trị chân lý của các mệnh đề trên luôn luôn đúng, hoặc luôn luôn sai như được chỉ ra trong bảng 1.2. 7
Bảng 1.2. Ví dụ về mệnh đề hằng đúng & mệnh đề mâu thuẫn p p p  p p p T F T F F T T F Định nghĩa 8. Hai mệnh đề p, q được gọi là tương đương logic với nhau (ký hiệu : p q, hoặc p  q , hoặc p=q) khi và chỉ khi các cột cho giá trị chân lý của chúng giống nhau. Hay mệnh đề pq là hằng đúng. Ví dụ 1. Hai mệnh đề p  q và p  q là tương đương logic vì các cột giá trị chân lý của chúng được thể hiện qua bảng sau: Bảng 1.3. Bảng giá trị chân lý đối với p  q và p  q p q pq p  q p q p  q T T T F F F F T F T F F T F F T T F T F F F F F T T T T Dùng bảng giá trị chân lý để chứng minh tính tương đương logic giữa hai mệnh đề phức hợp cho ta một phương pháp trực quan dễ hiểu. Tuy nhiên, với những mệnh đề logic phức hợp có k mệnh đề thành phần thì cần tới 2k tổ hợp các bộ giá trị chân lý khác nhau. Do đó, dùng bảng chân lý để chứng minh tính tương đương logic giữa hai mệnh đề phức hợp gặp nhiều khó khăn. Trong trường hợp này ta có thể chứng minh tính tương logic bằng việc thay thế một mệnh đề phức hợp bằng những tương đương logic có trước. Bằng phương pháp bảng chân lý, dễ dàng chứng minh được sự tương đương của các công thức dưới đây: PTIT p q p  q pq (p q)(q p) p p Bảng 1.4. Bảng các tương đương logic TƯƠNG ĐƯƠNG TÊN GỌI p  T p Luật đồng nhất 8
p  F p p  T T Luật nuốt p  F F p  p p Luật luỹ đẳng p  p p p p Luật phủ định kép p  q q  p Luật giao hoán p  q q  p (p  q)  r p  ( q  r) Luật kết hợp (p  q)  r p ( q  r) p  ( q  r) (p  q )  (p  r) Luật phân phối p  ( q  r) (p  q)  (p  r) p  q p  q Luật De Morgan p  q p  q Ví dụ: Chứng minh p  p  q p  q ? Chứng minh: p  p  q p  p  q p  p  q   theo luật De Morgan thứ 2 p  p  q   theo luật De Morgan thứ 2 p  PTITp  p  q theo luật phủ định kép F  p  q theo luật phân phối p  q  F tương đương tiện ích p  q Điều cần chứng minh. 1.2.3. Dạng chuẩn tắc Các công thức (mệnh đề) tương đương được xem như các biểu diễn khác nhau của cùng một mệnh đề. Để dễ dàng viết các chương trình máy tính thao tác trên các công thức, chúng ta cần chuẩn hóa các công thức, đưa chúng về dạng biểu diễn chuẩn được gọi là dạng chuẩn hội. Một công thức được gọi là ở dạng chuẩn hội nếu nó là hội của các 9
mệnh đề tuyển. Phương pháp để biến đổi một công thức bất kỳ về dạng chuẩn hội bằng cách áp dụng các thủ tục sau:  Bỏ các phép kéo theo ( ) bằng cách thay (p q) bởi p  q .  Chuyển các phép phủ định ( ) vào sát các ký hiệu mệnh đề bằng cách áp dụng luật De Morgan và thay p bởi p.  Áp dụng luật phân phối thay các công thức có dạng (p(qr)) bởi (pq)(pr). Ví dụ. Ta chuẩn hóa công thức p q  r  s . Lời giải. p q  r  s p  q  r  s p  q  r  s p  q  r  s p  q  r  p  q  s Như vậy công thức p q  r  s được đưa về dạng chuẩn hội là p  q  r  p  q  s . 1.3. Vị từ và lượng từ Trong toán học hay trong các chương trình máy tính chúng ta rất hay gặp những khẳng định chưa phải là một mệnh đề. Những khẳng định đó đều có liên quan đến các biến. Chẳng hạn khẳng đinh: P(x) = “x > 3” không phải là một mệnh đề nhưng tại những giá trị cụ thể của x=x0 nào đó thì P(x0) lại là một mệnhPTIT đề. Hoặc trong những đoạn chương trình gặp câu lệnh: if ( x > 3 ) then x:= x +1; thì chương trình sẽ đặt giá trị cụ thể của biến x vào P(x), nếu mệnh đề P(x) cho giá trị đúng x sẽ được tăng lên 1 bởi câu lệnh x:=x+1, P(x) có giá trị sai giá trị của x được giữ nguyên sau khi thực hiện câu lệnh if. Chúng ta có thể phân tích mỗi khẳng định thành hai phần chủ ngữ và vị ngữ (hay vị từ), trong câu “ x lớn hơn 3” thì x là chủ ngữ, “ lớn hơn 3” là vị ngữ. Hàm P(x) được gọi là hàm mệnh đề. Một hàm mệnh đề có thể có một hoặc nhiều biến. Giá trị chân lý của hàm mệnh đề tại những giá trị cụ thể của biến được xác định như những mệnh đề thông thường. Ví dụ. Cho Q(x, y, z) là hàm mệnh đề xác định câu x2 = y2 +z2 hãy xác định giá trị chân lý của các mệnh đề Q (3, 2, 1), Q ( 5, 4, 3)? 10
Lời giải. Đặt giá trị cụ thể của x , y , z vào Q(x,y,z) ta có : Q(3,2,1) là mệnh đề “32 = 22 + 12” là sai do đó Q(3,2,1) là mệnh đề sai. Trong đó, Q (5, 4, 3) là mệnh đề “ 52 = 42 + 32” là mệnh đề đúng. Tổng quát, giả sử M là một tập hợp các phần tử nào đó. M thường được gọi là trường hay miền xác định của các phẩn tử thuộc M. Khi đó, biểu thức P(x) gọi là vị từ xác định trên trường M nếu khi thay x bởi một phần tử bất kỳ của trường M thì P(x) sẽ trở thành một mệnh đề trên trường M. Khi tất cả các biến của hàm mệnh đề đều được gán những giá trị cụ thể, thì mệnh đề tạo ra sẽ xác định giá trị chân lý. Tuy nhiên, có một phương pháp quan trọng khác để biến một hàm mệnh đề thành một mệnh đề mà không cần phải kiểm chứng mọi giá trị chân lý của hàm mệnh đề tương ứng với các giá trị của biến thuộc trường đang xét. Phương pháp đó gọi là sự lượng hoá hay lượng từ. Chúng ta xét hai lượng từ quan trọng là lượng từ với mọi (ký hiệu :), lượng từ tồn tại (ký hiệu : ). Định nghĩa 1. Lượng từ với mọi của P(x) ký hiệu là x P(x) là một mệnh đề “ P(x) đúng với mọi phần tử x thuộc trường đang xét”. Ví dụ. Cho hàm mệnh đề P(x) = x2 + x + 41 là nguyên tố. Xác định giá trị chân lý của mệnh đề  P(x) với x thuộc không gian bao gồm các số tự nhiên [0 39]. Lời giải. Vì P(x) đúng với mọi giá trị của x [0 39]  P(x) là đúng. Ví dụ : Cho P(x) là hàm mệnh đề “ x + 1 > x”. Xác định giá trị chân lý của mệnh đề  x P(x), trong không gian các số thực. Lời giải : Vì P(x) đúng với mọi số thực x nên x P(x) là đúng. Định nghĩa 2. Lượng từ tồn tại của hàm mệnh đề P(x) (được ký hiệu là: x P(x) ) là một mệnh đề “ Tồn tại một phần tử x trong không gian sao cho P(x) là đúng “. Ví dụ: Cho P(x) là hàm mệnh đề “x > 3”. Hãy tìm giá trị chân lý của mệnh đề  x P(x) trong không gian các số thực.PTIT Lời giải: Vì P(4) là “ 4 > 3” đúng nên  x P(x) là đúng. Ví dụ: Cho Q(x) là “ x + 1 > x”. Hãy tìm giá trị chân lý của mệnh đề  x Q(x) trong không gian các số thực. Lời giải: vì Q(x) sai với mọi x R nên mệnh đề  x Q(x) là sai. Bảng 1.5: Giá trị chân lý của lượng từ ,  x P(x) P(x) đúng với mọi x Có một giá trị của x để P(x) sai x P(x) Có một giá trị của x để P(x) đúng P(x) sai với mọi x 11
Dịch những câu thông thường thành biểu thức logic: Dịch một câu được phát biểu bằng ngôn ngữ tự nhiên (câu hỏi thông thường) thành một biểu thức logic có vai trò hết sức quan trọng trong xây dựng các ngôn ngữ lập trình, chương trình dịch và xử lý ngôn ngữ tự nhiên. Quá trình dịch một câu từ ngôn ngữ tự nhiên thành một biểu thức sẽ làm mất đi tính tự nhiên của ngôn ngữ vì đa số các ngôn ngữ đều không rõ ràng, nhưng một biểu thức logic lại rất rõ ràng chặt chẽ từ cú pháp thể hiện đến ngữ nghĩa của câu. Điều này dẫn đến phải có một tập hợp các giả thiết hợp lý dựa trên một hàm xác định ngữ nghĩa cuả câu đó. Một khi câu đã được chuyển dịch thành biểu thức logic, chúng ta có thể xác định được giá trị chân lý của biểu thức logic, thao tác trên biểu thức logic, biến đổi tương đương trên biểu thức logic. Chúng ta sẽ minh hoạ việc dịch một câu thông thường thành biểu thức logic thông qua những sau. Ví dụ dịch câu “Bạn không được lái xe máy nếu bạn cao dưới 1.5 mét trừ phi bạn trên 18 tuổi” thành biểu thức logic. Lời giải. Ta gọi p là câu : Bạn được lái xe máy. q là câu : Bạn cao dưới 1.5m. r là câu : Bạn trên 18 tuổi. Khi đó: Câu hỏi trên được dịch là: (q  r ) p Ví dụ: Dịch câu “ Tất cả các sinh viên học tin học đều học môn toán học rời rạc” Lời giải: Gọi P(x) là câu “x cần học môn toán học rời rạc” và x được xác định trong không gian của các sinh viên học tin học. Khi đó chúng ta có thể phát biểu:x P(x). Ví dụ: Dịch câu “Có một sinh viên ở lớp này ít nhất đã ở tất cả các phòng của ít nhất một nhà trong ký túc xá”. Lời giải : Gọi tập sinh viên trong lớp là không gian xác định sinh viên x, tập các nhà trong ký túc xá là không gian xác định căn nhà y, tập các phòng là không gian xác định phòng z. Ta gọi P(z,y) là “ z thuộc y”, Q(x,z) là “ x đã ở z”. Khi đó ta có thể phát biểu : PTIT  x  y  z (P(z,y) Q(x,z)); 1.4. Một số ứng dụng trên máy tính Các phép toán bít: Các hệ thống máy tính thường dùng các bit (binary digit) để biểu diễn thông tin. Một bít có hai giá trị chân lý hoặc 0 hoặc 1. Vì giá trị chân lý của một biểu thức logic cũng có hai giá trị hoặc đúng (T) hoặc sai (F). Nếu ta coi giá trị đúng có giá trị 1 và giá trị sai là 0 thì các phép toán với các bít trong máy tính được tương ứng với các liên từ logic. 12
Một xâu bít (hoặc xâu nhị phân) là dãy không hoặc nhiều bít. Chiều dài của xâu là số các bít trong xâu đó. Ví dụ xâu nhị 101010011 có độ dài là 9. Một số nguyên đuợc biểu diễn như một xâu nhị phân có độ dài 16 bít. Các phép toán với bít được xây dựng trên các xâu bít có cùng độ dài, bao gồm : AND bít (phép và cấp bít), OR (phép hoặc cấp bít), XOR (phép tuyển loại trừ cấp bít). Ví dụ: cho hai xâu bít 01101 10110 và 11000 11101 hãy tìm xâu AND bít, OR bít, XOR bít. Bảng 1.5. Các phép toán cấp bít ứng dụng trong ngôn ngữ LT Giá trị của A Giá trị của B A and B A or B A xor B A = 13 =1100 B = 8=1000 1000 1101 0101 Thuật toán các phép tính số nguyên: Các thuật toán thực hiện các phép tính với các số nguyên khi dùng khai triển nhị phân là hết sức quan trọng trong bộ xử lý số học của máy tính. Như chúng ta đã biết, thực chất các số nguyên được biểu diễn trong máy tính là các xâu bít nhị phân, do vậy chúng ta có thể sử dụng biểu diễn nhị phân của các số để thực hiện các phép tính. Giả sử khai triển nhị phân của các số nguyên a và b tương ứng là: a = (an-1an-2 . . .a1a0)2 , b = (bn-1bn-2 . . .b1b0)2 . Khai triển của a và b có đúng n bít ( chấp nhận những bít 0 ở đầu để làm đặc n bít). Xét bài toán cộng hai số nguyên viết ở dạng nhị phân. Thủ tục thực hiện việc cộng cũng giống như làm trên giấy thông thường. Phương pháp này tiến hành bằng cách cộng các bít nhị phân tương ứng có nhớ để tính tổng hai số nguyên. Sau đây là mô tả chi tiết cho quá trình cộng hai xâu bít nhị phân. Để cộng a với b, trước hết ta cộng hai bít phải nhất, nghĩa là: a0 + b0 = c0*2 + s0; trong đó s0 là bít phải nhất của số nguyên tổng a + b, c0 là số cần để nhớ nó có thể bằng 0 hoặc 1. Sau đó ta cộng hai bít tiếp theo và số nhớ: a1 + b1 + c0 = c1*2 + s1; s1 là bít tiếp theo của số a + b, c1 là số nhớ. Tiếp tục quá trình này bằng cách cộng các bít tương ứng trong khai triển nhị phân và số nhớ, ở giai đoạn cuối cùng : an-1 + bn-1 + cnPTIT-2 = cn-1 * 2 + sn-1. Bít cuối cùng của tổng là cn-1. Khi đó khai triển nhị phân của tổng a + b là (snan-1 . . .s1s0)2. Ví dụ: cộng a =(1110)2, b = (1011)2 Lời giải: Trước hết lấy: a0 + b0 = 0 + 1 = 0 * 2 + 1 c0=0, s0 = 1 Tiếp tục: a1 + b1 + c0 = 1 + 1 + 0 = 1 * 2 + 0 c1=1, s1 = 0 a2 + b2 + c1 = 1 + 0 + 1 = 1 * 2 + 0 c2=1, s2 = 0 13
a3 + b3 + c2 = 1 + 1 + 1 = 1 * 2 + 1 c3=1, s3 = 1 Cuối cùng: s4 = c3 = 1 a + b = (11001)2 Thuật toán cộng: void Cong(a , b: positive integer) { /*a = (an-1an-2 . . .a1a0)2 , b = (bn-1bn-2 . . .b1b0)2 */ c=0; for (j=0 ; j n-1; j++) { d= [( aj + bj + c)/ 2]; sj = aj + bj + c – 2d; c = d; } sn = c; khai triển nhị phân của tổng là (snan-1 . . .s1s0)2; } Thuật toán nhân: Để nhân hai số nguyên n bít a, b ta bắt đầu từ việc phân tích: a = (an-1an-2. . .a1a0), b = (bn-1bn-2. . .b1b0) Ta có thể tính a.b từ phương trình trên. Trước hết, ta nhận thấy abj = a nếu bj=1, j abj=0 nếu bj=0. Mỗi lần tính ta nhân với 2 hay dịch chuyển sang trái j bít 0 bằng cách j thêm j bít 0 vào bên trái kết quả nhận được. Cuối cùng, cộng n số nguyên abj 2 (j=0 n-1) ta nhận được a.b. Ví dụ sau đây sẽ minh hoạ cho thuật toán nhân: Ví dụ: Tìm tích của a = (110)2, b= (101)2 Giải: Ta nhận thấy 0 0 ab02 = (110)2*1*2 = (110)2 1 1 ab12 = (110)2*0*2 = (0000)2 2 2 ab22 = (110)2*1*2 = (11000)PTIT2 Sử dụng thuật toán tính tổng hai số nguyên a, b có biểu diễn n bít ta nhận được(ta có thể thêm số 0 vào đầu mỗi toán hạng): (0 110)2 + (0000)2 = (0110)2 ; (0 0110)2 + (11000)2 = (11110)2 = ab. Thuật toán nhân hai số nguyên n bít có thể được mô phỏng như sau: void Nhan( a, b : Positive integer){ /* khai triển nhị phân tương ứng của a = (an-1an-2. . .a1a0), b = (bn-1bn-2. . .b1b0) */ for (j=0; j n-1; j++) { if ( ( bj==1) 14
j cj = a * 2 ; /* a được dịch trái j bít 0 */ else cj =0; } j /*c0, c1 , cn-1 là những tích riêng của abj 2 (j=0 n-1 */ p=0; for ( j=0 ; j n-1; j++) p= p + cj; /* p là giá trị của tích ab */ } 1.5. Những kiến thức cơ bản về lý thuyết tập hợp 1.5.1. Khái niệm & định nghĩa Các tập hợp dùng để nhóm các đối tượng lại với nhau. Thông thường, các đối tượng trong tập hợp có các tính chất tương tự nhau. Ví dụ, tất cả sinh viên mới nhập trường tạo nên một tập hợp, tất cả sinh viên thuộc khoa Công nghệ thông tin là một tập hợp, các số tự nhiên, các số thực cũng tạo nên các tập hợp. Chú ý rằng, thuật ngữ đối tượng được dùng ở đây không chỉ rõ cụ thể một đối tượng nào, sự mô tả một tập hợp nào đó hoàn toàn mang tính trực giác về các đối tượng. Định nghĩa 1. Tập các đối tượng trong một tập hợp được gọi là các phần tử của tập hợp. Các tập hợp thường được ký hiệu bởi những chữ cái in hoa đậm như A, B, X, Y . . ., các phần tử thuộc tập hợp hay được ký hiệu bởi các chữ cái in thường như a, b, c, u, v . . . Để chỉ a là phần tử của tập hợp A ta viết a A, trái lại nếu a không thuộc A ta viết a A. Tập hợp không chứa bất kỳ một phần tử nào được gọi là tập rỗng (ký hiệu là  hoặc { }). Tập hợp A được gọi là bằng tập hợp B khi và chỉ khi chúng có cùng chung các phần tử và được ký hiệu là A=B. Ví dụ tập A={ 1, 3, 5 } sẽ bằng tập B = { 3, 5, 1 }. Định nghĩa 2. Tập A được gọi là một tập con của tập hợp B và ký hiệu là AB khi và chỉ khi mỗi phần tử của A là mộtPTIT phần tử của B. Hay A  B khi và chỉ khi lượng từ  x (x A x B) cho ta giá trị đúng. Từ định nghĩa trên chúng ta rút ra một số hệ quả sau: Tập rỗng  là tập con của mọi tập hợp. Mọi tập hợp là tập con của chính nó. Nếu A B và B  A thì A=B hay mệnh đề : x (x A x B )   x (x B x A) cho ta giá trị đúng. Nếu A B và A B thì ta nói A là tập con thực sự của B và ký hiệu là AB. 15
Định nghĩa 3. Cho S là một tập hợp. Nếu S có chính xác n phần tử phân biệt trong S, với n là số nguyên không âm thì ta nói S là một tập hữu hạn và n được gọi là bản số của S. Bản số của S được ký hiệu là |S | hay N(S). Định nghĩa 4. Cho tập hợp S. Tập luỹ thừa của S ký hiệu là P(S) là tập tất cả các tập con của S. Ví dụ S = { 0, 1, 2 } P(S) ={ , {0}, {1}, {2}, {0,1}, {0, 2}, {1, 2} {0, 1, 2}}. Định nghĩa 5. Dãy sắp thứ tự (a1, a2, , an) là một tập hợp sắp thứ tự có a1 là phần tử thứ nhất, a2 là phần tử thứ 2, , an là phần tử thứ n. Chúng ta nói hai dãy sắp thứ tự là bằng nhau khi và chỉ khi các phần tử tương ứng của chúng là bằng nhau. Nói cách khác (a1, a2, , an) bằng (b1, b2, , bn) khi và chỉ khi ai = bi với mọi i =1, 2, n. Định nghĩa 6. Cho A và B là hai tập hợp. Tích đề các của A và B được ký hiệu là A B, là tập hợp của tất cả các cặp (a,b) với a A, b B. Hay có thể biểu diễn bằng biểu thức: A B = { (a, b) | a A, b B } Định nghĩa 7. Tích đề các của các tập A1, A2, . ., An được ký hiệu là A1 A2 An là tập hợp của dãy sắp thứ tự (a1, a2, , an) trong đó ai Ai với i = 1, 2, n. Nói cách khác: A1 A2 An = { (a1, a2, , an) | ai Ai với i = 1, 2, n } 1.5.2. Các phép toán trên tập hợp Các tập hợp có thể được tổ hợp với nhau theo nhiều cách khác nhau thông qua các phép toán trên tập hợp. Các phép toán trên tập hợp bao gồm: Phép hợp (Union), phép giao (Intersection), phép trừ (Minus). Định nghĩa 1. Cho A và B là hai tập hợp. Hợp của A và B được ký hiệu là AB, là tập chứa tất cả các phần tử hoặc thuộc tập hợp A hoặc thuộc tập hợp B. Nói cách khác: AB = { x | x A  x B } Định nghĩa 2. Cho A và B là hai tập hợp. Giao của A và B được ký hiệu là AB, là tập chứa tất cả các phần tử thuộc A PTITvà thuộc B. Nói cách khác: AB = { x | x A  x B } Định nghĩa 3. Hai tập hợp A và B được gọi là rời nhau nếu giao của chúng là tập rỗng (AB =  ). Định nghĩa 4. Cho A và B là hai tập hợp. Hiệu của A và B là tập hợp đuợc ký hiệu là A- B, có các phần tử thuộc tập hợp A nhưng không thuộc tập hợp B. Hiệu của A và B còn được gọi là phần bù của B đối với A. Nói cách khác: A – B = { x | x A  x B } Định nghĩa 5. Cho tập hợp A. Ta gọi A là phần bù của A là một tập hợp bao gồm những phần tử không thuộc A. 16
A x | x A Định nghĩa 6. Cho các tập hợp A1, A2, . ., An. Hợp của các tập hợp là tập hợp chứa tất cả các phần tử thuộc ít nhất một trong số các tập hợp Ai ( i=1, 2, . ., n). Ký hiệu: n  Α  Α  Α Αι 1 2 n i 1 Định nghĩa 7: Cho các tập hợp A1, A2, . ., An. Giao của các tập hợp là tập hợp chứa các phần tử thuộc tất cả n tập hợp Ai ( i=1, 2, . ., n). n  Ai A1 A2  An i 1 1.5.3. Các hằng đẳng thức trên tập hợp Mỗi tập con của tập hợp tương ứng với một tính chất xác định trên tập hợp đã cho được gọi là mệnh đề. Với tương ứng này, các phép toán trên tập hợp được chuyển sang các phép toán của logic mệnh đề: Phủ định của A, ký hiệu A (hay NOT A) tương ứng với phần bù A. Tuyển của A và B, ký hiệu A  B (hay A or B) tương ứng với A  B. Hội của A và B, ký hiệu A  B (hay A and B) tương ứng với A  B. Các mệnh đề cùng với các phép toán trên nó lập thành một đại số mệnh đề (hay đại số logic). Như thế, đại số tập hợp và đại số logic là hai đại số đẳng cấu với nhau (những mệnh đề phát biểu trên đại số logic tương đương với mệnh đề phát biểu trên đại số tập hợp). Với những trường hợp cụ thể, tuỳ theo tình huống, một bài toán có thể được phát biểu bằng ngôn ngữ của đại số logic hay ngôn ngữ của đại số tập hợp. Bảng 1.6 thể hiện một số hằng đẳng thức của đại số tập hợp. Bảng 1.6. MPTITột số hằng đẳng thức trên tập hợp HẰNG ĐẲNG THỨC TÊN GỌI A   = A Luật đồng nhất A  U = A (U là tập vũ trụ) A  U = U Luật nuốt A   = A AA = A Luật luỹ đẳng A  A = A 17
A = A Luật bù A  B = B  A Luật giao hoán A  B = B  A A  (B  C) = (A B)C Luật kết hợp A (B  C) = (AB)  C A  (B  C) = (A  B)  (A  C ) Luật phân phối A  (B  C) = (A  B)  (A  C) A  B A  B Luật De Morgan A  B A  B 1.6. Biểu diễn tập hợp trên máy tính Có nhiều cách khác nhau để biểu diễn tập hợp trên máy tính, phương pháp phổ biến là lưu trữ các phần tử của tập hợp không sắp thứ tự. Với việc lưu trữ bằng phương pháp này, ngoài những lãng phí bộ nhớ không cần thiết, thì quá trình tính hợp, giao, hiệu các tập hợp gặp nhiều khó khăn và mất nhiều thời gian vì mỗi phép tính đòi hỏi nhiều thao tác tìm kiếm trên các phần tử. Một phương pháp lưu trữ các phần tử bằng cách biểu diễn có thứ tự của các phần tử của một tập vũ trụ tỏ ra hiệu quả hơn rất nhiều trong quá trình tính toán. Giả sử tập vũ trụ U là hữu hạn gồm n phần tử(hữu hạn được hiểu theo nghĩa các phần tử của U lưu trữ được trong bộ nhớ máy tính). Giả sử ta muốn biểu diễn tập hợp A U. Trước hết ta chọn một thứ tự tuỳ ý nào đó đối với các phần tử của tập vũ trụ U, giả sử ta được bộ có thứ tự a1,a2, . ., an. Sau đó xây dựng một xâu bít nhị phân có độ dài n, sao cho nếu bít thứ i có giá trị 1 thì phần tử ai A, nếu ai =0 thì ai A (i=1,2 ,n). Ví dụ sau sẽ minh hoạ kỹ thuật biểu diễn tập hợp bằng xâu bít nhị phân. Ví dụ. Giả sử U = { 1, 2,PTIT 3, 4, 5, 6, 7, 8, 9, 10 }. Hãy biểu diễn tập hợp A  U là 1- Tập các số nguyên lẻ A U. 2- Tập các số nguyên chẵn BU. 3- Tập các số nguyên nhỏ hơn 5 C U. 4- Tìm A  B 5- Tìm AC . . . Lời giải. Trước hết ta coi thứ tự các phần tử được sắp xếp theo thứ tự tăng dần tức ai=i (i=1,2, ,10). Khi đó : 18
1. Xâu bít biểu diễn các số lẻ trong U ( {1, 3, 5, 7, 9 } ) là xâu có độ dài n = 10 trong đó các bít ở vị trí thứ 1, 3, 5, 7, 9 có giá trị là 1, các bít còn lại có giá trị là 0. Từ đó ta có xâu bít biểu diễn tập hợp A là: 1 0 1 0 1 0 1 0 1 0. 2. Xâu bít biểu diễn các số chẵn trong U ( {2, 4, 6, 8, 10 } ) là xâu có độ dài n = 10 trong đó các bít ở vị trí thứ 2, 4, 6, 8, 10 có giá trị là 1, các bít còn lại có giá trị là 0. Từ đó ta có xâu bít biểu diễn tập hợp B là: 0 1 0 1 0 1 0 1 0 1. 3. Xâu bít biểu diễn các số nhỏ hơn 5 trong U ( {1, 2, 3, 4 } ) là xâu có độ dài n = 10 trong đó các bít ở vị trí thứ 1, 2, 3, 4 có giá trị là 1, các bít còn lại có giá trị là 0. Từ đó ta có xâu bít biểu diễn tập hợp C là: 1 1 1 1 0 0 0 0 0 0. 4. Xâu bít biểu diễn tập hợp A  B là : (1 0 1 0 1 0 1 0 1 0  0 1 0 1 0 1 0 1 0 1) là xâu 1 1 1 1 1 1 1 1 1 1. Như vậy, A  B = U. 5. Tương tự như vậy với A  C  (1 0 1 0 1 0 1 0 1 0  1 1 1 1 0 0 0 0 0 0) là xâu 1 0 1 0 0 0 0 0 0 0. Như vậy A  C = { 1, 3 } 1.7. Những nội dung cần ghi nhớ Cần hiểu và nắm vững được những nội dung sau:  Các phép toán hội, tuyển, tuyển loại, suy ra, kéo theo của logic mệnh đề.  Các phương pháp chứng minh định lý dùng bảng chân lý và các tương đương locgic.  Phương pháp biểu diễn các câu hỏi thông thường bằng logic vị từ.  Định nghĩa và các phép toán trên tập hợp.  Phương pháp biểu diễn tập hợp trên máy tính PTITBÀI TẬP CHƯƠNG 1 1. Lập bảng giá trị chân lý cho các mệnh đề phức hợp sau: a) (p q)  (q p) b) (p q) (q p) c) (p  q)  (p  q ) d) (p  q) (p q ) e) (p q)  (p  q ) f) ( p  q )  (pq) g) ( p  q)  r h) (p  q)  r i) (p  q)  ( q r) j) ( p  q ) (qr) 19
2- Dùng bảng chân lý chứng minh: a) Luật giao hoán p  q q  p p  q q  p b) Luật kết hợp (p  q)  r p  ( q  r) ( p  q)  r p (q  r) c) Luật phân phối p  (q  r) (p  q)  (p  r) 3- Chứng minh các công thức sau đây là đồng nhất đúng bằng cách lập bảng giá trị chân lý: a) ( X (Y Z)) ((X Y) (X Z)); b) (X Y) ((X Z) (X (YZ))); c) (X Z) ((Y Z) ((XY) Z)). 4. Chứng minh các công thức sau đây là tương đương logic a) X  (Y1  Y2   Yn (X  Y1 )  (X  Y2 )   (X  Yn ) b) X  (Y1  Y2   Yn (X  Y1 )  (X  Y2 )   (X  Yn ) c) (X 1  X 2   X n X 1  X 1  X n d) X 1  X 2  X n X 1  X 2   X n 5. Cho A, B, C là các tập hợp. Chứng minh rằng: a) A  B  C A  B  C b) (A  B  C) PTIT(A  B) c) (A B) C  (A C) d) (A C)  (C B)  e) (B A)  (C A) (B  C) A f ) A B A  B g) (A  B)  (A  B A 20
CHƯƠNG 2. BÀI TOÁN ĐẾM Đếm các đối tượng có những tính chất nào đó là một bài toán quan trọng của lý thuyết tổ hợp. Giải quyết tốt bài toán đếm giúp ta giải nhiều bài toán khác nhau trong đánh giá độ phức tạp tính toán của các thuật toán và tìm xác suất rời rạc các biến cố. Phương pháp chung để giải bài toán đếm được dựa trên các nguyên lý đếm cơ bản (nguyên lý cộng, nguyên lý nhân). Một số bài toán đếm phức tạp hơn được giải bằng phương pháp qui về các bài toán con, xây dựng công thức truy hồi hoặc phương pháp hàm sinh. Nội dung chính được đề cập trong chương này bao gồm:  Các nguyên lý đếm cơ bản  Nguyên lý bù trừ  Hoán vị và tổ hợp  Hệ thức truy hồi  Qui về các bài toán con  Giới thiệu bài toán tồn tại Bạn đọc có thể tìm hiểu nhiều kỹ thuật đếm cao cấp hơn trong tài liệu [1], [2] trong phần tham khảo của tài liệu này. 2.1. Những nguyên lý đếm cơ bản 2.1.1. Nguyên lý cộng Giả sử có hai công việc. Việc thứ nhất có thể tiến hành bằng n1 cách, việc thứ hai có thể tiến hành bằng n2 cách và nếu hai việc này không thể tiến hành đồng thời. Khi đó sẽ có n1 + n2 cách để giải giải quyết một trong hai việc trên. Chúng ta có thể mở rộng qui tắc cộng cho trường hợp nhiều hơn hai công việc. Giả sử các việc T1, T2, , Tm có thPTITể làm tương ứng bằng n1, n2, , nm cách và giả sử không có hai việc Ti, Tj nào làm việc đồng thời (i,j = 1, 2, , m ; i j ). Khi đó, có n1 + n2 + +nm cách thực hiện một trong các công việc T1, T2, . ., Tm. Qui tắc cộng được phát biểu dưới dạng của ngôn ngữ tập hợp như sau: Nếu A và B là hai tập rời nhau (A  B = ) thì : N(AB) = N(A) + N(B). Nếu A1, A2, , An là những tập hợp rời nhau thì: N(A1  A2  . . An ) = N(A1) + N(A2) + + N(An). Ví dụ 1. Giả sử cần chọn hoặc một cán bộ hoặc một sinh viên tham gia một hội đồng của một trường đại học. Hỏi có bao nhiêu cách chọn vị đại biểu này nếu như có 37 cán bộ và 63 sinh viên. 21
Lời giải: Gọi việc thứ nhất là chọn một cán bộ từ tập cán bộ ta có 37 cách. Gọi việc thứ hai là chọn một sinh viên từ tập sinh viên ta có 63 cách. Vì tập cán bộ và tập sinh viên là rời nhau, theo nguyên lý cộng ta có tổng số cách chọn vị đại biểu này là 37 + 63 = 100 cách chọn. Ví dụ 2. một đoàn vận động viên gồm môn bắn súng và bơi được cử đi thi đấu ở nước ngoài. Số vận động viên nam là 10 người. Số vận động viên thi bắn súng kể cả nam và nữ là 14 người. Số nữ vận động viên thi bơi bằng số vận động viên nam thi bắn súng. Hỏi đoàn có bao nhiêu người. Lời giải. Chia đoàn thành hai tập, tập các vận động viên nam và tập các vận động viên nữ. Ta nhận thấy tập nữ lại được chia thành hai: thi bắn súng và thi bơi. Thay số nữ thi bơi bằng số nam thi bắn súng , ta được số nữ bằng tổng số vận động viên thi bắn súng. Từ đó theo nguyên lý cộng toàn đoàn có 14 + 10 = 24 người. Ví dụ 3. giá trị của biến k sẽ bằng bao nhiêu sau khi thực hiện đoạn chương trình sau : k := 0 for i1:= 1to n1 k:=k+1 for i2:= 1to n2 k:=k+1 . . . . . . . . . . for im:= 1 to nm k:=k+1 Lời giải. coi mỗi vòng for là một công việc, do đó ta có m công việc T1, T2, . ., Tm. Trong đó Ti thực hiện bởi ni cách (i= 1, 2, , m). Vì các vòng for không lồng nhau hay các công việc không thực hiện đồng thời nên theo nguyên lý cộng tổng tất cả các cách để hoàn thành T1, T2, , Tm là k= n1PTIT + n2 + + nm. 2.1.2. Nguyên lý nhân Giả sử một nhiệm vụ nào đó được tách ra hai công việc. Việc thứ nhất được thực hiện bằng n1 cách, việc thứ hai được thực hiện bằng n2 cách sau khi việc thứ nhất đã được làm, khi đó sẽ có n1.n2 cách thực hiện nhiệm vụ này. Nguyên lý nhân có thể được phát biểu tổng quát bằng ngôn ngữ tập hợp như sau: Nếu A1, A2, , Am là những tập hợp hữu hạn, khi đó số phần tử của tích đề các các tập này bằng tích số các phần tử của mỗi tập thành phần. Hay đẳng thức: N (A1 A2 Am ) = N (A1) N (A2) . . . N (Am). k k Nếu A1 = A2 =. . Am thì N(A ) = N(A) 22
Ví dụ 1. giá trị của k sẽ bằng bao nhiêu sau khi ta thực hiện đoạn chương trình sau: k:=0 for i1 = 1 to n1 for i2 = 1 to n2 . . for in =1 to nm k:=k +1 Lời giải. Giá trị khởi tạo k=0. Mỗi vòng lặp kồng nhau đi qua giá trị của k được tăng lên 1 đơn vị. Gọi Ti là việc thi hành vòng lặp thứ i. Khi đó, số lần vòng lặp là số cách thực hiện công việc. Số cách thực hiện công việc Tj là nj (j=1,2, . ., n). Theo qui tắc nhân ta vòng lặp kép được duyệt qua n1 +n2 + +nm lần và chính là giá trị của k. Ví dụ 2. Người ta có thể ghi nhãn cho những chiếc ghế của một giảng đường bằng một chữ cái và sau đó là một số nguyên nhỏ hơn 100. Bằng cách như vậy hỏi có nhiều nhất bao nhiêu chiếc ghế có thể ghi nhãn khác nhau. Lời giải: có nhiều nhất là 26 x 100 = 2600 ghế được ghi nhãn. Vì kí tự gán nhãn đầu tiên là một chữ cái vậy có 26 cách chọn các chữ cái khác nhau để ghi kí tự đầu tiên, tiếp theo sau là một số nguyên dương nhỏ hơn 100 do vậy có 100 cách chọn các số nguyên để gán tiếp sau của một nhãn. Theo qui tắc nhân ta nhận được 26 x 100 = 2600 nhãn khác nhau. Ví dụ 3. Có bao nhiêu xâu nhị phân có độ dài 7? Lời giải. một xâu nhị phân có độ dài 7 gồm 7 bít, mỗi bít có hai cách chọn (hoặc giá trị 0 hoặc giá trị 1), theo quiPTIT tắc nhân ta có 2.2.2.2.2.2.2 = 27 = 128 xâu bít nị phân độ dài 7. Ví dụ 4. Có bao nhiêu hàm đơn ánh xác định từ một tập A có m phần tử nhận giá trị trên tập B có n phần tử? Lời giải. Trước tiên ta nhận thấy, nếu m >n thì tồn tại ít nhất hai phần tử khác nhau của A cùng nhận một giá trị trên B, như vậy với m>n thì số các hàm đơn ánh từ A B là 0. Nếu m<=n, khi đó phần tử đầu tiên của A có n cách chọn, phần tử thứ hai có n-1 cách chọn, . ., phần tử thứ k có n-k+1 cách chọn. Theo qui tắc nhân ta có n(n-1) (n-2) . . .(n-m+1) hàm đơn ánh từ tập A sang tập B. Ví dụ 5. Dạng của số điện thoại ở Bắc Mỹ được qui định như sau: số điện thoại gồm 10 chữ số được tách ra thành một nhóm mã vùng gồm 3 chữ số, nhóm mã chi nhánh 23
gồm 3 chữ số và nhóm mã máy gồm 4 chữ số. Vì những nguyên nhân kỹ thuật nên có một số hạn chế đối với một số con số. Ta giả sử, X biểu thị một số có thể nhận các giá trị từ 0 9, N là số có thể nhận các chữ số từ 2 9, Y là các số có thể nhận các chữ số 0 hoặc 1. Hỏi theo hai dự án đánh số NYX NNX XXXX và NXX NXX XXXX có bao nhiêu số điện thoại được đánh số khác nhau ở Bắc Mỹ? Lời giải: đánh số theo dự án NYX NNX XXXX được nhiều nhất là : 8 x 2 x 10 x 8 x 8 x10 x10 x10 x 10 x 10 x10 = 2 x 83 x 106 = 1 024. 106 đánh số theo dự án NXX NXX XXXX được nhiều nhất là : 8 x 10 x 10 x 8 x 10 x10 x10 x10 x 10 x 10 x10 = 82 x 108 = 64. 108 Ví dụ 6. Dùng qui tắc nhân hãy chỉ ra rằng số tập con của một tập S hữu hạn là 2N(S). Lời giải. ta liệt kê các phần tử của tập S là s1, s2, , sN(S). Xây dựng một xâu bít nhị phân dài N(S) bít, trong đó nếu bít thứ i có giá trị 0 thì phần tử si S, nếu bít thứ i có giá trị 1 thì phần tử si S (i=1, 2, , N(S) ). Như vậy, theo nguyên lý nhân, số tập con của tập hợp S chính là số xâu bít nhị phân có độ dài N(S). Theo ví dụ 3, chúng ta có 2N(S) xâu bít nhị phân độ dài N(S). 2.2. Nguyên lý bù trừ Trong một số bài toán đếm phức tạp hơn. Nếu không có giả thiết gì về sự rời nhau giữa hai tập A và B thì N(AB) = N(A) + N(B) – N(AB). Ví dụ 1. lớp toán học rời rạc có 25 sinh viên giỏi tin học, 13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán và tin học. Hỏi lớp có bao nhiêu sinh viên nếu mỗi sinh viên hoặc giỏi toán hoặc học giỏi tin học hoặc giỏi cả hai môn? Lời giải. Gọi A tập là tập các sinh viên giỏi Tin học, B là tập các sinh viên giỏi toán. Khi đó A  B là tập sinh viên giỏi cả toán học và tin học. Vì mỗi sinh viên trong lớp hoặc giỏi toán, hoặc giỏi tin học hoặc giỏi cả hai nên ta có tổng số sinh viên trong lớp là N(AB). Do vậy ta có: PTIT N(AB) = N(A) + N(B) – N(AB) = 25 + 13 – 8 = 30. Ví dụ 2. Có bao nhiêu số nguyên không lớn hơn 1000 chia hết cho 7 hoặc 11. Lời giải. Gọi A là tập các số nguyên không lớn hơn 1000 chia hết cho 7, B là tập các số nguyên không lớn hơn 1000 chia hết cho 11. Khi đó tập số nguyên không lớn hơn 1000 hoặc chia hết cho 7 hoặc chia hết cho 11 là N(AB). Theo công thức 1 ta có: N(AB) = N(A) + N(B) – N(AB) = 1000/7 + 1000/11 - 1000/7.11 = 142 + 90 – 12 = 220. Trước khi đưa ra công thức tổng quát cho n tập hợp hữu hạn. Chúng ta đưa ra công thức tính số phần tử của hợp 3 tập A, B, C. 24
Ta nhận thấy N(A) + N(B) + N(C) đếm một lần những phần tử chỉ thuộc một trong ba tập hợp. Như vậy, số phần tử của A B, AC, BC được đếm hai lần và bằng N(AB), N(AC), N(BC), được đếm ba lần là những phần tử thuộc ABC. Như vậy, biểu thức: N(ABC) – N(AB)- N(AC) – N(BC) chỉ đếm các phần tử chỉ thuộc một trong ba tập hợp và loại bỏ đi những phần tử được đếm hai lần. Như vậy, số phần tử được đếm ba lần chưa được đếm, nên ta phải cộng thêm với giao của cả ba tập hợp. Từ đó ta có công thức đối với 3 tập không rời nhau: N(ABC)= N(A)+N(B)+N(C)–N(AB)–N(AC)–N(BC)+N(ABC) Định lý. Nguyên lý bù trừ. Giả sử A1, A2, . ., Am là những tập hữu hạn. Khi đó m-1 N(A1A2 . . .Am) = N1- N2 + . . +(-1) Nm, trong đó Nk là tổng phần tử của tất cả các giao của k tập lấy từ m tập đã cho. (nói riêng N1=N(A1) + N(A2) + . .+ N(Am), Nm = N(A1  A2  . . .Am ) . Nói cách khác: N(A1  A2  An )  N(Ai )  N(Ai  Aj )  N(Ai  A j  Ak 1 i n 1 i, j n 1 i j k n n 1 ( 1) N(A1  A2   An ) Định lý được chứng minh bằng cách chỉ ra mỗi phần tử của hợp n tập hợp được đếm đúng một lần. Bạn đọc có thể tham khảo cách chứng minh trong tài liệu [1]. Ví dụ 3. Tìm công thức tính số phần tử của 4 tập hợp. Lời giải. Từ nguyên lý bù trừ ta có N(A1A2A3A4) = N(A1) + N(A2) + N(A3) + N(A4) – N(A1A2) – N(A1A3) – N(A1A4) – N(A2A3) – N(A2A4) – N(A3A4) + N(A1A2A3) + N(A1A2A4) + N(A1A3A4 + N(A2A3A4) – N(A1A2A3A4). Ví dụ 4. Hỏi trong tập XPTIT = { 1, 2, . ., 10000} có bao nhiêu số không chia hết cho bất cứ số nào trong các số 3, 4, 7? Lời giải. Gọi A là tập các số nhỏ hơn 10000 chia hết cho 3, B là tập các số nhỏ hơn 10000 chia hết cho 4, C là tập các số nhỏ hơn 10000 chia hết cho 7. Theo nguyên lý bù trừ ta có: N(A BC)= N(A)+N(B) + N(C) – N(AB – N(AC) – N(BC) + N(ABC) trong đó : N(A) + N(B) + N (C) = [10 000/3] + [10 000/4] + [10 000/7] = 3333 + 2500 + 1428 = 7261 N(AB) = N(A) + N(B) – N(AB) = 3333 + 2500 – [10000/3x4] = 833 25
N(AC) = N(A) + N(C) – N(AC) = 3333 + 1428 – [10000/3x7] = 476 N(BC) = N(B) + N(C) – N(BC) = 2500 + 1428 – [10000/4x7] = 357 N(AB) + N(AC) + N(BC) = 833 + 476 + 357 = 1666 N(ABC) = [10000/3x4x7] = 119. =>Số các số nhỏ hơn 10000 cần đếm là : 1000 - N(ABC) = 7261 – 1666 + 119 = 4286. Ví dụ 5. Có bao nhiêu xâu nhị phân độ dài 10 bắt đầu bởi 00 hoặc kết thúc bởi 11. Lời giải. Gọi A là số xâu nhị phân độ dài 10 bắt đầu bởi 00 , B là số xâu nhị phân độ dài 10 kết thúc bởi 11. Dễ ràng nhận thấy, N(A) = N(B) = 256, N(AB) = 26 = 64. Theo nguyên lý bù trừ ta có: N(AB) = N(A) + N(B) – N(AB) = 256 + 256 – 64 = 448. Ví dụ 6. Bài toán bỏ thư. Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các phong bì. Hỏi xác suất để xảy ra không một là thư nào bỏ đúng địa chỉ là bao nhiêu? Lời giải: Có tất cả n! cách bỏ thư. Vấn đề đặt ra là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi X là tập hợp tất cả các cách bỏ thư và Ak là tính chất lá thư k bỏ đúng địa chỉ. Khi đó theo nguyên lý bù trừ ta có: n N N N1 N 2 ( 1) N n Trong đó N là số cần tìm, N = n!, Nk là số tất cả các cách bỏ thư sao cho có k lá thư đúng địa chỉ. Nhận xét rằng, Nk là mọi cách lấy k lá thư từ n lá, với mỗi cách lấy k lá thư, có (n-k )! cách bỏ để k lá thư này đúng địa chỉ, từ đó ta nhận được. n! 1 1 ( 1)n N C(n, k)(n k)! và N n!(1  k PTITk! 1! 2! n! Từ đó ta có xác xuất cần tìm là: 1 1 ( 1) n 1  e 1 1! 2! n! Số được tính như trên được gọi là số mất thứ tự và được ký hiệu là Dn. Dưới đây là một vài giá trị của Dn, sự tăng nhanh của Dn một lần nữa cho ta thấy rõ sự bùng nổ tổ hợp. N 2 3 4 5 6 7 8 9 10 11 Dn 1 2 9 44 265 1845 14833 133496 1334961 4890741 26
2.3. Đếm các hoán vị và tổ hợp 2.3.1. Chỉnh hợp lặp Định nghĩa 1. Một chỉnh hợp lặp chập k của n phần tử là bộ có thứ tự gồm k thành phần lấy từ n phần tử của tập đã cho. Như vậy, một chỉnh hợp lặp chập k của n phần tử có thể xem là phần tử của tích đề các Ak với A là tập đã cho. Theo nguyên lý nhân, số các tất cả các chỉnh hợp lặp chập k của n sẽ là nk. Ví dụ 1. Tính số hàm từ tập có k phần tử vào tập có n phần tử? Lời giải: Biểu diễn mỗi hàm bằng một bộ k thành phần, trong đó thành phần thứ i là ảnh của phần tử thứ i (1<=i<=k). Mỗi thành phần được lấy ra từ một trong n giá trị. Từ đó suy ra số hàm là số bộ k thành phần lấy từ n thành phần bằng nk. Ví dụ 2. Từ bảng chữ cái tiếng Anh có thể tạo ra được bao nhiêu xâu có độ dài n? Lời giải : Bảng chữ cái tiếng Anh gồm 26 kí tự [‘A’ ’Z’], số các xâu có độ dài n được chọn từ 26 chữ cái chính là chỉnh hợp lặp n của 26 phần tử và bằng 26n. Ví dụ 3. Tính xác xuất lấy ra liên tiếp được 3 quả bóng đỏ ra khỏi bình kín chứa 5 quả đỏ, 7 quả xanh nếu sau mỗi lần lấy một quả bóng ra lại bỏ nó trở lại bình? Lời giải: Số kết cục có lợi để ta lấy ra liên tiếp 3 quả bóng đỏ là 53 vì có 5 quả đỏ ta phải lấy 3 quả (chú ý vì có hoàn lại). Toàn bộ kết cục có thể để lấy ra ba quả bóng bất kỳ trong 12 quả bóng là 123. Như vậy, xác suất để có thể lấy ra 3 quả bóng đỏ liên tiếp là 53/123. 2.3.2. Chỉnh hợp không lặp Định nghĩa 2. Chỉnh hợp không lặp chập k của n phần tử là bộ có thứ tự gồm k thành phần lấy ra từ n phần tử đã cho. PTITCác phần tử không được lặp lại. Để xây dựng một chỉnh hợp không lặp, ta xây dựng từ thành phần đầu tiên. Thành phần này có n khả năng chọn. Mỗi thành phần tiếp theo những khả năng chọn giảm đi 1 (vì không được lấy lặp lại). Tới thành phần thứ k có n-k + 1 khả năng chọn. Theo nguyên lý nhân ta có số chỉnh hợp không lặp chập k của tập hợp n phần tử ký hiệu là P(n, k) được tính theo công thức: n! P(n,k) n(n 1) (n k 1) (n k)! Ví dụ 1. Tìm số hàm đơn ánh có thể xây dựng được từ tập k phần tử sang tập n phần tử? 27
Lời giải: Số hàm đơn ánh từ tập k phần tử sang tập n phần tử chính là P(n,k). Ví dụ 2. Giả sử có tám vận động viên chạy thi. Người về nhất sẽ được nhận huân chương vàng, người về nhì nhận huân chương bạc, người về ba nhận huy chương đồng. Hỏi có bao nhiêu cách trao huy chương nếu tất cả các kết cục đều có thể xảy ra? Lời giải. Số cách trao huy chương chính là số chỉnh hợp chập 3 của tập hợp 8 phần tử. Vì thế có P(8,3) = 8.7.6 = 336 cách trao huy chương. Ví dụ 3. Có bao nhiêu cách chọn 4 cầu thủ khác nhau trong đội bóng gồm 10 cầu thủ để tham gia các trận đấu đơn. Lời giải. Có P(10,4) = 10.9.8.7 = 5040 cách chọn. 2.3.3. Hoán vị Định nghĩa 3. Ta gọi các hoán vị của n phần tử là một cách xếp có thứ tự các phần tử đó. Số các hoán vị của tập n phần tử có thể coi là trường hợp riêng của chỉnh hợp không lặp với k = n. Ta cũng có thể đồng nhất một hoán vị với một song ánh từ tập n phần tử lên chính nó. Như vậy, số hoán vị của tập gồm n phần tử là P(n, n) = n!. Ví dụ 1. Có 6 người xếp thành hàng để chụp ảnh. Hỏi có thể bố trí chụp được bao nhiêu kiểu khác nhau? Lời giải. Mỗi kiểu ảnh là một hoán vị của 6 người. Do đó có 6! = 720 kiểu ảnh khác nhau có thể chụp. Ví dụ 2. Cần bố trí thực hiện n chương trình trên một máy tính. Hỏi có bao nhiêu cách bố trí khác nhau? Lời giải. Số chương trình được đánh số từ 1, 2, . ., n. Như vậy, số chương trình cần thực hiện trên một máy tính là số hoán vị của 1, 2, , n. Ví dụ 3. Một thương nhân đi bán hàng tại tám thành phố. Chị ta có thể bắt đầu hành trình của mình tại một thành phố nào đó nhưng phải qua 7 thành phố kia theo bất kỳ thứ tự nào mà chị ta muốn. HỏiPTIT có bao nhiêu lộ trình khác nhau mà chị ta có thể đi? Lời giải. Vì thành phố xuất phát đã được xác định. Do vậy thương nhân có thể chọn tuỳ ý 7 thành phố còn lại để hành trình. Như vậy, tất cả số hành trình của thương nhân có thể đi qua là 7! = 5040 cách. 2.3.4. Tổ hợp Định nghĩa 4. Một tổ hợp chập k của n phần tử là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho. Nói cách khác, ta có thể coi một tổ hợp chập k của n phần tử là một tập con k phần tử lấy trong n phần tử. Số tổ hợp chập k của n phần tử ký hiệu là C(n,k). 28
Ta có thể tính được trực tiếp số các tổ hợp chập k của tập n phần tử thông qua chỉnh hợp không lặp của k phần tử. Xét tập hợp tất cả các chỉnh hợp không lặp chập k của n phần tử. Sắp xếp chúng thành những lớp sao cho hai chỉnh hợp thuộc cùng một lớp chỉ khác nhau về thứ tự. Rõ ràng mỗi lớp như vậy là một tổ hợp chập k của n phần tử(P(n,k)). Số chỉnh hợp trong mỗi lớp đều bằng nhau và bằng k! (số hoán vị k phần tử: P(k,k) ). Số các lớp bằng số tổ hợp chập k của n (P(n,k)). Từ đó ta có: P(n,k) n! P(n,k) C(n,k).P(k,k) C(n,k) k! k!(n k)! Ví dụ 1. Cho S = { a, b, c, d } tìm C(4,2)? Lời giải. Rõ ràng C(4,2) = 6 tương ứng với 6 tập con {a, b}, {a, c}, {a, d}, {b,c}, {b, d} {c,d}. Ví dụ 2. Có n đội bóng thi đấu vòng tròn. Hỏi phải tổ chức bao nhiêu trận đấu. Lời giải: Cứ hai đội bóng thì có một trận. Từ đó suy ra số trận đấu sẽ bằng số cách chọn 2 trong n đội, nghĩa là bằng C(n, 2) = n! / 2!(n-2)! = n(n-1)/2 trận đấu. Ví dụ 3. Chứng minh a) C(n,k) = C(n, n-k) b) C(n, 0) = C(n,n)= 1 c) C(n,k) = C(n-1,k-1) + C(n-1,k) Lời giải a. C(n,n-k) = n!/(n-k)! (n-n+k)! = n!/k!(n-k)! = C(n,k). Hoặc C(n, k) = n!/k!(n-k)! = n!/ (n-k)! (n-(n-k))! = C(n, n-k); b) Chú ý 0!=1 => b hiển nhiên đúng c) C(n,k) = C(n-1,k-1) + C(n-1,k) (n 1)! (n 1)! C(n 1, k 1) C(n 1, k) PTIT(k 1)!(n 1 k 1)! k!(n k 1)! (n 1)! 1 1 (n 1)!.n (k 1)!(n k 1)! n k k (k 1)!k(n k 1)!(n k) n! C(n.k) k!(n k)! Từ những tính chất trên, ta có thể tính tất cả các hệ số tổ hợp chỉ bằng phép cộng. Các hệ số này được tính và viết lần lượt theo dòng, trên mỗi dòng ta tính và thực hiện theo cột. Bảng có dạng tam giác chính là tam giác Pascal. Các hệ số tổ hợp có liên quan chặt chẽ tới việc khai triển luỹ thừa của một nhị thức. Thực vậy, trong tích 29
(x+y)n = (x+y)(x+y). . .(x+y) hệ số của xkyk-n sẽ là số cách chọn k phần tử (x+y) mà từ đó lấy ra x và đồng thời (n-k) nhân tử còn lại lấy ra y, nghĩa là: n (x y) n C(n,0)x n C(n,1)x n 1 y C(n, n 1)xy n 1 C(n,0)y n C(n, k)x n k y k k 0 Công thức trên còn được gọi là khai triển nhị thức Newton, các hệ số tổ hợp còn được gọi là hệ số nhị thức. Chẳng hạn luỹ thừa bậc 8 của nhị thức (x+y)8 được khai triển như sau: (x y)8 x 8 8x 7 y 28x 6 y 2 56x 5 y 3 70x 4 y 4 56x 3 y 5 28x 2 y 6 8xy 7 y 8 Trong trường hợp y=1, tức khai triển (x+1)n ta có: (x 1) n C(n,0)x n C(n,1)x n 1 C(n,n 1)x C(n,n) Hoặc đẳng thức sau sẽ được rút ra từ khai triển nhị thức Newton: 2n (1 1) n C(n,0) C(n,1) C(n, n 1) C(n,n) Có thể nói rất nhiều đẳng thức về hệ số tổ hợp sẽ được suy ra. Như tính các tập lẻ, đạo hàm. 2.3.5. Tổ hợp lặp Từ Định nghĩa tổ hợp, ta có thể tính toán được số tổ hợp lặp chập k từ tập n phần tử bằng C( n + k -1, k). Ví dụ 1. Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm nguyên không âm? Lời giải. Mỗi nghiệm nguyên không âm của phương trình ứng với một cách chọn 11 phần tử từ một tập có 3 loại, sao cho có x1 phần tử loại 1 được chọn, x2 phần tử loại 2 được chọn, x3 phần tử loại 3 được chọn. Số này chính bằng số tổ hợp lặp chập 11 từ tập có 3 phần tử. Vì vậy, số nghiệm nguyên không âm của phương trình là: C( 3 + 11 -1, 11 ) = C (13, 11) = (13.12) / 2 = 78. Ví dụ 2. Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm nguyên không âm thỏa mãn x 1, x 2, x 3? PTIT 1 2 3 Lời giải. Mỗi nghiệm nguyên không âm của phương trình ứng với một cách chọn 11 phần tử từ một tập có 3 loại, sao cho có x1 phần tử loại 1 được chọn, x2 phần tử loại 2 được chọn, x3 phần tử loại 3 được chọn. Trong đó, có ít nhất một phần tử loại 1, hai phần tử loại 2 và ba phần tử loại 3. Vì thế ta chọn một phần tử loại 1, hai phần tử loại 2, ba phần tử loại 3 sau đó chọn thêm 5 phần tử nữa. Số này chính bằng số tổ hợp lặp chập 5 từ tập có 3 phần tử. Vì vậy, số nghiệm nguyên không âm của phương trình là: C( 3 + 5 -1, 5 ) = C (7, 5) = (7.6) / 2 = 21. Ví dụ 3. Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm nguyên không âm thỏa mãn 1 x1 3? 30
Lời giải. Ta nhận thấy, số nghiệm nguyên không âm của phương trình thỏa mãn 1 x1 3 chính bằng số nghiệm nguyên không âm của phương trình thỏa mãn x1 1 sau đó trừ bớt đi những nghiệm x1 4. Từ Ví dụ 1 ta tính được số nghiệm nguyên không âm của phương trình thỏa mãn 1 x1 3 là C( 3 + 10 -1, 10 ) - C(3 +7-1, 7) = C (12, 10) - C(9, 7). 2.4. Hệ thức truy hồi Thông thường người ta thường quan tâm tới những bài toán đếm trong đó kết quả đếm phụ thuộc vào một tham số đầu vào (mà ta ký hiệu là n), chẳng hạn như các số mất thứ tự Dn . Việc biểu diễn kết quả này như một hàm của n bằng một số hữu hạn các phép toán không phải là đơn giản. Trong nhiều truờng hợp, việc tìm ra một công thức trực tiếp giữa kết quả đếm và n là hết sức khó khăn và nhiều khi không giải quyết được, trong khi đó công thức liên hệ giữa kết quả đếm ứng với giá trị n với các kết quả bé hơn n lại đơn giản và dễ tìm. Thông qua công thức này và một vài giá trị ban đầu, ta có thể tính mọi giá trị còn lại khác. Công thức đó gọi là công thức truy hồi hay công thức đệ qui. Đặc biệt, công thức truy hồi rất thích hợp với lập trình trên máy tính. Nó cũng cho phép giảm đáng kể độ phức tạp cũng như gia tăng độ ổn định của quá trình tính toán. 2.4.1. Định nghĩa và ví dụ Định nghĩa 1. Hệ thức truy hồi đối với dãy số {an} là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy, cụ thể là a1, a2, , an-1 với mọi n n0 nguyên dương. Dãy số được gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các số hạng của nó thoả mãn hệ thức truy hồi. Ví dụ 1. Lãi kép. Giả sử một người gửi 10000 đô la vào tài khoản của mình tại một ngân hàng với lãi xuất kép 11% mỗi năm. Hỏi sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của mình? Lời giải. Gọi Pn là tổng số tiền có trong tài khoản sau n năm. Vì số tiền có trong tài khoản sau n năm bằng số tiềnPTIT có được trong n-1 năm cộng với lãi xuất năm thứ n. Nên dãy {Pn} thoả mãn hệ thức truy hồi : Pn = Pn-1 + 0.11Pn-1 = 1.11Pn-1 Chúng ta có thể dùng phương pháp lặp để tìm công thức trên cho Pn. Dễ nhận thấy rằng: P0 = 10000 P1 = 1.11P0 2 P2 = 1.11P1 = (1.11) P0 . . . . . . . . . . . . . . . . . . . . . n-1 Pn = 1.11Pn-1 = (1.11) P0 31
Ta có thể chứng minh tính đúng đắn của công thức truy hồi bằng qui nạp. Thay P0= 10000, và n = 30 ta được: 30 P30 = (1.11) 10000 = 228922,97 $ Ví dụ 2. Họ nhà thỏ và số Fibonaci. Một cặp thỏ sinh đôi (một con đực và một con cái) được thả lên một hòn đảo. Giả sử rằng cặp thỏ sẽ chưa sinh sản được trước khi đầy hai tháng tuổi. Từ khi chúng đầy hai tháng tuổi, mỗi tháng chúng sinh thêm được một cặp thỏ. Tìm công thức truy hồi tính số cặp thỏ trên đảo sau n tháng với giả sử các cặp thỏ là trường thọ. Số tháng Số cặp sinh sản Số cặp thỏ con Tổng số cặp thỏ 1 0 1 1 2 0 1 1 3 1 1 2 4 1 2 3 5 2 3 5 6 3 5 8 Lời giải: Giả sử fn là số cặp thỏ sau n tháng. Ta sẽ chỉ ra rằng f1, f2, . ., fn (n=1, 2, . ., n) là các số của dãy fibonaci. Cuối tháng thứ nhất số cặp thỏ trên đảo là f1 = 1. Vì tháng thứ hai cặp thỏ vẫn chưa đến tuổi sinh sản được nên trong tháng thứ hai f2 =1. Vì mỗi cặp thỏ chỉ được sinh sản sau ít nhất hai tháng tuổi, nên ta tìm số cặp thỏ sau tháng thứ n bằng cách cộng số cặp thỏ sau tháng n-2 và tháng n-1 hay fn = fn-1 + fn-2. Do vậy, dãy { fn} thoả mãn hệ thức truy hồi fn = fn-1 + fn- 2 với n>=3 và f1 = 1, f2 = 1. Ví dụ 3. Tính số mất thứ tự Dn. PTIT Lời giải: Đánh số thư và phong bì thư từ 1 đến n (thư i gửi đúng địa chỉ nếu bỏ vào phong bì i). Một cách bỏ thư đuợc đồng nhất với hoán vị (a1, a2, . ., an) của { 1, 2, . ., n }. Một mất thứ tự được định nghĩa là là một hoán vị (a1, a2, . ., an) sao cho ai i với mọi i. Thành phần a1 có thể chấp nhận mọi giá trị ngoài 1. Với mỗi giá trị k (k 1) của a1, xét hai trường hợp: 1. ak =1, khi đó các thành phần còn lại được xác định như một mất thứ tự của n-2 phần tử, tức là số mất thứ tự loại này bằng Dn-2. 2. ak 1, khi đó các thành phần từ 2 đến n được xác định như một mất thứ tự của n-1 phần tử còn lại, tức là số mất thứ tự này thuộc loại Dn-1. 32
Từ đó ta nhận được công thức Dn = (n-1) (Dn-1 + Dn-2), n>=3 với D1 = 0, D2 =1. Mọi giá trị còn lại được tính đơn giản nhờ luật kế thừa. D3 = (3 –1) (0 +1) =2 D4 = (4 –1 )( 1 + 2) = 9 D5 = (5 –1 )( 9 + 2) = 44 D6 = (6 –1 )(9 + 44) = 265 D7 = (7 –1 )( 44 + 265) = 1854 D8 = (8 –1 )( 265 + 1854) = 14833 . . . . . . . . . . . . . . . . . . . . . . . . . . . Để công thức đúng với n = 2, ta coi D0 = 1 Có thể nhận được số mất thứ tự thông qua công thức truy hồi trên vì: Dn (n 1)(Dn 1 Dn 2 ) Dn nDn 1 (Dn 1 (n 1)Dn 2 ) Đặt Vn Dn nDn 1 ta có: n 1 n Dn nDn 1 Vn Vn 1  ( 1) V1 ( 1) . Hay ta có thể viết: D D ( 1) n n n 1 . Cộng các hệ thức trên với n = 1, 2, , n ta được: n! (n 1)! n! D 1 1 ( 1) n n 1  . Từ đó thu lại được công thức cũ: n! 1! 2! n! 1 1 ( 1) n D n!(1  ) n 1! 2! n! Ví dụ 3. Tính hệ số tổ hợpPTIT C(n,k). Lời giải. Chọn phần tử cố định a trong n phần tử đang xét. Chia số cách chọn tập con k phần tử này thành hai lớp (lớp chứa a và lớp không chứa a). Nếu a được chọn thì ta cần bổ xung k-1 phần tử từ n-1 phần tử còn lại, từ đó lớp chứa a gồm C(n-1, k-1) cách. Nếu a không được chọn, thì ta phải chọn k phần tử từ n-1 phần tử còn lại, từ đó lớp không chứa a gồm C(n-1, k) cách. Theo nguyên lý cộng ta được công thức truy hồi: C(n, k) = C(n-1, k-1) + C(n-1,k) với các giá trị biên được suy ra trực tiếp: C(n,0) = C(n,n) = 1. Phương pháp này được gọi là phương pháp khử. Không phải lúc nào cũng dễ dàng khử được công thức truy hồi để đưa về công thức trực tiếp. Tuy nhiên, trong một số trường hợp đặc biệt ta có thể đưa ra phương pháp tổng quát để giải công thức truy hồi. 33
2.4.2. Giải công thức truy hồi tuyến tính thuần nhất với hệ số hằng số Định nghĩa 1. Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng số là hệ thức truy hồi có dạng: an c1an 1 c1an 2  ck an k (1) trong đó c1,c2, . ., ck là các số thực và ck 0 Ta cần tìm công thức trực tiếp cho số hạng an của dãy số {an} thoả mãn công thức (1). Theo nguyên lý thứ hai của qui nạp toán học thì dãy số thoả mãn định nghĩa trên được xác định duy nhất nếu như nó thoả mãn k điều kiện đầu: a0 = C0, a1 = C1, . ., ak-1 = Ck-1, trong đó C1, C2, . ., Ck-1 là các hằng số. Ví dụ 1. Hệ thức truy hồi Pn=(1.11)Pn-1 là hệ thức truy hồi tuyến tính thuần nhất bậc 1. Hệ thức truy hồi fn = fn-1 + fn-2 là hệ thức truy hồi tuyến tính thuần nhất bậc 2. Hệ thức truy hồi an = an-5 là hệ thức truy hồi tuyến tính thuần nhất bậc 5. Hệ thức truy hồi Bn=nBn-1 không phải là hệ thức truy hồi tuyến tính thuần nhất vì nó không có hệ số hằng số. Phương pháp cơ bản để giải hệ thưc truy hồi tuyến tính thuần nhất là tìm nghiệm n n dưới dạng an = r , trong đó r là hằng số. Cũng cần chú ý rằng an = r là nghiệm của hệ thức truy hồi an = c1an-1 + c2 an-2 + . .+ ckan-k nếu và chỉ nếu an = c1rn-1 + c2rn-2 + . .+ ckrn-k . Chia cả hai vế cho rn-k ta nhận được k k-1 k-2 r – c1r – c2r - . . – ck-1r –ck =0 (2) n Vậy dãy {an} với an=r là nghiệm nếu và chỉ nếu r là nghiệm của (2). Phương trình 2 còn được gọi là phương trình đặc trưng của hệ thức truy hồi, nghiệm của nó là nghiệm đặc trưng của hệ thức truy hồi. Nghiệm của phương trình đặc trưng dùng để biểu diễn công thức tất cả các nghiệm của hệ thức truy hồi. Chúng ta sẽ trình bày các kết quả với hệ thức truy hồi tuyến tính thuần nhất bậc hai. Sau đó ta sẽ nêu ra những kếtPTIT quả tương tự cho trường hợp tổng quát khi bậc lớn hơn hai. 2 Định lý 1. Cho c1, c2 là các hằng số thực. Giả sử r – c1r + c2 =0 có hai nghiệm phân biệt r1, r2. Khi đó dãy {an} là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2 khi và n n chỉ khi an = 1r1 + 2r 2 với n =1, 2, . , 1, 2 là các hằng số. Chứng minh: Để chứng minh định lý này ta cần thực hiện hai việc. Đầu tiên ta cần chỉ ra rằng nếu r1, r2 là hai nghiệm của phương trình đặc trưng và 1, 2 là hai hằng n n số thì dãy {an} với an 1r1 2 r2 là nghiệm của hệ thức truy hồi. Ngược lại, cần phải n n chứng minh rằng nếu {an} là nghiệm thì an 1r1 2 r2 với 1, 2 là các hằng số nào đó. 34
2 ( ): Giả sử r1 và r2 là hai nghiệm phân biệt của r – c1r + c2=0 , khi đó 2 2 2 r1 c1 r1 c2 ; r2 c1r2 c2 đồng thời ta thực hiện dãy các phép biến đổi sau: n 1 n 2 n 2 n 2 c1an 1 c2 an 2 c1 ( 1r1 2r2 ) c2 ( 1r1 2 r2 ) r n 1 (c r c ) r n 2 (c r c ) 1 1 1 1 2 2 2 1 2 2 n 2 2 n 2 2 1r1 r1 2r2 r2 n n 1r1 2r2 an n n Điều này chứng tỏ dãy {an} với an 1r1 2 r2 là nghiệm của hệ thức truy hồi đã cho. ():Để chứng minh ngược lại, ta giả sử dãy {an} là một nghiệm bất kỳ của hệ thức truy n n hồi. Ta chọn 1, 2 sao cho dãy {an} với an 1r1 2 r2 thoả mãn các điều kiện đầu a0 =C0, a1 = C1. Thực vậy, a C 0 0 1 2 a1 C1 1r1 2r2 Từ phương trình đầu ta có 2 = C0 - 1 thế vào phương trình thứ hai ta có: C1 1r1 (C0 1 )r2 1 (r1 r2 ) C0 r2 ; Từ đây suy ra: (C1 C0 r2 ) (C1 C0r2 ) (C0 r1 C1 ) 1 ; 2 C0 1 C0 . r1 r2 r1 r2 r1 r2 n n Như vậy, khi chọn những giá trị trên cho 1, 2 dãy {an} với an 1r1 2 r2 thoả mãn các điều kiện đầu. Vì hệ thức truy hồi và các điều kiện đầu được xác định duy nhất n n nên an 1r1 2 r2 . Định lý được chứng minh. Ví dụ 1. Tìm nghiệm của hệ thức truy hồi an = an-1 +2an-2 với a0 = 2, a1 = 7. Lời giải. Phương trình đặc trưng của hệ thức truy hồi có dạng r2 - r - 2 =0. Nghiệm của nó là r=2 và r = -1. Theo địnhPTIT lý 1, dãy {an } là nghiệm của hệ thức truy hồi nếu và chỉ nếu : n n an = 12 + 2(-1) với 1, 2 là các hằng số nào đó. Từ các điều kiện đầu suy ra: a0 = 2 = 1 + 2 a1 = 7 = 12 + 2(-1) Giải ra ta được 1=3, 2=-1. Vậy nghiệm của biểu thức truy hồi với điều kiện đầu là dãy n n {an} với an = 3.2 –(-1) . Ví dụ 2. Tìm công thức hiển của các số fibonaci. Giải: Các số fibonaci thoả mãn hệ thức fn = fn-1 + fn-2 và các điều kiện đầu f0 = 0, f1=1. Các nghiệm của phương trình đặc trưng là: 35
1 5 1 5 r ; r theo định lý 1 ta suy ra số fibonaci được cho bởi công 1 2 2 2 thức sau: n n 1 5 1 5 f với , là hai hằng số. Các điều kiện đầu f =0, n 1 2 1 2 0 2 2 f1=1 được dùng để xác định các hằng số 1, 2. f 0 1 2 0 1 5 1 5 f 1 1 1 2 2 2 1 1 Từ hai phương trình này ta suy ra 1 ; 2 do đó các số fibonaci được cho 5 5 bằng công thức dạng hiển như sau: n n 1 1 5 1 1 5 f n 5 2 5 2 Định lý 1 không dùng được trong trường hợp nghiệm của phương trình đặc trưng là nghiệm bội. Khi phương trình đặc trưng có nghiệm bội ta sử dụng định lý sau. 2 Định lý 2. Cho c1, c2 là các hằng số thực, c2 0. Giả sử r –c1r –c2 = 0 chỉ có một nghiệm r0. Dãy {an} là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi n n an 1r0 2 nr0 với n = 1, 2, . . trong đó 1, 2 là những hằng số. Ví dụ 3. Tìm nghiệm của công thức truy hồi an = 6an-1 –9an-2 với các điều kiện đầu a0=1, a1 = 6. Giải: Phương trình đặc trưng r2 – 6r –9 =0 có nghiệm kép r=3. Do đó nghiệm của hệ thức truy hồi có dạng: a 3n n3n với 1, 2 là các hằng số nào đó. Từ các điều kiện đầu ta suy ra: n 1 2 PTIT a0 = 1= 1 a1 = 6 = 13+ 23 1 =1, 2=1 vậy nghiệm của hệ thức truy hồi và các điều kiện đầu đã cho là: n n an = 3 +n3 Định lý 1, Định lý 2 không dùng được trong trường hợp nghiệm của phương trình đặc trưng là nghiệm phức. Khi phương trình đặc trưng có nghiệm phức ta sử dụng định lý sau. 2 Định lý 3. Cho c1, c2 là các hằng số thực, c2 0. Giả sử r –c1r –c2 = 0 có hai nghiệm phức liên hợp 36
r1 r cos  i.sin  r2 r cos  i.sin  Khi đó, dãy {an} là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi n an r 1 cos n 2 sin n với n = 1, 2, . . trong đó 1, 2 là những hằng số. Ví dụ. Tìm nghiệm của hệ thức truy hồi sau an = 2an-1 - 4an-2, với a0 = 4, a1 =4? Lời giải. Bước 1. Tìm nghiệm của phương trình đặc trưng: r1 2 cos /3 isin / 3 r 2 2r 4 0 r2 2 cos /3 isin /3 Bước 2. Xây dựng công thức tổng quát cho an: n n an r c1 cos(n ) c2 sin(n ) 2 c1 cos(n / 3) c2 sin(n / 3) Bước 3. Tìm các hằng số thông qua điều kiện đầu: 1 3 2 c c 4 1 2 2 2 1 1; 2 3 1 3 4 c c 4 1 2 2 2 Bước 4. Hoàn chỉnh công thức cho an. n an 2 cos n /3 3sin n /3 Bây giờ ta phát biểu kết quả tổng quát về nghiệm các hệ thức truy hồi tuyến tính thuần nhất với các hệ số hằng số. Định lý 4. Cho c , c , . . , c là PTITcác số thực. Giả sử phương trình đặc trưng 1 2 k k k-1 r – c1r -. .-ck = 0 có k nghiệm phân biệt r1, r2, . . , rk. Khi đó dãy {an} là nghiệm của hệ thức truy hồi an c1an 1 c2 an 2  ck an k khi và chỉ khi n n n an 1r1 2 r2  k rk với n=0,1,2, . ., trong đó 1, 2, . ., k là các hằng số. Ví dụ 4. Tìm nghiệm của hệ thức truy hồi an = 6an-1 –11an-2+6an-3 với điều kiện đầu a0=2, a1 =5, a2=15. Giải: Đa thức đặc trưng của hệ thức truy hồi là : 3 2 r – 6r + 11r – 6 có các nghiệm là r1=1, r2 = 2, r3 = 3. Do vậy nghiệm của hệ thức n n n truy hồi có dạng: an 11 2 2 3 3 . 37
Để tìm các hằng số 1, 2, 3 ta dựa vào những điều kiện ban đầu: a0 = 2 = 1 + 2 + 3 a1 = 5 = 1 + 22 + 33 a2 = 15= 1 + 24 + 39 Giải: hệ phương trình này ta nhận được 1 = 1, 2 =- 1, 3=2. Vì vậy nghiệm duy nhất của hệ thức truy hồi này và các điều đầu đã cho là dãy {an} với: n n an 1 2 2.3 2.5. Qui về các bài toán đơn giản Một trong những phương pháp giải quyết bài toán đếm phức tạp là qui bài toán đang xét về những bài toán nhỏ hơn. Sự phân chia này được thực hiện một cách liên tiếp cho tới khi nhận được lời giải của bài toán nhỏ một cách dễ dàng. Tuy nhiên điều này không phải lúc nào cũng thực hiện được vì nó đòi hỏi một sự phân tích sâu sắc cấu hình cần đếm. Giả sử rằng có một thuật toán phân chia bài toán cỡ n thành a bài toán nhỏ, trong đó mỗi bài toán nhỏ có cỡ n/b(để đơn giản ta giả sử n chia hết cho b); trong thực tế các bài toán nhỏ thường có cỡ là số nguyên gần nhất với n/b. Giả sử tổng các phép toán thêm vào khi thực hiện phân chia bài toán cỡ n thành các bài toán cỡ nhỏ hơn là g(n). Khi đó nếu f(n) là số các phép toán cần thiết để giải bài toán đã cho thì f thoả mãn hệ thức truy hồi sau: n f (n) af g(n) ; hệ thức này có tên là hệ thức chia để trị. b Ví dụ 1. Xét thuật toán nhân hai số nguyên kích cỡ 2n bít. Kỹ thuật này gọi là thuật toán nhân nhanh có dùng kỹ thuật chia để trị. Giải: Giả sử a và b là các số nguyên có biểu diễn nhị phân là 2n bít (có thể thêm các bít 0 vào đầu để chúng có thểPTIT dài bằng nhau) . a (a2n 1a2n 2 a1a0 ) 2 và b (b2n 1b2n 2 b1b0 ) 2 n n Giả sử a = 2 A1 +A0, b = 2 B1 +B0 trong đó A1 (a2n 1a2n 2 an 1an ) 2 ; A0 (an 1an 2 a1a0 )2 B1 (b2n 1b2n 2 bn 1bn ) 2 ; B0 (bn 1bn 2 b1b0 ) 2 Thuật toán nhân nhanh được dựa trên đẳng thức: 2n n n n ab (2 2 )A1 B1 2 (A1 A0 )(B0 B1 ) (2 1)A0 B0 38
Điều này chỉ ra rằng phép nhân hai số nguyên 2n bít có thể thực hiện bằng cách dùng 3 phép nhân các số nguyên n bít và các phép cộng, trừ dịch chuyển. Như vậy, nếu f(n) là tổng các phép toán nhị phân cần thiết để nhân hai số n bít thì f (2n) 3 f (n) Cn Ba phép nhân các số nhị phân n bít cần 3f(n) phép toán nhị phân. Mỗi một phép toán cộng, trừ, dịch chuyển dùng một hằng số nhân với n lần chính là Cn. Ví dụ 2. Bài toán xếp khách của Lucas. Có một bàn tròn, xung quanh có 2n ghế. Cần sắp chỗ cho n cặp vợ chồng sao cho các ông ngồi sen kẽ các bà và không có hai cặp vợ chồng nào ngồi cạnh nhau. Hỏi có tất cả bao nhiêu cách xếp ? Lời giải. Gọi số phải tìm là Mn. Xếp cho các bà trước(cứ xếp một ghế thì một ghế để trống dành cho các ông), số cách xếp cho các bà là 2n! cách. Gọi số cách xếp cho các ông ứng với một cách xếp các bà là Un ta được số cách xếp là Mn = 2n! x Un .Vấn đề còn lại là tính số Un. Đánh số các bà (đã xếp) từ 1 đến n, đánh số các ông tương ứng với các bà (ông i là chồng bà i), sau đó đánh số các ghế trống theo nguyên tắc: ghế số i nằm giữa bà i và bà i+1 (các phép cộng được hiểu lấy modul n nghĩa là n +1 = 1). Mỗi cách xếp các ông được biểu diễn bằng một phép thế trên tập {1, 2, . ., n } với qui ước (i) = j có nghĩa là ghế i được xếp cho ông j. Theo giả thiết phải thoả mãn: (i) i và (i) i+1 (*) Như vậy, Un là số tất cả các phép thế thoả mãn điều kiện (*). Trong toán học gọi Un là số phân bố. Xét tập hợp tất cả các phép thế của { 1, 2, . ., n }. Trên tập này ta gọi Pi là tính chất (i) = i, Qi là tính chất (i) = i+1. Đặt Pn+i = Qi, theo nguyên lý bù trừ tương ứng với 2n tính chất Pi ta có: U n N n! N1 N 2 trong đó Nk là tổng số tất cả các phép thế thoả mãn k tính chất lấy từ 2n tính chất đang xét. Cần chú ý rằng, không thể xảy ra đồng thời thoả mãn P và Q . Do đó trong các phépPTIT lấy ra k tính chất từ 2n tính chất đang xét cần thêm i i vào điều kiện: Pi và Qi hoặc Pi+1 và Qi không được đồng thời có mặt. Gọi số các cách này là g(2n, k) ( nói riêng g(2n,k)=0 khi k>n). Với mỗi cách lấy ra k tính chất như vậy (k<=n) ta có (n-k)! phép thế thảo mãn chúng. Từ đó ta nhận được Nk = g(2n, k) (n-k)! và n U n n! g(2n,1)(n 1)! g(2n 2)(n 2)!  ( 1) g(2n,n) Bây giờ chúng ta phải tính các hệ số g(2n,k), k = 1, 2, . ., n. Xếp 2n tính chất đang xét trên còng tròn theo thứ tự P1, Q1, P2, Q2, . . , Pn, Qn, ta thấy rằng g(2n,k) chính là số cách lấy k phần tử trong 2n phần tử xếp thành vòng tròn sao cho không có hai phần tử nào kề nhau cùng được lấy ra. Để tính g(2n,k) ta giải hai bài toán con sau: 39
Bài toán 1. Có bao nhiêu cách lấy ra k phần tử trong n phần tử xếp trên đường thẳng sao cho không có hai phần tử nào kề nhau cùng được lấy ra. Lời Giải. Khi lấy k phần tử, ta còn n-k phần tử. Giữa n-k phần tử còn lại có n-k+1 khoảng trống (kể cả hai đầu). Mỗi cách lấy ra k khoảng từ các khoảng này sẽ tương ứng với một cách chọn k phần tử thoả mãn yêu cầu đã nêu. Vậy số cách chọn cần tìm là C(n-k+1, k). Bài toán 2. Giống như bài toán 1 nhưng n phần tử xếp trên vòng tròn. Lời giải. Cố định phần tử a được chọn chia các cách lấy thành 2 lớp 1- Các cách mà a được chọn khi đó 2 phần tử kề a sẽ không được chọn và phải lấy k-1 phần tử từ n-3 phần tử còn lại. Các phần tử này xem như kết quả của bài toán 1. Theo bài toán 1, số cách thuộc lớp kiểu này là C(n-k-1, k-1). 2- Các cách mà a không được chọn, khi đó bỏ a đi và bài toán trở về bài toán 1 chọn k phần tử từ n-1 phần tử xếp trên đường thẳng. Theo bài toán 1 số cách xếp kiểu này là C(n-k,k). Vậy theo nguyên lý cộng số cách cần tìm là : n C(n k 1,k 1) C(n k,k) C(n k,k) n k Từ kết quả của hai bài toán trên ta nhận được: 2n g(2n,k) C(2n k,k)và số phân bố Un được tính bằng 2n k 2n 2n 2n U n! C(2n 1,1)(n 1)! C(2n 2,2)(n 2)!  ( 1) n C(2n,n) n 2n 1 2n 2 n Dưới đây là một số giá trị của Un, một lần nữa chúng ta lại được quan sát hiện tượng bùng nổ tổ hợp. n 2 3 4 PTIT5 6 7 8 9 10 Un 0 1 2 13 80 579 4783 43387 439792 2.6. Phương pháp liệt kê Việc tìm một công thức cho kết quả đếm ngay cả trong trường hợp công thức truy hồi không phải dễ dàng và lúc nào cũng thực hiện được. Cho đến nay còn nhiều bài toán đếm chưa có lời giải dưới dạng một công thức. Đối với những bài toán như vậy, người ta chỉ còn cách chỉ ra một phương pháp liệt kê, theo đó có thể đi qua được tất cả các cấu hình cần đếm. Rõ ràng bản thân phương pháp liệt kê không chỉ ra được một kết quả cụ thể nào nhưng qua đó người ta có thể lập trình cho máy tính điện tử đếm hộ. 40
Để minh hoạ cho phương pháp liệt kê, ta xét một cấu hình tổ hợp nổi tiếng đó là các hình chữ nhật la tinh. Giả sử S là tập gồm n phần tử. Không mất tính tổng quát ta giả sử S = {1, 2, . ., n} Một hình chữ nhật la tinh trên S là một bảng gồm p dòng, q cột sao cho mỗi dòng của nó là một chỉnh hợp không lặp chập q của S và mỗi cột của nó là một chỉnh hợp không lặp chập p của S. Theo định nghĩa ta có p n, q n. Đặc biệt trong trường hợp q = n, mỗi dòng của hình chữ nhật la tinh là một hoán vị của S, sao cho không có cột nào chứa hai phần tử lặp lại. Hình chữ nhật la tinh dạng này được gọi là chuẩn nếu dòng đầu của nó là hoán vị 1, 2,. ., n. Ví dụ. Hình la tinh chuẩn trên tập S = {1, 2, 3, 4, 5, 6, 7 } 1 2 3 4 5 6 7 2 3 4 5 6 7 1 3 4 5 6 7 1 2 Gọi L(p,n) là số hình chữ nhật la tinh p x n, còn K(p,n) là số hình chữ nhật la tinh chuẩn p x n ta có: L(p,n) = n! K(p,n) Dễ dàng nhận thấy rằng, số mất Dn là số hình la tinh chuẩn 2 x n, số phân bố Un là số hình chữ nhật la tinh chuẩn 3 x n với hai dòng đầu là: 1 2 . . . n-1 n 2 3 . . . n 1 Riodan J(1946) đã chứng minh công thức: m K(3,n) k 0 C(n,k)Dn k DkU n 2k trong đó m= [n/2], U0 = 1. Bài toán đếm với số dòng nhiều hơn đến nay vẫn chưa được giải quyết. Người ta mới chỉ đưa ra được một vài dạngPTIT tiệm cận của L(p,n). Nếu p=q=n, thì hình chữ nhật la tinh được gọi là hình vuông la tinh. Một hình vuông la tinh cấp n được gọi là chuẩn nếu có dòng đầu và cột đầu là hoán vị 1, 2,. .n. Thí dụ một hình vuông la tinh chuẩn cấp 7. 1 2 3 4 5 6 7 2 3 4 5 6 7 1 3 4 5 6 7 1 2 4 5 6 7 1 2 3 5 6 7 1 2 3 4 6 7 1 2 3 4 5 41
7 1 2 3 4 5 6 Gọi ln là số các hình vuông như thế ta có L(n,n) = n!(n-1)!ln Việc tìm một công thức cho ln đến nay vẫn bỏ ngỏ. Tuy nhiên ta có thể nhờ máy tính liệt kê tất cả các hình vuông chuẩn cấp n. Dưới đây là một vài giá trị tính được. N 1 2 3 4 5 6 7 ln 1 1 1 4 56 9408 16942080 PTIT 42
BÀI TẬP CHƯƠNG 2 1. Xâu thuận nghịch độc là một xâu khi viết theo thứ tự ngược lại cũng bằng chính nó. Hãy đếm số xâu nhị phân có độ dài n là thuận nghịch độc. 2. Cô dâu và chú rể mời bốn bạn đứng thành một hàng để chụp ảnh. Hỏi có bao nhiêu cách xếp hàng nếu: a) Cô dâu đứng cạnh chú rể b) Cô dâu không đứng cạnh chú rể c) Cô dâu đứng ở phía bên phải chú rể 3. Có bao nhiêu xâu nhị phân độ dài 10 có năm số 0 liền nhau hoặc năm số 1 liến nhau. 4. Có bao nhiêu xâu nhị phân độ dài bằng 8 có 3 số 0 liền nhau hoặc 4 số 1 liền nhau. 5. Mỗi sinh viên lớp toán học rời rạc hoặc giỏi toán hoặc giỏi tin học hoặc giỏi cả hai môn này. Trong lớp có bao nhiêu sinh viên nếu 38 người giỏi tin (kể cả người giỏi cả hai môn), 23 người giỏi toán (kể cả người giỏi cả hai môn), và 7 người giỏi cả hai môn. 6. Chứng tỏ rằng, trong n+1 số nguyên dương không vượt quá 2n tồn tại ít nhất một số chia hết cho một số khác. 7. Chứng minh rằng, trong dãy gồm n2 + 1 số thực phân biệt đều có một dãy con dài n+1 hoặc thực sự tăng, hoặc thực sự giảm. 8. Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn, hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn của nhau hoặc là kẻ thù của nhau. 9. Hãy chỉ ra rằng, trong 102 người có chiều cao khác nhau đứng thành một hàng có thể tìm được 11 người có chiều PTITcao tăng dần hoặc giảm dần mà không cần thay đổi thứ tự của họ trong hàng. 10. Một đô vật tay tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta thi đấu ít nhất một trận, nhưng toàn bộ anh ta không thi đấu quá 125 trận. Chứng tỏ rằng, có những giờ liên tiếp anh ta thi đấu 24 trận. 11. Một nhân viên bắt đầu làm việc tại công ty từ năm 1987 với mức lương khởi điểm là 50000 đô la. Hàng năm anh ta được nhận thêm 1000 đô la và 5% lương của năm trước. a) Hãy thiết lập hệ thức truy hồi tính lương của nhân viên đó n năm sau năm 1987. b) Lương vào năm 1995 của anh ta là bao nhiêu? c) Hãy tìm công thức tường minh tính lương của nhân viên này n năm sau năm 1987. 43
12. Tìm hệ thức truy hồi cho số hoán vị của tập n phần tử. Dùng hệ thức truy hồi đó tính hoán vị của tập n phần tử. 13. Một máy bán tem tự động chỉ nhận các đồng xu một đô la và các loại tờ tiền 1 đô la và 5 đô la. a) Hãy tìm hệ thức truy hồi tính số cách đặt n đô la vào trong máy bán hàng, trong đó thứ tự các đồng xu, các tờ tiền là quan trọng. b) Tìm các điều kiện đầu. c) Có bao nhiêu cách đặt 10 đô la vào máy để mua một bộ tem. 14. Giải các hệ thức truy hồi với các điều đầu sau: a) an = an-1 + 6an-2 với n 2, a0 = 3, a1 = 6. b) an = 7an-1 - 6an-2 với n 2, a0 = 2, a1 = 1. c) an = 6an-1 - 8an-2 với n 2, a0 = 4, a1 = 10. d) an = 2an-1 - an-2 với n 2, a0 = 4, a1 = 1. e) an = an-2 với n 2, a0 = 5, a1 = -1. f) an = -6an-1 - 9an-2 với n 2, a0 = 3, a1 = -3. g) an+2 = -4an+1 + 5an với n 0, a0 = 2, a1 = 8. 15. Tìm các nghiệm đặc trưng của hệ thức truy hồi tuyến tính thuần nhất a) an = 2an-1 - 2an-2 b) Tìm nghiệm thoả mãn hệ thức truy hồi trên và các điều kiện đầu a0 =1, a1 =2. 16. a) Tìm nghiệm đặc trưng của hệ thức truy hồi tuyến tính thuần nhất an = an-4 b) Tìm nghiệm thoả mãn hệ thức truy hồi trên và các điều kiện đầu a0=1, a1=0, a2=-1, a3=1. 17. Một báo cáo về thị trường máy tính cá nhân cho biết có 65000 người sẽ mua modem cho máy tính của họ trong PTITnăm tới, 1 250 000 người sẽ mua ít nhất một sản phẩm phần mềm. Nếu báo cáo này nói rằng 1.450.000 người sẽ mua hoặc là modem hoặc là ít nhất một sản phẩm phần mềm thì sẽ có bao nhiêu người sẽ mua cả modem và mua ít nhất một sản phẩm phần mềm. 44
CHƯƠNG 3. BÀI TOÁN LIỆT KÊ Nội dung bài toán đếm là đếm xem có bao nhiêu cấu hình tổ hợp thỏa mãn một số tính chất nào đó. Bài toán liệt không chỉ đếm được các cấu hình tổ hợp thỏa mãn các tính chất đặt ra mà còn xem xét từng cấu hình tổ hợp đó là gì. Đối với mỗi bài toán, khi chưa tìm được thuật giải thì liệt kê được xem là biện pháp cuối cùng để thực hiện với sự hỗ trợ của máy tính. Có thể nói, liệt kê được xem là phương pháp giải vạn năng một bài toán bằng máy tính. Nội dung chính của chương này tập chung giải quyết những vấn đề cơ bản sau:  Giới thiệu bài toán liệt kê.  Thuật toán và độ phức tạp tính toán.  Giải quyết bài toán liệt kê bằng phương pháp sinh.  Giải quyết bài toán liệt kê bằng phương pháp quay lui. Bạn đọc có thể tìm thấy cách giải nhiều bài toán liệt kê trong các tài liệu [1] và [2] trong tài liệu tham khảo. 3.1- Giới thiệu bài toán Bài toán đưa ra danh sách tất cả các cấu hình tổ hợp có thể có được gọi là bài toán liệt kê tổ hợp. Khác với bài toán đếm là tìm kiếm một công thức cho lời giải, bài toán liệt kê lại cần xác định một thuật toán để theo đó có thể xây dựng được lần lượt tất cả các cấu hình cần quan tâm. Một thuật toán liệt kê phải đảm bảo hai nguyên tắc: Không được lặp lại bất kỳ một cấu hình nào. Không được bỏ sót bất kỳ một cấu hình nào. Ví dụ 1. Cho tập hợp các số a1, a2, , an và số M. Hãy tìm tất cả các tập con k phần tử của dãy số {an} sao cho tổng số các PTITphần tử trong tập con đó đúng bằng M. Lời giải: Như chúng ta đã biết, số các tập con k phần tử của tập gồm n phần tử là C(n,k). Như vậy chúng ta cần phải duyệt trong số C(n,k) tập k phần tử để lấy ra những tập có tổng các phần tử đúng bằng M. Vì không thể xác định được có bao nhiêu tập k phần tử từ tập n phần tử có tổng các phần tử đúng bằng M nên chúng ta chỉ còn cách liệt kê các cấu hình thoả mãn điều kiện đã cho. Ví dụ 2. Một thương nhân đi bán hàng tại tám thành phố. Chị ta có thể bắt đầu hành trình của mình tại một thành phố nào đó nhưng phải qua 7 thành phố kia theo bất kỳ thứ tự nào mà chị ta muốn. Hãy chỉ ra lộ trình ngắn nhất mà chị ta có thể đi. Lời giải: Vì thành phố xuất phát đã được xác định. Do vậy thương nhân có thể chọn tuỳ ý 7 thành phố còn lại để hành trình. Như vậy, tất cả số hành trình của thương nhân có thể 45
đi qua là 7! = 5040 cách. Tuy nhiên trong 5040 cách chúng ta phải duyệt toàn bộ để chỉ ra một hành trình là ngắn nhất. Có thể nói phương pháp liệt kê là biện pháp cuối cùng nhưng cũng là biện pháp phổ dụng nhất để giải quyết các bài toán tổ hợp. Khó khăn chính của phương pháp này là sự bùng nổ tổ hợp. Để xây dựng chừng 1 tỷ cấu hình (con số này không phải là lớn đối với các bài toán tổ hợp như số mất thứ tự Dn, số phân bố Un, số hình vuông la tinh ln), ta giả sử cần 1 giây để liệt kê một cấu hình thì chúng ta cũng cần 31 năm mới giải quyết xong. Tuy nhiên với sự phát triển nhanh chóng của máy tính, bằng phương pháp liệt kê, nhiều bài toán khó của lý thuyết tổ hợp đã được giải quyết và góp phần thúc đẩy sự phát triển của nhiều ngành toán học. 3.2. Thuật toán và độ phức tạp tính toán 3.2.1. Ví dụ và Định nghĩa Định nghĩa. Dãy hữ hạn các thao tác sơ cấp F=F1F2 Fn(Input) Output được gọi là một thuật toán trên tập thông tin vào Input để có được kết qua ra Output. Dãy các thao tác sơ cấp ở đây được hiểu là các phép toán số học, các phép toán logic, các phép toán so sánh. Một thuật toán cần thỏa mãn các tính chất dưới đây: • Tính đơn định. Ở mỗi bước của thuật toán, các thao tác sơ cấp phải hết sức rõ ràng, không gây nên sự lộn xộn, nhập nhằng, đa nghĩa. Thực hiện đúng các bước của thuật toán trên tập dữ liệu vào, chỉ cho duy nhất một kết quả ra. • Tính dừng. Thuật toán không được rơi vào quá trình vô hạn. Phải dừng lại và cho kết quả sau một số hữu hạn các bước. • Tính đúng. Sau khi thực hiện tất cả các bước của thuật toán theo đúng qui trình đã định, ta phải nhận được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó được kiểm chứng bằng yêu cầu của bài toán. • Tính phổ dụng. Thuật toán phải dễ sửa đổi để thích ứng được với bất kỳ bài toán nào trongPTIT lớp các bài toán cùng loại và có thể làm việc trên nhiều loại dữ liệu khác nhau. • Tính khả thi. Thuật toán phải dễ hiểu, dễ cài đặt, thực hiện được trên máy tính với thời gian cho phép. 3.2.2. Phương pháp biểu diễn thuật toán: Thông thường, để biểu diễn một thuật toán ta có thể sử dụng các phương pháp sau: • Biểu diễn bằng ngôn ngữ tự nhiên. Ngôn ngữ tự nhiên là phương tiện giao tiếp giữa con người với con người. Ta có thể sử dụng chính ngôn ngữ này vào việc biểu diễn thuật toán. 46
• Ngôn ngữ hình thức. Ngôn ngữ hình thức là phương tiện giao tiếp trung gian giữa con người và hệ thống máy tính. Ví dụ ngôn ngữ sơ đồ khối, ngôn ngữ tựa tự nhiên, ngôn ngữ đặc tả. Đặc điểm chung của các loại ngôn ngữ này là việc sử dụng nó rất gần với ngôn ngữ tự nhiên và ngôn ngữ máy tính. • Ngôn ngữ máy tính. Là phương tiện giao tiếp giữa máy tính và máy tính. Trong trường hợp này ta có thể sử dụng bất kỳ nôn ngữ lập trình nào để mô tả thuật toán. Ghi chú. Trong các phương pháp biểu diễn thuật toán, phương pháp biểu diễn bằng ngôn ngữ hình thức được sử dụng rộng dãi vì nó gần với ngôn ngữ tự nhiên và không phụ thuộc vào ngôn ngữ máy tính. Ví dụ 1. Biểu diễn thuật toán tìm USCLN (a, b) bằng ngôn ngữ tự nhiên. Đầu vào (Input). Hai số tự nhiên a, b. Đầu ra (Output). Số nguyên u lớn nhất để a và b đều chia hết cho u. Thuật toán (Euclide Algorithm): Bước 1. Đưa vào hai số tự nhiên a và b. Bước 2. Nếu b 0 thì chuyển đến bước 3, nếu b=0 thì thực hiện bước 4. Bước 3. Đặt r = a mod b; a = b; b = r ; Sau đó quay trở lại bước 2. Bước 4 (Output). Kết luận u=a là số nguyên cần tìm. Ví dụ 2. Biểu diễn Biểu diễn thuật toán tìm USCLN (a, b)bằng ngôn ngữ hình thức. Thuật toán Euclide: Đầu vào (Input): a N, a N. Đầu ra (Output): s = max { u N : a mod u =0 and b mod u =0}. Format : s = Euclide (a, b). Actions : PTIT while (b 0 ) do r = a mod b; a = b; b = r; endwhile; return(a); Endactions. Ví dụ 3. Biểu diễn thuật toán tìm USCLN (a, b) bằng ngôn ngữ máy tính (C++). Int USCLN( int a, int b) { while ( b != 0 ) { r = a % b; a = b; b = r; 47
} return(a); } 3.2.3. Độ phức tạp tính toán Một bài toán có thể thực hiện bằng nhiều thuật toán khác nhau. Chọn giải thuật nhanh nhất giải bài toán là một nhu cầu của thực tế. Vì vậy ta cần phải có sự ước lượng cụ thể để minh chứng bằng toán học mức độ nhanh chậm của mỗi giải thuật. Khái niệm độ phức tạp thuật toán: Thời gian thực hiện một giải thuật bằng chương trình máy tính phụ thuộc vào các yếu tố: • Kích thước dữ liệu vào: Dữ liệu càng lớn thì thời gian xử lý càng chậm. • Phần cứng máy tính: máy có tốc độ cao thực hiện nhanh hơn trên máy có tốc độ thấp. Tuy vậy, yếu tố này không ảnh hưởng đến quá trình xác định thời gian thực hiện của thuật toán nếu xem xét thời gian thực hiện thuật toán như một hàm của độ dài dữ liệu T(n). Tổng quát, cho hai hàm f(x), g(x) xác định trên 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. Hàm f(x) được gọi là O(g(x)) nếu tồn tại một hằng số C>0 và n0 sao cho: |f(x)| ≤C.|g(x)| vớ mọi x≥n0. Điều này có nghĩa với các giá trị x ≥n0 hàm f(x) bị chặn trên bởi hằng số C nhân với g(x). Nếu f(x) là thời gian thực hiện của một thuật toán thì ta nói giải thuật đó có cấp g(x) hay độ phức tạp thuật toán là O(g(x)). Ghi chú. Các hằng số C, n0 thỏa mãn điều kiện trên là không duy nhất. Nếu có đồng thời f(x) là O(g(x)) và h(x) thỏa mãnPTIT g(x) n0 thì ta cũng có f(x) là O(h(n)). n n 1 Ví dụ 1. Cho f x an x an 1 x a1 x a0 . Trong đó, ai là các số thực (i =0,1, 2, ,n). Khi đó f(x) = O(xn). Chứng minh. Thực vậy, với mọi x>1: 48
n n 1 f x an x an 1 x a1 x a0 n n 1  an x an 1 x a1 x a0  a x n a x n a x n a x n n n 1 1 0 n  x an an 1 a1 a0  C.x n O(x n ). C an an 1 a1 a0 PTIT 49
Ví dụ 2. Tìm độ phức tạp thuật toán sắp xếp kiểu Bubble-Sort? Void Bubble-Sort ( int A[], int n ) { for ( i=1; i A[j]) { t = A[i]; A[i] = A[j]; A[j] = t; } } } } Lời giải. Sử dụng trực tiếp nguyên lý cộng ta có: • Với i =1 ta cần sử dụng n-1 phép so sánh A[i] với A[j]; • Với i = 2 ta cần sử dụng n-1 phép so sánh A[i] với A[j]; • . . . . . • Với i = n-1 ta cần sử dụng 1 phép so sánh A[i] với A[j]; Vì vậy tổng số các phép toán cần thực hiện là: S = (n-1) + (n-2) + . . . + 2 + 1 = n(n-1)/2 n2 = O(n2). Ghi chú. Độ phức tạp thuật toán cũng là số lần thực hiện phép toán tích cực. Phép toán tích cực là phép toán thực hiện nhiều nhất đối với thuật toán. Một số tính chất của độ phức tạp thuật toán: • Với P(n) là một đa thức bậc k thì O(P(n)) = O(nk). Vì thế ta nói, một thuật toán có độ phức tạp cấp đa thức là O(nk). • Với a, b là hai PTIT cơ số tùy ý và f(n) là một hàm xác định dương thì logaf(n)=logab.logb(f(n)). Vì vậy độ phức tạp thuật toán cấp logarit được ký hiệu là O(log(f(n)) mà không cần quan tâm đến cơ số. • Nếu độ phức tạp thuật toán là hằng số, nghĩa là thời gian tính toán không phụ thuộc vào độ dài dữ liệu được ký hiệu là O(1). • Một giải thuật có cấp 2n, n!, nn được gọi là giải thuật hàm mũ. Những giải thuật này thường có tốc đọ rất chậm. • Độ phức tạp tính toán của một đoạn chương trình P chính bằng số lần thực hiện một phép toán tích cực. Trong đó, phép toán tích cực trong một đoạn chương trình là phép toán mà số lần thực hiện nó không ít hơn các phép toán khác. 50
Các dạng hàm đánh giá độ phức tạp thuật toán: Dạng đánh giá Tên gọi O(1) Hằng số O(lg lg n) Log log O(lg n) Logarithm O(n) Tuyến tính O(n2) Bậc hai O(n3) Bậc 3 O(nm) Đa thức O(mn) Hàm mũ O(n!) Giai thừa 3.2.4. Qui tắc xác định độ phức tạp thuật toán Qui tắc tổng: Nếu f1(x) có độ phức tạp là O(g1(x)) và f2(x) có độ phức tạp là O(g2(x)) thì độ phức tạp của (f1(x) + f2(x) là O( Max(g1(x), g2(x)). Chứng minh. • Vì f1(x) có độ phức tạp là O(g1(x) nên tồn tại hằng số C1 và k1 sao cho |f1(x)| |g1(x)| với mọi x k1; • Vì f2(x) có độ phức tạp là O(g2(x)) nên tồn tại hằng số C2 và k2 sao cho |f2(x)| |g2(x)| với PTITmọi x k2; • Ta lại có : |f1(x)+ f2(x)| |f1(x)| + |f2(x)| C1|g1(x)| + C2|g2(x)| C|g(x)| với mọi x >k; Trong đó, C = C1 + C2; g(x) = max( g1(x), g2(x)); k = max (k1, k2). Tổng quát. Nếu độ phức tạp của f1(x), f2(x), , fm(x) lần lượt là O(g1(x)), O(g2(x)), , O(gn(x)) thì độ phức tạp của f1(x) + f2(x) + +fm(x) là O(max(g1(x), g2(x), ,gm(x)). 51
Qui tắc nhân: Nếu f(x) có độ phức tạp là O(g(x) thì độ phức tạp của fn(x) là O(gn(x). Trong đó: fn(x) = f(x).f(x) .f(x). //n lần f(x). gn(x) = g(x).g(x) g(x).//n lần g(x) Nói cách khác, đoạn chương trình P có thời gian thực hiện T(n)= O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) là O(g(n)) thì độ phức tạp tính toán là O(f(n). g(n)). Chứng minh. Thật vậy theo giả thiết f(x) là O(g(x)) nên tồn tại hằng số C và k sao cho với mọi x>k thì |f(x)| C.|g(x). Ta có: f n x f 1 x . f 2 x f n x C.g 1 x .C.g 2 x C.g n x C n g n x O g n x 3.3. Phương pháp sinh Phương pháp sinh có thể áp dụng để giải các bài toán liệt kê tổ hợp đặt ra nếu như hai điều kiện sau được thực hiện: (i) Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể xác định được cấu hình tổ hợp đầu tiên và cuối cùng trong thứ tự đã được xác định. (ii) Xây dựng được thuật toán từ cấu hình chưa phải là cuối cùng đang có để đưa ra cấu hình kế tiếp sau nó. Ta gọi thuật toán trong điều kiện (ii) là thuật toán sinh kế tiếp. Rõ ràng thuật toán này chỉ thực hiện được khi có một cấu hình được xác định theo điều kiện (i). Giả sử một bài toán đều thoả mãn các điều kiện trên, khi đó phương pháp sinh kế tiếp có thể được mô tả bằng thủ tục như sau: PTIT procedure Generation ( ){ ; stop =false while (! stop) { ; ; } } 52
Ví dụ 1. Liệt kê tất cả các dãy nhị phân độ dài n. Lời giải. Viết dãy nhị phân dưới dạng b1b2 bn, trong đó bi {0, 1 }. Xem mỗi dãy nhị phân b=b1b2 bn là biểu diễn nhị phân của một số nguyên p(b). Khi đó thứ tự hiển nhiên nhất có thể xác định trên tập các dãy nhị phân là thứ tự từ điển được xác định như sau: Ta nói dãy nhị phân b = b1b2 bn đi trước dãy nhị phân b’ = b’1b’2 b’n theo thứ tự từ điển và ký hiệu b i. Dãy thu được là dãy cần tìm. Ví dụ với xâu nhị phân đPTITộ dài 10: 1100111011. Ta có i = 8, ta đặt b8 =1, b9,b10 =0 ta được xâu nhị phân kế tiếp: 1100111100. Thuật toán sinh kế tiếp được mô tả trong thủ tục sau: void Next_Bit_String( void ){ int i = n;//Xuất phát tại i=n while (i> 0 && bi !=0 ) { //Nếu bi=1 thì gán thành 0 bi = 0; i = i-1; } if ( i > 0 ) bi = 1; //Nếu chưa là cấu hình cuối cùng thì i>0 else OK = False; ///Nếu là cấu hình cuối cùng thì i=0 } 53
Dưới đây là chương trình liệt kê các xâu nhị phân có độ dài n. #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 int n, X[MAX], OK=TRUE, dem=0; void Init (void ){ cout >n; for (int i=1; i 0 && X[i]!=0){ X[i] = 0; i ; } if (i > 0 ) X[i] = 1; else OK = FALSE; } int main() { Init(); //Nhap n = 4 while (OK ){ Result(); Next_Bit_String(); } system("PAUSE"); return 0; } Kết quả thực hiện chương trìnhPTIT: Nhap n=4 Ket qua buoc 1:0 0 0 0 Ket qua buoc 2:0 0 0 1 Ket qua buoc 3:0 0 1 0 Ket qua buoc 4:0 0 1 1 Ket qua buoc 5:0 1 0 0 Ket qua buoc 6:0 1 0 1 Ket qua buoc 7:0 1 1 0 Ket qua buoc 8:0 1 1 1 Ket qua buoc 9:1 0 0 0 Ket qua buoc 10:1 0 0 1 Ket qua buoc 11:1 0 1 0 54
Ket qua buoc 12:1 0 1 1 Ket qua buoc 13:1 1 0 0 Ket qua buoc 14:1 1 0 1 Ket qua buoc 15:1 1 1 0 Ket qua buoc 16:1 1 1 1 Ví dụ 2. Liệt kê tập con m phần tử của tập n phần tử. Cho X = { 1, 2, . ., n }. Hãy liệt kê tất cả các tập con k phần tử của X (k n). Lời giải: Mỗi tập con của tập hợp X có thể biểu diễn bằng bộ có thứ tự gồm k thành phần a =(a1a2 ak) thoả mãn 1 a1 a2 . . ak n. Trên tập các tập con k phần tử của X có thể xác định nhiều thứ tự khác nhau. Thứ tự dễ nhìn thấy nhất là thứ tự từ điển được định nghĩa như sau: Ta nói tập con a = a1a2. . . ak đi trước tập con a’ = a1’a2’. . .ak’ trong thứ tự từ điển và ký hiệu là a<a’, nếu tìm được chỉ số j ( 1 j k ) sao cho a1 = a1’, a2 = a2’, . . ., aj-1 = a’j-1, aj < a’j. Chẳng hạn X = { 1, 2, 3, 4, 5 }, k = 3. Các tập con 3 phần tử của X được liệt kê theo thứ tự từ điển như sau: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 Như vậy, tập con đầu tiên trong thứ tự từ điển là (1, 2, . ., k) và tập con cuối cùng là (n-k+1, n-k+2, . ., n). Giả sử a = (a1, a2, . ., ak) là tập con hiện tại và chưa phải là cuối cùng, khi đó có thể chứng minhPTIT được rằng tập con kế tiếp trong thứ tự từ điển có thể được xây dựng bằng cách thực hiện các qui tắc biến đổi sau đối với tập con đang có. Tìm từ bên phải dãy a1, a2, . ., ak phần tử ai n – k + i Thay ai bởi ai +1, Thay aj bởi ai + j – i, với j:= i+1, i + 2, . . ., k Chẳng hạn với n = 6, k =4. Giả sử ta đang có tập con (1, 2, 5, 6), cần xây dựng tập con kế tiếp nó trong thứ tự từ điển. Duyệt từ bên phải ta nhận được i =2, thay a2 bởi a2 + 1 = 2 + 1 =3. Duyệt j từ i + 1 = 3 cho đến k, ta thay thế a3 = a2 + 3 – 2 = 3 + 3 - 2 = 4, a4 = a2 + 4 - 2 = 3 + 4 – 2 = 5 ta nhận được tập con kế tiếp là ( 1, 3, 4, 5). Với qui tắc sinh như trên, chúng ta có thể mô tả bằng thuật toán sau: 55
Thuật toán liệt kê tập con kế tiếp m phần tử của tập n phần tử: void Next_Combination(void){ i = k; //Xuất phát từ vị trí thứ k while ( i> 0 && ai == n-k+i) //Xác định i để ai n-k+i i = i -1; if (i>0) { //Nếu chưa phải là tổ hợp cuối cùng thì i>0 ai = ai + 1; for ( j = i+1; j #include #define MAX 100 #define TRUE 1 #define FALSE 0 int n,k,X[MAX],OK=TRUE,dem=0; void Init (void ){ cout >n; cout >k; for (int i=1; i<=k; i++) PTITX[i] =i; } void Result(void){ cout<<"\n Ket qua buoc "<<++dem<<":"; for (int i=1; i<=k; i++) cout<<X[i]<<" "; } 56
void Next_Combination(void) { int i= k; while (i>0 && X[i]==n-k+i)i ; if (i > 0 ) { X[i] = X[i] +1; for (int j = i+1; j<=k; j++) X[j] = X[i] + j - i; } else OK = FALSE; } int main() { Init(); //Nhap n = 5, k = 3 while (OK ){ Result(); Next_Combination(); } system("PAUSE"); return 0; } Kết quả thực hiện chương trình với n = 5, k= 3. Nhap n=5 Nhap k=3 Ket qua buoc 1:1 2 3 Ket qua buoc 2:1 PTIT 2 4 Ket qua buoc 3:1 2 5 Ket qua buoc 4:1 3 4 Ket qua buoc 5:1 3 5 Ket qua buoc 6:1 4 5 Ket qua buoc 7:2 3 4 Ket qua buoc 8:2 3 5 Ket qua buoc 9:2 4 5 Ket qua buoc 10:3 4 5 Ví dụ 3. Liệt kê các hoán vị của tập n phần tử. Cho X = { 1, 2, , n }. Hãy liệt kê các hoán vị từ n phần tử của X. Lời giải : Mỗi hoán vị từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự n thành phần 57
a = (a1, a2, , an) thoả mãn ai X, i = 1, 2, , n, ap aq, p q. Trên tập các hoán vị từ n phần tử của X có thể xác định nhiều thứ tự khác nhau. Tuy nhiên, thứ tự dễ thấy nhất là thứ tự từ điển được định nghĩa như sau: Ta nói hoán vị a = a1a2. . . an đi trước hoán vị a’ = a1’a2’. . .an’ trong thứ tự từ điển và ký hiệu là a<a’, nếu tìm được chỉ số k ( 1 k n ) sao cho a1 = a1’, a2 = a2’, . . ., ak-1 = a’k-1, ak < a’k. Chẳng hạn X = { 1, 2, 3, 4}. Các hoán vị các phần tử của X được liệt kê theo thứ tự từ điển như sau: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Như vậy, hoán vị đầu tiên trong thứ tự từ điển là (1, 2, , n) và hoán vị cuối cùng là (n, n-1, . . ., 1). Giả sử a = a1a2. . . an là một hoán vị chưa phải là cuối cùng. Khi đó ta có thể chứng minh được rằng, hoán vị kế tiếp trong thứ tự từ điển có thể xây dựng bằng cách thực hiện các qui tắc biến đổi sau đối với hoán vị hiện tại: Tìm từ phải qua trái hoán vị có chỉ số j đầu tiên thoả mãn aj <aj+1(hay j là chỉ số lớn nhất để aj <aj+1); Tìm ak là số nhỏ nhất còn lớn hơn aj trong các số ở bên phải aj; Đổi chỗ aj với ak Lật ngược đoạn từ aj+1 đến an. Chẳng hạn ta đang có hoán vị (3, 6, 2, 5, 4, 1), cần xây dựng hoán vị kế tiếp theo thứ tự từ điển. Ta duyệt từ j= n-PTIT1 sang bên trái để tìm j đầu tiên thoả mãn aj < aj+1 ta nhận đuợc j=3 ( a3=2<a4=5). Số nhỏ nhất còn lớn hơn a3 trong các số bên phải a3 là a5 (a5=4). Đổi chỗ a3 cho a5 ta thu đuợc (3, 6, 4, 5, 2, 1), lật ngược đoạn từ a4 đến a6 ta nhận được (3,6,4,1,2,5). Từ đó thuật toán sinh kế tiếp có thể được mô tả bằng thủ tục sau: 58
Thuật toán sinh hoán vị kế tiếp: void Next_Permutation( void ){ j = n-1; //Duyệt từ vị trí j=n-1 while (j> 0 && aj > aj +1 ) //Tìm vị trí j để aj > aj +1 j = j -1; if (j>0) { // Nếu j>0 thì hoán vị chưa phải cuối cùng k = n; //Xuất phát từ vị trí k=n while (aj > ak ) // Tìm k để aj #define MAX 100 #define TRUE 1 #define FALSE 0 int n,X[MAX],OK=TRUE,dem=0;PTIT void Init (void ){ cout >n; for (int i=1; i<=n; i++) X[i] =i; } void Result(void){ cout<<"\n Ket qua buoc "<<++dem<<":"; for (int i=1; i<=n; i++) cout<<X[i]<<" "; } 59
void Next_Permutation(void) { int j= n-1; while (j>0 && X[j]>X[j+1])j ; if (j > 0 ) { int k =n; while(X[j]>X[k]) k ; int t = X[j]; X[j]=X[k]; X[k]=t; int r = j +1, s =n; while (r b2> > bk, và duyệt theo trình tự từ điển ngược. Chẳng hạn với n = 5, chúng ta có thứ tự từ điển ngược của các cách phân chia như sau: 60
5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 1 Như vậy, cách chia đầu tiên chính là n. Cách chia cuối cùng là dãy n số 1. Bây giờ chúng ta chỉ cần xây dựng thuật toán sinh kế tiếp cho mỗi cách phân chia chưa phải là cuối cùng. Thuật toán sinh cách phân chia kế tiếp: void Next_Division(void){ int i, j, R, S, D; i = k; //Xuất phát từ cuối cách chia trước đó while(i>0 && C[i]==1) //Tìm i sao cho C[i] 1 i ; if(i>0){ // Nếu chưa phải là cách chia cuối cùng thì i>0 C[i] = C[i]-1; //Giảm C[i] đi một đơn vị. D = k - i +1; R = D / C[i]; S = D % C[i]; k = i; if(R>0){ for(j=i+1; j 0){ PTIT k=k+1; C[k] = S; } } else Stop=TRUE; } 61
Chương trình liệt kê các cách chia số n thành tổng các số nhỏ hơn: #include #include #define MAX 100 #define TRUE 1 #define FALSE 0 int n, k, X[MAX], dem =0, OK =TRUE; void Init(void ){ cout >n; k = 1; X[k] = n; } void Result(void) { cout 0 && X[i]==1 ) i ; if (i>0 ) { X[i] = X[i] - 1; D = k - i + 1; R = D / X[i]; S = D % X[i]; k= i; if (R>0) { for ( j = i +1; j 0 ){ k = k +1; X[k] = S; } } else PTITOK =0; } int main() { Init(); while (OK ) { Result(); Next_Division(); } system("PAUSE"); return 0; } 62