信息技术导论

1、即，一条信息发生的概率越小，信息量越大；概率越大（一种极端情况是“必然的事情”信息量为0）则信息量越小于是，对于一条信息x，人们用下列公式表示其信息量I (书上用了先验概率和后验概率这两个术语)(log)(1logxpxpIaa（式（式1-4-1） 之所以取对数是由于信息量的之所以取对数是由于信息量的“累加性累加性”决定的决定的两个消息加在一起的总信息量等于每个信息各自信息量之和，即：. Log(m1m2)Logm1Logm2 一.信息度量的方法(重点) 度量信息量的方法度量信息量的方法 设：P(x) 消息发生的概率， I 消息中所含的信息量， 则 P(x) 和 I 之间应该有如下关系： I

2、是 P(x) 的函数： I I P(x) P(x) ，I ； P(x) ，I ； P(x) = 1时，I 0； P(x) = 0时，I ； 满足上述3条件的关系式如下：信息量的定义)()()()(2121xPIxPIxPxPI)(log)(1logxPxPIaa一.信息度量的方法(重点) 上式的单位由对数底的取值决定。 若对数以2为底时单位是“比特”（bit binary unit的缩写）；（现阶段我们主要采用这个单位） 若以e e为底为底时单位是“奈特奈特”（natnature unit的缩写）； 若以1010为底为底时单位是“哈特哈特”（Hart Hartley的缩写）。 通常采用“比特比

3、特”作为信息量的实用单位，这时有一.信息度量的方法(重点)(log)(1logxPxPIaa221loglog( )( )IP xP x 【例例】 设一个二进制离散信源，以相等的概率发送数字“0”或“1”，则信源每个输出的信息含量为 在工程应用中，习惯把一个二进制码元称作1比特 )b(12log2/11log) 1 ()0(22 II一.信息度量的方法(重点)若有M个等概率波形（P = 1/M），且每一个波形的出现是独立的，则传送M进制波形之一的信息量为若M是2的整幂次，即 M = 2k，则有当M = 4时，即4进制波形，I = 2比特，当M = 8时，即8进制波形，I = 3比特。)b(lo

4、g/11log1log222MMPI2log 2( )kIkb一.信息度量的方法(重点)对于非等概率情况：设：一个离散信源是由M个符号组成的集合，其中每个符号xi (i = 1, 2, 3, , M)按一定的概率P(xi)独立出现，即 且有则x1 , x2, x3, xM 所包含的信息量分别为于是，每个符号所含平均信息量为由于H(x)同热力学中的熵形式相似，故称它为信息源的熵熵 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比特 符号）一.信息度量的方法(重点)二、分辨率课堂练习例：在1200 800分辨率的显示器上分别显示800 600分辨率，600 400的图像，会占屏幕的多大面积。解 (800 600) /（1200 800） = 1/2 (600 400) /（1200 800） = 1/4 存储介质的分类(现状)磁存储介质磁存储介质光存储介质光存储介质半导体存储介质半导体存储介质存储介质一般分为光存储（CD，DVD等）、磁存储（硬盘，磁带等）和半导体（电）存储（内存条、U盘等）。闪存（Flash ROM），是一种采用

6、集成电路的可多次擦写的存储器，广泛用于广泛用于U盘、数码设备的存储卡等领域盘、数码设备的存储卡等领域。有体积小便于携带，不怕震动，不磨损，保存时间长等优点。和其他存储设备相比主要缺点是速度慢，容量小。随着科技的进步，这些缺点也在逐渐被克服，高端的闪存容量已经达到4GB以上，擦写速度也达到每秒钟几十兆。010.39010.35010.611000.261010.11a1a2a3a4a5a6a70.200.190.180.170.150.100.01101100000101001100111信源符号信源符号 概率概率HuffmanHuffman码码编码过程编码过程Huffman编码过程数据结构的图

7、示一般用示意图表示数据结构。用小圆圈代表数据元素，用小圆圈之间的连线代表小圆圈对应的数据元素具有的关系，如果强调关系的方向性，可用带箭头的线段表示关系。具体地讲，若d1和d2表示两个数据元素，它们具有关系d1,d2，则表示为如图6-3所示的结构。图中表示的只是一个抽象关系，不代表具体意义。对于具体的应用，也可以表示家族关系中的父子关系。例如，d1,d2可代表d1是d2的父亲。三、常见的几种数据结构l至此，我们已经知道数据结构是想要解决非数值计算问题的求解，我们也知道了数据结构应该包含两层含义，即数据的逻辑结构和物理结构。但是，非数值计算的问题可能是五花八门 l计算机科学家对这类问题研究后发现：

8、非数值计算问题，虽然在确定数据元素时，每一个具体问题都各不相同，但数据的逻辑结构可以归结为以下四种基本类型： l集合：数据元素间除了“同属于一个集合”外，别无其它关系。 l线性结构：数据元素间存在一个对一个的关系。 l树形结构：数据元素间存在一个对多个的关系。 l图或网状结构：数据元素间存在多个对多个的关系。2、树结构二叉树的遍历所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。 由于二叉树的基本组成部分是：根（N），左子树（L），右子树（R），因此可以有NLR、LNR、LRN、RNL、NRL、RLN六种遍历次序。通常使用前三种，即：限定先

9、左后右这三种次序的递归定义如下：先序遍历（NLR）：先访问根，先序遍历左子树，先序遍历右子树。后序遍历（LRN）：后序遍历左子树，后序遍历右子树，访问根。中序遍历（LNR）：中序遍历左子树，访问根，中序遍历右子树。 对于以下动画所示的二叉树，它的结点先序序列是：ABDEGCF；后序序列是：DGEBFCA；中序序列是：DBGEACF。 有向图有向图与无向图无向图:任意图中的边有方向性就称为有向图,反之则是无向图.本节主要讨论有向图的操作出度出度与入度入度:就有向图而言任一顶点发射的边的数量称为该顶点的出度,而所接收的边的数量称为该顶点的入度.源点源点与汇点汇点:入度为0的点称为源点,出度为0的点

10、称为汇点.(通常这两种特殊顶点分别代表工程的始、终)2、图的定义、术语 二、图的存储有向图的有向图的邻接矩阵邻接矩阵表示法：表示法： 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在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧1 abchdekfg812345670F F F F F F F F F0 1 2 3 4

11、 5 6 7 8TTTTTT TTTachdkfe bgachkfedbg访问标志访问标志: :访问次序访问次序: :DFSDFS：achdkfe广度优先搜索遍历图广度优先搜索遍历图Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余各顶点必定存在路径。 其中，V-w1, V-w2, V-w8 的路径长度为1;V-w7, V-w3, V-w5 的路径长度为2;V-w6, V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点按这些顶点被访问的先后次序依次访问它们的邻接点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。遍历思想第八章 重要知识点8.1.1 信息系统的定义8.1.2 信息系统的结构8.2