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
36 trang |
Chia sẻ: anhquan78 | Lượt xem: 912 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Toán ứng dụng - Bài 2: Bài toán đếm và bài toán tồn tại, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
aA (đọ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 xA xB}
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 xA xB}
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 xA xB}
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 xA và xB
Ký hiệu là A B hoặc A.B
A B = {(x,y)| xA, yB}
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) xiAi (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 ( aX\{0} )
b có 4 cách chọn ( bX\{a, 0} )
TH1 có 1x4x5 =20
TH2 . c≠0. Khi đó
c có 2 cách chọn
a có 4 cách chọn ( aX\{c, 0} )
b có 4 cách chọn ( bX\{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ì:
|AB| =
|A|+|B|-|AB|
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ì:
|ABC| =
|A|+|B|+|C|-|AB|-|BC|-|CA|+|ABC|
3. Bài toán đếm
A B
A C BC
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