硕士算法2010第2章数学基础.ppt

w集合论 w逻辑学 w概率论 w求和与递归 w快速估算方法 第2章 算法的数学基础 1 w集合是由互不相同的元素组 成的一个整体。通常这些元素都 是属于同一种类型的，具有某些 共同的性质。 w一个元素e是集合S的成员， 用符号 表示，读作e在S中或 e属于S。 集合 2 集合论 w集合是现实世界高度的抽象。例 如，它可以很好地解释类与对象的 关系。 w集合中元素是无序的，但在计算 机存放时往往是有序的，如数组/序 列。Java支持集合操作，但其元素 必须是对象，而不是基本数据类型 。 3 集合的表达方式 w一个 特定的集合可以用列举或描述的 方法来给出。列举就是将集合里的元素排 列在花括号中。比如：S1 = a, b, c。 集合中的元素是没有先后顺序的。 w对于那些有很多个 或无限多个 元素 的集合，可以采取把集合中的元素所满足 的条件写出来，例如： S2 = x | x is an integer power of 2 读作“所有元素x都是整数的平方的集合”。 w一个 特殊的集合叫做空集，用表示, S3 = = 。空集中没有任何元素。 4 集合的运算 w如果集合S1的所有元素都在集合S2中， 那么S1叫做S2的子集，用S1 S2,表示。而S2 叫做S1的超集，用S2 S1表示。一个集合也 是自身的子集和超集。我们规定，空集是任 何集合S的子集： S 。 w设S、T是任意两个集合，定义S和T的交 集为： S T = x | x S and x T wS和T的并集定义为： S T = x | x S or x T 5 势 w如果存在有限多个 整数的集合N = n1, n2, nk ，N的元素和S中的元素有着 一一对应关系，那么称集合S是有限集。S 的基数或势（cardinality）等于k，表示为 |S| = k 。 w任意一个有n个元素的有限集的全部 子集（包括空集）的数目为2n ，其中基数 为k 的子集的个数为 6 序列 w一组具有确定顺序的元素叫做一个序列。除 了元素之间具有确定的顺序之外，序列与集合的 不同之处还在于序列中的元素是可以重复的。 w与集合的描述方式类似，我们也可以用列举 或给出通项公式的方法表示一个序列，列举的方 法是将序列中的元素用一对圆括号括起来。例如 ：S1=(a,b,c), S2=(b,c,a), S3=(a,a,b,c)。 7 序列 w如果一个序列与前n个正整数的序列 ( 1, 2, 3, , n ) 中的元素有一一对应关 系，则称此序列是有限的。 w如果有限序列中的元素互不相同， 那么称这个序列是一个有限集合的置换 或排列（permutation）。 w一个有n个元素的集合有n! 个互不相 同的排列。 8 数组 w一个有限序列有时也称作数组，一个k元数组 就是具有k个元素的序列。例如二元组或叫有序数 对(x, y)，三元组（x, y, z），等。 w一个k元数组也表示由 k 个集合的叉乘得到 的乘积空间中的点。这里两个集合S和T的叉乘定 义为 S T = (x, y) | x S, y T w乘积空间ST的基数（势）：| S T | = |S| |T| w一种常见的乘积空间是由相同的集合的叉乘 得到的，例如RR，或写为 R2，表示二维欧氏空 间（实平面）。 9 N元关系 w一个n元关系定义为n维乘积空间中的一个子 集。这个子集可以是有限的或者无限的，也可能 是空集或者是整个乘积空间。 wn元关系中最重要的例子是二元关系：R ST。例如定义在自然数集上的“小于”关系，可以 表示为：R = (x, y) | x N, y N, x y w当R SS，即R中的每个关系的两个元素都 来自于同一个集合S时，这些二元关系可能具有以 下一些重要的性质： n反身性：对所有x S, 有 (x, x) R. n对称性：若(x, y) R，则有(y, x) R. n反对称性（不满足对称性）：若(x, y) R，则有 (y, x) R. n传递性：若 (x, y) R 且 (y, z) R，则必有(x, z) R. 10 等价关系 w如果一个二元关系同时满足反身性、 对称性和传递性，那么这个关系叫做等价 关系，记做“”。等价关系是一类十分重要 的关系，因为通过它可以将下层集合S划分 为若干个互不相交的子集，每一个子集叫 做一个等价类。例如 x = y S | xy 表示 S 中所有与x 等价的元素的集合。 w根据等价关系的传递性，等价类中的 所有元素都相互“等价”。 11 Logic w逻辑学是用形式语言来规范自然语言叙述的 系统方法，是使我们可以更精确地进行推理和推 导的工具。 w在逻辑学中最简单的命题叫做原子公式。更 复杂的命题可以通过原子公式和逻辑连接符来表 示，称为逻辑表达式。 w常用的逻辑连接符包括：（与）、（或） 、（非），这三个符号也叫做布尔运算符。 w还有一个常用的符号是“”，AB表示从事 件A可以推出事件B，即如果A为真，就一定有B为 真。 12 Logic w运算符 并非一个新的布尔运算 符，因为“AB”等价于“AB”，这个 逻辑恒等式可以通过真值表加以验证 。 w另外两个非常有用的恒等式叫做德 摩根（DeMorgan）定律： (AB) A B (AB) A B 13 量词: all, some w限制词all 和some也是两种重要的逻辑连接符。all 叫做整体性限定符，记做 x 。读作“对所有x”，some叫 做存在性限定符，记做 x 。读作“存在x”。这些连接符可 以应用到含有x的叙述中。例如： w P(x) 为真当且仅当P(x) 对所有的x都成立。x P(x) is true iff P(x) is true for all x整体性限定（包含 全体的点）； w P(x) 为真当且仅当对某个x有P(x) 成立。x P(x) is true iff P(x) is true for some value of x存在性 限定； wx(A(x)B(x) 为真当且仅当所有的x，如果A(x)成 立，则有B(x)成立。普遍的隐含关系。 w整体性限定和存在性限定的逻辑关系可以相互转化 x A(x) is logically equivalent to x(A(x) x A(x) is logically equivalent to x(A(x) 14 逻辑证明 w证明一个逻辑论断的方法除了采用 真值表以外，还可以通过已经证明了的 逻辑等价关系或逻辑恒等式来达到。下 面我们再给出几个重要的逻辑恒等式： （反证法）AB (AB)B （逆反法）AB (B)A （反例法）(x P(x) x P(x) 15 例：反证法 w我们用反证法来证明 B(BC) C 成立。假设C为假，即C成立，则有 wC B(B C) C B(BC) w C (BB)(BC) w C (BC) w C BC.(恒为假) w这样我们就推出了一个矛盾：假设C为 真且已知B(BC)为真，但C B(BC)不为真！因此C为真的假设是不 成立的，从而C为真成立。B(BC) C 得证。 16 概率论 w随机试验的每一个可能的结果称为一个基 本事件，用表示。全体基本事件的集合称作 样本空间，用字母表示。 w设样本空间为 = 1, 2, , n，对于 的每个基本事件i，都有唯一的一个实数与 之对应，记为P(i)，且满足： （1）非负性。对任一基本事件i, 有 0P(i)1； （2 ）规范性。i P(i)=1。 P(i)称为基本事件i的概率。 17 事件 w样本空间的一个子集称为一个事件。一个事件 可以由多个基本事件所组成。事件A的概率记为P(A) ， w样本空间本身也是一个事件，称为必然事件， P()=1, 即任意一次试验的结果必然包含在中。 w另一个特例是空集，用表示。由于 对任意一 次试验的结果，都有，也就是说事件永远不 可能发生，所以P()=0。即空集代表不可能发生的 事件。 w对于 A， 称事件 A为A的补事件，记为 A。显然有P(A) = 1P(A) 成立。 18 条件概率 w我们把这种已知事件T发生的条件下， 事件S发生的可能性的客观度量称为条件概 率，记为P(S | T)。 Pr(S|T) = Pr(ST)/Pr(T) = siSTPr(si) /sjTPr(sj) w独立事件 设S, T为两个随机事件，若有 Pr(ST) = Pr(S)Pr(T) 成立，则称事件S, T是互相独立的。 19 随机变量 w若随机试验的每一个可能的结果（样本 点） 唯一地对应一个实数F()，则称实变 量F()为随机变量，通常用希腊字母 或大写 字母X, Y, Z等表示随机变量。 w w 定义定义 设随机试验的样本空间为 ，对于 每一个样本点，都有唯一实数X()与之 对应, 且对于任意实数xR，事件|X() x都有确定的概率，则称X() 为随机变量， 简记为X。 20 数学期望 设X是离散型随机变量,其分布为 若 则称 为X的数学期望（或均值）。 21 条件数学期望 w设X是离散型随机变量,S是一个事 件，则称 为随机变量X关于事件S的条件数 学期望（或条件均值）。 22 期望公式 w若1和2是两个随机变量，S是一 个事件，k 1, k 2是两个常数。假设 E(1|S)和E(2|S)都存在，则E(k 11+k 22 |S)也存在，且满足： E(k 11+k 22|S)=k 1E(1|S)+k 2E(2|S) 2. 设是一个随机变量，S是一个事 件，是S的补事件，则有条件期望公式 ： 3. 若 和 是两个随机变量，则有 下面的全期望公式成立：23 待定系数法 (Guess and test ) 例: 求和 猜测和式的可能形式 解出系数的值 (令 n = 0, 1, 2) 用归纳法证明和式对一切n成立 求和方法一 24 移位加减法 (Shift and reduce ) 例: 求和 将序列右移一位 消去中间项 求和方法二 25 一些常用的级数和 w算术级数 w多项式级数 n平方和级数 n一般形式 w以2为底的幂级数 w算术-几何级数 26 利用积分估计和式 定义：函数f(x) 是单调非减的, 若对于 x y 有 f(x) f(y). 函数f(x) 是单调非增的, 若-f(x) 是单调非减的. w若 f(x) 是单调非减的，则 w若 f(x) 是单调非增的，则 27 例：求解 T(n) = 2T(n/2) + 5n2, (n=2k); T(1) = 7 递归展开得: 展开法解递归方程 28 例：求解 T(n) = aT(n/b) + cnk, (n=bm ); T(1) = c 递归展开 求和得 带参数的