Bài giảng Toán rời rạc - Chương 5: Phép đếm

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 5: PHÉP ĐẾM Toán rời rạc: 2011-2012 Nội dung 1. Giới thiệu. 2. Hai nguyên lý đếm cơ bản. 3. Nguyên lý chuồng bồ câu (Phúc). 4. Hoán vị (Khánh). 5. Tổ hợp (Hoa). Chương 05: Phép đếm 2 Toán rời rạc: 2011-2012 Giới thiệu: Phép đếm Chương 05: Phép đếm 3 Toán rời rạc: 2011-2012 Giới thiệu Chương 05: Phép đếm 4 Password (chỉ gồm letters và numbers): Dài 6 ký tự  Có thể có bao nhiêu? Dài 8 ký tự  Có thể có bao nhiêu? Dài 10 ký tự  Có thể có bao nhiêu?  Đếm nhưng đếm như thế nào? Toán rời rạc: 2011-2012 Giới thiệu Thuật toán:  Tính số phép toán phải thực hiện  độ phức tạp. Lập trình:  Tính số lần lặp, số vòng lặp  Xác định tài nguyên. Đếm nhưng đếm như thế nào? Chương 05: Phép đếm 5 Toán rời rạc: 2011-2012 Hai nguyên lý đếm cơ bản 1. Quy tắc cộng (sum rule). 2. Quy tắc nhân (product rule).  Chú ý: ngoài ra còn có các nguyên lý đếm nâng cao. Chương 05: Phép đếm 6 Toán rời rạc: 2011-2012 Quy tắc cộng Chương 05: Phép đếm 7 Nếu một việc có thể thực hiện bằng cách chọn 1:  hoặc trong n1 cách  hoặc trong n2 cách,  mỗi 1 cách chọn trong tập n1 không giống bất cứ cách chọn nào trong tập n2  tổng cộng n1+n2 cách. Toán rời rạc: 2011-2012 Quy tắc cộng – Ví dụ 1. Chọn chồng:  Có máy bay: 15 ông.  Có du thuyền: 9 ông. 2. Chọn nghề để:  Trở thành siêu sao: 3 nghề.  Trở thành kỹ sư: 20 nghề.  Trở thành vô gia cư: 1 nghề. Chương 05: Phép đếm 8  Số cách chọn?  Số cách chọn? Toán rời rạc: 2011-2012 Quy tắc cộng mở rộng Có nhiều tập cách chọn:  n1, n2,, nm  Cách chọn của 1 tập không giống bất cứ cách chọn nào của các tập khác. Có tổng cộng: n1 + n2 + + nm cách Chương 05: Phép đếm 9 Toán rời rạc: 2011-2012 Dưới góc độ lý thuyết tập hợp Chương 05: Phép đếm 10 Nếu là các tập hữu hạn tách rời nhau (disjoint). Số cách chọn 1 phần tử từ một trong các tập là: nAAA ,...,, 21 nn AAAAAA  ...... 2121 Toán rời rạc: 2011-2012 Quy tắc nhân Chương 05: Phép đếm 11 Giả sử 1 thủ tục có thể chia thành 2 việc:  Công việc 1: n1 cách.  Với mỗi 1 cách thực hiện công việc 1, có n2 cách thực hiện công việc 2.  Có n1n2 cách để thực hiện thủ tục. Toán rời rạc: 2011-2012 Quy tắc nhân – Ví dụ 1. Có 12 đề tài, có 2 sv, cần giao mỗi sv 1 đề tài:  SV1: có 12 cách giao đề tài.  SV2: có 11 cách giao đề tài.  Tổng cộng: 12*11 = 132 cách. 2. Có bao nhiêu chuỗi bit có độ dài là 7?  Mỗi bit có 2 cách chọn: 0 và 1.  Số cách chọn: 2.2.2.2.2.2.2 = 27 Chương 05: Phép đếm 12 Toán rời rạc: 2011-2012 Dưới góc độ lý thuyết tập hợp Chương 05: Phép đếm 13 Nếu là các tập hữu hạn. Số các phần tử thuộc tích Cartersian của các tập này là tích số phần tử của chúng: nAAA ,...,, 21 nn AAAAAA ......... 2121  Toán rời rạc: 2011-2012 Nguyên tắc loại trừ Ví dụ: Có bao nhiêu chuỗi dài 8 bit mà có thể bắt đầu bằng “1” hoặc kết thúc bằng “00”? Giải:  Số chuỗi bắt đầu bằng “1”: 27 = 128  Số chuỗi kết thúc bằng “00”: 26 = 64  Số chuỗi bắt đầu bằng “1” và kết thúc bằng “00”: 25 = 32  Tổng số chuỗi: 128 + 64 – 32 = 160 Chương 05: Phép đếm 14