Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Lý thuyết tổ hợp: Phần 1

Cùng nắm kiến thức trong bài giảng "Lý thuyết tổ hợp: Phần 1" thông qua việc tìm hiểu các nội dung sau: mở đầu, bài toán đếm tổ hợp, bài toán tồn tại tổ hợp, bài toán liệt kê tổ hợp, bài toán tối ưu tổ hợp. . | Toán rời rạc Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Hà Nội 2014 Toán rời rạc Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc Chương 1. BÀI TOÁN ĐẾM Nguyên lý cộng và nguyên lý nhân Các cấu hình tổ hợp cơ bản Nguyên lý bù trừ Công thức đệ qui Hàm sinh Toán rời rạc 1. Nguyên lý cộng và Nguyên lý nhân Đây là hai nguyên lý cơ bản của tổ hợp, được vận dụng rộng rãi vào việc giải quyết các bài toán đếm Còn gọi là Qui tắc cộng và Qui tắc nhân (Sum Rule và Product Rule) Toán rời rạc 1.1. Nguyên lý cộng (The sum rule) NÕu A vµ B lµ hai tËp hîp rêi nhau th× N(A B) = N(A) + N(B). Nguyªn lý céng ®­îc më réng cho nhiÒu tËp con rêi nhau: NÕu A1, A2, ., Ak lµ mét ph©n ho¹ch cña tËp hîp X th× N(X) = N(A1) + N(A2) + . + N(Ak). Mét tr­ường hîp riªng hay dïng cña nguyªn lý céng: NÕu A lµ mét tÝnh chÊt cho trªn tËp X th× N(A) = N(X) - N(Ac). Toán rời rạc Nguyên lý cộng: Ví dụ Ví dụ 2. Trong một đợt phổ biến đề tài tốt nghiệp, Ban chủ nhiệm Khoa công bố danh sách các đề tài bao gồm 80 đề tài về chủ đề "xây dựng hệ thông tin quản lý", 10 đề tài về chủ đề "thiết kế phần mềm dạy học" và 10 đề tài về chủ đề "Hệ chuyên gia". Hỏi một sinh viên có bao nhiêu khả năng lựa chọn đề tài? Giải: Sinh viên có thể lựa chọn đề tài theo chủ đề thứ nhất bởi 80 cách, theo chủ đề thứ hai bởi 10 cách, theo chủ đề thứ ba bởi 10 cách. Vậy tất cả có 100 cách lựa chọn. Toán rời rạc Nguyên lý cộng: Ví dụ VÝ dô 3. Hái r»ng gi¸ trÞ cña k sÏ lµ bao nhiªu sau khi ®o¹n chươnng tr×nh PASCAL sau ®­ược thùc hiÖn? n1:=10; n2:=20; n3:=30; k:=0; for i1:= 1 to n1 do k:=k+1; for i2:= 1 to n2 do k:=k+1; for i3:= 1 to n3 do k:=k+1; Gi¶i: §Çu tiªn gi¸ trÞ cña k ®­îc g¸n b»ng 0. Cã 3 vßng lÆp for ®éc lËp. Sau mçi lÇn lÆp cña mçi mét trong 3 vßng for, gi¸ trÞ cña k t¨ng lªn 1. Vßng for thø nhÊt lÆp 10 lÇn, vßng for thø hai lÆp 20 lÇn, vßng for thø ba lÆp 30 lÇn. VËy, kÕt thóc 3 vßng lÆp for gi¸ trÞ . | Toán rời rạc Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Hà Nội 2014 Toán rời rạc Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc Chương 1. BÀI TOÁN ĐẾM Nguyên lý cộng và nguyên lý nhân Các cấu hình tổ hợp cơ bản Nguyên lý bù trừ Công thức đệ qui Hàm sinh Toán rời rạc 1. Nguyên lý cộng và Nguyên lý nhân Đây là hai nguyên lý cơ bản của tổ hợp, được vận dụng rộng rãi vào việc giải quyết các bài toán đếm Còn gọi là Qui tắc cộng và Qui tắc nhân (Sum Rule và Product Rule) Toán rời rạc 1.1. Nguyên lý cộng (The sum rule) NÕu A vµ B lµ hai tËp hîp rêi nhau th× N(A B) = N(A) + N(B). Nguyªn lý céng ®­îc më réng cho nhiÒu tËp con rêi nhau: NÕu A1, A2, ., Ak lµ mét ph©n ho¹ch cña tËp hîp X th× N(X) = N(A1) + N(A2) + . + N(Ak). Mét tr­ường hîp riªng hay dïng cña nguyªn lý céng: NÕu A lµ mét tÝnh chÊt cho trªn tËp X th× N(A) = N(X) - N(Ac). Toán rời rạc Nguyên lý cộng: Ví dụ