Bài giảng Toán rời rạc: Bài 1 - TS. Nguyễn Văn Hiệu

Bài 1 "Mở đầu" thuộc bài giảng Toán rời rạc trình bày về nguyên lý cơ bản toán rời rạc, cấu hình tổ hợp cơ bản. Đây là tài liệu tham khảo hữu ích cho các bạn chuyên ngành Toán học.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 1 - TS. Nguyễn Văn Hiệu BÀI 1MỞ ĐẦU Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vnNguyễn Văn Hiệu, 2012, Discrete Mathematics 1 Nội dung1. Nguyên lý cơ bản2. Cấu hình tổ hợp cơ bản1. Nguyên lý cơ bản• A , B - tập hợp• N(A) = |A| = 3 • ‘3’  Lực lượng của A • ‘3’  Số pt của A• A hợp B = ?• A giao B = ?• A nhân B = ?1. Nguyên lý cơ bản1.1. 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)  Nếu { A1, A2, ..., Ak } là một phân hoạch của X thì N(X)= N(A1)+N(A2)+ …+N(Ak)  Nếu A là một tính chất cho trên X thì N(A)= N(X) - N( A) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 41. Nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 1 – {Cờ tướng, Cờ vua} – {Nam, Nữ } – Nam có 10 người. – Số thi cờ tướng(cả nam lẫn nữ) là 14. – Số Nữ thi cờ vua = Số Nam thi cờ tướng. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 51. Một số nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 1 ĐS: 24 người Toàn đoàn Nam (10) Nữ Cơ Cờ Cờ vua Cờ vua tướng tướng 14 = Nguyễn Văn Hiệu, 2012, Discrete Mathematics 61. Một số nguyên lý cơ bản1.1. Nguyên lý cộng Ví dụ 2 Trong một đợt phổ biến đề tài tốt nghiệp, Ban chủ nhiệm Khoa công bố danh sách các đề tài bao gồm: + 80 đề tài về chủ đề “xây dựng hệ thống thông tin quản lý” + 10 đề tài về chủ đề “ thiết kế phần mềm dạy học” + 10 đề tài về chủ đề “ Hệ chuyên gia”. Hỏi một sinh viên có bao nhiêu khả năng lựa chọn đề tài ? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 71. Một số nguyên lý cơ bản1.1. Nguyên lý cộng Ví dụ 2  80 “MS”  10 “ES”,  10 “DS” Nguyễn Văn Hiệu, 2012, Discrete Mathematics 81. Nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 2 ĐS: 100 Khả năng chọn MS (80) ES (10) DS(10) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 91. Một số nguyên lý cơ bản1.1. Nguyên lý cộng Ví dụ 3 Tính giá trị của s = ? s = 0; for( i = 0; i 1. Một số nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 3 ĐS: 60 s=? for( i = 0; i 1. Nguyên lý cơ bản1.2. Nguyên lý nhân  Một bộ có 2 thành phần (a1, a2) và mỗi ai có ni khả năng chọn, thì số bộ sẽ được tạo ra là: n1. n2  Hệ quả : N(A1 A2  … Ak )= N(A1)N(A2)...N(Ak)  Phát biểu lại: để thực hiện một thủ tục có 2 công việc kế tiếp nhau:  Thực hiện công việc thứ nhất có n1 cách  Ứng với cách thực hiện công việc thứ nhất có n2 cách thực hiện công việc thứ hai  Để hoàn thành thủ tục có số cách là : n1. n2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 121. Nguyên lý cơ bản1.2. Nguyên lý nhân Ví dụ 1  Từ Hà nội đền Đà nẵng có 3 cách đi: • Máy bay; • Ô tô; • Tàu hỏa;  Từ Đà nẵng đến Sài gòn có 4 cách đi: • Máy bay; • Ô tô ; • Tàu hỏa; • Tàu thủy.; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 131. Nguyên lý cơ bản1.2. Nguyên lý nhân ĐS: 12 Ví dụ 1 ĐN SG HN Chặng 1 Chặng 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 141. Nguyên lý cơ bản1.2. Nguyên lý nhân Ví dụ 2 S = 0; for( i = 0; i 1. Nguyên lý cơ bản1.2. Nguyên lý nhân Ví dụ 2 for( S=0, i = 0; i 1. Nguyên lý cơ bản Lời khuyên  Nếu đếm trực tiếp số cấu hình là khó,  Thì phân hoạch cấu hình cần đếm ra thành các cấu hình con:  s/d nguyên lý cộng cộng  Thì xây dưng cấu hình theo tầng bước.  s/d nguyên lý nhân Cảm nhận Nguyễn Văn Hiệu, 2012, Discrete Mathematics 172. Các cấu hình tổ hợp cơ bản2.1. Chỉnh hợp lặp – Một chỉnh hợp lặp chập k của n phần tử là một bộ có thứ ...