Bài giảng Toán rời rạc - Bài 1: Mở đầu - Nguyễn Văn Hiệu

Nội dung text: Bài giảng Toán rời rạc - Bài 1: Mở đầu - 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(A )+N(A )+ +N(A ) 1 2 k . 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 <10 ; i ++) s += 1; for( j = 0; j < 20; j++) s += 1; for (k = 0; k <30; k++) s += 1; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
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 <10 ; i for (k = 0; k ++) for( j = 0; j < 20; j++) <30; k++) s += 1; s += 1; s += 1; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
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 <10 ; i ++) for( j = 0 ; j <20 ; j++) for (k= 0 ; k <30; k++) S += 1; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
16. 1. Nguyên lý cơ bản 1.2. Nguyên lý nhân Ví dụ 2 for( S=0, i = 0; i <10 ; i ++) ĐS: 6000 for( j = 0; j < 20 ; j ++) for(k= 0; k < 30 ; k ++) S+=1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
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à: nk – 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
21. 2. Các cấu hình tổ hợp cơ bản 2.1. Chỉnh hợp lặp Ví dụ 3 Tính số tập con của một tập gồm n phần tử? HD: X = {x1,x2, ,xn}, Tập con A thuộc X: b =(b1,b2, ,bn) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21
22. 2. Các cấu hình tổ hợp cơ bản 2.2. Chỉnh hợp không lặp . Một chỉnh hợp không 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ử không được lặp lặp lại. . Số chỉnh hợp không lặp chập k không lặp của n phần tư: n*(n-1)* (n-k+1), với k <=n . Minh họa X = {x,y,z}, k =2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22
23. 2. Các cấu hình tổ hợp cơ bản 2.2. Chỉnh hợp không lặp Ví dụ 1 Tính số đơn ánh từ tập k phần tử vào tập n phần tử Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23
24. 2. Các cấu hình tổ hợp cơ bản 2.3. Hoán vị . Một hoán vị của một tập n phần tử là một cách sắp sếp có thứ tự các phần tử đó. . Một hoán vị của n phần tử là trường hợp riêng của chỉnh hợp không lặp khi k = n. . Số hoán vị của tập n phần tử là n*(n-1)* *1 = n! . Minh họa X = {x,y,z} Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24
25. 2. Các cấu hình tổ hợp cơ bản 2.3. Hoán vị Ví dụ 1 Có 6 người đứng xếp thành một hàng ngang để chụp ảnh. Hỏi có thể bố trí bao nhiêu kiểu? Ví dụ 2 Cần bố trí thực hiện n chương trình trên máy vi tính. Hỏi có bao nhiêu cách? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 25
26. 2. Các cấu hình tổ hợp cơ bản 2.4. Tổ hợp không lặp . Một tổ hợp chập k của n phần tử là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ tập n phần tử. . Số tổ hợp chập k của n phần tử là n( n 1)( n 2) ( n k 1) n ! k Cn k! ( n k )! k ! . Tổ hợp chập k của n phần tử luôn là số nguyên thì có kết quả lý thú số học sau: tích của k số tự nhiên liên tiếp bao giờ cũng chi kết cho k! Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26
27. 2. Các cấu hình tổ hợp cơ bản • Tính chất 1: (đối xứng) CCk n k nn • Tính chất 2: (điều kiện đầu) 0 n CCnn 1 • Tính chất 3: (công thức đệ quy) k k 1 k Cn C n 11 C n , n k 0 Why Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27
28. 2. Các cấu hình tổ hợp cơ bản 2.4. Tổ hợp Ví dụ 1 Có n đội bóng thi đấu vòng tròn. Hỏi phải tổ chức bao nhiêu trận? Ví dụ 2 Cho một đa giác lồi n (n>=4) đỉnh , nếu biết rằng không có ba đường chéo nào đồng quy tại điểm ở trong đa giác. Hỏi có bao nhiêu giao điểm của các đường chéo nằm trong đa giác? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 28
29. Tam giác Pascal Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29
30. Khai triển (x y )n ( x y )( x y ) ( x y ) n = C ( n , k ) xk y n k k 0 n (x 1)nk C ( n , k ) x k 0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30
31. Bài tập