chp2信息论与数学基础.pptVIP

第2章 信息论与数学基础 信息论 Shannon 与20世纪40年代提出 信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到 1948 年，香农提出了“信息熵” 的概念，才解决了对信息的量化问题。 信息量与不确定性 一条信息的信息量大小和它的不确定性有直接的关系。 比如说，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。从这个角度可认为，信息量的度量就等于不确定性的多少。 例子：冠军队预测 熵（Entropy）的定义： 设随机变量X，取值空间Ω，Ω为有限集合。X的分布密度为p(x)，p(x)=P(X=x) x∈X，则该随机变量的取值不确定程度，即其熵为： 当使用log2时，熵的单位为比特 反映一个信源发出不同信号，具有的平均信息量。 熵率（语言信息率） ：： r=H(M)/N 语言绝对信息率：R=log2L 语言多余度：D=R-r 密码体制的安全性 唯一解距离 唯一解距离是指，当进行强力攻击时，可能接触唯一有意义的明文所需要的最少密文量。一般而言，唯一解距越长，密码体制越好。 混乱和散布 混乱用于掩盖明文和密文之间的关系，如凯撒移位密码。 散布是通过将明文多余度分散到密文中使之分散开来的方法，如置换密码。 复杂性理论 1、算法的复杂性 一个密码体制的强度是通过破译它所需的计算能力来确定的，所需的计算能力越大，表明密码体制的安全强度越大。 一个算法的计算复杂性由两个角度来度量：T（时间复杂性）、S（空间复杂性）。通常，一个算法的计算复杂性的数量级用“O”表示 表2.1 当n= 106不同算法族运行时间 与n的关系 复杂度 所需运算 所需时间（106运算/s） 常数 线性 二次方 三次方 指数 O(1) O(n) O(n2) O(n3) O(2n) 1 106 1012 10181us 1s 11.6d 32000年 宇宙年龄 2、问题的复杂性 复杂性理论也将各种问题，按照解决问题时所 需最少的时间及最小的空间将之归纳为不同类别的 复杂度。 能够用多项式时间算法解决（输入与n成多项 式关系）的问题称之为易处理的。 不能在多项式时间内解决的问题称之为难处理 的，难处理的问题有时也称之为难解问题。 复杂度与输入值成指数关系的问题属于难解问题。 依照求解问题所需的时间，复杂性理论也将各种 问题区分成下面各类： （1） P问题：代表那些能够在多项式时间内可解的问题 易处理的，在确定性图灵机上多项式时间内可计算 （2）NP问题：多项式时间内可验证的问题 在不确定性Turing machine上多项式时间内可计算, 不确定性Turing machine能进行猜测, 即不确定性Turing machine如能猜出一个解的话, 则确定性Turing machine在多项式时间内可校验解的正确性. （3）NP－完全问题：是NP问题中的一些特殊问题，NP中的所有问题都可以转换成NP完全问题。换句话说，只要NP完全问题解决了，其他问题都可以解决。NP完全问题是NP问题中最困难的问题。 3、NP－完全问题 （一）旅行商问题：一名旅行商必须旅行到n个不同的城市，而他只有一箱汽油（即有一个他能旅行的最远距离）。有方法使他仅用一箱汽油而旅行到每个城市恰好一次吗？（这是一般的汉密尔顿问题） （二）三方匹配问题：有一屋子的人，包括n个男人，n个女人和n个牧师（祖父，犹太教士等等）。正常的婚礼将包括一个男人、一个女人和一个愿主持仪式的牧师。有了这样一张可能的三人一组的表，是否可能安排n个婚礼，使每一个人要么和一个人结婚，要么主持一个婚礼？ （三）整数分解问题 （四）背包问题 （五）离散对数问题 数论 数论是研究数性质的一个数学分支，他同时也是密码学的基础学科之一。 全体整数所组成的集合通常用Z表示，即： Z={…, -3, -2, -1, 0, 1, 2, 3,…} 欧几里德（Euclid）算法 欧几里德（Euclid）算法 首先我们介绍整数的带余除法，它是整个数论的基础性定理之一。 对于两个整数a和b，可以对其进行分解来计算它们的最大公因数，但对于大整数而言，目前还没有足够有效的办法进行。实际中常用的用来计算两个数的最大公因数的算法称为欧几里德算法。它的理论依据正是前面所述的带余