Bài giảng Toán rời rạc: Chương 5 - ThS. Trần Quang Khải

Bài giảng Toán rời rạc: Chương 5 Phép đếm, cung cấp cho người học những kiến thức như: Giới thiệu; Hai nguyên lý đếm cơ bản; Nguyên lý chuồng bồ câu (Phúc); Hoán vị (Khánh); Tổ hợp (Hoa). Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 5 - ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 5: PHÉP ĐẾM Giảng viên: ThS. Trần Quang Khải 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). Toán rời rạc: 2011-2012 Chương 05: Phép đếm 2 Giới thiệu: Phép đếm Toán rời rạc: 2011-2012 Chương 05: Phép đếm 3 Giới thiệu  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 Chương 05: Phép đếm 4 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? Toán rời rạc: 2011-2012 Chương 05: Phép đếm 5 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. Toán rời rạc: 2011-2012 Chương 05: Phép đếm 6 Quy tắc cộng 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 Chương 05: Phép đếm 7 Quy tắc cộng – Ví dụ 1. Chọn chồng:  Có máy bay: 15 ông.  Số cách chọn?  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ề.  Số cách chọn?  Trở thành vô gia cư: 1 nghề. Toán rời rạc: 2011-2012 Chương 05: Phép đếm 8 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 Toán rời rạc: 2011-2012 Chương 05: Phép đếm 9 Dưới góc độ lý thuyết tập hợp Nếu A1 , A2 ,..., An 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à: A1  A2  ...  An  A1  A2  ...  An Toán rời rạc: 2011-2012 Chương 05: Phép đếm 10 Quy tắc nhân 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 Chương 05: Phép đếm 11 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 Toán rời rạc: 2011-2012 Chương 05: Phép đếm 12 Dưới góc độ lý thuyết tập hợp Nếu A1 , A2 ,..., An 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: A1  A2  ...  An  A1 . A2 ..... An Toán rời rạc: 2011-2012 Chương 05: Phép đếm 13 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 Toán rời rạc: 2011-2012 Chương 05: Phép đếm 14