Title MAD101- Chapter 5.pptx ✅

Chapter 5: Counting The Basic of Counting Recurrence Relation Divide - and - Conquer Algorithm
5. 1 The Basic of Counting Review of Counting Principle The Sum Rule: Nếu một công việc/nhiệm vụ A có thể hoàn thành theo 2 phương pháp: phương pháp 1 có m cách làm, phương pháp 2 có n cách làm (giả sử rằng không có cách nào được thực hiện bằng cả 2 phương pháp). Khi đó có m +n cách hoàn thành công việc A Phát biểu theo ngôn ngữ tập hợp: If S₁ and S are disjoint sets. Then | S₁ ∪ S₂| = | S₁ |+ | S₂ |
5. 1 The Basic of Counting Review of Counting Principle 2. The Product Rule (quy tắc nhân) Nếu một công việc/nhiệm vụ A có thể hoàn thành theo 2 bước: bước 1 có m cách làm, bước 2 có n cách làm,..., bước k có Khi đó có (m.n) cách hoàn thành công việc (tổng quát) Nếu một công việc/nhiệm vụ A có thể hoàn thành theo k bước: bước 1 có n₁ cách làm, bước 2 có n₂ cách làm,..., bước k có nₖ cách làm Khi đó có n₁.n₂…nₖ cách hoàn thành công việc A Phát biểu theo ngôn ngữ tập hợp: If S₁ and S₂ are sets. Then | S₁ x S₂| = | S₁ |.| S₂ | If S₁ , S₂, …, Sₖ are sets. Then | S₁ x S₂ x…x Sₖ| = | S₁ |.| S₂ |...| Sₖ |