Xem mẫu
- 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
nguon tai.lieu . vn
