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

Nội dung text: Bài giảng môn Toán ứng dụng - Bài 2: Bài toán đếm và bài toán tồn tại

1. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: MƠN HỌC: TỐN ỨNG DỤNG Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: THUẬT TỐN TÌM KIẾM TRÊN ĐỒ THỊ Bài 5: CÂY VÀ CÁC ỨNG DỤNG BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
2. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Bài 2: BÀI TỐN ĐẾM VÀ BÀI TỐ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 TỐ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 Hốn vị 4.2 Chỉnh hợp 4.3 Tổ hợp 4.4 Hốn vị lặp 4.5 Tổ hợp và chỉnh hợp lặp 5. BÀI TỐN TỒN TẠI 5.1 Nguyên lý Dirichlet 5.2 Nguyên lý Dirichlet tổng quát BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
3. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Cơ sở Logic 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 Tố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. BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
4. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Cơ sở Logic 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") BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
5. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Cơ sở Logic 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} BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
6. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 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 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
7. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 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 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
8. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 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 B A C ≠ D C D BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
9. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.6 Các phép tố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 B= {c,d,e,f} A  B = {a,b,c,d,e,f} A BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
10. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.6 Các phép tố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 A  B = {c,d} A BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
11. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.6 Các phép tố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 A Ví dụ A= {a,b,c,d} BB A\B B= {c,d,e,f} A\B = {a,b} BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
12. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.7 Tính chất của phép tốn trên tập hợp a/. Tính giao hố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) BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
13. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.7 Tính chất của phép tốn trên tập hợp d/. Cơng thức De Morgan: A  B A  B và A  B A  B e/. Tính lũy đẳng: A  A = A A  A = A BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
14. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 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 hốn. |A x B| = |A| x |B| BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
15. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 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:  Ai (x i ) i I  i I , x i A i  i I BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
16. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Quan hệ 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 R = { (a1, b1), (a1, b3), (a3, b3) } BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
17. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Quan hệ 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 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
18. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Quan hệ 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: 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 TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
19. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Quan hệ 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 0 nếu (ai , bj) R mij = 1 nếu (ai , bj) R Ví dụ: 1 2 Nếu R là quan hệ từ 0 0 1 A = {1, 2, 3} đến B = {1, 2} M 1 0 2 với a R b khi a > b. R Ma trận biểu diễn của R là MR 1 1 3 19 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
20. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Quan hệ 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)} b1 b2 b3 b4 b5 0 1 0 0 0 a1 a2 M R 1 0 1 1 0 a3 1 0 1 0 1 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
21. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 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 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
22. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 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. BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
23. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 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 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
24. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 3.2 Nguyên lý nhân Ví dụ A B C Cĩ 3x2 =6 cách đi từ A đến C BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
25. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 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à a b c 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 tốn) BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
26. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 3.3 Nguyên lý bù trừ Với hai tập hợp A và B thì: |AB| = |A|+|B|-|AB| A A  B 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) BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
27. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Bài tốn đếm 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| C A  C BC A  B  C A B A  B BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
28. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 4.1 Hố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 hốn vị của n phần tử. - Số các hố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 hốn vị sau abc,acb, bac,bca, cab,cba BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
29. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 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ử k Số các chỉnh hợp chập k của n ký hiệu là An n! - Cơng thức Ak n n k ! 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. BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
30. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 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ử k Số các tổ hợp chập k của n ký hiệu là Cn k n! - Cơng thức C n k!! n k Ví dụ. Một lớp cĩ 30 học sinh. Hỏi cĩ bao nhiêu cách chọn 10 bạn? 10 C30 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
31. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 4.4 Hố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 hốn vị lặp của n. Số hố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, n đối tượng giống nhau thuộc loại k, là k n! n1! n 2 ! nk ! BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
32. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 4.4 Hố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à 7 ! 420 3!1!2 !1! BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
33. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 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: BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
34. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4. Giải tích tổ hợp 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? 2 2 2 KCC3 3 2 1 4 6 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 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
35. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 5. Bài tốn tồn tại 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. 2 1 1 2 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI
36. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 5. Bài tốn tồn tại 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. 2 1 1 2 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI