TAILIEUCHUNG - Giáo trình: Lý thuyết thông tin.H(X) = H(p1 , p 2 ,..., p M ) = −∑ pi log 2 ( pi )i

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

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.