Toán học - Bài 1: Mở đầu

MỞ ĐẦU Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1 BÀI 1 Giáo viên: TS. Nguyễn Văn Hiệu Email: [email protected] Nội dung 1. Nguyên lý cơ bản 2. Cấu hình tổ hợp 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ản 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ếu { A1, A2, ..., Ak } là một phân hoạch của X thì  Nếu A là một tính chất cho trên X thì Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4 N(A B)= N(A)+N(B) N(X)= N(A1)+N(A2)+ +N(Ak) N(A)= N(X) - N( ) A 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 1. Một số nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6 Toàn đoàn Nam (10) Cơ tướng Cờ vua Nữ Cờ tướng Cờ vua ĐS: 24 người = 14 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 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 1. Nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9 Khả năng chọn MS (80) ES (10) DS(10) ĐS: 100 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 = ? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10 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; 1. Một số nguyên lý cơ bản 1.1. Nguyên lý cộng Ví dụ 3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11 s = ? for( i = 0; i <10 ; i ++) s += 1; for( j = 0; j < 20; j++) s += 1; for (k = 0; k <30; k++) s += 1; ĐS: 60 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ả :  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 N(A1 A2   Ak )= N(A1)N(A2)...N(Ak) 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 1. Nguyên lý cơ bản 1.2. Nguyên lý nhân Ví dụ 1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14 HN SG ĐN ĐS: 12 Chặng 1 Chặng 2 1. Nguyên lý cơ bản 1.2. Nguyên lý nhân Ví dụ 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15 S = 0; for( i = 0; i <10 ; i ++) for( j = 0 ; j <20 ; j++) for (k= 0 ; k <30; k++) S += 1; 1. Nguyên lý cơ bản 1.2. Nguyên lý nhân Ví dụ 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16 for( S=0, i = 0; i <10 ; i ++) for( j = 0; j < 20 ; j ++) for(k= 0; k < 30 ; k ++) S+=1 ĐS: 6000 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 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à: – X = {x,y,z}, k = 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18 kn 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ử Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19  f = (f1, f2, , fk).  fi có n giá trị.  Kq: n mũ k 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? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20  1bit có hai khả năng chọn  Kq: 2 mũ n. 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ử? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21 HD: X = {x1,x2,,xn}, Tập con A thuộc X: b =(b1,b2,,bn) 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 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 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 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 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à  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 ( 1)( 2)...( 1) ! ! ( )! ! k n n n n n k n C k n k k        2. Các cấu hình tổ hợp cơ bản • Tính chất 1: (đối xứng) • Tính chất 2: (điều kiện đầu) • Tính chất 3: (công thức đệ quy) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27 k n k n nC C  0 1nn nC C  1 1 1 , 0 k k k n n nC C C n k     Why 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 Tam giác Pascal Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29 Khai triển Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30 0 ( ) ( )( )...( ) = ( , ) n n k n k k x y x y x y x y C n k x y         0 ( 1) ( , ) n n k k x C n k x    Bài tập