Giáo trình: Lý thuyết thông tin. H(X) = H(p1 , p 2 ,., p M ) = −∑ pi log 2 ( pi ) i =1 M Qui ước trong cách viết: log(pi)= log2(pi) Ví dụ minh họa Nếu sự kiện A có xác suất xuất hiện là 1/2 thì h(A)=h(1/2)= -log(1/2) = 1 (bit) Xét BNN X có phân phối sau: X P x1 x2 1/2 1/4 x3 1/4 H(X) = H(1/2, 1/4, 1/4) = -(1/2log(1/2)+1/4log(1/4)+1/4log(1/4)) =3/2 (bit) Bài toán về cây tìm kiếm nhị phân-Đặt vấn đề Giả sử, tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau: X x1. | Giáo trình Lý thuyết thông tin. M H X H P1 P2 . Pm -E Pi log2 pt i 1 Qui ước trong cách viết log pi log2 pi Ví dụ minh họa Nếu sự kiện A có xác suất xuất hiện là 1 2 thì h A h 1 2 -log 1 2 1 bit Xét BNN X có phân phối sau X X1 x2 X3 P 1 2 1 4 1 4 H X H 1 2 1 4 1 4 - 1 2log 1 2 1 4log 1 4 1 4log 1 4 3 2 bit Bài toán về cây tìm kiếm nhị phân-Đặt vấn đề Giả sử tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau X x1 x2 x3 x4 x5 P 0 2 0 3 0 2 0 15 0 15 Trong đó x1 . x5 lần lượt là tên của 5 người mà ta cần nhận ra với cách xác định tên bằng câu hỏi đúng sai yes no . Sơ đồ dưới đây minh họa cách xác định tên của một người X x1 X x1 x2 Yes No Yes No x1 x2 _ . Yes ---- No x3 X 4 r_ Yes -- - No x4 x5 Bài toán về cây tìm kiếm nhị phân - Diễn giải Theo sơ đồ trên Để tìm x1 x2 x3 với xác suất tương ứng là ta chỉ cần tốn 2 câu hỏi. Để tìm x4 x5 với xác suất tương ứng thì ta cần 3 câu hỏi. Vậy Số câu hỏi trung bình là 2 x 0 2 0 3 0 2 3 x 0 15 0 15 Mặt khác Entropy của X H X H . Ta luôn có số câu hỏi trung bình luôn H X theo định lý Shannon sẽ trình bày sau . Vì số câu hỏi trung bình trong trường hợp này xấp sỉ H X nên đây là số câu hỏi trung bình tối ưu để tìm ra tên chính xác của một người. Do đó sơ đồ tìm kiếm trên là sơ đồ tối ưu. Biên soạn TS. L ê Quy ết Thắng ThS. Phan Tấn Tài Ks. Dương Văn Hiếu. 17 Giáo trình Lý thuyết thông tin. Sinh viên tự cho thêm 1 hay 2 sơ đồ tìm kiếm khác và tự diễn giải tương tự - xem như bài tập. Bài tập Tính H X với phân phối sau X X1 X2 X3 P 1 3 1 3 1 3 Tính H Y với phân phối sau Y X1 X2 X3 X4 P 1 6 2 6 1 6 2 6 Biên soạn TS. L ê Quy ết Thắng ThS. Phan Tấn Tài Ks. Dương Văn Hiếu. 18 Giáo trình Lý thuyết thông tin. BÀI CÁC TÍNH CHẤT CỦA ENTROPY Mục tiêu Sau khi hoàn tất bài học này bạn có thể - Hiểu các tính chất cơ bản của Entropy - Hiểu định lý cực đại của Entropy - Vận dụng giải một số bài toán về Entropy - Làm cơ sở để vận dụng giải quyết các bài toán tính dung lượng
