Bài giảng Toán rời rạc - Chương 3: Phương pháp đếm
TOÁN RỜI RẠC
Chương 3: PHƯƠNG PHÁP ĐẾM
GV: NGUYỄN LÊ MINH
Bộ môn Công nghệ thông tin
Nội dung
Tập hợp và hàm số
Các nguyên lý đếm
Lý thuyết tổ hợp
Nguyên lý Dirichlet
Hệ thức truy hồi
2
Tập hợp
Định nghĩa: Là một trong những khái niệm cơ
bản của toán học, làm cơ sở cho các định
nghĩa toán học. Đó là những đối tượng được
nhóm lại theo một tính chất nào đó
Ví dụ: Tập hợp các bài tập toán rời rạc
Tập hợp số sinh viên lớp CNTT K59
Hệ các phương trình tuyến tính
(Tập hợp đồng nghĩa với họ, hệ, lớp ….)
3
Tập hợp
Những yếu tố 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
Kí hiệu:
Nếu a là phần tử của A
a∈A (a thuộc A)
3
Diễn tả tập hợp
Có 2 cách diễn tả tập hợp:
Nêu tính chất đặc trưng các phần tử tạo
thành tập hợp
Liệt kê các phần tử của tập hợp
Ví dụ: A = 푥 ∈ 푁| 푥 푙à 푠ố 푛푔푢푦ê푛 푡ố
A = 1 ; 2 ; 3 ; 4 ; 5
3
Tập hợp
Các tập hợp số:
N = … −> tập hợp số tự nhiên
푁∗ = … −> tập hợp số tự nhiên khác 0
Z = … −> tập hợp các số nguyên
Q = … −> tập hợp các số hữu tỉ
R = … −> tập hợp các số thực
C = … −> tập hợp các số phức
3
Tập hợp
- Tập hợp A có n phần tử |A| = n
- Tập hợp A có vô số phần tử |A| = +∞
- Tập hợp không có phần tử nào ( tập hợp
rỗng) |A| = ∅
( Lưu ý: Tập hợp rỗng ≠ tập hợp có phần tử 0)
3
Tập hợp
Nếu mọi phần tử của tập hợp A đều là phần tử
của tập hợp B thì A là tập hợp con của B
Ngoài ra:
A
A B
Nếu
và
thì A = B
B A
Nếu 퐴 ≠ 퐵 thì
hay
3
Tập hợp
Mối quan hệ giữa hai tập hợp được biểu diễn
bằng biểu đồ Venn
3
Các phép toán trên tập hợp
• Phép giao: 푨 ∩ 푩 = 풙 ∈ 푼|(풙 ∈ 푨) (풙 ∈ 푩)
• Phép hợp: 푨 ∪ 푩 = 풙 ∈ 푼|(풙 ∈ 푨)(풙 ∈ 푩)
A U \ A xU | x A
• Phần bù:
3
Tính chất của các phép toán
Với A, B, C là các tập con tùy ý của U
3
Tích Descartes của các tập hợp
Tích Descartes của hai tập hợp A, B (ký hiệu
AxB) là tập các cặp có thứ tự (a,b) trong đó 푎 ∈ 퐴
và 푏 ∈ 퐵
퐴푥퐵 = 푎, 푏 |푎 ∈ 퐴 푣à 푏 ∈ 퐵
Ví dụ:
Nếu A = {a,b} và B={c,d,e}
A x B = {(a,c),(a,d),(a,e),(b,c),(b,d),(b,e)}
Từ đó suy ra trường hợp tổng quát
Tích Descartes của n tập 퐴1, 퐴2, 퐴3, … , 퐴푛
3
Ánh xạ
Một ánh xạ f từ tập hợp X vào tập hợp Y, ký hiệu
f: X−>Y là phép tương ứng liên kết mỗi phần tử
푥 ∈ 푋 với một phần tử duy nhất 푦 ∈ 푌
• X gọi là tập nguồn, Y gọi là tập đích
• Phần tử y = f(x)∈Y gọi là ảnh của X
f :X Y
x
3
Xác định một ánh xạ
• Liệt kê tất cả các ảnh của từng phần tử của X
• Công thức để xác định ảnh f(x) của mỗi phần
tử x
• Đưa ra một thủ tục xác định để tính ra (hay
tìm ra) được phần tử f(x) ứng với mỗi phần tử
x X
3
Ảnh của tập hợp
• Cho f là một ánh xạ từ X vào Y
• Giả sử A là một tập hợp con của X
• Ảnh của tập A qua ánh xạ f, ký hiệu bởi f(A),
là tập hợp con của Y gồm tất cả những phần
tử y sao cho y là ảnh của ít nhất một phần tử
x thuộc A.
f(A) = { f(a) : a A }
3
Ánh xạ hợp
• Cho 2 ánh xạ
f : X Y
g : Y Z
• Ánh xạ hợp h của f và g là ánh xạ từ X vào Z
xác định bởi:
h:X Z
x g f (x)
• Ký hiệu: h = g o f.
3
Đơn ánh
• Ánh xạ f : X Y được gọi là một đơn ánh khi
các ảnh của 2 phần tử khác nhau tùy ý thì khác
nhau
• Với mọi x và x' thuộc X ta có:
x x' f(x) f(x')
Hay f(x) = f(x') x = x'
3
Toàn ánh
• Ánh xạ f : X Y được gọi là một toàn ánh khi
mọi phần tử của Y đều là ảnh của ít nhất một
phần tử x thuộc X, nghĩa là
f(X) = Y
3
Song ánh
• Ánh xạ f : X Y được gọi là một song ánh khi
nó vừa là đơn ánh vừa là toàn ánh.
• Khi ấy với mỗi y Y, có duy nhất phần tử x X
sao cho f(x) = y
• Phép tương ứng liên kết y với x sẽ cho một ánh
xạ từ Y vào X. Ánh xạ này là ánh xạ ngược của
f và ký hiệu là 푓−1
f-1 : Y X, xác định bởi f-1(y) = x, với f(x) =
y
3
Phép đếm
Các bài toán đếm xuất hiện phổ biến trong toán
học cũng như trong tin học. Dùng để giải nhiều
dạng bài toán khác nhau, ví dụ: Số phép toán
trong một thuật toán để nghiên cứu độ phức tạp,
số mật khẩu truy nhập vào hệ máy tính …
3
Tải về để xem bản đầy đủ
53 trang
12/01/2024
19520
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 3: Phương pháp đếm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_3_phuong_phap_dem.pdf
