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

Chia sẻ: Lê Trang | Ngày: | Loại File: PPT | Số trang:62

0
83
lượt xem
17
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:
Lưu

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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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<2n (n nguyên dương)  06/20/11 8
  9. 06/20/11 9
  10. Bài toán đếm Đếm có bao nhiêu cấu hình tổ hợp thõa mãn  tính chất nào đó 06/20/11 10
  11. Bài tập Bài 1 Có bao nhiêu cách đăng ký biển xe ô tô nếu mỗi biển chứa một dòng 3 chữ cái, tiếp sau là 3 chữ số?(Bảng chữ cái có 26 chữ) Giải (C1,C2,C3,S4,S5,S6) C1,C2,C3: có 26 x 26 x 26 cách chọn. S1,S2,S3 có 10 x 10 x 10 cách chọn Tổng số là: 263 . 103 = 17 576 000 06/20/11 11
  12. Bài 2 Ghi nhãn cho ghế ở giảng đường bắt đầu bằng một chữ cái và một số nguyên dương ≤ 100. Hỏi có bao nhiêu ghế có nhãn khác nhau? Giải Một nhãn có dạng (C,S) Có 26 cách chọn C Có 100 cách chọn S Vậy có 26 x 100 = 2600 nhãn 06/20/11 12
  13. Bài 3: Mật khẩu được đặt theo quy tắc sau - Dài từ 6 đến 8 ký tự - Mỗi ký tự là một chữ cái hoặc chữ số - Mỗi mật khẩu phải chứa ít nhất 1 chữ số. Hỏi có bao nhiêu mật khẩu? Giải P = P6 + P7 + P8 Tính P6: Trước hết tính xem có bao nhiêu mật khẩu dài 6 ký tự chứa chữ cái hoặc chữ số.(26+10 = 36)6). Tính có bao nhiêu mật khẩu không chứa chữ số nào:(toàn chữ cái): 266 P6 = 366 - 266 Tương tự P7= 367 - 267 ; P8 = 368 - 268; 06/20/11 13 Vậy P = P + P + P
  14. Bài 4 Có bao nhiêu xâu nhị phân độ dài 8 bit hoặc được bắt đầu bằng bit 1 hoặc được kết thúc bằng 2 bit 00. Giải - Đếm có bao nhiêu xâu bắt đầu bằng bit 1: 27 - Đếm có bao nhiêu xâu kết thúc bằng 00: 26 - Đếm có bao nhiêu xâu bắt đầu bằng 1 và kết thúc bằng 00: 25 - Kết quả = 27 + 26 - 25 = 128 + 64 - 32 = 160 06/20/11 14
  15. Bài 5 Một phiếu trắc nghiệm gồm 10 câu hỏi. Mỗi câu h ỏi có 4 phương án trả lời. Hỏi có bao nhiêu cách điền một phiếu trắc nghiệm nếu mọi câu hỏi đều phải trả lời. Giải Có bao nhiêu cách Một phiếu trả lời sẽ có dạng: điền nếu các câu {x1,x2,x3,x4,x5,x6,x7,x8,x9,x10} có thể bỏ trống? - có 4 cách chọn x1 Tượng tự có 4 cách chọn x2 .. x10 510 Vậy có tất cả 410 phương án 06/20/11 15
  16. Bài 6 Một trường có 18 sinh viên toán, và 325 sinh viên tin. a/ Có bao nhiêu cách chọn hai đại diện sao cho một là sinh viên toán, người kia là sinh viên tin? b/ Có bao nhiêu cách chọn một đại biểu hoặc là sinh viên toán hoặc là sinh viên tin? Giải a/ 18 x 325 = 5850 b/ 18 + 325 = 343 06/20/11 16
  17. Bài 7 Có bao nhiêu người có tên viết tắt bằng 3 chữ cái khác nhau, trong đó chữ cái đầu tiên là A. Giải Bảng chữ cái có 26 chữ cái. Một tên viết tắt có dạng AX1X2 Có 25 cách chọn X1 Có 24 cách chọn X2 (vì các chữ cái là khác nhau). Tổng số tên là: 24 x 25 = 600 06/20/11 17
  18. Bài 8 Có bao nhiêu xâu nhị phân có độ dài nhỏ hơn hoặc bằng n và chứa toàn số một, trong đó n là một số nguyên dương. Giải Xét n = 1: có một xâu {1} Xét n = 2: Có hai xâu {1} và {11} ...... n = k: có k xâu {1},{11},{111} .. {111111..11} Vậy có n xâu. 06/20/11 18
  19. Bài 9 Có bao nhiêu xâu gồm 3 chữ số thập phân có đúng hai chữ số 3. Giải Số đó có dạng 33X, 3X3 và X33. Vậy có tất cả 9 + 9 + 9 = 27 xâu Bài 10 Có bao nhiêu xâu gồm 3 chữ số thập phân bắt đầu bằng số lẻ. Giải Có 5 số lẻ: Vậy có tất cả 5 x 10 x 10 = 500. 06/20/11 19
  20. Bài 11 Cô dâu và chú rể mời 4 người bạn xếp hàng ngang để chụp ảnh với mình. Có bao nhiêu cách xếp hàng nếu a/ Cô dâu đứng cạnh chú rể Giải Ta có thể xem cô dâu và chú rể là một vị trí. Vậy một cách xếp hàng sẽ là một hoán vị của 5 vị trí = 5! Lưu ý: trường hợp hoán chuyển vị trí giữa cô dâu và chú rể . Kết quả:5! x 2 = 240 06/20/11 20
Đồng bộ tài khoản