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

第2章 算法的数学基础 集合论 逻辑学 概率论 求和与递归 快速估算方法 集合 集合是由互不相同的元素组成的一个整体。通常这些元素都是属于同一种类型的，具有某些共同的性质。 一个元素e是集合S的成员，用符号 表示，读作e在S中或e属于S。 集合论 集合是现实世界高度的抽象。例如，它可以很好地解释类与对象的关系。 集合中元素是无序的，但在计算机存放时往往是有序的，如数组/序列。Java支持集合操作，但其元素必须是对象，而不是基本数据类型。 集合的表达方式 一个 特定的集合可以用列举或描述的方法来给出。列举就是将集合里的元素排列在花括号中。比如：S1 = {a, b, c}。 集合中的元素是没有先后顺序的。 对于那些有很多个 或无限多个 元素的集合，可以采取把集合中的元素所满足的条件写出来，例如： S2 = {x | x is an integer power of 2}读作“所有元素x都是整数的平方的集合”。 一个 特殊的集合叫做空集，用Φ表示, S3 = {} = ?。空集中没有任何元素。 集合的运算 如果集合S1的所有元素都在集合S2中，那么S1叫做S2的子集，用S1 ? S2,表示。而S2叫做S1的超集，用S2 ? S1表示。一个集合也是自身的子集和超集。我们规定，空集是任何集合S的子集：? ? S 。 设S、T是任意两个集合，定义S和T的交集为： S ? T = {x | x ? S and x ? T} S和T的并集定义为： S ? T = {x | x ? S or x ? T} 势 如果存在有限多个 整数的集合N = {n1, n2,…, nk }，N的元素和S中的元素有着一一对应关系，那么称集合S是有限集。S的基数或势（cardinality）等于k，表示为|S| = k 。 任意一个有n个元素的有限集的全部子集（包括空集）的数目为2n ，其中基数为k 的子集的个数为 序列 一组具有确定顺序的元素叫做一个序列。除了元素之间具有确定的顺序之外，序列与集合的不同之处还在于序列中的元素是可以重复的。 与集合的描述方式类似，我们也可以用列举或给出通项公式的方法表示一个序列，列举的方法是将序列中的元素用一对圆括号括起来。例如：S1=(a,b,c), S2=(b,c,a), S3=(a,a,b,c)。 序列 如果一个序列与前n个正整数的序列 ( 1, 2, 3, … , n ) 中的元素有一一对应关系，则称此序列是有限的。 如果有限序列中的元素互不相同，那么称这个序列是一个有限集合的置换或排列（permutation）。 一个有n个元素的集合有n! 个互不相同的排列。 数组 一个有限序列有时也称作数组，一个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，表示二维欧氏空间（实平面）。 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. 等价关系 如果一个二元关系同时满足反身性、对称性和传递性，那么这个关系叫做等价关系，记做“≌”。等价关系是一类十分重要的关系，因为通过它可以将下层集合S划分为若干个互不相交的子集，每一个子集叫做一个等价类。例如 [x] = {y ? S | x≌y} 表示 S 中所有与x 等价的元素的集合。 根据等价关系的传递性，等价类中的所有元素都相互“等价”。 Logic 逻辑学是用形式语言来规范自然语言叙述的系统方法，是使我们可以更精确地进行推理和推导的工具。 在逻辑学中最简单的命题叫做原子公式。更复杂的命题可以通过原子公式和逻辑连接符来表示，称为逻辑表达式。 常用的逻辑连接符包括：?（与）、?（或）、