intTypePromotion=1
ADSENSE

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

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:31

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

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.

Chủ đề:
Lưu

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

  1. BÀI 1 MỞ ĐẦU Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
  2. Nội dung 1. Nguyên lý cơ bản 2. Cấu hình tổ hợp cơ bản
  3. 1. 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 = ?
  4. 1. Nguyên lý cơ bản 1.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 4
  5. 1. 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 5
  6. 1. 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 6
  7. 1. Một số nguyên lý cơ bản 1.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 7
  8. 1. Một số nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 2  80 “MS”  10 “ES”,  10 “DS” Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
  9. 1. 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 9
  10. 1. Một số nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 3 Tính giá trị của s = ? s = 0; for( i = 0; i
  11. 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
  12. 1. Nguyên lý cơ bản 1.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 12
  13. 1. Nguyên lý cơ bản 1.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 13
  14. 1. Nguyên lý cơ bản 1.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 14
  15. 1. Nguyên lý cơ bản 1.2. Nguyên lý nhân Ví dụ 2 S = 0; for( i = 0; i
  16. 1. Nguyên lý cơ bản 1.2. Nguyên lý nhân Ví dụ 2 for( S=0, i = 0; i
  17. 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 17
  18. 2. Các cấu hình tổ hợp cơ bản 2.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ứ tự gồm k phần từ lấy từ n phần tử, trong đó các phần tử có thể lặp lại. – Số tất cả chỉnh hợp lặp chập k của n phần tử là: n k – X = {x,y,z}, k = 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
  19. 2. Các cấu hình tổ hợp cơ bản 2.1. Chỉnh hợp lặp Ví dụ 1  Tập k phần tử  Tập n phần tử  f = (f1, f2, …, fk).  fi có n giá trị.  Kq: n mũ k Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
  20. 2. Các cấu hình tổ hợp cơ bản 2.1. Chỉnh hợp lặp Ví dụ 2 Tính số xâu nhị phân có độ dài n?  1bit có hai khả năng chọn  Kq: 2 mũ n. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2