COMP5270 Week 0 总结：课程预备知识（算法、离散数学与概率基础）

Posted on 2026-05-26 In Course Notes , COMP5270 Word count in article: 1.9k Reading time ≈ 7 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 0 — What to know before we start

这篇是课程正式开始前的预备知识回顾，涵盖三大块：经典算法、离散数学常用结论、以及概率论基础。如果有些内容感觉陌生，建议在上课前补一补。

1. 算法预备知识

这门课默认你已经熟悉经典算法。如果有需要，推荐两个资源：

Tim Roughgarden 的 Algorithms Illuminated 系列（有视频和编程作业）
Jeff Erickson 的 Algorithms（免费 textbook，覆盖面很广）

Big-O 记号

确保你熟悉渐近记号：

这些用来描述算法复杂度：上界、下界、紧确界。Tim Roughgarden 书的第一卷第二章有完整讲解。

两个具体算法

主题	要求	参考位置
Median in Linear Time	能在时间求中位数	Erickson Ch.1.8 / Roughgarden Vol.1 Ch.6
Max-Flow and Min-Cut	熟悉 Max Flow 和 Min Cut 算法	Erickson Ch.10–11

Median in Linear Time 用到了 median-of-medians 的分治策略，也是练习解递推式（以及 Master Theorem）的好机会。

2. 离散数学：需要记住的结论

以下结论不需要全会证明，但要熟悉并能使用。

阶乘与 Stirling 近似

阶乘的增长速度：

$等价地$

更精确的 Stirling 近似：

其中表示“随趋于 0 的项”。

由 Stirling 可以推出组合数的渐近行为：

调和数

第个调和数：

也就是说，调和数以对数速度增长。

常用级数

平方倒数级数（收敛）：

根号倒数级数（发散，但可估阶）：

几何级数：

对：

当时无穷级数收敛：

还有一个进阶结论（求导可得）：

建议自己试着推一遍这个式子，很有价值。

AM-GM 不等式

对任意：

特别地，二元情形：

3. 概率论基础

记号约定

记号	含义
	概率
	期望
	方差
	随机变量服从分布
	至少为 5 的概率
	额外指定的分布为

概率分布的公理化定义

离散情形：概率分布可以看作定义在子集上的非负函数，满足：

，（空集概率为 0，全集概率为 1）
对任意可数、两两不交的事件：

这就是概率的可数可加性。特别地，若不交：

对任意（不一定不交）事件：

连续情形：类似，只是把求和换成积分。

随机变量

随机变量由其概率分布 刻画。对任意事件：

离散型（取有限或可数无限个值）：由概率质量函数（pmf）完全描述：

于是。

连续型：用累积分布函数（cdf）描述：

如果两个随机变量的 cdf 相同，它们的分布就相同。

指示随机变量（Indicator Random Variable）

对事件，定义：

$若发生若不发生$

例子：设在上均匀分布，则

$为偶数或或$

指示变量本质上就是参数为的 Bernoulli 随机变量，后面会详细讲。

独立性

两个随机变量独立：

等价表述：对任意函数：

特别地：。

多个随机变量相互独立：

等价地：

Bayes 规则与条件概率

对两个事件（且）：

例子：在上均匀分布，求“ 是质数，已知是偶数”：

（因为 2 是唯一的偶质数。）

条件期望

对事件的条件期望（离散情形）：

更一般地，可以定义关于随机变量的条件期望 ：它表示“知道了之后，对求平均”。有两个非常重要的性质：

性质 1：全期望公式（Law of Total Expectation）

直观：分步求期望和一步到位结果一样。

性质 2：独立性

若独立，则知道对的期望没有影响：

性质 3：确定性函数

若（完全由决定），则条件期望“不再平均”：

例子： - - 若独立：

条件期望在行为上很像普通期望，只是末尾多了“”。

4. 常用概率分布

Geometric 分布

取值于，pmf：

表示：每次试验成功概率为，第一次成功发生在第次试验的概率。

期望：
方差：

Poisson 分布

取值于，pmf：

期望：
方差：

Bernoulli 分布

取值于，pmf：

期望：
方差：

Bernoulli 就是的 Binomial，也是指示随机变量的分布。

Binomial 分布

取值于，pmf：

表示：次独立 Bernoulli 试验中，成功次的概率。

期望：
方差：

5. 总结检查清单

知识点	是否熟悉	备注
Big-O / /	☐	渐近分析基础
Median in Linear Time	☐	median-of-medians
Max-Flow / Min-Cut	☐	图算法
Stirling 近似	☐	的渐近
调和数	☐
几何级数求和	☐
AM-GM 不等式	☐	均值不等式
概率公理	☐	可加性、规范性
指示随机变量	☐
独立性	☐
Bayes 规则	☐	条件概率
全期望公式	☐
Geometric / Poisson / Bernoulli / Binomial	☐	期望和方差

这篇里的内容如果有些不太熟，没关系——课程中遇到时会再解释。但如果大面积感觉陌生，建议提前复习一下，这样上课会更顺畅！