算法合集之信息論在信息學競賽中的簡單應用(已修改)
2024-10-28 03:11 本頁面
【正文】 在信息學競賽中的簡單應用 侯啟 明 信息論簡介 ?信息論是關于信息的本質(zhì)和傳輸規(guī)律的科學的理論。 ?通過它可以很方便地得到某些交互式問題的一個較好的步數(shù)下界 (“ 信息論下界” ) 讓我們先來看一些信息論的基本理論 理論基礎 ?定義：如果一個隨機變量 x共有 n種取值，概率分別為 p0,p2,......,pn，則其熵為H(x)=f(p0,p2,......,pn)=∑Cpilogpi ?定理 1：在得到關于隨機變量 x的一個熵為 h的信息后， x的熵將會減少 h。 ?定理 2：當一個隨機變量的各種取值概率相等時，它的熵最大。 這些理論看上去和某些題目關系密切，不是嗎？ 那么，具體應該如何運用呢？讓我們來看一些例子： 我們宿舍二樓到三樓之間樓梯的窗戶外面是相鄰的一個平房的房頂。在那一帶棲息著三只渾身雪白，有著一只藍眼睛和一只綠眼睛的 —— 例 1：驗證一下定理 1 貓 ！ A B C 例 1：驗證一下定理 1 在天冷的時候，它們喜歡趴在樓內(nèi)的暖氣上。于是，每只貓就有了兩種狀態(tài)：在屋內(nèi)和在屋外。因此，三只貓的狀態(tài)共有 8種可能情況，假設它們是等概率的。 現(xiàn)在，我在一樓的小賣部。由于種種原因，我希望知道貓當時的狀況，因此，我往上看了一眼，結果發(fā)現(xiàn)在這個位置只能知道屋內(nèi)貓的只數(shù) …… 例 1：驗證一下定理 1 問題 1： 把所有貓的情況作為一個隨機變量 x，則當我在小賣部的時候， x的熵是多少？ 解答 1： 由于 8種情況的概率相等，所以： H(x)=f(1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=log8 問題 2： 我看一眼所得到的信息 y的熵是多少？ 解答 2： 由于貓的只數(shù)共有 0,1,2,3四種情況，概率分別為 (1/8,3/8,3/8,1/8)，所以： H(y)=f(1/8,3/8,3/8,1/8)=log86log3/8 例 1：驗證一下定理 1 問題 3： 我看完之后， x的熵 H39。(x)是多少？ 解答 3： 此時貓的只數(shù)為 0,1,2,3的四種情況的概率依次是 (1/8,3/8,3/8,1/8)，而每種情況的熵分別為(0,log3,log3,0)，所以此時 H39。(x)的數(shù)學期望為： H39。(x)=1/8*0+3/8*log3+3/8*log3+1/8*0=6log3/8 可以發(fā)現(xiàn) H(x)=H(y)+H
教學課件相關推薦
鄂ICP備17016276號-1