Toán Rời Rạc - Gv:Ths.Trần Xuân Sang

Chia sẻ: matbuon_140891

Các phép toán tập hợpPhần bù: của A trong X ký hiệu A là các phần tử của X không thuộc vào A. Hợp: A và B ký hiệu A  B là các phần tử hoặc thuộc vào A hoặc thuộc vào B hoặc thuộc vào cả A và B

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Toán Rời Rạc - Gv:Ths.Trần Xuân Sang

Toán Rời Rạc


Giảng viên: Ths. Trần Xuân Sang
E-mail: transang1981dhv@yahoo.com




06/20/11 1
Chương I: Lý thuyết tổ hợp

Nội dung

Một số nguyên lý cơ bản


Bài toán đếm


Bài toán tồn tại


Bài toán liệt kê


Công thức truy hồi





06/20/11 2
Một số nguyên lý cơ bản

Nội dung

Các phép toán tập hợp


Nguyên lý nhân


Nguyên lý cộng


Nguyên lý bù trừ


Nguyên lý quy nạp


Bài tập


06/20/11 3
Các phép toán tập hợp
Phần bù: của A trong X ký hiệu A là các


phần tử của X không thuộc vào A.
Hợp: A và B ký hiệu A ∪ B là các phần tử


hoặc thuộc vào A hoặc thuộc vào B hoặc thuộc
vào cả A và B
Giao: của A và B, ký hiệu A ∩ B là các phần tử


đồng thời thuộc vào cả A và B
Tích Đêcac:


A x B = {(a,b)|a ∈ A, b ∈ B}
06/20/11 4
Nguyên lý nhân

Nếu mỗi thành phần ai của bộ có thứ tự k


thành phần (a1,a2,...ak) có ni khả năng chọn
thì số bộ được tạo ra là tích số của các khả
năng này n1n2..nk
Vd1: Đi qua các chăng đường


Vd2: Chương trình vòng for lồng nhau


Vd3: Có bao nhiêu tên biến trong Pascal độ


dài 10 chỉ chứa hai chữ cái A,B bắt đầu bởi
AAA hoặc ABA (KQ 256)
06/20/11 5
Nguyên lý cộng

Nếu A và B là hai tập hợp rời nhau thì


N(A ∪ B) = N(A)+N(B)
Có thể mở rộng ra cho n tập


Vd1: Chương trình pascal các vòng for ko lồng


nhau
Vd2: Có 90 đề tài toán, 10 đề tài tin học. Mỗi sinh


viên được chọn 1 đề tài. Hỏi 1 sinh viên có bao
nhiêu khả năng lựa chọn đề tài.


06/20/11 6
Nguyên lý bù trừ

Có bao nhiêu phần tử trong hợp của hai tập


hợp hữu hạn
N(A ∪ B) = N(A)+N(B)- N(A ∩ B )


Vd1: Trong trường có 1807 sinh viên năm thứ


nhất. Trong số này có 453 sv chọn môn tin học,
576 sv chọn môn toán và 299 sv chọn cả hai môn
toán và tin. Có bao nhiêu sinh viên không học
toán cũng không học tin. (Kq 1807-721=1086)
Vd2: Tính: N(A ∪ B ∪ C)


06/20/11 7
Nguyên lý quy nạp

Chứng minh P(n) đúng với mọi số nguyên


dương n thì cần hai bước
B1: Bước cơ sở: Chỉ ra P(1) là đúng


B2: Bước quy nạp: Chứng minh phép kéo theo


p(n) -->P(n+1) là đúng với mọi số nguyên dương
n, trong đó P(n) được gọi là giả thiết quy nạp.
Vd1: Chứng minh 1+3+5+(2n-1) = n2


vd2: Chứng minh: n 364521



Lật ngược đoạn (a4, a5, a6)

Tìm hoán vị liền
Kết quả: 364125 kề của 326541.





06/20/11 46
Giải thuật sinh hoán vị
Mô phỏng thuật toán sinh hoán vị kế tiếp từ hoán vị {a1, a2,


a3, ...,an-1, an} # {n,n-1,..2,1)
procedure sinh_hoan_vi;


begin
i:=n-1;
while (i>0) and (ai>ai+1) do i:=i-1; {Tìm i sao cho ai 0) and (xi = n - k + i) do i := i - 1;


(1, 2, 6, 7, 8, 9);


Nếu tìm thấy:


if i > 0 then


♦Tăng xi đó lên 1. xi := xi + 1;


(1, 3, 6, 7, 8, 9)


♦Đặt tất cả các phần tử phía sau xi bằng giới hạn dưới:


for j := i + 1 to k do xj := xj-1 + 1;


(1, 3, 4, 5, 6, 7)




06/20/11 50
Bài tập

Bài 1: Lập chương trình liệt kê tất cả các xâu nhị phân có độ dài
n, với n được nhập từ bàn phím(n>0).
Bài 2: Lập chương trình liệt kê tất cả hoán vị của n số tự nhiên
từ 1 đến n, với n được nhập từ bàn phím(n>0)
Bài 3: Lập chương trình liệt kê tất cả các tổ hợp chập k của tập
hợp n số tự nhiên từ 1 đến n, với n, k được nhập từ bàn
phím(k
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản