Slide Bài Giảng Toán Rời Rạc - Chương 1 Bài Toán đếm Nguyên Lý ...

Tải bản đầy đủ (.ppt) (176 trang)

1. Trang chủ
>>
2. Giáo Dục - Đào Tạo
>>
3. Cao đẳng - Đại học

Slide bài giảng Toán rời rạc - chương 1 bài toán đếm nguyên lý cộng và nguyên lý nhân

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.48 MB, 176 trang )

Chương 1. BÀI TOÁN ĐẾM1.Nguyên lý cộng và nguyên lý nhân2.Các cấu hình tổ hợp cơ bản3.Nguyên lý bù trừ4.Công thức đệ qui5.Hàm sinhToán rời rạc11. Nguyên lý cộng và Nguyên lý nhânĐây là hai nguyên lý cơ bản của tổ hợp, được vận dụng rộng rãivào việc giải quyết các bài toán đếmCòn gọi là Qui tắc cộng và Qui tắc nhân (Sum Rule và ProductRule)Toán rời rạc21.1. Nguyờn lý cng(The sum rule)Nếu A và B là hai tập hợp rời nhau thìN(A B) = N(A) + N(B).Nguyên lý cộng đợc mở rộng cho nhiều tập con rời nhau:Nếu A1, A2, ..., Ak là một phân hoạch của tập hợp X thìN(X) = N(A1) + N(A2) + ... + N(Ak).Một trờng hợp riêng hay dùng của nguyên lý cộng:Nếu A là một tính chất cho trên tập X thìN(A) = N(X) - N(Ac).N ( A) = N ( X ) N ( A )Toỏn ri rc3Nguyên lý cộng: Ví dụVí dụ 1. Một đoàn vận động viên gồm 2 môn bắn súng vàbơi được cử đi thi đấu ở nước ngoài. Nam có 10 người.Số vận động viên thi bắn súng (kể cả nam và nữ) là 14.Số nữ vận động viên thi bơi bằng số nam vận động viênthi bắn súng. Hỏi toàn đoàn có bao nhiêu người?Giải: Chia đoàn thành 2 lớp: nam và nữ. Lớp nữ lạiđược chia 2: thi bắn súng và thi bơi. Thay số nữ thi bơibằng số nam thi bắn súng (2 số này bằng nhau theo đầubài), ta được số nữ bằng tổng số đấu thủ thi bắn súng.Từ đó, theo nguyên lý cộng, toàn đoàn có 10 + 14 = 24người.Toán rời rạc4Nguyên lý cộng: Ví dụVí dụ 2. Trong một đợt phổ biến đề tài tốt nghiệp, Banchủ nhiệm Khoa công bố danh sách các đề tài bao gồm80 đề tài về chủ đề "xây dựng hệ thông tin quản lý", 10đề tài về chủ đề "thiết kế phần mềm dạy học" và 10 đề tàivề chủ đề "Hệ chuyên gia". Hỏi một sinh viên có baonhiêu khả năng lựa chọn đề tài?Giải: Sinh viên có thể lựa chọn đề tài theo chủ đề thứnhất bởi 80 cách, theo chủ đề thứ hai bởi 10 cách, theochủ đề thứ ba bởi 10 cách. Vậy tất cả có 100 cách lựachọn.Toán rời rạc5Nguyờn lý cng: Vớ dVí dụ 3. Hỏi rằng giá trị của k sẽ là bao nhiêu sau khi đoạn chơng trình PASCAL sau đợc thực hiện?n1:=10; n2:=20; n3:=30;k:=0;for i1:= 1 to n1 do k:=k+1;for i2:= 1 to n2 do k:=k+1;for i3:= 1 to n3 do k:=k+1;Giải: Đầu tiên giá trị của k đợc gán bằng 0. Có 3 vòng lặp forđộc lập. Sau mỗi lần lặp của mỗi một trong 3 vòng for, giá trịcủa k tăng lên 1. Vòng for thứ nhất lặp 10 lần, vòng for thứhai lặp 20 lần, vòng for thứ ba lặp 30 lần. Vậy, kết thúc 3 vònglặp for giá trị của k sẽ là 10+20+30= 60.Toỏn ri rc6Nguyên lý cộng: Ví dụVí dụ 4: Có bao nhiêu xâu gồm 4 chữ số thập phân cóđúng 3 ký tự là 9?Giải: Xâu có thể chứa:• Ký tự khác 9 ở vị trí thứ nhất• hoặc ký tự khác 9 ở vị trí thứ hai• hoặc ký tự khác 9 ở vị trí thứ ba• hoặc ký tự khác 9 ở vị trí thứ tư• Ta có thể sử dụng qui tắc cộng• Đối với mỗi trường hợp, có 9 khả năng chọn ký tựkhác với 9 (bất kể chữ số khác 9 nào trong 9 chữ số0, 1, ...,8)• Vậy, đáp số là 9+9+9+9 = 36Toán rời rạc71.2. Nguyờn lý nhõnThe product ruleNếu mỗi thành phần ai của bộ có thứ tự k thànhphần (a1, a2, ..., ak) có ni khả năng chọn (i = 1, 2, ...,k), thì số bộ sẽ đợc tạo ra là tích số của các khả năngnày n1n2 ... nk.Một hệ quả trực tiếp của nguyên lý nhân:N(A1 ì A2 ì ... ì Ak) = N(A1) N(A2) ... N(Ak),với A1, A2, ..., Ak là những tập hợp nào đó, nói riêng:N(Ak) = [N(A)]k .Toỏn ri rc81.2. Nguyờn lý nhõnThe product ruleTrong nhiều bài toán đếm, chỉ sau khi xây dựng xong thànhphần thứ nhất ta mới biết cách xây dựng thành phần thứ hai,sau khi xây dựng xong hai thành phần đầu ta mới biết cáchxây dựng thành phần thứ ba,... Trong trờng hợp đó có thể sửdụng nguyên lý nhân tổng quát:Giả sử ta xây dựng bộ có thứ tự k thành phần (a1, a2, ..., ak)theo từng thành phần vàa1 có thể chọn bởi n1 cách;Sau khi a1 đã chọn, a2 có thể chọn bởi n2 cách;...Sau khi a1, a2,...,ak-1 đã chọn, ak có thể chọn bởi nk cách;Thế thì số bộ đợc tạo ra là tích số n1n2 ... nk.Toỏn ri rc9Nguyờn lý nhõn: Vớ dVí dụ 1. Từ Hà nội đến Huế có 3 cách đi: máy bay, ô tô,tàu hoả. Từ Huế đến Sài gòn có 4 cách đi: máy bay, ô tô,tàu hoả, tàu thuỷ. Hỏi từ Hà nội đến Sài gòn (qua Huế)có bao nhiêu cách đi?Giải: Mỗi cách đi từ Hà nội đến Sài gòn (qua Huế) đợcxem gồm 2 chặng: Hà nội - Huế và Huế - Sài gòn. Từđó, theo nguyên lý nhân, số cách đi từ Hà nội đến Sàigòn là 3 ì 4 = 12 cách.H niHuToỏn ri rcSi gũn10Nguyờn lý nhõn: Vớ dVí dụ 2. Hỏi rằng giá trị của k sẽ là bao nhiêu sau khi đoạn chơng trình PASCAL sau đợc thực hiện?n1:=10; n2:=20;k:=0;for i1:=1 to n1for i2:=1 tofor i3:=1 to n3n3:=30;don2 dodo k:=k+1;Giải: Đầu tiên giá trị của k đợc gán bằng 0. Có 3 vòng lặp forlồng nhau. Sau mỗi lần lặp của vòng for, giá trị của k tăng lên1. Vòng for thứ nhất lặp 10 lần, vòng for thứ hai lặp 20 lần,vòng for thứ ba lặp 30 lần. Vậy, theo nguyên lý nhân, kết thúc 3vòng lặp for lồng nhau, giá trị của k sẽ là 10 ì 20 ì 30 = 6000.Toỏn ri rc11Nguyên lý nhân: Ví dụVí dụ 3: Hỏi có bao nhiêu lá cờ gồm 3 vạch mầu, mầu của mỗi vạchlấy từ ba mầu xanh, đỏ, trắng sao cho:a) Không có hai vạch liên tiếp nào cùng màub) Không có hai vạch nào cùng màuGiải. Đánh số các vạch của lá cờ bởi 1, 2, 3 từ trên xuống.Trường hợp a)Màu của vạch 1 có 3 cách chọn.Sau khi màu của vạch 1 đã chọn, màu của vạch 2 có 2 cách chọn(không được chọn lại màu của vạch 1).Sau khi màu của hai vạch 1, 2 đã chọn, màu của vạch 3 có 2 cáchchọn (không được chọn lại màu của vạch 2).Theo nguyên lý nhân số lá cờ cần đếm trong trường hợp a) là 3.2.2=12Toán rời rạc12Nguyên lý nhân: Ví dụ 3 (tiếp)Trường hợp b): Màu của vạch 1 có 3 cách chọn. Sau khi màu của vạch 1 đã chọn, màu của vạch 2 có2 cách chọn (không được chọn lại màu của vạch 1). Sau khi màu của hai vạch 1, 2 đã chọn, màu củavạch 3 có 1 cách chọn (không được chọn lại màucủa vạch 1 và 2). Theo nguyên lý nhân số lá cờ cần đếm trong trườnghợp b) là 3.2.1=6Toán rời rạc13Nguyên lý nhân: Ví dụVí dụ 4. Có bao nhiêu xâu gồm 4 chữ số thập phâna) không chứa một chữ số nào hai lần?Chúng ta sẽ chọn chữ số vào lần lượt từng vị trí••••Ký tự thứ nhất có 10 cách chọnKý tự thứ hai có 9 cách (không chọn lại chữ số đã chọn vào vịtrí thứ nhât)Ký tự thứ ba có 8 cách chọnKý tự thứ tư có 7 cách chọnTổng cộng có 10*9*8*7 = 5040 xâu cần đếm.b) kết thúc bởi chữ số chẵn?Ba ký tự đầu tiên mỗi ký tự có 10 cách chọnKý tự cuối cùng có 5 cách chọnTổng cộng có 10*10*10*5 = 5000 xâu cần đếm.Toán rời rạc14Các ví dụ phức tạp hơnKhi nào sử dụng qui tắc cộng?Khi nào sử dụng qui tắc nhân?Ta có thể sử dụng phối hợp cả qui tắc cộng vàqui tắc nhânBằng cách đó ta có thể giải được nhiều bài toánthú vị và phức tạp hơnToán rời rạc15Chụp ảnh đám cướiXét bài toán: Có 10 người tham gia vào việc chụp ảnh kỷ niệm ởmột đám cưới, trong đó có cô dâu và chú rể. Ta xét bức ảnhchỉ gồm 6 người trong họ.a) Có bao nhiêu bức ảnh trong đó có mặt cô dâu?Qui tắc nhân: Xếp chỗ cho cô dâu VÀ sau đó xếp chỗ cho những nhân vậtcòn lại trong bức ảnh.Trước hết xếp chỗ cho cô dâu: Cô dâu có thể đứng ở 1 trong 6 vị tríTiếp đến, xếp 5 nhân vật còn lại của bức ảnh nhờ sử dụng qui tắc nhân: Có9 người để chọn nhân vật thứ hai, 8 người để chọn nhân vật thứ ba, ...Tổng cộng có 9*8*7*6*5 = 15120 cách xếp 5 nhân vật còn lại củabức ảnh.Qui tắc nhân cho ta 6 * 15120 = 90 720 bức ảnhToán rời rạc16Chụp ảnh đám cướib) Có thể chụp bao nhiêu bức ảnh mà trong đó có mặt cả cô dâu lẫn chú rể?Qui tắc nhân: Xếp dâu/rể VÀ sau đó xếp những nhân vật còn lại trongbức ảnhTrước hết xếp dâu và rể•••Cô dâu có thể xếp vào 1 trong 6 vị tríChú rể có thể xếp vào 1 trong 5 vị trí còn lạiTổng cộng có 30 khả năngTiếp theo, xếp chỗ cho 4 nhân vật còn lại trong bức ảnh theo qui tắcnhân••Có 8 người để chọn nhân vật thứ ba, 7 người để chọn nhân vật thứ tư, ...Tổng cộng có 8*7*6*5 = 1680Theo qui tắc nhân có 30 * 1680 = 50 400 bức ảnhToán rời rạc17Chụp ảnh đám cướic) Có bao nhiêu bức ảnh mà trong đó có mặt chỉ một người trong cặp tân hôn?Qui tắc cộng: Chỉ xếp cô dâu•••Qui tắc nhân: xếp cô dâu và sau đó xếp các nhân vật còn lạiTrước hết xếp cô dâu: Cô dâu có thể đứng ở một trong 6 vị tríTiếp đến, xếp những nhân vật khác theo qui tắc nhân: Có 8 người đểchọn nhân vật thứ hai, 7 để chọn nhân vật thứ ba, v.v. (Ta không đượcchọn chú rể!)Tổng cộng = 8*7*6*5*4 = 6720•Qui tắc nhân cho 6 * 6720 = 40 320 khả nănghoặc chỉ xếp chú rể•Số lượng khả năng cũng giống như cô dâu: 40 320Qui tắc cộng cho 40 320 + 40 320 = 80 640 khả năngToán rời rạc18Chụp ảnh đám cướiMột cách khác để thu được lời giải câu c)c) Có bao nhiêu bức ảnh mà trong đó có mặt chỉ một ngườitrong cặp tân hôn?• Tổng số bức ảnh trong đó có cô dâu (có hoặc không cóchú rể): 90 720• Theo kết quả phần (a)• Tổng số bức ảnh có mặt cả dâu lẫn rể: 50 400• Theo kết quả phần (b)• Số bức ảnh chỉ có mặt cô dâu: 90 720 – 50 400 = 40 320• Đó cũng là số bức ảnh chỉ có mặt chú rể• Tổng cộng = 40 320 + 40 320 = 80 640Toán rời rạc19Số lượng Mật khẩuMỗi cá nhân sử dụng mạng máy tính đều có mậtkhẩu gồm từ 6 đến 8 ký tự, mỗi ký tự là chữ cáiin hoa hoặc chữ số. Mật khẩu phải chứa ít nhấtmột chữ số. Có bao nhiêu mật khẩu khác nhau?Theo qui tắc cộng, nếu P là số lượng mật khẩuvà P6, P7, P8 là số lượng mật khẩu độ dài 6, 7, và8, tương ứng, thìP = P6+P7+P8Toán rời rạc20Số lượng Mật khẩuP6 = số lượng mật khẩu gồm 6 ký tự chứa ít nhất một chữ số= (tổng số mật khẩu gồm 6 ký tự) trừ bớt (số mật khẩu gồm 6 ký tựkhông chứa chữ số)= (26+10)(26+10)(26+10)(26+10)(26+10) – (26)(26)(26)(26)(26)(26) =366 – 266= 1 867 866 560Toán rời rạc21Số lượng Mật khẩuTương tự như vậy, ta cóP7 = 367 – 267= 70 332 353 920P8 = 368 – 268= 2 612 282 842 880P6 + P7 + P8 = 2 684 483 063 360Chú ý: Nếu máy tính 2 GHz có thể thử 200 triệu mật khẩutrong một giây, thì trong thời gian bao nhiêu lâu có thể xácđịnh được mật khẩu để thâm nhập hệ thống máy tính này?(2 684 483 063 360/200 000 000)/(60*60) giờGần 4 tiếng đồng hồ!Toán rời rạc22Chương 1. BÀI TOÁN ĐẾM1.Nguyên lý cộng và nguyên lý nhân2.Các cấu hình tổ hợp cơ bản3.Nguyên lý bù trừ4.Công thức đệ qui5.Hàm sinhToán rời rạc232. Các cấu hình tổ hợp cơ bảnCác cấu hình tổ hợp cơ bản là:• Chỉnh hợp lặp,• Chỉnh hợp không lặp,• Hoán vị,• Tổ hợpPhép đếm các cấu hình tổ hợp cơ bản được sử dụng đểgiải các bài toán đếm phức tạp hơnGiả sử X là tập n phần tử, mà không giảm tổng quát tacó thể coi X là tập gồm các số 1, 2, ..., n.Toán rời rạc24Chỉnh hợp lặpĐịnh nghĩa. Ta gọi chỉnh hợp lặp chập m từ n phần tử củaX là bộ có thứ tự gồm m thành phần, mỗi thành phần đềulà phần tử của X.Ký hiệu số lượng chỉnh hợp lặp chập m từ n phần tử là AnmTheo định nghĩa, một chỉnh hợp lặp chập m từ n phần tửcủa X có thể biểu diễn bởi(a1, a2, ..., am), ai ∈ X, i = 1, 2, ..., m.Dễ thấy tập tất cả các chỉnh hợp lặp chập m từ n phần tửcủa X chính là Xm. Vì vậy, theo nguyên lý nhân ta cóĐịnh lý 1. Anm = nm.Toán rời rạc25

Trích đoạn

• Tiếp đến học sinh thứ hai cú thể xếp vào 1 trong 9 chỗ cũn lại,
• Công thức đệ qu
• Phỏt biểu nguyờn lý
• Xõy dựng cụng thức đệ qui  Do đú, theo nguyờn lý cộng:

Tài liệu liên quan

• Giáo trình toán rời rạc - Chương 1
  • 18
  • 1
  • 7
• Giáo trình Toán rời rạc Chương 1
  • 23
  • 1
  • 3
• Toán rời rạc - Chương 1
  • 18
  • 682
  • 1
• toan roi rac chuong 1
  • 18
  • 438
  • 0
• Toán rời rạc - chương 1 - Một số khái niệm cơ bản về logic và đại số quan hệ
  • 59
  • 2
  • 35
• Trắc nghiệm toán rời rạc-chuơng 1 ppt
  • 31
  • 1
  • 15
• Bài giảng toán rời rạc chương 1 cơ sở logic
  • 20
  • 4
  • 2
• QUY HOẠCH RỜI RẠC - CHƯƠNG 1 pps
  • 20
  • 351
  • 0
• Slide bài giảng môn khoa học quản lý: Chương 1: tổng quan về quản lý tổ chức
  • 34
  • 1
  • 1
• Bài giảng Công trình ngoài khơi - Chương 1 Tải trọng tác dụng lên Công trình ngoài khơi
  • 86
  • 558
  • 1

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(1.48 MB - 176 trang) - Slide bài giảng Toán rời rạc - chương 1 bài toán đếm nguyên lý cộng và nguyên lý nhân Tải bản đầy đủ ngay ×