信息技術(shù)導(dǎo)論

1、即，一條信息發(fā)生的概率越小，信息量越大；概率越大（一種極端情況是“必然的事情”信息量為0）則信息量越小于是，對于一條信息x，人們用下列公式表示其信息量I (書上用了先驗(yàn)概率和后驗(yàn)概率這兩個術(shù)語)(log)(1logxpxpIaa（式（式1-4-1） 之所以取對數(shù)是由于信息量的之所以取對數(shù)是由于信息量的“累加性累加性”決定的決定的兩個消息加在一起的總信息量等于每個信息各自信息量之和，即：. Log(m1m2)Logm1Logm2 一.信息度量的方法(重點(diǎn)) 度量信息量的方法度量信息量的方法 設(shè)：P(x) 消息發(fā)生的概率， I 消息中所含的信息量， 則 P(x) 和 I 之間應(yīng)該有如下關(guān)系： I

2、是 P(x) 的函數(shù)： I I P(x) P(x) ，I ； P(x) ，I ； P(x) = 1時，I 0； P(x) = 0時，I ； 滿足上述3條件的關(guān)系式如下：信息量的定義)()()()(2121xPIxPIxPxPI)(log)(1logxPxPIaa一.信息度量的方法(重點(diǎn)) 上式的單位由對數(shù)底的取值決定。 若對數(shù)以2為底時單位是“比特”（bit binary unit的縮寫）；（現(xiàn)階段我們主要采用這個單位） 若以e e為底為底時單位是“奈特奈特”（natnature unit的縮寫）； 若以1010為底為底時單位是“哈特哈特”（Hart Hartley的縮寫）。 通常采用“比特比

3、特”作為信息量的實(shí)用單位，這時有一.信息度量的方法(重點(diǎn))(log)(1logxPxPIaa221loglog( )( )IP xP x 【例例】 設(shè)一個二進(jìn)制離散信源，以相等的概率發(fā)送數(shù)字“0”或“1”，則信源每個輸出的信息含量為 在工程應(yīng)用中，習(xí)慣把一個二進(jìn)制碼元稱作1比特 )b(12log2/11log) 1 ()0(22 II一.信息度量的方法(重點(diǎn))若有M個等概率波形（P = 1/M），且每一個波形的出現(xiàn)是獨(dú)立的，則傳送M進(jìn)制波形之一的信息量為若M是2的整冪次，即 M = 2k，則有當(dāng)M = 4時，即4進(jìn)制波形，I = 2比特，當(dāng)M = 8時，即8進(jìn)制波形，I = 3比特。)b(lo

4、g/11log1log222MMPI2log 2( )kIkb一.信息度量的方法(重點(diǎn))對于非等概率情況：設(shè)：一個離散信源是由M個符號組成的集合，其中每個符號xi (i = 1, 2, 3, , M)按一定的概率P(xi)獨(dú)立出現(xiàn)，即 且有則x1 , x2, x3, xM 所包含的信息量分別為于是，每個符號所含平均信息量為由于H(x)同熱力學(xué)中的熵形式相似，故稱它為信息源的熵熵 1212,MMxxxP xP xP x1()1MiiP x21222log()log()log()MP xP xP x， ，121222221( )( ) log( )() log()() log()( ) g( )(

5、/(1.4 6)MMMiiiH xP xP xP xP xP xP xP x loP x比特 符號）一.信息度量的方法(重點(diǎn))二、分辨率課堂練習(xí)例：在1200 800分辨率的顯示器上分別顯示800 600分辨率，600 400的圖像，會占屏幕的多大面積。解 (800 600) /（1200 800） = 1/2 (600 400) /（1200 800） = 1/4 存儲介質(zhì)的分類(現(xiàn)狀)磁存儲介質(zhì)磁存儲介質(zhì)光存儲介質(zhì)光存儲介質(zhì)半導(dǎo)體存儲介質(zhì)半導(dǎo)體存儲介質(zhì)存儲介質(zhì)一般分為光存儲（CD，DVD等）、磁存儲（硬盤，磁帶等）和半導(dǎo)體（電）存儲（內(nèi)存條、U盤等）。閃存（Flash ROM），是一種采用

6、集成電路的可多次擦寫的存儲器，廣泛用于廣泛用于U盤、數(shù)碼設(shè)備的存儲卡等領(lǐng)域盤、數(shù)碼設(shè)備的存儲卡等領(lǐng)域。有體積小便于攜帶，不怕震動，不磨損，保存時間長等優(yōu)點(diǎn)。和其他存儲設(shè)備相比主要缺點(diǎn)是速度慢，容量小。隨著科技的進(jìn)步，這些缺點(diǎn)也在逐漸被克服，高端的閃存容量已經(jīng)達(dá)到4GB以上，擦寫速度也達(dá)到每秒鐘幾十兆。010.39010.35010.611000.261010.11a1a2a3a4a5a6a70.200.190.180.170.150.100.01101100000101001100111信源符號信源符號 概率概率HuffmanHuffman碼碼編碼過程編碼過程Huffman編碼過程數(shù)據(jù)結(jié)構(gòu)的圖

7、示一般用示意圖表示數(shù)據(jù)結(jié)構(gòu)。用小圓圈代表數(shù)據(jù)元素，用小圓圈之間的連線代表小圓圈對應(yīng)的數(shù)據(jù)元素具有的關(guān)系，如果強(qiáng)調(diào)關(guān)系的方向性，可用帶箭頭的線段表示關(guān)系。具體地講，若d1和d2表示兩個數(shù)據(jù)元素，它們具有關(guān)系d1,d2，則表示為如圖6-3所示的結(jié)構(gòu)。圖中表示的只是一個抽象關(guān)系，不代表具體意義。對于具體的應(yīng)用，也可以表示家族關(guān)系中的父子關(guān)系。例如，d1,d2可代表d1是d2的父親。三、常見的幾種數(shù)據(jù)結(jié)構(gòu)l至此，我們已經(jīng)知道數(shù)據(jù)結(jié)構(gòu)是想要解決非數(shù)值計(jì)算問題的求解，我們也知道了數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含兩層含義，即數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。但是，非數(shù)值計(jì)算的問題可能是五花八門 l計(jì)算機(jī)科學(xué)家對這類問題研究后發(fā)現(xiàn)：

8、非數(shù)值計(jì)算問題，雖然在確定數(shù)據(jù)元素時，每一個具體問題都各不相同，但數(shù)據(jù)的邏輯結(jié)構(gòu)可以歸結(jié)為以下四種基本類型： l集合：數(shù)據(jù)元素間除了“同屬于一個集合”外，別無其它關(guān)系。 l線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一個對一個的關(guān)系。 l樹形結(jié)構(gòu)：數(shù)據(jù)元素間存在一個對多個的關(guān)系。 l圖或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)元素間存在多個對多個的關(guān)系。2、樹結(jié)構(gòu)二叉樹的遍歷所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。 由于二叉樹的基本組成部分是：根（N），左子樹（L），右子樹（R），因此可以有NLR、LNR、LRN、RNL、NRL、RLN六種遍歷次序。通常使用前三種，即：限定先

9、左后右這三種次序的遞歸定義如下：先序遍歷（NLR）：先訪問根，先序遍歷左子樹，先序遍歷右子樹。后序遍歷（LRN）：后序遍歷左子樹，后序遍歷右子樹，訪問根。中序遍歷（LNR）：中序遍歷左子樹，訪問根，中序遍歷右子樹。 對于以下動畫所示的二叉樹，它的結(jié)點(diǎn)先序序列是：ABDEGCF；后序序列是：DGEBFCA；中序序列是：DBGEACF。 有向圖有向圖與無向圖無向圖:任意圖中的邊有方向性就稱為有向圖,反之則是無向圖.本節(jié)主要討論有向圖的操作出度出度與入度入度:就有向圖而言任一頂點(diǎn)發(fā)射的邊的數(shù)量稱為該頂點(diǎn)的出度,而所接收的邊的數(shù)量稱為該頂點(diǎn)的入度.源點(diǎn)源點(diǎn)與匯點(diǎn)匯點(diǎn):入度為0的點(diǎn)稱為源點(diǎn),出度為0的點(diǎn)

10、稱為匯點(diǎn).(通常這兩種特殊頂點(diǎn)分別代表工程的始、終)2、圖的定義、術(shù)語 二、圖的存儲有向圖的有向圖的鄰接矩陣鄰接矩陣表示法：表示法： A B C D E A B C D EABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0有向圖的鄰接表有向圖的鄰接表1 4230 120 1 2 3 4 A B C D EABECDABECD有向圖的逆鄰接表有向圖的逆鄰接表A B C D E 303420 01234在有向圖的逆鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧1 abchdekfg812345670F F F F F F F F F0 1 2 3 4

11、 5 6 7 8TTTTTT TTTachdkfe bgachkfedbg訪問標(biāo)志訪問標(biāo)志: :訪問次序訪問次序: :DFSDFS：achdkfe廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。 其中，V-w1, V-w2, V-w8 的路徑長度為1;V-w7, V-w3, V-w5 的路徑長度為2;V-w6, V-w4 的路徑長度為3。w1Vw2w7w6w3w8w5w4 從圖中的某個頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。 若此時圖中尚有頂點(diǎn)未被訪問,則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。遍歷思想第八章 重要知識點(diǎn)8.1.1 信息系統(tǒng)的定義8.1.2 信息系統(tǒng)的結(jié)構(gòu)8.2