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! | 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í
