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

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