Bài giảng Lý thuyết thông tin - Bùi Văn Thành

Nội dung text: Bài giảng Lý thuyết thông tin - Bùi Văn Thành

1. Trường Đại Học Cơng Nghệ Thơng Tin KHOA MẠNG & TRUYỀN THƠNG LÝ THUYẾT THƠNG TIN Bùi Văn Thành thanhbv@uit.edu.vn 1 Tháng 7 năm 2013
2. CHƯƠNG 0 XÁC SuẤT MA TRẬN 2
3. XÁC SUẤT (PROBABILITY) 1.1. THÍ NGHIỆM NGẪU NHIÊN, KHƠNG GIAN MẪU, BIẾN CỐ: 1.1.1. Thí nghiệm ngẫu nhiên (Random Experiment) Thí nghiệm ngẫu nhiên là một thí nghiệm cĩ hai đặc tính : -Khơng biết chắc hậu quả nào sẽ xảy ra. -Nhưng biết được các hậu quả cĩ thể xảy ra Ví dụ: Tung một con xúc sắc là một thí nghiệm ngẫu nhiên vì : -Ta khơng biết chắc mặt nào sẽ xuất hiện -Nhưng biết được cĩ 6 trường hợp xảy ra (xúc sắc cĩ 6 mặt 1, 2, 3, 4, 5, 6) Ràng buộc: 3 -Con xúc sắc đồng chất để 6 mặt đều cĩ thể xuất hiện như nhau. -Cách tung xúc sắc khơng cố ý thiên vị cho mặt nào hiện ra.
4. 1.1.2. Khơng gian mẫu (Sample Space) Tập hợp các hậu quả cĩ thể xảy ra trong thí nghiệm ngẫu nhiên gọi là khơng gian mẫu của thí nghiệm đĩ. Ví dụ: Khơng gian mẫu của thí nghiệm thảy một con xúc xắc là: E = {1, 2, 3, 4, 5, 6} Khơng gian mẫu của thí nghiệm thảy cùng một lúc hai đồng xu là: E = {SS, SN, NS, NN} với S: Sấp, N: Ngửa 1.1.3. Biến cố (Event) a) Biến cố -Mỗi tập hợp con của khơng gian mẫu là một biến cố -Biến cố chứa một phần tử gọi là biến cố sơ đẳng Ví dụ: Trong thí nghiệm thảy 1 con xúc sắc : -Biến cố các mặt chẵn là : {2, 4, 6}. Biến cố các mặt lẻ: {1, 3, 5} -Các biến cố sơ đẳng là : {1}, {2}, {3}, {4}, {5}, {6} 4
5. b) Biến cố xảy ra (hay thực hiện) Gọi r là một hậu quả xảy ra và A là một biến cố: -nếu r ∈ A ta nĩi biến cố A xảy ra -nếu r ∉ A ta nĩi biến cố A khơng xảy ra Ví dụ: Trong thí nghiệm thảy một con xúc sắc nếu mặt 4 xuất hiện thì: -Biến cố {2,4,6} xảy ra vì 4 ∈{2, 4, 6} -Biến cố {1,3,5} khơng xảy ra vì 4 ∉{1, 3, 5} Ghi chú: -φ⊂ E => φ là một biến cố ∀r, r ∉φ => φ là một biến cố vơ phương (biến cố khơng) -E ⊂ E => E là một biến cố ∀ r, r ∈ E => E là một biến cố chắc chắn 5
6. 1.1.4. Các phép tính về biến cố Cho 2 biến cố A, B với A⊂ E và B ⊂ E a) Biến cố hội A ∪ B (Union): Biến cố hội của 2 biến cố A và B được ký hiệu là A ∪ B: A ∪ B xảy ra  (A xảy ra HAY B xảy ra) b) Biến cố giao A ∩ B (Intersection): A ∩ B xảy ra (A xảy ra VÀ B xảy ra) 6 A∩B
7. c) Biến cố phụ A (Biến cố đối lập, Component of A):A xảy ra  A khơng xảy ra d) Biến cố cách biệt ( biến cố xung khắc, mutually exclusive event) A cách biệt với B  A ∩ B = φ A cách biệt với B  A với B khơng cùng xảy ra 7
8. Ví dụ: Trong thí nghiệm thảy một con xúc sắc, ta cĩ khơng gian mẫu: E = {1, 2, 3, 4, 5, 6} -Gọi A là biến cố mặt lẻ xuất hiện => A = {1, 3, 5} -Gọi B là biến cố khi bội số của 3 xuất hiện => B = {3, 6} -Gọi C là biến cố khi mặt 4 xuất hiện => C = {4}, biến cố sơ đẳng. Ta cĩ: A ∪ B = {1, 3, 5, 6} A ∩ B = {3} A = {2,4,6} : biến cố khi mặt chẵn xuất hiện. A ∩ C = φ => A và C là 2 biến cố cách biệt. e) Hệ đầy đủ (Collectively Exhaustive) Gọi A1, A2 , Ak là k biến cố trong khơng gian mẫu E Nếu A1∪ A2∪ ∪Ak = E thì K biến cố trên được gọi là một hệ đầy đủ. 8
9. 1.2. XÁC SUẤT (Probability). 1.2.1. Định nghĩa: Nếu thơng gian mẫu E cĩ N biến cố sơ đẳng và biến cố A cĩ n biến cố sơ đẳng thì xác suất của biến cố A là : P(A) = n(A)/N Một cách khác ta cĩ thể viết : P(A) = Số trường hợp A xảy ra/Số trường hợp cóthể xảy ra Ví dụ: Trong thí nghiệm thảy một con xúc sắc, xác suất biến cố các mặt chẵn xuất hiện là : P(A) =n(A)/N = 3/6=1/2 1.2.2. Tính chất: a. Gọi A là một biến cố bất kỳ trong khơng gian mẫu E : 0 ≤ P(A) ≤ 1 b. P (φ) = 0 => φ là Biến cố vơ phương P (E) = 1 => E là Biến cố chắc9 chắn
10. 1.2.3. Cơng thức về xác suất : a) Xác suất của biến cố hội: P (A ∪ B) = P (A) + P(B) - P( A ∩ B) Chứng minh: Gọi N : là số phần tử của khơng gian mẫu E n1: là số phần tử của (A - B) n2: là số phần tử của (A∩B) n3: là số phần tử của (B - A) n(A ∪ B)=n1 + n2 + n3= n1+n2+n2+n3 –n2 = n(A) +n(B) -n(A ∩ B) Do đĩ : n( A ∪ B)/N = n(A)/N + n(B)/N - n(A ∩ B )/N P(A ∪ B) = P(A) + P(B) - P(A ∩ B) 10
11. Ghi chú : Nếu A và B là 2 biến cố cách biệt, ta cĩ: A ∩ B = φ =>P(A ∩ B) = P(φ) = 0 ==> P (A ∪ B) = P(A) + P(B) b) Xác suất của biến cố phụ (biến cố đối lập) Biến cố phụ của biến cố A trong khơng gian mẫu E là A : P(A) + P (A) = 1 Chứng minh: A∪ A = E P (A∪A ) = P(E) P(A) + P( A ) - P(A ∩ A ) = 1 vì P(A∩ A ) = P(φ) = 0 11
12. 1.2.4. Cơng thức nhân về xác suất : a) Xác xuất cĩ điều kiện : Gọi P (B / A) là xác suất cĩ điều kiện của biến cố B sau khi biến cố A đã thực hiện. Với P(A) > 0 ; P(B) > 0 12
13. Chứng minh : Gọi E là khơng gian mẫu chứa hai biến cố A,B Giả sử A thực hiện rồi thì A là biến cố chắc chắn, ta cĩ thể chọn A làm khơng gian mẫu thu gọn. Biến cố B thực hiện sau khi biến cố A xảy ra trở thành biến cố B/A. Trong khơng gian mẫu biến cố B/A thực hiện nếu và chỉ nếu A ∩ B thực hiện. r ∈ B/A  r ∈ A ∩ B Theo định nghĩa, ta cĩ: P(B/ A) =n(A ∩ B) /n(A) =(n(A ∩ B) /N)/(n(A)/N) = P(A ∩ B)/P(A) 13
14. b) Cơng thức nhân về xác suất: Cho hai biến cố A và B trong khơng gian mẫu E, xác suất của biến cố giao được tính: P(A∩B) = P(B/A) * P(A) hay P(A∩B) = P(A/B) * P(B) c) Biến cố độc lập : Biến cố gọi là độc lập với biến cố A về phương diện xác suất nếu xác suất của biến cố B khơng thay đổi cho dù biến cố A đã xảy ra, nghĩa là: P(B/A) = P(B) ngược lại: P(A/B) = P(A) Trong trường hợp hai biến cố độc lập, cơng thức nhân trở thành: P(A∩B) = P(A) * P(B) 14
15. 1.2.5. Cơng thức xác suất đầy đủ - Cơng thức Bayes a) Cơng thức xác suất đầy đủ : Giả sử biến cố B xảy ra khi và chỉ khi một trong các biến cố của hệ đầy đủ cách biệt nhau từng đơi một A1, A2 , Ak xảy ra. Biết xác suất P(Ai) và P(B/Ai) hãy tìm P(B) A1 Ak A2 B 15 B ∩A1 B∩A2 B∩Ak
16. Theo giả thiết bài tốn thì B = (B ∩ A1) ∪ (B ∩ A2) ∪ ∪ (B∩Ak) P(B)= P[(B∩A1) ∪ (B∩A2) ∪ ∪ (B∩Ak)] = P(B∩A1) + P(B∩A2) + + P(B∩Ak) Vì: P(B∩Ai) = P(B/Ai) * P(Ai) k P(B) = ∑ P(B/ Ai)*P(Ai) i=1 Cơng thức này được gọi là cơng thức xác xuất đầy đủ. 16
17. Ví dụ: Trong nhà máy cĩ 4 phân xưởng.Phân xưởng I sản xuất chiếm 1/3 tổng sản lượng của nhà máy; Phân xưởng II chiếm 1/4; Phân xưởng III chiếm 1/4; Phân xưởng IV chiếm 1/6. Tỷ lệ phế phẩm tương ứng với các phân xưởng là 0,15; 0,08; 0,05; 0,01. Tìm xác suất để lấy ngẫu nhiên một sản phẩm trong kho sản phẩm của nhà máy thì sản phẩm đĩ là phế phẩm Giải : Gọi A1, A2, A3, A4 là biến cố lấy đúng một sản phẩm của phân xưởng I,II,III,IV. Gọi B là biến cố lấy được một phế phẩm B = (B∩A1) ∪ (B∩A2) ∪ (B∩A3) ∪ (B∩A4) 4 ==>P(B) = ∑P(B/ Ai)*P(Ai) i=1 Theo đề bài: P(A1) = 1/3, P(A2) = 1/4, P(A3)= 1/4, P(A4) = 1/6, ∑P(Ai) = 1 P(B/A1) = 0,15, P(B/A2) = 0,08, P(B/A3) = 0,05, P(B/A4) = 0,01 Vậy P(B) =1/3 * 0,15 + 1/4 * 0,08 + 1/4 * 0,05 + 1/6 * 0,01 = 0,081617
18. b) Cơng thức Bayes: Giải bài tốn ngược của bài tốn trên, tức là biết các P(Ai), P(B/Ai) và biến cố B đã xảy ra, tìm P(Ai/B) Ta cĩ : B = (B∩A1) ∪ (B∩A2) ∪ (B∩A3) ∪ (B∩A4) và P(Ai∩B) = P(Ai/B) * P(B) = P(B/Ai) * P(Ai)P(B/Ai )* P(Ai ) P(Ai/B)= P(B/Ai )* P(Ai )/P(B) k P(Ai/B)= P(B/Ai )* P(Ai ) /(∑ P(B/Ai ) * P(Ai )) i=1 18
19. Cơng thức này được gọi là cơng thức Bayes, hay cơng thức xác suất các giả thiết về các biến cố Ai cĩ thể xem như giả thiết theo đĩ biến cố B xuất hiện. Ta phải tính xác suất của các giả thiết với điều kiện biến cố B xuất hiện. Ví dụ: Xét lại thí dụ 2.2, cũng với giả thiết đĩ bây giờ ta yêu cầu xác suất để lấy một sản phẩm của phân xưởng thứ nhất biết nĩ là một phế phẩm. Ta phải tìm P(A1/B) P(A1/B) = [P(B/A1) * P(A)]/P(B) = [0,15 * 1/3]/0,0816 = 0,61 19
20. 1.2.6. Cơng thức Bernoulli : a)Cơng thức Bernoulli : Nếu tiến hành những phép thử độc lập, trong mỗi phép thử xác suất hiện của biến cố A như nhau và bằng p thì xác suất để biến cố A xuất hiện k lần trong n phép thửđĩ được biểu diễn bằng cơng thức Bernoulli k k n-k Pn(k) = Cn p q Với q = 1-p Ghi chú : a.Trong trường hợp biến cố A xuất hiện từ k1 đến k2 lần trong n phép thử thì ta ký hiệu xác xuất đĩ là Pn(k1,k2) Gọi Aki là biến cố A xuất hiện ki lần A = Aki ∪ Ak1+1 ∪ ∪ Ak2 k2 i i n-i 20 Pn(k1,k2)=P(A)= ∑Cn p q i=k1
21. b.Khi n và k khá lớn việc tính tốn Pn(k) và Pn(k1, k2) sẽ phức tạp. Để khắc phục điều đĩ người ta phải tìm cách tính gần đúng các xác suất đĩ bằng cách áp dụng các định lý giới hạn. Ví dụ: Trong thùng cĩ 30 bi: 20 trắng và 10 đen. Lấy liên tiếp 4 bi, trong đĩ mỗi bi lấy ra đều hồn lại thùng trước khi lấy bi tiếp theo và các bi đều được trộn lại. Hỏi xác suất để trong 4 bi lấy ra cĩ 2 bi trắng. Giải: Xác suất lấy được bi trắng p = 20/30 =2/3 cĩ thể xem như nhau trong 4 phép thử: q = 1 - p = 1/3 áp dụng cơng thức Bernoulli 21
22. Ví dụ: Xác suất xuất hiện biến cố A bằng 0,4. Hỏi xác suất để trong 10 phép thử biến cố A xuất hiện khơng quá 3 lần. Giải: p = 0.4, q = 0.6 Xác suất để biến cố A xuất hiện 0 lần : P10(0) = q10 Xác suất để biến cố A xuất hiện 1 lần : P10(1) = 10pq9 Xác suất để biến cố A xuất hiện 2 lần : P10(2) = 45p2q8 Xác suất để biến cố A xuất hiện 3 lần : P10(3) = 120p3q7 Xác suất để biến cố A xuất hiện khơng quá 3 lần P10(0,3) = P10(0) + P10(1) + P10(2) + P10(3) ≈ 0.38 22
23. Ghi chú: b) Số lần xuất hiện chắc chắn nhất: Trị số của Pn(k) nĩi chung phụ thuộc vào k. Ta tìm một số k0 sao cho Pn(k0) đạt giá trị lớn nhất. Số k0 gọi là số lần xuất hiện chắc chắn nhất của biến cố A trong n phép thử. Ta cĩ: 23 np-q ≤ k0 ≤ np + p p ≠ 0 và p ≠ 1
24. Ví dụ: Xác suất bắn trúng đích của một người bằng 0,7. Nếu người đĩ bắn 25 phát. Xác định sốlần cĩ khả năng trúng đích nhất. Giải : n = 25, p = 0,7, q = 0,3 np - q ≤ k0 ≤ np + p 25 * 0,7 – 0,3 ≤ k0 ≤ 25 * 0,7 + 0,7 17,2 ≤ k0 ≤ 18,2 Vì k là số nguyên, nên chọn k = 18 24
25. c) Các cơng thức gần đúng để tính Pn (k) và Pn (k1,k2) Các cơng thức được rút ra từ các định lý giới hạn. Cơng thức Moixre - Laplace : Pn(k) ≈ϕ(xk)/ npq • Cơng thức Moixre - Laplace được sử dụng khi n khá lớn • p là xác suất của biến cố A trong phép thử Bernoulli, p khơng quá gần 0 và 1 xk = (k-np) / npq ϕ(x) = 1 / 2π * e-x²/2 : hàm số Gauss 25
26. Ví dụ: Xác suất để sản xuất ra một chi tiết loại tốt là 0.4.Tìm xác suất để trong 26 chi tiết sản xuất ra thì cĩ 13 chi tiết loại tốt. Vấn đề là tìm P26(13) n = 26 p = 0.4 q = 0.6 xk = (k - np) / npq = 1,04 ϕ(xk) = ϕ(1,04) = 0,2323 P26(13) = ϕ(xk)/ npq = 0,2323/2,5 = 0,093 Pn (k1, k2) ≈∅ (β) -∅ (α) α = (k1 - np)/ npq β = (k2 - np)/ npq x -x²/2 26 ∅(x) = 1/ 2π∫0 e dx : hàm Laplace chuẩn
27. Ví dụ: Một phân xưởng sản xuất bĩng đèn đạt trung bình là 70% sản phẩm loại tốt. Tìm xác suất để trong 1000 bĩng đèn cĩ từ 652 đèn 760 bĩng đèn loại tốt. Xác suất phải tìm là P1000 (652, 760) n = 1000, p = 0,7 q = 0,3 k1 = 652 k2 = 700 α = (k1 - np)/ npq = - 3,31 =>∅ (α) = ∅(-3,31) = - 0,499520 β = (k2 - np)/ npq = 4,14 =>∅ (β) = ∅(4,14) = 0,499968 P1000 (652, 760) = ∅ (β) -∅ (α) = 0,999488 27
28. Cơng thức Poisson • Nếu n →∞ và p → 0 sao cho np = λ (const) thì Pn (k) ≈ (e-λλk) / k! Định lý Poisson cũng cĩ thể dùng để tính gần đúng Pn (k1,k2) 28
29. Ví dụ: Tổng sản phẩm của xí nghiệp A trong 1 quí là 800. Xác xuất để sản xuất ra một phế phẩm là 0.005. Tìm xác suất để cho : Cĩ 3 sản phẩm là phế phẩm Cĩ khơng quá 10 sản phẩm bị hỏng Giải: n =800, p = 0,005 => λ = np = 4 -4 1. P800(3) = e 4³/3! = 0,1954 2. P800(0,10) = 29
30. MA TRẬN Mơ tả: Các dịng ngang của ma trận gọi là hàng và các cột thẳng đứng là cột. Hình dạng ma trận được đặc trưng bởi số hàng và số cột (kích thước ma trận). k phần tử. Ma trận thường được viết thành bảng kẹp giữa 2 dấu ngoặc vuơng "[" và "]" (hoặc, hiếm hơn, dấu ngoặc "(" và ")"). Thí dụ: Ma trận thường được dùng để mơ ta khơng gian trạng thái trong điều khiển tự động. 30
31. CÁC LOẠI MA TRẬN ĐẶC BIỆT Ma trận tam giác là ma trận vuơng được chia thành hai loại là ma trận tam giác trên và ma trận tam giác dưới.  Ma trận tam giác trên khi các phần tử nằm phía dưới hạng tử cĩ giá trị = 0, aij=0 với mọi i>j.  Ma trận tam giác dưới khi các phần tử nằm phía trên hạng tử cĩ giá trị bằng khơng, aij=0 với mọi i<j. Ma trận chéo là ma trận vuơng trong đĩ tất cả các phần tử khơng nằm trên đường chéo chính thì đều bằng 0, nghĩa là =0 với mọi i ≠ j. 31
32. MA TRẬN ĐƠN VỊ Ma trận đơn vị trên một vành nào đĩ, là ma trận vuơng, cĩ các phần tử nằm trên một đường chéo mang giá trị là đơn vị nhân của vành đĩ (nếu là vành số thơng thường thì là số 1), tất cả các phần tử cịn lại mang giá trị trung hịa (nếu là vành số thơng thường thì là số 0). 32
33. MA TRẬN ĐỐI XỨNG A=[aij]mxn A được gọi là đối xứng khi và chỉ khi aij=aji với mọi i,j Tức là: Ma trận phản đối xứng 33
34. Ma trận ba đường chéo: Là ma trận mà các phần tử nằm ngồi ba đường chéo đều bằng 0. Ma trận sơ cấp:  Một ma trận sơ cấp hàng nhận được khi ta thực hiện một phép biến đổi sơ cấp đối với hàng (cột) của một ma trận đơn vị I. Kí hiệu là: E Ma trận sơ cấp E1 nhận được khi ta nhân một số α khác 0 vào một hàng của ma trận đơn vị I. 34
35. Ma trận sơ cấp E2 nhận được khi ta nhân cộng vào hàng j với hàng i đã được nhân với một số β khác 0 đối với ma trận đơn vị I. Ma trận sơ cấp E3 nhận được khi ta đổi vị trí hàng j với hàng i của ma trận đơn vị cho nhau. 35
36. CÁC PHÉP TỐN ĐẠI SỐ TRÊN MA TRẬN Phép cộng ma trận Cĩ thể cộng hai hoặc nhiều ma trận cĩ cùng kích thước x . Cho các ma trận cấp x và , tổng là ma trận cùng cấp x nhận được do cộng các phần tử tương ứng (nghĩa là : 36
37. PHÉP NHÂN MA TRẬN Phép nhân ma trận với một số  Cho ma trận và số, tích được tính bằng cách nhân tất cả các phần tử của với số (nghĩa là ). Chẳng hạn: Phép nhân ma trận  Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dịng của ma trận bên phải. Nếu ma trận cĩ kích thước x và ma trận cĩ kích thước x , thì ma trận tích cĩ kích thước x cĩ phần tử đứng ở hàng thứ i, cột thứ j xác định bởi: 37 với mọi cặp =1 m; j =1 p.
38. Chẳng hạn: Phép nhân ma trận cĩ các tính chất sau:  (AB)C=A(BC) với mọi ma trận cấp Akxm , ma trận Bmxn và ma trận Cnxp ("kết hợp“)  (A+B)C= AC+BC với mọi ma trận cấp Amxn và các ma trận B và ma trận C cấp nxk ("phân phối bên phải").  C(A+B)=CA+CB ("phân phối bên trái").  Cần chú ý rằng phép nhân ma trận khơng giao hốn. 38