1037Life

2-数理基础

Part 2

数理基础

前言

数理基础是计算机学习的 “底层架构”,如同大厦的地基,决定着技术能力的上限与深度。从底层原理来看,计算机的硬件设计依赖离散数学中的逻辑运算构建电路逻辑,操作系统的进程调度、内存管理需用数学模型优化资源分配,甚至编程语言的语法规则也源于形式语言与自动机理论 —— 这些核心知识若脱离数理基础,只能停留在 “知其然” 的表层记忆,无法理解 “知其所以然” 的内在逻辑。

在计算机热门领域中,数理基础更是突破技术瓶颈的关键:人工智能与机器学习的模型训练,本质是通过线性代数处理高维数据、用概率论量化预测误差、靠微积分优化损失函数;大数据领域的分布式计算,需借助概率论与数理统计设计抽样算法、评估数据可信度;密码学的加密与解密,依赖数论中的素数分解、模运算构建安全体系。哪怕是看似 “偏应用” 的开发岗位,面对系统性能优化、算法效率提升等问题时,是否能通过复杂度分析(离散数学)选择更优方案,是否能用数学思维拆解复杂需求,往往成为区分普通开发者与资深工程师的核心差距。

缺乏数理基础的计算机学习,就像没有罗盘的航行 —— 或许能掌握基础操作,却难以应对深度问题与创新挑战。只有扎实掌握数学(线性代数、微积分、概率论)与离散数学的核心思想,才能在计算机技术的迭代中快速理解新理论、适配新场景,真正实现从 “技术使用者” 到 “技术创造者” 的跨越。

通用的数学理论

对于计算机专业是一个传统且经典的理工科专业,理工科专业必然是需要浓厚的数学基础,我在这里不按课程,按数学的方向来介绍学习计算机科学需要的数学能力.但是我们对数学的要求肯定是不如数学专业的,如果有更感兴趣的方向可以参考数学专业的教材.

数学分析

大学数学可以笼统地分成三个板块,一个板块是分析学,一个板块是代数学,一个板块就是几何学.

分析,本质上就是数学的一个分支学科,以微积分方法为基本工具,以函数(映射、关系等更丰富的内涵)为主要研究对象,以极限为基本思想的众多数学经典分支及其现代拓展的统称,简称分析.具体来说,就是微分学、积分学和级数理论.

多元函数

在微积分学的课程中,我们把函数的定义进行一定的推广得到多元函数.

定义:多元函数
设$D$为一个非空的$n$元有序数组的集合, $f$为某一确定的对应规则. 若对于每一个有序数组 $(x_1,x_2,\dots,x_n) \in D$,通过对应规则$f$,都有唯一确定的实数$y$与之对应,则称对应规则$f$为定义在$D$上的$n$元函数.
记为$y=f(x_1,x_2,\dots,x_n)$ 其中 $(x_1,x_2,\dots,x_n)\in D$. 变量$x_1,x_2,\dots,x_n$称为自变量, $y$称为因变量.

在计算机科学中,多元函数是处理高维数据的基础.例如在机器学习中,损失函数通常是高维参数空间上的多元函数,其自变量包括模型的权重、偏置等多个参数;在计算机图形学中,三维物体的表面渲染需要考虑位置$(x,y,z)$、光照方向等多个变量的函数关系.

极限

极限的本义就是数学中某一个函数中的某一个变量,此变量在变大(或者变小)的永远变化的过程中,逐渐向某一个确定的数值$A$不断地逼近而永远不能够重合到$A$(永远不能够等于$A$, 但是取等于$A$已经足够取得高精度计算结果)的过程中, 此变量的变化, 被人为规定为永远靠近而不停止、其有一个不断地极为靠近$A$点的趋势.极限是一种变化状态的描述.

对于上面的通俗定义,我们可以给出极限的严谨的定义:

定义:函数极限
$\forall \epsilon >0$, $\exists \delta >0$, s.t. $|f(x)-A|<\epsilon$在$0<|x-a|<\delta$范围内成立.

按照这个极限的严谨定义可以推导出函数的左右极限以及连续性等关键性命题,了解两个重要的极限, 了解求极限的两种方法–夹逼定则还有单调有界定则.

极限理论在计算机科学中有重要应用.数值计算中,许多算法的收敛性分析依赖极限理论,例如迭代法求解方程的根时,需要证明迭代序列收敛到真实解;在分布式系统中,一致性算法的收敛性分析也需要用到极限思想.此外,极限是定义导数、积分等概念的基础,是整个分析学的核心思想.

一元微分学

微分的定义就是当自变量的值从$a$变化为$a+\mathrmx$,函数的值的变化值.这个时候可以记作$\mathrmf(x)$,具体用极限的定义可以这么写

$$\mathop}\limits_ \left( f(x+\Delta x)-f(x) \right)$$

这个时候可以定义导数,导数的定义就是

定义:导数
$$\frac(f(x))}x} \mathop=\limits^} \lim_ \frac.$$

根据微分和导数的定义我们可以有很多工具来求导数,包括你高中没学过的对数求导,隐函数求导和参数方程求导,我们可以根据导数和二次导数的值来认定函数的单调性和凹凸性.

在计算机科学中,导数的应用极为广泛.机器学习中的梯度下降算法依赖于损失函数的导数(梯度)来更新模型参数;计算机视觉中的边缘检测算法利用图像灰度函数的导数来识别图像中的边缘;在数值优化中,导数是寻找函数极值点的关键工具.理解导数的几何意义(函数在某点的切线斜率)和物理意义(变化率)对于解决实际问题至关重要.

多元微分学

多元微分学就是在一元微分学的基础上添加关于多元的讨论,其中导数的定义会变成偏导数,通俗地来说就是求导数的时候只把一个变量看成变量,剩下的变量看成常量即可.这个时候可以对导数的定义进行修整:

定义:多元函数的偏导数
$$\frac = \lim_ \frac.$$

进一步,我们可以定义梯度,它是一个向量,由函数对各个自变量的偏导数组成:

定义:梯度
对于$n$元函数$f(x_1,x_2,\dots,x_n)$,其梯度为:
$$\nabla f = \left( \frac, \frac, \dots, \frac \right)$$

梯度方向是函数值增长最快的方向,这一性质在机器学习、计算机图形学等领域有重要应用.例如,在神经网络训练中,反向传播算法本质上是计算损失函数对各层参数的偏导数;在计算机视觉中,基于梯度的特征提取算法(SIFT、HOG等)利用图像的梯度信息来构建特征描述子.此外,多元函数的泰勒展开在数值计算和优化算法中也经常用到,它可以对复杂函数进行局部近似.

一元积分学

在微积分中,一个函数$f$的不定积分,或原函数,或反导数,是一个导数等于$f$的函数$F$, 即$F' = f$.

定积分是积分的一种,是函数$f(x)$在区间$a,b$上积分和的极限。这里应注意定积分与不定积分之间的关系:若定积分存在,则它是一个具体的数值,而不定积分是一个函数表达式,它们仅仅在数学上有一个计算关系,这个关系叫做Newton-Leibniz公式:
$$\int_a^b f(x) \mathrmx = F(b) - F(a)$$
其中$F$是$f$的一个原函数。

当然一个函数,可以存在不定积分,而不存在定积分;也可以存在定积分,而不存在不定积分。一个连续函数,一定存在定积分和不定积分;若只有有限个间断点,则定积分存在;若有跳跃间断点,则原函数一定不存在,即不定积分一定不存在。

定积分的几何意义是曲边梯形的面积,这一概念在计算机图形学中用于计算不规则图形的面积;在信号处理中,积分用于计算信号的能量和功率;在概率统计中,概率密度函数的积分用于计算随机变量落在某一区间的概率.数值积分算法(如梯形法、辛普森法)在计算机无法求得解析解时提供了有效的近似计算方法.

多元积分学

将积分的函数推广到多元函数就是多元积分学,那么多元积分学的区间就会变成多种多样的几何图形.比如说重积分,第一类和第二类的线积分,第一类和第二类的面积分.我们知道定积分可以计算曲边梯形的面积,重积分就可以计算体的体积,对于曲线积分可以计算出曲线的重量,第二类的曲线积分可以计算出做功的值,曲面积分可以计算曲面的重量,第二类曲面积分可以计算出通量,对于这几类积分,做法就是降维,转化成一元的定积分即可.

在计算机科学中,多元积分有诸多应用.计算机图形学中,计算三维物体的体积和表面积需要用到重积分和曲面积分;在物理模拟中,计算物体所受的力和力矩需要用到线积分和面积分;在机器学习中,某些概率模型的归一化常数计算涉及高维积分,由于高维空间的复杂性,通常需要采用蒙特卡洛方法等数值积分技术来近似计算.

级数

级数是指将数列$a_n$的项$a_1,a_2,\dots,a_n$依次用加号连接起来的函数,是数项级数的简称。如:$a_1+a_2+\dots+a_n$,简写为$\sum_^ a_n$, 称$a_n$为级数的通项, 记$S_n = \sum_^n a_k$为级数的部分和。如果当$n \to \infty$时 ,数列$S_n$有极限,极限为$S$,则说级数收敛,否则就说级数发散.

对于函数项级数,我们重点讨论幂级数,即形如$\sum_^ a_n x^n$的级数.幂级数有其收敛半径和收敛域,在收敛域内可以进行逐项求导和逐项积分等运算.

另一种重要的级数是傅里叶级数,任何满足一定条件的周期函数都可以展开为傅里叶级数:
$$f(x) = \frac + \sum_^ \left( a_n \cos(nx) + b_n \sin(nx) \right)$$
其中$a_n, b_n$为傅里叶系数.

级数理论在计算机科学中应用广泛.数值计算中,许多函数通过幂级数展开进行近似计算,如指数函数、对数函数等;在信号处理中,傅里叶级数是傅里叶变换的基础,用于将信号从时域转换到频域进行分析和处理;在图像压缩中,基于傅里叶级数的变换(如JPEG压缩中的离散余弦变换)可以去除图像中的冗余信息.

微分中值定理与泰勒展开

主要介绍了Rolle定理, Lagrange定理还有Cauchy中值定理.

定理:Rolle定理
若函数$f(x)$满足:

  1. 在闭区间$a,b$上连续;
  2. 在开区间$(a,b)$内可导;
  3. $f(a) = f(b)$.
    则至少存在一点$\xi \in (a,b)$,使得$f'(\xi) = 0$.

定理:Lagrange中值定理
若函数$f(x)$满足:

  1. 在闭区间$a,b$上连续;
  2. 在开区间$(a,b)$内可导.
    则至少存在一点$\xi \in (a,b)$,使得$f(b) - f(a) = f'(\xi)(b - a)$.

这些中值定理是连接函数及其导数的桥梁,在证明不等式、研究函数性质等方面有重要作用.

更具实用价值的是泰勒展开,它可以将一个光滑函数表示为幂级数的形式:

定义:泰勒展开
若函数$f(x)$在点$x_0$处有$n$阶导数,则在$x_0$的邻域内有:
$$f(x) = f(x_0) + f'(x_0)(x - x_0) + \frac(x - x_0)^2 + \dots + \frac(x_0)}(x - x_0)^n + R_n(x)$$
其中$R_n(x)$为余项.当$n \to \infty$时,若$R_n(x) \to 0$,则得到函数的泰勒级数.

泰勒展开在数值计算中用于函数的近似表示,在优化算法中用于目标函数的局部近似(如牛顿法中用二次泰勒展开近似目标函数),在机器学习中用于分析算法的收敛性和稳定性.理解泰勒展开的截断误差对于控制数值计算的精度至关重要.

反常积分与含参变量积分

除了前面介绍的正常积分,还有两类重要的积分形式需要了解:

反常积分

反常积分是定积分的推广,包括无穷区间上的积分和无界函数的积分:
$$\int_a^ f(x) \mathrmx = \lim_ \int_a^b f(x) \mathrmx$$
$$\int_a^b f(x) \mathrmx = \lim_ \int_a^ f(x) \mathrmx \quad (f在b点附近无界)$$

反常积分在概率统计中用于定义连续型随机变量的概率密度函数,如正态分布的概率密度函数的归一化就是通过反常积分实现的;在信号处理中,某些信号的能量计算也需要用到反常积分.

含参变量积分

含参变量积分是形如$F(t) = \int_a^b f(x,t) \mathrmx$的积分,其中$t$为参数.这类积分在很多领域都有应用,如在机器学习中,某些模型的边缘概率计算涉及含参变量积分;在数值分析中,含参变量积分的数值解法是研究的重要内容.

含参变量积分的分析性质(连续性、可微性、可积性)为处理复杂函数提供了工具,其导数可以通过莱布尼茨法则计算:
$$\frac}t} \int_a^b f(x,t) \mathrmx = \int_a^b \frac(x,t) \mathrmx$$
这一法则在最优化理论和变分法中经常用到.

线性代数

线性代数是计算机专业的“数学工具箱”——从数据结构的矩阵存储,到AI模型的参数计算,再到图形学的坐标变换,都离不开它。作为大一新生,我们不用死记公式,重点是理解“向量如何表示数据”“矩阵如何描述变化”,为后续专业课打基础。

向量:高维数据的“容器”

高中我们学过二维向量(比如平面上的箭头),大学线性代数会把它扩展到高维(比如描述一张图片的像素值、一个学生的多科成绩),核心是用“有序数字列表”表示复杂数据。

1. 行向量与列向量:存储形式的区别

高中常写的“横着的向量”叫行向量,比如表示“成绩(数学80,英语90)”:
$$
\mathbf = \begin 80 & 90 \end

$$

大学更常用“竖着的向量”——列向量,因为它方便后续矩阵运算,上面的成绩可改写为:
$$
\mathbf = \begin 80 \ 90 \end

$$

两者可以通过“转置”互相转换:行向量转置成列向量,列向量转置成行向量,用符号“$\top$”表示,比如$\mathbf^\top = \mathbf$,$\mathbf^\top = \mathbf$。

2. 基底与线性组合:向量如何“搭出”空间

想象你在平面上画箭头:任意两个“不重合、不共线”的向量(比如$\mathbf=(1,0)$,$\mathbf=(0,1)$,也就是x轴和y轴的单位向量),能通过“缩放+相加”得到平面上所有向量。比如向量$\mathbf=(3,2)$,可以写成:
$$
\mathbf = 3 \times \mathbf + 2 \times \mathbf

$$

这里的$\mathbf、\mathbf$就是“基底”,$3\mathbf + 2\mathbf$就是它们的“线性组合”。
扩展到高维:比如3维向量(x,y,z),需要3个不共面的基底;描述100个像素的向量,需要100个线性无关的基底——“线性无关”就是“没有一个向量能被其他向量的线性组合表示”,就像3个坐标轴不能互相替代一样。

3. 向量张成的空间:数据能覆盖多大范围

n个d维向量(比如5个3维向量)能“搭出”的空间维度,取决于其中“线性无关向量的最大个数”。比如3个3维向量若线性无关,能搭出完整的3维空间;若有1个向量能被另外2个表示,就只能搭出2维平面(像一张纸)。
这就像:100个学生的成绩向量(每科分数为一维),如果大家的数学、物理成绩成比例(线性相关),那么这两科实际只算“1维信息”,最终数据的有效维度会小于科目数——这在机器学习“降维”中很有用。

矩阵:向量的“变形工具”

矩阵可以理解为“线性变换的说明书”——把一个向量输入,按矩阵的规则变换后输出新向量。比如图形学中“旋转图片”“放大缩小”,本质就是用矩阵变换像素的坐标向量。

1. 矩阵如何表示线性变换

线性变换有两个特点:① 原点位置不变;② 直线变换后还是直线(比如网格线不会变曲线)。
以二维为例:原基底是$\mathbf=(1,0)$(x轴)、$\mathbf=(0,1)$(y轴)。若变换后基底变成$\mathbf'=(1,2)$、$\mathbf'=(3,4)$,这个变换就可以用矩阵记录——把新基底按列拼成矩阵:
$$
\mathbf = \begin 1 & 3 \ 2 & 4 \end

$$

那么任意向量$\mathbf=\begin x \ y \end$(比如$\mathbf=(1,2)$),变换后的新向量$\mathbf'$就是:
$$
\mathbf \mathbf = x \times \mathbf' + y \times \mathbf' = 1 \times \begin 1 \ 2 \end + 2 \times \begin 3 \ 4 \end = \begin 7 \ 10 \end

$$

计算规则:矩阵第1列乘x,第2列乘y,再相加(高维矩阵同理,按列对应缩放后相加)。

2. 矩阵乘法:连续变换的“叠加”

如果要对向量做两次变换(比如先旋转、再放大),就需要用矩阵乘法把两个变换“合并”。
比如先做变换$\mathbf=\begin 0 & 1 \ 1 & 0 \end$(交换x、y轴),再做变换$\mathbf=\begin 1 & 1 \ 1 & 0 \end$,合并后的变换就是$\mathbf \times \mathbf$(注意顺序:先算右边的$\mathbf$,再算左边的$\mathbf$)。

计算规则:若$\mathbf$是$m \times n$矩阵(m行n列),$\mathbf$是$n \times p$矩阵,乘积$\mathbf\mathbf$是$m \times p$矩阵,其中第i行第j列的元素等于“$\mathbf$第i行的每个元素,乘$\mathbf$第j列的对应元素,再求和”。比如:
$$
\begin a & b \ c & d \end \times \begin e & f \ g & h \end = \begin ae+bg & af+bh \ ce+dg & cf+dh \end

$$

关键提醒:矩阵乘法没有交换律!$\mathbf\mathbf$和$\mathbf\mathbf$通常不一样(就像“先穿袜子再穿鞋”和“先穿鞋再穿袜子”结果不同)。

行列式:线性变换的“缩放比例”

行列式是矩阵的一个“数值特征”,它描述了“线性变换后空间的缩放程度”——比如二维矩阵的行列式,就是“变换前单位正方形的面积,与变换后平行四边形面积的比值”。

1. 行列式的直观意义

三维矩阵的行列式,对应“体积的缩放比例”,符号表示空间是否被“镜像翻转”(可用右手定则判断)。

2. 行列式的计算(以2、3阶为例)

$$

不用死记复杂公式,大一阶段能计算2、3阶行列式,理解其“缩放”意义即可。

逆矩阵与秩:变换的“反向操作”与“有效维度”

1. 逆矩阵:如何“还原”线性变换

如果用矩阵$\mathbf$把向量$\mathbf$变成$\mathbf'=\mathbf\mathbf$,那么“逆矩阵”$\mathbfinv$就是能把$\mathbf'$还原回$\mathbf$的矩阵,满足:
$$
\mathbfinv \times \mathbf = \mathbf \quad (\mathbf是单位矩阵)

$$

单位矩阵$\mathbf$是“无变换”的矩阵(主对角线为1,其余为0),比如2阶单位矩阵$\mathbf=\begin 1 & 0 \ 0 & 1 \end$,用它乘任何向量都不变。

什么时候有逆矩阵? 只有行列式$\det(\mathbf) \neq 0$的矩阵才有逆矩阵。因为若$\det(\mathbf)=0$,表示变换把空间“压缩”了(比如2维平面压成1维直线),此时多个原向量会变成同一个新向量,无法还原(就像把纸揉成球,没法再展开成原来的纸)。

2. 秩:矩阵的“有效信息维度”

矩阵的秩,就是“矩阵列向量中线性无关的最大个数”(也等于行向量的线性无关最大个数)。比如:

秩的意义:在计算机中,矩阵的秩代表“数据的有效信息维度”。比如一张100×100的图片,若存储为矩阵后秩为50,说明这张图的信息其实用50维就能表示,剩下的50维是冗余的——这就是“图像压缩”的基本思想。

特征值与特征向量:变换中“不变方向”的向量

有些向量经过线性变换后,方向不变,只被缩放——这些向量就是“特征向量”,缩放的比例就是“特征值”,用公式表示:
$$
\mathbf \mathbf = \lambda \mathbf

$$

其中$\mathbf$是特征向量,$\lambda$是对应的特征值。

1. 直观例子

比如矩阵$\mathbf=\begin 2 & 0 \ 0 & 3 \end$(沿x轴放大2倍,y轴放大3倍):

2. 为什么重要?

在AI中,“主成分分析(PCA)”就是找数据矩阵的特征向量——特征值最大的特征向量,对应数据变化最剧烈的方向(比如人脸图片中“五官位置”的主要变化方向),用这些向量能快速降维,保留关键信息。

概率论:计算机中的“不确定性”数学

计算机常要处理“不确定的问题”——比如预测明天是否下雨、识别图片中的物体是否是猫、网络传输是否会出错。概率论就是描述“不确定性”的数学工具,大一阶段重点理解“概率如何计算”“数据分布有什么规律”。

基础概念:概率不是“频率”

首先要区分两个概念:

事件之间的关系(用例子理解):

条件概率与贝叶斯公式:“已知信息”下的概率

生活中常需要“已知某个条件,求另一个事件的概率”——这就是条件概率。

1. 条件概率公式

若已知事件B发生,求事件A发生的概率,记为$P(A|B)$,公式为:
$$
P(A|B) = \frac

$$

其中$P(A \cap B)$是“事件A和B同时发生的概率”(联合概率)。

例子:箱子里有2个红球、3个白球,不放回摸两次。已知第一次摸的是红球,求第二次摸红球的概率:

2. 贝叶斯公式:“反向推理”的工具

把条件概率公式变形,就得到贝叶斯公式:
$$
P(A|B) = \frac

$$

它的核心是“根据结果反推原因”——比如“已知地面湿(结果B),求下雨(原因A)的概率”。

在计算机中的应用:垃圾邮件识别——已知邮件包含“免费”“中奖”等词(结果B),反推这封邮件是垃圾邮件(原因A)的概率,就是用贝叶斯公式计算。

概率分布:数据“扎堆”的规律

现实中的数据往往有“规律的分布”——比如学生的考试成绩大多集中在平均分附近,掷骰子的结果均匀分布。根据数据是否“可数”,分为离散型和连续型分布。

1. 离散型分布(数据可数,比如次数、个数)

常见的有3种,用“掷骰子、抛硬币”就能理解:

$$

其中$\binom$是“从n个中选k个的组合数”(比如$\binom=120$)。

$$

其中$\lambda$是“平均发生次数”(比如1小时平均访问4次,$\lambda=4$)。

2. 连续型分布(数据不可数,比如时间、长度)

最常用的是“正态分布”(钟形曲线),比如学生的身高、体重、考试成绩大多符合正态分布,公式:
$$
f(x) = \frac\sigma} e^}

$$

其中:

3. 常用分布汇总表

为了方便对比,整理成下表(不用死记,知道每种分布的用途即可):

计算机常用概率分布汇总

分布类型 分布名称 核心用途
离散型 0-1分布 单次二选一试验(如硬币、是否中奖)
二项分布 n次独立试验的成功次数(如抛n次硬币)
泊松分布 稀有事件的发生次数(如网站访问、故障次数)
连续型 均匀分布 数据均匀取值(如随机生成0-1之间的数)
正态分布 自然现象、数据的集中分布(如身高、成绩)
指数分布 事件发生的间隔时间(如设备寿命、服务等待时间)

期望与方差:数据的“平均水平”与“波动大小”

拿到一组数据,我们常想知道“平均是多少”“数据散不散”——期望就是“平均水平”,方差就是“波动大小”。

1. 期望(均值):数据的“中心”

$$

意义:在计算机中,期望是“损失函数的平均误差”——比如AI模型预测房价,期望就是“长期预测的平均偏差”,我们希望这个值越小越好。

2. 方差:数据的“分散程度”

方差是“每个数据与期望差的平方的期望”,公式:
$$
D(X) = E\left (X - E(X))^2 \right

$$

也可以简化为:
$$
D(X) = E(X^2) - E(X)^2

$$

例子:两组数据1,3,5和2,3,4,期望都是3,但方差分别是:

意义:方差越小,数据越稳定——比如网络传输的延迟,方差小说明延迟波动小,服务更可靠。

3. 协方差:两个数据的“关联程度”

方差描述“单个数据的波动”,协方差描述“两个数据的关联的方向”,公式:
$$
\text(X,Y) = E\left (X - E(X))(Y - E(Y)) \right

$$

协方差矩阵:把多个数据的两两协方差写成矩阵,比如3个数据X,Y,Z,协方差矩阵是:
$$
\begin
\text(X,X) & \text(X,Y) & \text(X,Z) \
\text(Y,X) & \text(Y,Y) & \text(Y,Z) \
\text(Z,X) & \text(Z,Y) & \text(Z,Z)
\end

$$

它在机器学习“降维”和“聚类”中经常用到,用来衡量数据之间的相关性。

最大似然估计:从数据反推“最可能的参数”

我们常知道“数据符合某种分布”,但不知道分布的参数(比如知道考试成绩符合正态分布,但不知道均值$\mu$和标准差$\sigma$)——最大似然估计就是“用已有数据,找最可能的参数值”。

核心思路:

  1. 假设数据符合某种分布(比如正态分布),写出“似然函数”——就是“现有数据出现的概率,作为参数的函数”。

  2. 找使似然函数最大的参数值(因为“现有数据出现的概率最大”,说明这个参数最合理)。

例子:抛10次硬币,出现6次正面。假设符合0-1分布,求正面概率p:

在计算机中的应用:AI模型的参数训练——比如线性回归模型,假设误差符合正态分布,用最大似然估计能推导出“最小二乘法”,就是我们常用的“找最优拟合直线”的方法。

计算机领域的数学基础

算法的复杂度标记

限界函数的定义

算法时间复杂度的限界函数常用的有三个对应的渐进记号.$O$(上界函数),$\Omega$(下界函数),$\Theta$(渐进紧确界函数).

定义
如果函数$f(n)$,存在一个$c$和$n_0$,使得对于任意的$n\geq n_0$,都有$0 \leq f(n) \leq cg(n)$,那么我们可以说$f(n)=O(g(n))$

含义:当$n$足够大的时候,$f(n)$总小于$|g(n)|$的一个常数倍.,

O记号给出的是渐进上界,称为上界函数(upper bound).

上界函数代表了算法最坏情况下的时间复杂度.

在确定上界函数时,应试图找阶最小的$g(n)$作为$f(n)$的上界函数——紧确上界(tight upper bound).

如:若:$3n+2=O(n^2)$ 则是松散的界限;

而:$3n+2=O(n)$ 就是紧确的界限.

这样说来,紧确上界就是阶数最小的上界函数.

同样的,也有其他集合符号的定义.

定义
如果函数$f(n)$,存在一个$c$和$n_0$,使得对于任意的$n\geq n_0$,都有$f(n) \geq cg(n)$,那么我们可以说$f(n)=\Omega(g(n))$

含义:当$n$足够大的时候,$f(n)$总不小于$|g(n)|$的一个常数倍.

同样的,$\Omega$记号给出一个渐进下界,称为下界函数(lower bound).
在确定下界函数时,应试图找出数量级最大的$g(n)$作为$f(n)$的下界函数——紧确下界.

定义
如果函数$f(n)$,存在一个$c_1$、$c_2$和$n_0$使得对于任意的$n\geq n_0$,都有$c_1g(n) \leq f(n) \leq c_2g(n)$,那么我们可以说$f(n)=\Theta(g(n))$

含义:当$n$足够大的时候,$f(n)$总不小于$|g(n)|$的一个常数倍.总不大于$|g(n)|$的一个常数倍.

但是$\Theta$给出的就是一个渐进的紧确界.

下面这张图片可以反映各个符号所代表的关系

一般来说,可能会让你证明某个函数是怎样怎样的,比如说
$$\frac-3n=\Omega(n^2),$$

这个时候我们只需要求出三个数,满足渐进符号的定义即可.

解答
根据渐进符号的定义,可以写出使得对于任意的$n\geq n_0$,都有$c_1n^2 \leq \dfracn^2-3n \leq c_2n^2$.

两边同除$n^2$,有:
$$c_1 \leq \frac-\frac \leq c_2,$$

这里只要取$c_1=\dfrac$, $c_2=\dfrac$, $n_0=7$,即可得证.$\hfill\blacksquare$

注意: $f(n)=O(g(n))$不能写成$g(n)=O(f(n))$.

下面继续介绍渐进符号:这里引入$o$, $\omega$记号专门用来表示一种非渐进紧确的上界或下界.

定义
如果函数$f(n)$, 对于任意正常数$c$存在常数$n_0$, 使得对于任意的$n\geq n_0$, 都有$f(n) \leq cg(n)$, 那么我们可以说$f(n)=o(g(n))$.

定义
如果函数$f(n)$,对于任意正常数$c$存在常数$n_0$,使得对于任意的$n\geq n_0$,都有$f(n) \geq cg(n)$,那么我们可以说$f(n)=\omega (g(n))$

限界函数的性质

所有的渐进符号都有传递性,假设渐进符号为$X$,有
$$f(n)=X(g(n)),g(n)=X(h(n)) \to f(n)=X(h(n)).$$

只有三个大写的渐进符号有自反性,假设渐进符号为$X$,有
$$f(n)=X(f(n)).$$

只有一个渐进符号有对称性.
$$f(n)=\Theta(g(n)) \to g(n)=\Theta(f(n)).$$

还有两个符号有转置对称性.
$$f(n)=O(g(n)) \to g(n)=\Omega(f(n)),$$
$$f(n)=o(g(n)) \to g(n)=\omega(f(n)).$$

最后,如果说算法的时间复杂度为$O(n)$,也就是说算法的执行时间与问题的规模$n$成正比.

生成函数

定义
(生成函数)
对于一个数列${a_n}$,定义它的(普通)生成函数为$F(x)=\displaystyle\sum_^ a_ixi$,<u>指数型生成函数</u>为$G(x)=\displaystyle\sum_{i=1} a_i\dfrac$.

定义
(生成函数的封闭形式)
将函数项级数化简表示为一些函数的有限次四则运算与开方等简单运算,称为其封闭形式.封闭形式进行Taylor级数展开就是展开形式.

这个展开一般是Maclaurin展开,也就是函数在$x=0$处的Taylor展开.

接下来补充一个关于计算生成函数的手段.

定义
(离散卷积)
给定数列$a_n$和$b_n$,定义$\sum_^n a_ib_$为$a_n$和$b_n$的离散卷积,记为$a_n*b_n$.

根据离散卷积的定义我们可以介绍生成函数的基本运算.

定理
定义函数$f(x)=\sum_^n a_i xi$,$g(x)=\sum_{i=0}n b_i xi$,则二者之和为$f(x)+g(x)=\sum_{i=0}n (a_i+b_i) xi$,二者之积为$f(x)g(x)=\sum_{i=0} (a_i*b_i)x^i$.

下面来简单介绍生成函数在组合数学中的应用.

生成函数可以用乘幂来表示计数的相加,这样可以便于计算出计数的结果.考虑如下问题:

例
我们要从小玉、大玉、札弹和光玉中拿一些弹幕出来,要求小玉组成偶数弹,大玉的个数要是$5$的倍数,札弹最多拿$4$个,光玉要么不拿,要么只能拿一个.问按这样的要求拿$n$个弹幕的方案数.
解:
g(x)&=(1+x2+x4+cdots)(1+x5+x10+cdots)(1+x+x2+x3+x^4)(1+x)
&=11-x2*11-x51-x^51-x(1+x)
&=1(1-x)^2
&=C(1,0)+C(2,1)x+C(3,2)x2+C(4,3)x3cdots
&=1+2x+3x2+4x3+5x^4+cdots
解答的每一项$a_nx^ n$中,$a_n$表示组弹幕的方法,$x$的次数表示这一项所拿弹幕的数量.

组合数学

由于组合数学和计算机非常贴近,我们在这里着重介绍一下:

计数原理

定义:排列
从$n$个不同元素中取出$m(\leqslant n)$个元素,按照一定的顺序排成一列,叫做从$n$个元素中取出$m$个元素的一个排列,排列的种数叫做排列数,记为$P(n,m)$.
排列数的计算公式为$P(n,m)\frac$.

定义:组合
从$n$个不同的元素中,任取$m(\leqslant n)$个元素为一组,叫作从$n$个不同元素中取出$m$个元素的一个组合,组合的种数叫组合数,记为$C(n,m)$.
组合数的计算公式$C(n,m)=\dfrac$.

例
设今有$4$个$e$,$3$个$f$,$2$个$g$,$1$个$h$,这些字母能组合成几种有序字母串?

首先优先考虑重复的元素,先把$4$个$e$放到$10$个位置中的$4$个,有$C(10,4)$种方法;再把$3$个$f$放在剩下$6$个位置中的$3$个,有$C(6,3)$种方法;接下来$2$个$g$,有$C(3,2)$种方法;最后一个$h$只能放在最后一个剩余的位置上.

所以种类数为$C(10,4)C(6,3)C(3,2)=12600$种.

另一种思考的方式是除序.

假设其他$6$个字母不变,$4$个$e$分别记为$1,2,3,4$那么对于$1234$的排列或者是$4321$的排列都是一样的,这个时候可以除以$4!$来表示元素是没有区别的.所以上述问题的答案就是$\dfrac=12600$.

接下来考虑有重复元素的组合,一般采用隔板法.对于$n$个元素放进$m$个盒子里面的情况,我们可以构造$m-1$个隔板,这样就可以用隔板间夹住的部分表示盒子了,即$C(n+m-1,m-1)$.

定义:环排列
从$n$个不同的元素中,取出$m$个元素将其围成圆环(经过旋转可以重合的视为同一种)称为从$n$个不同元素中取出$m$个元素的一个环排列.环排列的种数称为环排列数.

为了求环排列数,我们不妨先考虑从$n$个元素中已经选好$m$个元素,求这$m$个元素组成环的种数:如果固定一个长度为$m$的圆,在不将可旋转重合的情形视为一种时,种数就是全排列数$m!$,而可视为一种的那些情况反过来都可以当成由取定环排列旋转得来的,每个环排列经过旋转$1\sim m$个单位,产生$m$个不同的情况,故$m$倍的环排列数就等于排列数.故从$n$个元素取出$m$个元素的环排列数为:$C(n,m)\dfrac=C(n,m)(m-1)!$种.

容斥定理

$$p(A+B)=p(A)+p(B)-p(AB)$$

概率论衡量的是本质是对事件的计数,这一公式的本质就是容斥定理.

推广后即

定理:容斥定理
$$\left|\bigcupn_{i=1}S_i\right|=\sumn_(-1){m-1}\sum_{1<a_{i_1}<...<a_{i_m}<n}\left|\bigcapm_S_\right|.$$

最后一项可能看着很复杂,其实就是可以表为$m$个集合的交的子集的元素个个数,再让$m$从$1$跑到$n$.下面给出简要的证明:

对于元素$x$,假设它出现在$T_1,T_2,T_3,\dots,T_m$的集合中,那么它的出现次数为$1$.
对于$m$个分类,这个元素$x$都在分类里面,我们可以写出:
$$
\begin
\mathrm=& |{T_i}|-|{T_i\cap T_j|i<j}|+\cdots+(-1){k-1}\left|\left{\bigcap_{i=1}T_\Bigg|a_i<a_\right}\right|\
&+\cdots+(-1)^|{T_1\cap\cdots\cap T_m}|\
=& C(m,1)-C(m,2)+\cdots+(-1)^C(m,m)\
=& C(m,0)-\sum_m(-1)iC(m,i)\
=& 1-(1-1)^m=1.
\end
$$

于是每个元素出现的次数为$1$,合并起来就是并集. $\blacksquare$

现在我们来引出一个叫做错位排序的概念.

定义:错位排列
对于$1\sim n$的排列$P$如果满足对任意$i=1,2,\cdots,n$,都有$P_i\ne i$,则称$P$是$n$的错位排列.

求错位排序的个数需要转换一下思路:我们可以把全排序$|U|=n!$求出来,减去不满足错位排序要求的,错位排序就是没有一个元素是匹配的,那么我们设$S_i$代表有$P_i=i$满足

这个$\left|\displaystyle\bigcup^_S_i\right|$就可以用容斥定理求出来
这个数就是满足一个的部分,减去满足两个的部分,再加上满足三个的部分,再减去满足四个的部分……依此类推,有

$$\left|\bigcup{n}_{i=1}S_i\right|=\sumn_(-1)^C(n,k)(n-k)!.$$

上面的式子的含义是:对于有$k$个$i$,满足$P_i=i$的情况的计数结果,就是先从$n$个数里面选$k$个,然后剩下的$n-k$个元素进行全排序.

于是错位排序的计算式为$$D_n=n!(1-\sumn_{k=1}\dfrac{(-1)^{k-1}}{k!})=n!\sumn_\dfrac.$$

本节的最后,给出与容斥定理相关的二项式反演公式,它也被称为广义反演公式.

定理:二项式反演公式
$$
\begin
F_n=& \sum^_C(n,i)G_i,\
G_n=& \sum{n}_{i=0}(-1)C(n,i)F_i.
\end
$$

下面给出证明:

将二项式反演公式中的第一式代入第二式,有
$$
\begin
G_n &=\sum_{n}(-1)C(n,i)F_i\
&=\sum_{n}(-1)C(n,i)\sum^C(i,k)G_k\
&=\sum
{n}\left(\sum_(-1)^C(n,i)C(i,k)\right)G_i.
\end
$$

根据二项式定理,可以得到最后一行就是$G_n$,于是二项式反演公式成立. $\blacksquare$

也可以用生成函数来进行证明.先给出生成函数相乘的数学依据:
$$
\begin
\hat(x)\hat(x) &=\sum_a_i\frac\sum_b_j\frac\
&=\sum_x{n}\sum_{i=0}na_ib_\frac\
&=\sum_\frac}\sum_^nC(n,i)a_ib_ .
\end
$$

由于
$$F(x)=\sum_^F_i \dfrac,$$
并且数列$a_n=1$对应的生成函数就是$\e^x$,所以有
$$F(x)=\sum_{n}\left(\sum_C(i,k)G_k\right)\dfrac=G(x)\e^x,$$
可得$G(x)=F(x)\e^$.

Stirling数

定义:第一类Stirling数
第一类Stirling数(或称Stirling轮换数)的符号为$s(n,k)$,表示将$n$个不同的元素,划分为$k$个环排列的方案数.

根据定义,我们有下面这三条推论:

  1. $s(n,1)=(n-1)!$;
  2. $s(n,n)=1$;
  3. $s(n,n-1)=C(n,2)$.

由定义我们还可以得到递推式
$$s(n,m)=s(n-1,m-1)+(n-1)s(n-1,m).$$
其组合意义是:对$n-1$个元素的情况分类,前一项表示在已经做好$n-1$个元素的安排基础上令第$n$个元素自成一个单元素的环排列,后一项表示已将$n-1$个元素组成$m$个环排列,再将第$n$个元素依次插入环排列中$1\sim n-1$这些元素的前面形成的新的$m$个环排列的情况.

定义:第二类Stirling数
第二类Stirling数的符号为$S(n,m)$,表示将不同的$n$个元素划分为$m$个集合的方法数.

类似地,有第二类Stirling数的递推式:$S(n,m)=S(n-1,m-1)+mS(n-1,m)$.

前一项表示将一个新元素单独放在一个子集之中,有$S(n-1,k-1)$个方案,后一项表示将新元素放入一个现有的非空子集,有$kS(n-1,k)$个方案.

下面我们来求第二类Stirling数的通项公式:

假设有$n$个两两不同的元素,划分到$i$个两两不同的集合的方案数是数列$G_i$,如果还要求这个集合非空,那就是数列$F_i$,这个时候我们可以写下$G_i=i^n$.

我们现在知道,可以假设有$0\sim i$个非空集合,这个时候可以写出$F_i$和$G_i$的联系.

我们知道对于一个$i$,$G_i$里面包含$i$种情况,就是有$1,2,3,4,\cdots,i$个集合里面有元素,这个时候可以根据加法原则得到$G_i$就是等于这几种情况相加得来的结果,对于$j$个集合里面有元素的情况,就是$i$个集合里面选$j$个集合有元素$F_iC(i,j)$.

$$G_i=\sum^i_C(i,j)F_j$$
根据二项式反演公式,$F_i=\sumi_{j=0}(-1)C(i,j)G_j$,代入$G_i=i^n$.第二类Stirling数要求集合之间互不区分,因此$F_i$ 正好就是$S(n,i)$的$i!$倍.

Catalan数

定义:Catalan数
Catalan数可以表示成从$(0,0)$到$(n,n)$的除端点外不穿越直线$y=x$ 的非降路径数非降路径是指只能向上或向右走的路径.,记为$H_n$.

对于第一步和最后一步,我们知道这两步一定是从$(0,0)$到$(1,0)$和从$(n,n-1)$到$(n,n)$来的.这时所有的非降路径就就是$C(2n-2,n-1)$条,随遇任意一条穿越了$y=x$的路径,我们可以把最后离开这条线的点到$(1,0)$的部分关于$y=x$进行对称变换,就可以得到一条从$(0,1)$到$(n,n-1)$的非降路径,同理反之亦成立.

上面那一部分就是说明:总的有$C(2n-2,n-1)$条路径,其中不符合要求的就是从$(1,0)$到$(n-1,n)$的路径,就是$C(2n-2,n)$.

根据对称性有$2(C(2n-2,n-1)-C(2n-2,n))$,这个时候我们可以求出$$H_n=C(2n,n)-C(2n,n-1)=\dfrac.$$

当然只能在筒内有龙珠的情况下取最上面的一个.
我们借助龙珠的情形来说,第一次进行的操作必然是放龙珠,我们假设这颗龙珠在第$i$次取出时被取走,那么在其被取走之前就是一次$i-1$颗龙珠小型但完整的进出龙珠的过程,而且之后的$n-i$次取出也构成了$n-i$颗龙珠的进出过程.这里的$i$会取遍$1$到$n$,把他们加起来就是所有的情况了.写作:
$$H_n=\sum_^H_iH_.$$

设$C(x)=\sum_^ H_nx^n$,计算
$$(C(x))2=\sum_{n=0}\left(\sum_{n}H_iH_{n-i}xn\right)=\sum_{\infty}H_{n+1}xn.$$

这样我们就可以注意到$(C(x))2$的每项几乎是$C(x)$的对应系数向后移位得到的,那么我们凑角标作差即可发现$x(C(x))2-C(x)=-H_0=-1$.

对此二次方程解得$$C(x)=\dfrac}.$$这里显然要舍去负根,我们就得到了Catalan数的生成函数.

图论

图论是应用数学的一个分支,它将实际问题抽象成``图''这一模型加以研究.

图论在很多领域中都有应用,在外界的式神——计算机涉及到的如数据库、超文本、操作系统、计算机网络等关系型中都有很强的应用.

在学习图论的相关知识之前,先要了解``图''是什么.

定义:图
设$G$是一个有序二元组$(V,E)$.若$E$中元素按照某种规则映射到$V \times V^$上此处$V\times V$的含义是:$V\times V={(v,v)|v\in V}$,称这种集合运算为直积.,则$G$就称为图,并称$V$为顶点集,$E$为边集.其中,$V$中的元素被称为顶点或节点,$E$中的元素被称为边.

直观用琪露诺也能听懂的话来说, 图就是点和线的集合,表示一堆点和一堆连接点的线.

图的种类有很多,一个常用的分类方法是分为有向图和无向图.

定义:有向图和无向图
对于图$G=(V,E)$,如果任意连接两个顶点$D_1,D_2$的边$E$是没有方向的,那么这个图就是无向图.如果任意连接两个顶点$D_1,D_2$的边$E$是有方向的,那么这个图就是有向图.

图模型的建模需要说明点集和边集的意义以及图的类型.

例
如果将幻想乡内朋友关系表示成一个图模型$G$,顶点集$V$就代表幻想乡内的每一个人,边集$E$代表的含义如下:

若$(D_1,D_2) \in E$,代表$D_1$和$D_2$是朋友关系.

成为朋友肯定是双向的,那么这个图模型就是无向的,所以若$(D_1,D_2) \in E$,则$(D_2,D_1) \in E$.

例如作者是杂食党,cp关系仅供参考.:$(\text,\text) \in E$,则有$(\text,\text) \in E$.

在计算机科学领域,我们研究得比较多的是最简单的简单无向图.

定义:简单无向图
称连接顶点自身的边为自环,称连接同一对顶点的多条边为平行边.

没有自环和平行边的无向图称为简单无向图.

例中的描述朋友关系的图就是一个简单无向图的实例,因为两个人之间不存在$2$个及以上的朋友关系.

度是图中很重要的一个概念,讨论度可以解决最短通路问题和握手问题.

定义:度
图中与某顶点$D$相连的边数称为该点的度,记为$\deg(D)$.

下面介绍一些特殊的图.

二部图(也称二分图或偶图)是一种特殊的图,在之后的二部图博弈论中还会用到它.因此这里简要介绍一下二部图和匹配的概念.

定义:二部图
若一个简单图$G=(V,E)$的节点集$V$可以分成两个子集$V_1,V_2$,它们满足$V=V_1\cup V_2$,$V_1\cap V_2=\varnothing$,且边集$E$中的任意一条边连接的两个节点都来自于不同的两节点子集$V_1,V_2$,则称图$G$为二部图.

直观来说,二部图里面的每一个顶点都可以用给定两个颜色中的一个进行上色,并且每条边的连接的顶点颜色不同.

定义:完全二部图
设二部图$G=(V,E)$的节点集$V$可分为两个子集$V_1,V_2$,且对任意$D_1\in V_1,D_2\in V_2$,都有$(D_1,D_2) \in E$,则称$G$为完全二部图,记为$K_$.

定义:匹配
设$M$是图$G=(V,E)$中边集$E$的子集,且满足任取$M$中两边都没有公共顶点,则称$M$是一个匹配.

换句话说,若$(D_s,D_t)$和$(D_u,D_v)$是匹配$M$中的两条边,则$s,t,u,v$是不同的顶点.

称边数最多的匹配为最大匹配,记为$M_$.

定义:完全匹配
设二部图$G=(V,E)$,$V = V_1 \cup V_2$.如果一个匹配$M$由$|V_1|$指顶点集$V_1$中元素的个数.后边出现的类似的符号都有相似的含义,即表示符号$||$内事物的数量.$|V_1|$条从$V_1$引向$V_2$的边组成,则称$M$是$V_1$对$V_2$的完全匹配.
这些边在$V_2$中对于不同的节点,也不关联$V_1$的相同结点.

在限制了$V_1$和$V_2$的内容的情况下,一个完全匹配是边的个数最大的匹配.

定义:点独立集
对于一个图$G=(V,E)$,一个点集$S\subseteq V$被称为点独立集当且仅当$S$中没有任意两个点相邻,即$\forall x,y \in S,(x,y)\notin E$,称点集$S$为点独立集.

定义:点覆盖集
对于一个图$G=(V,E)$,一个点集$S\subseteq V$被称为点覆盖集当且仅当对于图中的任意一条边,这
条边所连接的两个点至少有一个属于$S$,即$\forall(x,y)\in E$, $x\in S$或$y \in S$,称点集$S$为点覆盖集.

点覆盖和点独立集里面点的个数最大或者最小有特殊的含义.

定义:极小点覆盖, 最小点覆盖
若点覆盖$S$的任何真子集都不是点覆盖,则称$S$是极小点覆盖.顶点个数最少的点覆盖称为最小点覆盖.

定义
(极大点独立集·最大点独立集)
若在点独立集$S$中加入任何顶点都不再是独立集,则称$S$为极大点独立集.顶点数最多的点独立集称为最大点独立集.

这里的极大与最大的差异同上.

定理
设无向图$G(V, E)$中无孤立顶点,顶点集合 $S\subseteq V$,则 $S$是$G$的点覆盖,当且仅当$V-S$是$G$的点独立集.

设$G$是$n$阶($n$个顶点)无孤立点的图,则$S$是$G$的极小(最小)点覆盖集,当且仅当$V–S$是$G$的极大(最大)点独立集,从而有:$\alpha_0+\beta_0 = n$ ($n$为顶点个数).

其中$\alpha_0$是极小点覆盖集的顶点数,$\beta_0$是极大点独立级的顶点数.

设最小点覆盖集为$V$,假如有两个没在$V$中的点之间有一条边,那么这条边就不会被$V$中的点所覆盖,那么$V$就不是最小点覆盖集,又因为$V$是最小点覆盖集,所以刚才假设的两个点时不存在的,除过$V$之外的点都是两两相互独立的.

定义
(边独立集)
一个无向图$G(V,E)$,一个边集$S\subseteq E$被称为边独立集当且仅当$S$中任意两个
边不可能与同一节点相邻,即$\forall x,y,z \in V$,$(x,y)(y,z)\notin S$,称边集$S$为边独立集(匹配).

定义
(边覆盖集)
一个无向图$G(V,E)$,一个边集$S \subseteq E$被称为边覆盖集当且仅当任意取$V$中任何一个节点,都能找到$S$中的一条边,这个节点通过这条边与其他节点连接.即$\forall x \in V$,$\exists y \in V$,$(x,y)\in S$,称边集$S$为边覆盖集.

类似的,我们可以定义极小边覆盖、最小边覆盖、极大匹配、极小匹配:

最后介绍几个有趣的定理,证明从略.

定理
最大点独立集与最小顶点覆盖的和等于图的点数.

定理
在二分图中,最大匹配等于最小顶点覆盖.

1.5
比如最大匹配是$M$.为了求最少的点让每条边都至少和期中一个点关联.

(1) $M$个点是必需的.匹配的$M$条边,由于他们两两无公共点,就是说至少有$M$个点才能把他们覆盖.

最小点集覆盖一定$\geqslant$最大匹配,因为假设最大匹配为$n$,那么我们就得到了$n$条互不相邻的边,光覆盖这些边就要用到$n$个点.

(2) $M$个点是足够的.就是说他们覆盖最大匹配的那$M$条边后,假设有某边$e$没被覆盖,那么把$e$加入后会得到一个更大的匹配,出现矛盾.

任何一种$n$个点的最小点集覆盖,一定可以转化成一个$n$的最大匹配.因为最小点集覆盖中的每点都能找到一条边,这条边只有这个点在点集中.(在点集中就代表被覆盖)

如果找不到则说明该点链接所有的边的另外一个端点都被覆盖,所以该点则没必要被覆盖,和它在最小点集覆盖中相矛盾.

只要每个端点都选择一个这样的边,就必然能转化为一个匹配数与点集覆盖的点数相等的匹配方案.所以最大匹配至少为最小点集覆盖数,即最小点集覆盖一定$\leqslant$最大匹配.

定理
Hungary算法可以在$O(|V||E|)$求出一组二分图的最大匹配.$^$

$O(\cdot)$的含义可见$\S 0.1$的注脚.

匈牙利算法的本质就是找到增广路$^$若$P$是图$G$中一条连通两个未匹配顶点的路径,并且属于即已匹配和待匹配的边在$P$上交替出现,则称$P$为相对于$M$的一条增广路径.,有增广路径的存在就可以扩充匹配的个数,找到最大匹配.
我们从左侧一个点$A$出发,枚举所有和他有边连接的点$B$并试图与之进行匹配,即如果这个点$B$失败便再对下一个$C$尝试.如果$B$没有和任何左侧点匹配自然最好,如果没有$B$和左侧某个点$C$已经匹配了,那么我们连接线$AB$,拆掉$BC$匹配,重新试图给$C$找一个点和它匹配.

这样的处理方式是递归式的,为了让这个过程能够停止,我们不允许处理过程重复寻找点的匹配,比如找$A$,为此去找$C$,又为此去找$A$的匹配.这样一来,我们最多递归$n$次这样的寻找,有了停止步数的上界.

这样一条$A\cdots B-C\cdots D-E$的路径,我们也称之为增广路.

这样的方法虽然思想简单粗暴,但却行之有效.(补充一个证明这样能得到最大匹配的证明)

我们再计算这个算法的速度.之前已经提到每次寻找增广路,我们会进行$n$层递归,而每一层递归当中我们最多会对另一侧所有的点尝试一遍,总共$n$次.而我们又只会从每一个点开始一次,寻找增广路.所以最后我们最多运行$n$三次方次的搜索语句,这个算法是$O(N^3)$的.

定义
(完美匹配)
一个无向图$G(V,E)$,一个边独立集$S$是完美匹配当且仅当所有节点都与中的边相邻,即$2|S|=|V|$.

第四册有练习题,大家没事的时候可以做一下,一共15道题。