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