intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Codon_01 Codon_01 | Ngày: | Loại File: PPT | Số trang:77

Thêm vào BST
Báo xấu
135
lượt xem 20
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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".

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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…
  2. 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…
  3. 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…
  4. 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…
  5. 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…
  6. 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…
  7. 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…
  8. 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 26 � � 26  ít nhất có 2 từ bắt đầu trùng chữ cái TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  9. I. Các nguyên lý Ví dụ. Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng bằng 10. Giải. Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  10. I. Các nguyên lý Tính lượng SV tối thỉểu cần có ghi tên vào Ví dụ danh sách lớp A, để chắc chắn có ít nhất 6 SV có cùng một điểm trong thang điểm 5? Giải: Theo Nguyên lý Dirichlet n n� � n = 6 < +1    6 1 5 5 � 5� � � 5 Cách 1: n (5 * 5) 1 26 Cách 2: n 5 * 5 25 Vậy tối thiểu có 26 SV ghi tên vào DS lớp TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  11. Bài tập về nhà DẠNG 3 (Homework-3): Bài 3.1: Tính lượng SV tối thỉểu cần có ghi tên vào danh sách lớp CC02, để chắc chắn có ít nhất 5 SV có cùng một điểm trong thang điểm 10? Bài 3.2: Thời khoá biểu trường xx học từ thứ 2 đến thứ 7. CMR nều trường có 7 lớp thì it nhất có 2 lớp học cùng ngày? TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  12. Bài tập về nhà DẠNG 3 (Homework-3): Mỗi SV trong lớp A đều có quê ở 1 trong 64 tỉnh Bài 3.3: thành. Trường cần phải tuyển bao nhiêu SV để đảm bảo trong 1 lớp A có ít nhất: a/ 2 SV có quê cùng tỉnh b/ 10 SV có quê cùng tỉnh c/ 50 SV có quê cùng tỉnh Bài 3.4: Lớp có 32 SV, CMR có ít nhất 2 SV có tên bắt đầu cùng 1 chữ cái? TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  13. Bài tập về nhà DẠNG 3 (Homework-3): CMR trong 5 số chọn từ tập hợp 8 số Bài 3.5: {1,2,3,4,5,6,7,8} bao giờ cùng có 1 cặp số có tổng bằng 9? CMR trong 6 số bất kỳ chọn từ tập hợp 9 số Bài 3.6: nguyên dương đầu tiên {1,2,3,4,5,6,7,8,9} bao giờ cũng chứa it nhất 1 cặp số có tổng bằng 10? TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  14. I. Các nguyên lý 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó |A B|= |A|+|B| - |A B| A A B B TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  15. I. Các nguyên lý C A C B C A B C A B A B |A B C|=? TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  16. I. Các nguyên lý Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người Giải. Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Khi đó. Số học sinh của lớp là |A B |. Theo nguyên lý bù trừ ta có |A B|= |A|+|B| - |A B|=24+26-15=35 TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  17. I. Các nguyên lý Ví dụ 2.2: Cho các tập hợp như sau 1 9 A 1,2,3,4,5,6,7,8,9,10 3 7 5 A1 1,3,5,7,9 A2 2,4,6,8,10 2 4 6 A3 1,4,5,8 10 8 Hãy chứng minh A1 A 2 A 3 A1 A 2 A 3 A1 A 2 A 3 A1 A 2 A 2 A 3 A 3 A1 TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  18. I. Các nguyên lý Ví dụ 2.3: THỰC HÀNH: X 1,2,3,4,5,6,7,8,9,10,11,12 X1 X 2 X 3 .......... ................... ………………………………….. X1 ………………………………….. X1 1,3,7,9 X1 X 2 ………………………………….. X 2 2,4,6,10, X 2 ………………………………….. ................. ? .............. X3 5,7,10,11 X2 X3 .......... ..... ? ................ ………………………………….. X3 ................. ? .............. ………………………………….. ………………………………….. X 3 X1 .......... ...... ? ................ ………………………………….. X1 X2 X3 .......... ...... ? ................ ………………………………….. ? X1 X 2 X 3 X1 X1 X 2 X 2 X 2 X 3 X 3 X 3 X1 X1 X 2 X 3 TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  19. II. Giải tích tổ hợp 1. Hoán vị Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là P n Pn = n! = n.(n-1).(n-2)…1 Quy ước 0! =1 Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
  20. II. Giải tích tổ hợp Ví dụ. Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X  5! TOÁN ỨNG DỤNG Chương 2: TÍNH TOÁN – XÁC SUẤT HDXB-2009…
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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