离散数学

基础

函数的增长(估算复杂度)

大O记号:上限

  • logn, n, nlogn n2, 2n, n!
  • f1(x)是O(g1(x)),f2(x)是O(g2(x)),(f1+f2)(x)为O(max(g1(x),g2(x))).

大Ω记号:下限;大Θ记号:同阶

-- 多项式与最高阶同

整数和除法

简介

-- 从整除性建立的一个重要概念是素数,素数是大于1且能被1和它自己整除的整数。数论中一个重要的定理:每个正整数能都唯一地被分解为素数的乘积。把整数分解为素数因子在密码学中是很重要的。
-- 用一个整数除另一个整数得到商和余数。贯穿计算机科学的同于算法就是这些余数。本节讨论同余算法的三个应用:生成伪随机数、为文件分配内存地址和为信息加密/解密。

除法

整除:a | b 表示a整除b,可以用写为 Ec(ac=b),论域为整个整数集合(E为倒E,存在量词)

素数:素数是构造正整数的积木。

-- 证明素数的算法:如果n是合数,则n必有小于或等于根号n的一个素因子。

  • 如果n是合数,则n必有小于或等于根n的一个素数因子。
  • 梅森素数:2^n-1 及卢卡斯-莱默尔检验方法
  • 素数定理:当X趋于无限,不超过x的素数个数约等于x/lnx。
    --一个随机选择的正整数是素数的概率为1/lnx,只选奇书可以是找素数的速度加倍

证明101是素数;
求7007的素因子分解:从最小素数开始除,若整除,则余数继续用被除数素数除,否则有下一个素数。

整除算法:商与余数唯一

最大公约数与最小公倍数

  • 最大公约数:利用两个整数的素因子分解。

    a = p1^a1 * p2^a2 …… pn^an, b = p1^b1 * p2^b2 …… pn^bn
    gcd(a, b) = p1^min(a1, b1) * p2^min(a2, b2) …… pn^min(an, bn)
    
  • 最小公倍数

    lcm(a, b) = p1^max(a1, b1) * p2^max(a2, b2) …… pn^max(an, bn)

同余算术

令m为正整数,整数a和b模m同余的充要条件是存在整数k 使得 a = b + km

同余应用

  • 散列函数:h(k) = k mod m ,其中k为记录的关键字,m为内存的容量,h(k)为其分配的内存地址,用于为计算机文件分配内存地址。涉及到冲突处理。
  • 伪随机数:在一定范围内随机选择的数。最常用的产生 伪随机数的过程为线性同余法。
    xn+1 = a(xn + c) mod m
    若其中m = 0,则称为纯乘式发生器。例如以231 - 1为模,以75 = 16807为乘数的纯乘式发生器就广为采用。
  • 密码学
    凯撒加密法:f(p) = (p + 3) mod 26
    f-1(p) = (p - 3) mod 26

整数和算法

-- 定理:若a和b为正整数,则存在整数s和t,使得gcd(a, b) = sa + tb

数学推理、归纳与递归

证明策略

-- 一般情况下,如果命题是蕴含式,就应该首先尝试直接证明;如果这样不行,就尝试间接证明。如果这些方法都不行,就尝试归谬证明。
-- 前推、后推;分情况证明;修改现有证明;

序列与求和

数学归纳法

强归纳法

-- p(1)^p(2)……p(n-1) --> p(n)

良序性

-- 每个非空的非负数集都有最小元

递归定义与结构归纳法

-- 递归算法
-- 欧几里德最大公约数递归算法
-- 归并排序

程序的正确性

计数

计数原则

加法原则

乘法原则

排列和组合

排列

P(n, k) = n!/(n-k)!

组合

C(n, k) = n!/{(n-k)!*k!}

其他

C(n+1, k) = C(n, k) + C(n-1, k)

二项式定理

(x + y)^n = C(n, 0)x^n + C(n,1)x^(n-1)y +……+ C(n,n)y^n
2^n, 0

有重复的排列和组合

有重复的排列

  • 具有n个物体的集合允许重复的r排列数是n^r

有重复的组合

  • n个元素的集合中允许重复的r组合是C(n+r-1, r)=C(n+r-1, n-1)个。
    例如:
    方程 x1 + x2 + x3 = 11
    有多少个解?其中x1,x2,x3是非负数。
    C(11+3-1, 11) = C(13, 11)= 78

生成排列和组合

生成排列:P138页算法1

生成组合:P138页算法2、算法3

高级计数

递推关系

  • 常系数线性齐次方程
  • 递推与递归
  • 递推与分治

生成的函数

1/(1-ax)

容斥原理

|A并B| = |A| + |B| - |A交B|
|A并B并C| = |A| + |B| + |C| - |A交B | - |A交C | - |B交C | + |A交B交C|
N(P1' P2' ... Pn') = N - |A1并A2...An|

算法例题:

1、P147 汉诺塔
2、P161 并归排序、整数的快速乘法
3、P172 使用生成函数求解递推问题
4、P181 埃拉托色筛
5、P183 错位排序

关系

关系种类与表示

  • 自反

  • 对称/反对称

  • 传递

  • 邻接矩阵 0-1构成
    R R^n

关系的闭包

  • 自反闭包

  • 对称闭包

  • 传递闭包 = 等价于有向图的连通性 R* = ∪R^n

  • P211 传递闭包的过程

  • P213 沃舍尔算法

等价

  • 定义
    自反 + 对称 + 传递 = 等价

偏序

  • 定义
    自反 + 反对称 + 传递 = 偏序

  • 偏序集:即定义在某个集合上的关系

  • 全序集:偏序集都可比,即集合上所有元素都满足关系时,称为全序集。

  • 良序集:对于全序集,若其每个子集都有最小元素,则称为良序集。

  • 哈塞图:对于偏序集,去除本身的一定存在的关系的最小关系的图,称为哈塞图。
    即去除自反、传递关系

  • P228:拓扑排序

基本定义

  • 度:deg(v) 定点v的度指与v连接的边的个数。

  • 握手定理:2e = ∑deg(v).每个定点度数之和,为边的2倍。

  • 起点/终点,入度与出度
    ∑deg-(v) = ∑deg+(v) = e。入度 = 出度 = 边的个数。

  • 完全图 Kn,每两个顶点之间都有边。

  • 圈图 Cn,完全图的外围。

  • 轮图,在圈图中心加一顶点,并与其他顶点相连接。

  • 偶图,分两类,类内部无边,之间有边

图的表示

  • 邻接矩阵:边之间有连接为1,无连接为0,对称矩阵。

  • 关联矩阵:边与顶点间的关联关系,每个边上都有两个顶点。

  • 图的同构:顶点的度相同;邻接矩阵相同

连通性

  • 通过邻接矩阵的n次方来求长度为n的通路。

通路/回路

  • 欧拉通路:边不重复,dev(v) 为偶数
  • 哈密顿通路:顶点不重复,dev(v) + dev(u) >= n
  • P274:格雷码

最短路径

  • P280,迪克斯特拉算法:将顶点分成2个集合,每次从未加的集合中,选择最短加入集合,并更新未加集合的权值。
  • P283,弗洛伊德算法

可平面图

  • 定义:连线不相接

  • 面与顶点、边的定理: r= e - v + 2 面=边-顶点+2,证明方法:数学归纳法

  • 推论:若G是带e条边,v个顶点的联通和平面简图,其中v>=3,则e<=3v-6。

  • 理解:边数不能太多,太多总有连接。

  • 同胚:可以从同一张图经过初等细分(在边中加一个点)来获得,则称他们为同胚。

  • 定理:一个图是非可平面的,当且仅当她们包含一个同胚与K3,3或者K5的子图。

图着色

  • 平面图的色数不超过4个。
  • 回溯算法进行图着色。
  • P294例5、例6.

树的应用:

  • 二叉搜索树:P315 算法1 【左孩子小,右孩子大】
  • 哈夫曼编码:前缀码,P318哈夫曼编码算法。叶子字节
  • 决策树,每次结果都用树来表示出来。
  • 博弈树,最大最小策略。决策树后,两个人都朝自己有利的方向进行。 P322例8

树的遍历

  • 前序

    父 -> 左子 -> 右子
    P325 例1

  • 中序

    左子 -> 父 -> 右子
    从树外面包围它。

  • 后序

    左子 -> 右子 -> 父

P330 算法1-3

搜索

  • 深度优先搜索

    P338 :算法1

  • 广度优先搜索

    P339 :算法2

  • 回溯

    图着色、N皇后问题。

最小生成树:带权最小生成树

  • P345:普林算法,例1

  • P346:布鲁斯卡尔例3

其他算法

  • 遗传算法
  • 模糊算法
# 数学 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×