Bài giảng Toán ứng dụng trong Tin học: Chương 2 - Tính toán & xác suất

Mời các bạn cùng tìm hiểu các nguyên lý; giải tích tổ hợp được trình bày cụ thể trong "Bài giảng Toán ứng dụng trong Tin học: Chương 2 - Tính toán & xác suất".
Nội dung trích xuất từ tài liệu:
Bài giảng Toán ứng dụng trong Tin học: Chương 2 - Tính toán & xác suất TRƯỜNG CAO ĐẲNG NGHỀ iSPACE 137C Nguyễn Chí Thanh, P 9, Q 5, TP. Hồ Chí Minh Web: ispace.edu.vn - Tel: 08.6.261.0303 - Fax: 08.6.261.0304 Bài giảng TOÁN ỨNG DỤNG TRONG TIN HỌC (Tài liệu cập nhật – 2009) Chương 2 TÍNH TOÁN & XÁC SUẤT www.math.hcmus.edu.vn/~ntchuyen/ispace Mail: ntchuyen@gmail.com TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… I. Các nguyên lý A. Tính toán 1. Nguyên lý cộng Giả sử để làm công việc A có 2 phương pháp - Phương pháp 1 có n cách làm - Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n+m Ví dụ. An có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… Phép đếm I. Các nguyên lý 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Ví dụ: A B C Có 3.2 =6 con đường đi từ A đến C TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… I. Các nguyên lý Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1 . c=0. Khi đó c có 1 cách chọn a có 5 cách chọn ( a X\{0} ) TH1 có 1.4.5 =20 b có 4 cách chọn ( b X\{a, 0} ) TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn ( a X\{c, 0} ) TH2 có 2.4.4 =32 b có 4 cách chọn ( b X\{a, c} ) Vậy có 20+32 =52 TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… I. Các nguyên lý 3- Nguyên lý Dirichlet Nếu có n vật đặt trong k hộp n  tồn tại 1 hộp chứa ít nhất k vật n là số nguyên dương nhỏ nhất thoả điều kiện k n n n,      n n hay 1 k k k k k ,       Ví dụ 2.9: [x] gọi là hàm sàn trên của x 4 4 1 5 5 5 5 2 4 4 0 4 4 5 5 TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… I. Các nguyên lý 3. Nguyên lý chuồng bồ câu (Derichlet) x Gọi ��là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít n / k �bồ câu trở lên. nhất một chuồng chứa từ � Ví dụ. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên - Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… I. Các nguyên lý Ví dụ Trong một nhóm có 366 người thì ít nhất có 2 người trùng ngày sinh nhật? Giải: 366 � � Một năm có 365 ngày  n=365, k=366 � �=2 Theo Nguyên lý Dirichlet 365 � �  tối thiểu có 2 người trùng ngày sinh nhật TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009… I. Các nguyên lý Ví dụ Trong một nhóm có 28 từ tiếng Anh thì ít nhất có 2 từ bắt đầu bằng cùng một chữ cái? a b c d e f g h i j k l m 1 2 3 4 5 6 7 8 9 10 11 12 13 n o p q r s t u v w x y z Giải: 14 15 16 17 18 19 20 21 22 23 24 25 26 Bảng chữ cái tiếng Anh có 26 mẫu �28 � 28 tự  n=26, k=28 � �= 2 Theo Nguyên lý Dirichlet ...