zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Bài toán đếm - ThS. Hoàng Thị Thanh Hà

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:41

Báo xấu

28
lượt xem 4
download

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

Bài giảng Toán rời rạc - Bài toán đếm được biên soạn gồm các nội dung chính sau: giới thiệu chung; cơ sở của phép đếm; nguyên lý dirichlet; các cấu hình tổ hợp; bài toán liệt kê; hệ thức truy hồi. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Bài toán đếm - ThS. Hoàng Thị Thanh Hà

Toán rời rạc (2): BÀI TOÁN ĐẾM Ths. Hoàng Th Thanh Hà Khoa Th ng kê –Tin h c Trư ng Đ i h c Kinh t Đ i h c Đà N ng 23 September 2008 Nội dung 1. GIỚI THIỆU CHUNG 2. CƠ SỞ CỦA PHÉP ĐẾM 3. NGUYÊN LÝ DIRICHLET 4. CÁC CẤU HÌNH TỔ HỢP 5. BÀI TOÁN LIỆT KÊ 6. HỆ THỨC TRUY HỒI 23 September 2008 1
Nội dung 1. GIỚI THIỆU CHUNG 2. CƠ SỞ CỦA PHÉP ĐẾM 3. NGUYÊN LÝ DIRICHLET 4. CÁC CẤU HÌNH TỔ HỢP 5. BÀI TOÁN LIỆT KÊ 6. HỆ THỨC TRUY HỒI 23 September 2008 1. GIỚI THIỆU CHUNG Lý thuyết tổ hợp là một phần quan trọng của TRR Nghiên cứu sự phân bố các phần tử vào các tập hợp. Được nghiên cứu từ thế kỷ 17 Liệt kê, đếm các đối tượng có tính chất nào đó -> rất quan trọng trong lý thuyết tổ hợp Chúng ta cần phải đếm các đối tượng để giải nhiều bài toán khác nhau 23 September 2008 2
1. GIỚI THIỆU CHUNG Ví dụ: Bài toán đếm: – Cần chọn hoặc là 01 sinh viên hoặc là 01 cán bộ trong khoa tham dự diễn đàn “Thanh niên với NCKH” của thành phố. Hỏi có bao nhiêu cách chọn 01 thành viên trên (khoa có 500 sinh viên và 20 cán bộ)? – Tính số mật khNu cho phép truy nhập vào hệ thống máy tính…? – Hãy chứng minh nếu có nhiều hơn 14 sinh viên thì có ít nhất 3 bạn sinh cùng một ngày trong tuần? – Có bao nhiêu cách chia 52 quân bài cho 4 người, mỗi người được chia 5 quân? – … 23 September 2008 1. GIỚI THIỆU CHUNG Trong chương này, chúng ta sẽ đề cập đến: – Những nguyên tắc đếm cơ bản: giải quyết được nhiều dạng bài toán khác nhau, làm cơ sở cho các bài toán đếm khác – Nguyên lý Dirichlet (nlý lồng chim bồ câu): giải bài toán tồn tại Chứng minh nếu có nhiều hơn 14 sinh viên, có ít nhất 3 bạn sinh cùng một ngày trong tuần – Tổ hợp, hoán vị, chỉnh hợp: giải bài toán đếm, liệt kê các cấu hình thỏa mãn điều kiện nào đó Có bao nhiêu cách chia 52 quân bài cho 4 người (mỗi người 5 quân)? – Kỹ thuật đếm mở rộng : hệ thức truy hồi, quan hệ chia để trị 23 September 2008 3
Nội dung 1. GIỚI THIỆU CHUNG 2. CƠ SỞ CỦA PHÉP ĐẾM 3. NGUYÊN LÝ DIRICHLET 4. CÁC CẤU HÌNH TỔ HỢP 5. BÀI TOÁN LIỆT KÊ 6. HỆ THỨC TRUY HỒI 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM Đặt vấn đề: – Mật kh u vào máy tính gồm 3, 4 hoặc 5 kí tự. Kí tự đầu tiên phải là chữ cái, các kí tự tiếp theo có thể số hoặc chữ cái, nhưng trong mật kh u đó phải có ít nhất một kí tự số. Hỏi có bao nhiêu mật kh u như thế? -> đếm số mật kh u có thể Các nguyên lý đếm cơ bản: – Nguyên lý cộng – Nguyên lý nhân – Nguyên lý bù trừ 23 September 2008 4
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý cộng Giả sử có k công việc T1, T2, ..., Tk, trong đó: – T1 làm bằng n1 cách, – T2 làm bằng n2 cách, – T3 làm bằng n3 cách, – ..., – Tk làm bằng nk cách Giả sử không có hai việc nào có thể làm đồng thời => số cách làm một trong k việc đó là n1+n2+...+nk 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý cộng Ví dụ: – Cần chọn hoặc là 01 sinh viên hoặc là 01 cán bộ trong khoa tham dự diễn đàn “Thanh niên với NCKH” của thành phố. Hỏi có bao nhiêu cách chọn 01 thành viên trên (khoa có 500 sinh viên và 20 cán bộ)? Trả lời: – Có 500 cách chọn 01 sinh viên và 20 cách chọn 01 cán bộ. Hai cách chọn này độc lập nhau. Vậy theo nguyên lý cộng : có tất cả 500+20=520 cách chọn 01 vị đại biểu nói trên 23 September 2008 5
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý cộng Phát biểu nguyên lý cộng dưới dạng ngôn ngữ tập hợp: Nếu A1, A2, ..., Ak là các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các tập hợp này bằng tổng số các phần tử của các tập thành phần |A1 ∪ A2 ∪...∪ Ak| = |A1| + |A2| + ... + |Ak| ∪ A1 A2 A3 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý cộng Ví dụ: – Cần chọn hoặc là 01 sinh viên hoặc là 01 cán bộ trong khoa tham dự diễn đàn “Thanh niên với NCKH” của TP. Hỏi có bao nhiêu cách chọn 01 thành viên trên (khoa có 500 sinh viên và 20 cán bộ)? Trả lời: – Gọi A1 là tập các cách chọn 1 trong 500 sinh viên, |A1| = 500. Gọi A2 là tập các cách chọn 1 trong 20 cán bộ trong khoa, |A2| = 20. – A1 ∩ A2 = ∅. Vậy số cách chọn 01 vị đại biểu hoặc thuộc A1 hoặc thuộc A2 là cách chọn 01 vị đại biểu của tập A1 ∪ A2 : |A1 ∪ A2 | = |A1| + |A2| =500+20=520 23 September 2008 6
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý nhân Giả sử một nhiệm vụ T nào đó được tách ra thành k việc T1, T2, ..., Tk. Nếu: – T1 có thể làm bằng n1 cách, – T2 có thể làm bằng n2 cách (sau khi đã làm xong T1), – … – Tk có thể làm bằng nk cách (sau khi đã làm xong T1, T2, ... Tk-1 ) Khi đó, số cách để thi hành nhiệm vụ T là tích của: n1.n2....nk 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý nhân Ví dụ: – Người ta có thể ghi nhãn cho những chiếc ghế trong một giảng đường bằng một chữ cái và một số nguyên dương không vượt quá 100. Hỏi nhiều nhất có bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau? Trả lời: – Thủ tục ghi nhãn ghế gồm hai việc: gán một trong 26 chữ cái gán một trong 100 số nguyên dương – Theo nguyên lý nhân: có 26.100=2600 cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãn cho 2600 chiếc ghế khác nhau 23 September 2008 7
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý nhân Ví dụ : – Mật khNu (MK) vào máy tính gồm 3, 4 hoặc 5 kí tự. Kí tự đầu tiên phải là chữ cái, các kí tự tiếp theo có thể số hoặc chữ cái, nhưng trong MK có ít nhất một kí tự số. Hỏi có bao nhiêu MK như thế? Trả lời: – Gọi P, P3, P4, P5 là số MK thỏa mãn điều kiện trên, trong đó P là số MK có độ dài tùy ý, P3, P4, P5 là số MK có độ dài tương ứng 3,4,5. – Theo quy tắc cộng : P = P3 + P4 + P5. Ta tìm P3, P4, P5? 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý nhân Trả lời (tiếp): – Kí tự đầu là chữ cái =>chọn 1 trong 52 (= 26.2 chữ hoa & chữ thường) – 2 kí tự tiếp theo chọn 1 trong 62 khả năng (52 chữ cái và 10 chữ số), 62.62 = 622 – Nhưng phải có ít nhất một kí tự số, nên ta trừ đi số xâu có độ dài là 2 mà không có kí tự số nào là 52.52=522 – Áp dụng nguyên lý nhân : P3 = 52. (622- 522) – Tương tự P4= 52. (623- 523 ) , P5 = 52. (624- 524 ) – =>P = 52. (622- 522 ) + 52. (623- 523 ) + 52. (624- 524 ) P = 7,563,580 23 September 2008 8
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý nhân Phát biểu nguyên lý nhân bằng ngôn ngữ tập hợp: nếu A1, A2,..., Ak là các tập hữu hạn, khi đó số phần tử của tích Descartes của các tập này bằng tích của số các phần tử của mọi tập thành phần |A1 x A2 x ... x Ak| = |A1|.|A2|...|Ak| 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý nhân Ví dụ : – Biển số đăng ký xe máy tại Đà Nẵng có dạng : 43 AX XXXX. Hỏi tổng số xe tối đa đăng ký tại Đà Nẵng là bao nhiêu? (Trong đó A là chữ cái viết hoa, X là kí tự số) Trả lời: – Gọi A1 là tập hợp các kí tự alphabet viết hoa A1={A,B,C,…, Z}, |A1| = 26. Gọi A2 là tập hợp các kí tự số, A2={0,1,2,…, 9}, |A2| = 10 – Thành phần 43 là cố định, muốn chọn 1 số đăng kí xe máy, ta chọn một phần tử của tích decartes sau: A1xA2xA2xA2xA2xA2. Theo quy tăc nhân, ta có tổng số xe máy đăng ký tối ta tại Đà Nẵng : |A1|.|A2|.|A2|.|A2|.|A2|.|A2| = 26.105 = 2 600 000 xe 23 September 2008 9
2. Bài tập: nguyên lý cộng, nhân 1. Đếm số n gồm 2 chữ số, nếu: a) n chẵn b) n lẻ c) n lẻ gồm 2 chữ số khác nhau d) n chẵn gồm 2 chữ số khác nhau 2. Một phiếu trắc nghiệm gồm 10 câu hỏi. Mỗi câu có 4 phương án Trả lời. a) Có bao nhiêu cách điền một phiếu trắc nghiệm nếu các câu hỏi đều được Trả lời b) Có bao nhiêu cách điền một phiếu trắc nghiệm nếu có thể bỏ trống 3. Có bao nhiêu người có tên họ viết tắt bằng 3 chữ cái khác nhau, trong đó không có chữ cái nào được lặp lại? 23 September 2008 2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý bù trừ Đặt vấn đề: Có bao nhiêu xâu nhị phân có độ dài là 8 bắt đầu hoặc kết thúc bằng 01? Trả lời: – Tách bài toán thành 2 phần : Tìm số xâu nhị phân độ dài là 8 bắt đầu bằng 01 (gọi là T1) Tìm số xâu nhị phân độ dài là 8 kết thúc bằng 01 (gọi là T2) (??? Sẽ có những xâu bắt đầu bằng 01 nhưng cũng kết thúc bằng 01 (gọi là T3)) – Nếu áp dụng nguyên lý cộng, tổng T1 + T2 là đáp án của bài toán. Nhưng vì có những xâu sẽ được cộng 2 lần (vừa bắt đầu bằng 01 vừa kết thúc bằng 01) => không thể áp dụng nguyên lý cộng cho bài toán này. 23 September 2008 10
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý bù trừ Nguyên lý bù trừ: – Khi hai công việc có thể được làm đồng thời, ta không thể dùng nguyên lý cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là hai tập hữu hạn, khi đó |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2| 23 September 2008 ∑| A i1 1≤i1
2. CƠ SỞ CỦA PHÉP ĐẾM: nguyên lý bù trừ Nguyên lý bù trừ tổng quát: – Với ba tập hợp hữu hạn A1, A2, A3, ta có: – |A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A2 ∩ A3| − |A3 ∩ A1| + |A1 ∩ A2 ∩ A3| – Bằng quy nạp, với k tập hữu hạn A1, A2, ..., Ak ta có: – | A1 ∪ A2 ∪ ... ∪ Ak| = N1 − N2 + N3 − ... + (−1)k-1Nk, – Trong đó Nm (1 ≤ m ≤ k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là: – Nm = ∑| A i1 1≤i1 < i2
∑| A i1 1≤i1
∑| A i1 1≤i1 2 bit cuối 01, 6 bit đầu tùy ý: ??????01 => |A2|= 26 = 64 Tìm số xâu bắt đầu 01, kết thúc 01 (chính là A1∩A2) =>2 bit đầu 01, 4 bit tiếp theo tùy ý, 2 bit cuối 01: 01????01 => |A1∩A2| = 24 =16 – Theo nguyên lý bù trừ: |A1|+|A2|- |A1∩A2| = 64+64-16 = 112 xâu 23 September 2008 14
Nội dung 1. GIỚI THIỆU CHUNG 2. CƠ SỞ CỦA PHÉP ĐẾM 3. NGUYÊN LÝ DIRICHLET 4. CÁC CẤU HÌNH TỔ HỢP 5. BÀI TOÁN LIỆT KÊ 6. HỆ THỨC TRUY HỒI 23 September 2008 3. Nguyên lý Dirichlet Đặt vấn đề: – 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 nhất trong một ngăn có nhiều hơn một con chim. – Nguyên lý này dĩ nhiên là có thể áp dụng cho các đối tượng không phải là chim bồ câu và chuồng chim. – Nguyên lý này giúp ta giải quyết một số bài toán tồn tại 23 September 2008 15
3. Nguyên lý Dirichlet Nguyên lý: Nếu có k+1 (hoặc nhiều hơn k) đồ vật được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật Nguyên lý này thường gọi là nguyên lý Dirichlet, mang tên nhà toán học người Đức thế kỷ 19. Ông thường xuyên sử dụng nguyên lý này trong công việc của mình 23 September 2008 3. Nguyên lý Dirichlet Ví dụ 3.1: Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau. Trả lời: Bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau, nên, nếu có 367 người, thì theo nguyên lý Dirichlet thì sẽ có ít nhất 2 người có cùng ngày sinh nhật. 23 September 2008 16
3. Nguyên lý Dirichlet Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất N/k đồ vật  – x : roundup (làm tròn trên: là số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x) 23 September 2008 3. Nguyên lý Dirichlet Ví dụ 3.2: Có 5 loại học bổng khác nhau. Hỏi phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người nhận cùng một loại nhận học bổng nào đó trong 5 loại trên? Trả lời: Gọi N là số sinh viên, khi đó N/5 = 6 khi và chỉ khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. Vậy số N cần tìm là 26 23 September 2008 17
3. Nguyên lý Dirichlet: một vài ứng dụng Trong nhiều ứng dụng thú vị của nguyên lý Dirichlet, khái niệm đồ vật và hộp cần phải được lựa chọn một cách khôn khéo Ví dụ 3.3: Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau 23 September 2008 3. Nguyên lý Dirichlet: một vài ứng dụng Trả lời: – Số người quen của mỗi người trong phòng nhận các giá trị từ 0 đến n − 1 (từ không quen ai cả đến quen tất cả n-1 ngươi còn lại) – Quen ở đây có giá trị 2 chiều, tức A quen B thì B quen A và ngược lại. => không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là n − 1 (tức là quen tất cả) – =>theo số lượng người quen, ta chỉ có thể phân n người ra thành n−1 nhóm. Vậy theo nguyên lý Dirichlet, tồn tại một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có số người quen là như nhau 23 September 2008 18
3. Nguyên lý Dirichlet: một vài ứng dụng Ví dụ 3.4: Chứng tỏ rằng trong n + 1 số nguyên dương không vượt quá 2n, tồn tại ít nhất một số chia hết cho số khác 23 September 2008 kj 2 3. Nguyên lý Dirichlet: một vài ứng dụng Trả lời: – Ta viết mỗi số nguyên a1, a2,..., an+1 dưới dạng aj = 2 k j .qj trong đó kj là số nguyên không âm còn qj là số dương lẻ nhỏ hơn 2n – Vì chỉ có n số nguyên dương lẻ nhỏ hơn 2n nên theo nguyên lý Dirichlet tồn tại i và j sao cho qi = qj = q. Khi k kj đó ai= 2 j .q và aj = 2 .q. Vì vậy, nếu ki ≤ kj thì aj chia hết cho ai còn trong trường hợp ngược lại ta có ai chia hết cho aj 23 September 2008 19
Nội dung 1. GIỚI THIỆU CHUNG 2. CƠ SỞ CỦA PHÉP ĐẾM 3. NGUYÊN LÝ DIRICHLET 4. CÁC CẤU HÌNH TỔ HỢP 5. BÀI TOÁN LIỆT KÊ 6. HỆ THỨC TRUY HỒI 23 September 2008 4. CÁC CẤU HÌNH TỔ HỢP (CHTH) Đặt vấn đề: Giả sử 1 đội bóng bàn có 10 cầu thủ. Người ta cần chọn: – 5 người để đi thi đấu ở nơi khác – và một danh sách có thứ tự gồm 4 cầu thủ để tham gia 4 trận chơi đơn khác Bài toán đặt ra: – có bao nhiêu cách chọn một tập 5 trong 10 cầu thủ để đi thi đấu – có bao nhiêu cách chọn một danh sách gồm 4 trong 10 cầu thủ đi thi đấu giải đơn ở 4 địa điểm khác nhau? Trong bài này chúng ta sẽ đi giải quyết vấn đề đó. 23 September 2008 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.