Bài giảng MH/MĐ: Toán ứng dụng - Bài 2: Bài toán đếm và bài toán tồn tại

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: MÔN HỌC: TOÁN ỨNG DỤNG Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ Bài 5: CÂY VÀ CÁC ỨNG DỤNG BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI 1. TẬP HỢP 2. QUAN HỆ 2.1 Khái niệm quan hệ 2.2 Ma trận biểu diễn quan hệ 3. BÀI TOÁN ĐẾM 3.1 Nguyên lý cộng 3.2 Nguyên lý nhân 3.3 Nguyên lý bù trừ 4. GIẢI TÍCH TỔ HỢP 4.1 Hoán vị 4.2 Chỉnh hợp 4.3 Tổ hợp 4.4 Hoán vị lặp 4.5 Tổ hợp và chỉnh hợp lặp 5. BÀI TOÁN TỒN TẠI 5.1 Nguyên lý Dirichlet 5.2 Nguyên lý Dirichlet tổng quát BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.1 Khái niệm Tập hợp là một khái niệm cơ bản của Toán học, không được định nghĩa. Có thể hiểu tập hợp là một nhóm đối tượng có chung một tính chất nào đó. Ví dụ: 1) Tập hợp sinh viên một trường đại học. 2) Tập hợp các số nguyên 3) Tập hợp các bài thơ của Nguyễn Bính. Cơ sở Logic BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.1 Khái niệm Những đối tượng tạo thành một tập hợp gọi là phần tử (hay điểm) của tập hợp. Nếu a là một phần tử của tập hợp A, ta viết aA (đọc "a thuộc A") Trường hợp ngược lại, ta viết a A (đọc "a không thuộc A") Cơ sở Logic BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.2 Diễn tả tập hợp Cách 1: Bằng lời "A là tập hợp bốn số nguyên dương đầu tiên" "B là tập hợp các màu trên quốc kỳ Pháp" Cách 2: Liệt kê các phần tử, đặt giữa cặp { } X = {4, 2, 1, 3} Y= {đỏ, trắng, xanh} Cách 3: Đưa ra tính chất đặc trưng A={ n N | n chia hết cho 3} Cơ sở Logic BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.3 Lực lượng của tập hợp Số phần tử của tập hợp A được gọi là lực lượng của tập hợp, kí hiệu |A|. Nếu tập hợp A có hữu hạn phần tử, ta nói A hữu hạn. Ngược lại, ta nói A vô hạn. Tập hợp không có phần tử nào gọi là tập hợp rỗng, kí hiệu là Ø Ví dụ Tập hợp số N, Z, R, là các tập vô hạn Tập hợp X={1,3,4,5} là tập hữu hạn, Ta có: |X|=4 1. Tập hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.4 Tập hợp con Nếu mọi phần tử của tập hợp B đều là phần tử của tập hợp A thì ta nói B là tập hợp con của A (hay B được bao hàm trong A). Kí kiệu: B  A hay A  B B  A  (x | x B  x A) P(A)-là kí hiệu tập hợp tất cả tập con của A Ví dụ A={1,2}, B={1} - là tập con của A P(A)={Ø,{1},{2},{1,2}} Ø: là tập con của mọi tập hợp 1. Tập hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.5 Biểu đồ Venn Biểu diễn tập hợp bởi một đường cong kín Mỗi phần tử của tập hợp được đặc trưng bởi điểm nằm trong đường cong ấy Ví dụ A  B C ≠ D 1. Tập hợp AB C D BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.6 Các phép toán trên tập hợp Phép hợp: Hợp của tập hợp A và B là một tập hợp tạo bởi tất cả các phần tử thuộc A hoặc thuộc B. Ký hiệu: A  B A  B= {x  xA  xB} Ví dụ A= {a,b,c,d} B= {c,d,e,f} A  B = {a,b,c,d,e,f} A B 1. Tập hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.6 Các phép toán trên tập hợp Phép giao: Giao của tập hợp A và B là một tập hợp tạo bởi các phần tử thuộc A và thuộc B. Ký hiệu: A  B A  B ={x  xA  xB} Ví dụ A= {a,b,c,d} B= {c,d,e,f} A  B = {c,d} 1. Tập hợp A B A BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.6 Các phép toán trên tập hợp Hiệu của hai tập hợp: Hiệu của tập hợp A với B là một tập hợp tạo bởi tất cả các phần tử thuộc tập A mà không thuộc tập B. Kí hiệu: A\B A\B= { x  xA  xB} Phần bù: Cho B  A, A\B gọi là bù của B trong A Ví dụ A= {a,b,c,d} B= {c,d,e,f} A\B = {a,b} 1. Tập hợp A BB A\B BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.7 Tính chất của phép toán trên tập hợp a/. Tính giao hoán: A  B = B  A A  B = B  A. b/. Tính kết hợp: (A  B)  C = A  (B  C) (A  B)  C = A  (B  C) c/. Tính phân phối: A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) 1. Tập hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.7 Tính chất của phép toán trên tập hợp d/. Công thức De Morgan: e/. Tính lũy đẳng: A  A = A A  A = A 1. Tập hợp BABAvaøBABA  BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.8 Tích Descartes của các tập hợp Tích Descartes của tập hợp A với tập hợp B là tập hợp gồm tất cả các cặp thứ tự (x,y) với xA và xB Ký hiệu là A B hoặc A.B A B = {(x,y)| xA, yB} Tích của 2 tập hợp không có tính chất giao hoán. |A x B| = |A| x |B| 1. Tập hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.8 Tích Descartes của các tập hợp Tích Đề các của n tập hợp A1, A2,..., An là tập mọi dãy có thứ tự (x1,x2,...,xn), trong đó xi  Ai (i=1,...,n) Kí hiệu A1. A2... An A1. A2...An = {(x1,x2,...,xn)  xiAi (i=1,...,n) } Cách viết khác: 1. Tập hợp  i i i I i i i I A (x ) i I , x A      BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.1 Khái niệm Một quan hệ hai ngôi giữa tập hợp A và tập hợp B là tập con R của AxB. Kí hiệu: R  A x B. Viết a R b thay cho (a, b)  R Quan hệ từ A đến A được gọi là quan hệ trên A 2. Quan hệ R = { (a1, b1), (a1, b3), (a3, b3) } BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.1 Khái niệm Ví dụ: Cho A = {1, 2, 3, 4}, R = {(a, b) | (a A, b A, a là ước của b} R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} 1 2 3 4 1 2 3 4 2. Quan hệ BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.1 Khái niệm Một quan hệ n-ngôi giữa các tập hợp A1, A2,..., An là tập con R của A1x A2x...xAn. Ví dụ: Xét quan hệ 4-ngôi có tên là Sinh viên biểu diễn trong bảng sau: 2. Quan hệ Mã SV Họ tên Ngày sinh Khóa học 99051110 Tran Anh 20-10-1990 1 99051111 Hoang Xuan 02-07-1990 1 99051112 Nguyen Viet 16-11-1990 1 ... BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: mij = 0 nếu (ai , bj)  R 1 nếu (ai , bj)  R Ví dụ: Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} với a R b khi a > b. Ma trận biểu diễn của R là MR 2.2 Ma trận biểu diễn quan hệ Cho R là quan hệ từ A = {a1,a2,,am} đến B = {b1,b2,,bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR = [mij] xác định bởi 19 2. Quan hệ            11 01 00 RM 1 2 1 2 3 BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.2 Ma trận biểu diễn quan hệ Ví dụ: Cho R là quan hệ từ A = {a1, a2, a3} đến B = {b1, b2, b3, b4, b5} R xác định gồm các cặp: {(a1, b2),(a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}            10101 01101 00010 RM b1 b2 b3 b4 b5 a1 a2 a3 2. Quan hệ BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.1 Nguyên lý cộng Giả sử để thực hiện công việc A có n-phương pháp - Phương pháp 1 có m1 cách làm - Phương pháp 2 có m2 cách làm - Phương pháp n có mn cách làm Khi đó số cách chọn thực hiện công việc là m1 + m2 +...+mn 3. Bài toán đếm BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.1 Nguyên lý cộng Ví dụ Cho tập hợp A={1,2,3}. Hỏi có bao nhiêu cách chọn 1 tập con B của A. Giải: - t/hợp 1: chọn tập B là tập hợp rỗng- 1 cách chọn - t/hợp 2: chọn tập B chứa 1 phần tử của A - 3 cách chọn - t/hợp 3: chọn tập B chứa 2 phần tử của A - 3 cách chọn - t/hợp 4: chọn tập B chứa 3 phần tử của A - 1 cách chọn Áp dụng nguyên lý cộng, số cách chọn tính được là 8 cách. 3. Bài toán đếm BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.2 Nguyên lý nhân Giả sử một công việc A cần được thực hiện qua n- bước liên tiếp. - bước 1 có t1 cách làm - bước 2 có t2 cách làm - bước n có tn cách làm Khi đó số cách chọn thực hiện công việc là t1 x t2 x ... x tn 3. Bài toán đếm BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.2 Nguyên lý nhân Ví dụ A B C Có 3x2 =6 cách đi từ A đến C 3. Bài toán đếm BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau (lấy từ tập X) mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1: c=0. Khi đó c có 1 cách chọn a có 5 cách chọn ( aX\{0} ) b có 4 cách chọn ( bX\{a, 0} ) TH1 có 1x4x5 =20 TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn ( aX\{c, 0} ) b có 4 cách chọn ( bX\{a, c} ) TH2 có 2x4x4 =32 Tổng cộng có 20+32 =52 (số có 3 chữ số thỏa mãn bài toán) 3. Bài toán đếm BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.3 Nguyên lý bù trừ Với hai tập hợp A và B thì: |AB| = |A|+|B|-|AB| Ví dụ: Trong một cơ quan có 180 người. Có 55 người biết sử dụng MS-Word, 45 người biết sử dụng MS-Excel và 15 người vừa thạo MS-Word, vừa thạo MS-Excel. Hỏi có bao nhiêu người không sử dụng được cả hai tiện ích? (95) 3. Bài toán đếm A  B BA BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.3 Nguyên lý bù trừ Với ba tập hợp A, B và C thì: |ABC| = |A|+|B|+|C|-|AB|-|BC|-|CA|+|ABC| 3. Bài toán đếm A  B A  C BC A  B  C A B C BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.1 Hoán vị Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. - Số các hoán vị của n phần tử ký hiệu là Pn Pn = n! = 1.2.3... (n-1).n Quy ước 0! =1 Ví dụ Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba 4. Giải tích tổ hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.2 Chỉnh hợp Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử Số các chỉnh hợp chập k của n ký hiệu là - Công thức   ! ! k n n A n k   k nA Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb. 4. Giải tích tổ hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.3 Tổ hợp Cho A là tập hợp gồm n phần tử. Mỗi tập con gồm k phần tử (1 k n) của A (không phân biệt thứ tự) được gọi là một tổ hợp chập k của n phần tử Số các tổ hợp chập k của n ký hiệu là - Công thức Ví dụ. Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn? 4. Giải tích tổ hợp k nC   ! ! ! k n n C k n k   10 30C BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.4 Hoán vị lặp Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau (i =1,2,,k ; n1+ n2,+ nk= n). Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2, ... nk đối tượng giống nhau thuộc loại k, là 4. Giải tích tổ hợp 1 2 ! ! !... !k n n n n BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.4 Hoán vị lặp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Vậy tổng số chuỗi tạo được là 4. Giải tích tổ hợp 7 ! 420 3!1!2 !1!  BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.5 Tổ hợp và chỉnh hợp lặp a/. Một chỉnh hợp lặp chập k từ n phần tử là một bộ có thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đó mỗi phần tử có thể lấy lặp lại. Cách tính: b/. Một tổ hợp lặp chập k từ n phần tử là một bộ gồm k phần tử (không phân biệt thứ tự), mỗi phần tử có thể lấy lặp lại từ n phần tử đã cho Cách tính: 4. Giải tích tổ hợp BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.5 Tổ hợp và chỉnh hợp lặp Ví dụ Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn? Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể là AA, AB, AC, BB, BC, CC Ví dụ Để đăng ký một loại hàng hóa mới, người ta dùng 3 chữ số trong 9 chữ số từ 1 đến 9. Hỏi có thể đánh số theo cách này được cho bao nhiêu loại hàng hóa? Kết quả là: 93 = 729 4. Giải tích tổ hợp 2 2 2 3 3 2 1 4 6K C C    BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 5.1 Nguyên lý Dirichlet (nguyên lý chuồng chim bồ câu) Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì tồn tại ít nhất một ngăn có nhiều hơn một con chim. 5. Bài toán tồn tại 2 1 1 2 BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 5.2 Nguyên lý Dirichlet tổng quát Nếu xếp nhiều hơn n đối tượng vào n cái hộp, thì tồn tại ít nhất một hộp chứa không ít hơn 2 đối tượng. Tổng quát: Nếu xếp nhiều hơn n đối tượng vào k cái hộp, thì tồn tại ít nhất một hộp chứa không ít hơn [n/k] đối tượng. Kí hiệu [x] là số nguyên nhỏ nhất không nhỏ hơn x. 5. Bài toán tồn tại 2 1 1 2