Posts

Problem 1 假设有 $ m $ 个俱乐部和 $ n $ 个人，满足以下条件： (i) 每个俱乐部的人数为偶数； (ii) 任意两个俱乐部之间共同拥有的人数为奇数。 证明：$ m \le n $。 证： 我们在有限域 $ \mathbb{F}_{2} $ 上考虑。设 $ v_{1},\dots,v_{m}\in \mathbb{F}_{2}^{n} $ 为每个俱乐部对应向量。根据条件，我们知道 人数为偶数：$ v_{i}\cdot v_{i}=0 $ 交集为奇数：$ v_{i}\cdot v_{j}=1(i\neq j) $ 考察这 $ m $ 个向量的线性相关性。假设存在系数 $ c_{1},\dots c_{m}\in \mathbb{F}_{2} $ 使得 $$ \sum_{i=1}^{m} c_{i}v_{i}=\mathbf{0} $$ 那么对于任意 $ j\in [m] $，我们将上式与 $ v_{j} $ 做内积 $$ \left( \sum_{i=1}^{m} c_{i}v_{i} \right)\cdot v_{j} = c_{j}(v_{j}\cdot v_{j}) + \sum_{i\neq j}c_{i}(v_{i}\cdot v_{j}) = 0 $$ 带入得到 $$ \sum_{i\neq j}c_{i}=0 $$ 由于对于每个 $ j $ 这个条件都要成立，从而 $ c_{j}=\sum_{i\in[m]}c_{i} $，这意味着所有的 $ c_{i} $ 都相等，因此要么全为 $ 0 $，要么全为 $ 1 $。若全为 $ 0 $，则线性无关；若全为 $ 1 $，显然与 $ \sum_{i\neq j}c_{i}=0 $ 矛盾。 ...

Problem 1 给定平面上 $ 2n $ 个点，任意将 $ n $ 个点染成红色，剩下 $ n $ 个点染成蓝色。证明存在一种红蓝点的 $ 1 $-$ 1 $ 配对，使得连接它们的 $ n $ 条线段相互不相交。 证 定义红点集 $ R=\{ r_{1},r_{2},\dots,r_{n} \} $，蓝点集 $ B=\{ b_{1},b_{2},\dots,b_{n} \} $。$ R\to B $ 的映射，对应一种配对方案，总数为 $ n! $。 对于任意一种配对方案 $ \sigma $，我们定义它的总长度 $ L(\sigma) $ 为该方案中所有线段的长度之和 $$ L(\sigma) = \sum_{(r,b)\in\sigma}\text{dist}(r,b) $$ 由于总方案数有限，因此一定存在一种方案 $ \sigma_{m} $ 使得总长度 $ L(\sigma_{m}) $ 最小。我们下面证明这个最小方案中没有相交的线段。 假设在 $ \sigma_{m} $ 中存在两条线段相交，设为 $ (r_{1},b_{1}) $ 和 $ (r_{2},b_{2}) $，相交于点 $ P $。那么我们考虑交换配对变为 $ (r_{1},b_{2}) $ 和 $ (r_{2},b_{1}) $。根据三角不等式，有 $ \left| r_{1}b_{2} \right|<\left| r_{1}X \right|+\left| Xb_{2} \right|,\left| r_{2}b_{1} \right|<\left| r_{2}X \right|+\left| Xb_{1} \right| $，从而 $$ \left| r_{1}b_{2} \right| +\left| r_{2}b_{1} \right| < \left| r_{1}X \right| +\left| Xb_{1} \right| +\left| r_{2}X \right| +\left| Xb_{2} \right| = \left| r_{1}b_{1} \right| +\left| r_{2}b_{2} \right| $$ 发现交换后得到了一个总长度更小的方案，从而与总长度最小矛盾。这样我们就证明了总长度最小的配对方案所有线段必然不相交，证毕。 ...

Problem 1 设 $ n>rst $。证明 $ n $ 个数的实数列一定至少含有长度为 $ r $ 的严格上升子序列、长度为 $ s $ 的严格下降子序列、长度为 $ t $ 的常数列中的一个。 证 反证法，假设结论不成立。 我们为第 $ i $ 个元素 $ x_{i} $ 记下标签 $ (a_{i},b_{i}) $，其中 $ a_{i} $ 表示以 $ x_{i} $ 结尾的最长上升子序列长度，$ b_{i} $ 表示以 $ x_{i} $ 结尾的最长下降子序列长度。那么我们有 $ a_{i}\in[r-1],b_{i}\in[s-1] $。因此总共只有 $ (r-1)(s-1) $ 种标签，此时又有 $ n>t\cdot(r-1)(s-1) $，所以至少有 $ t $ 个元素的标签完全相同。 我们假设 $ a_{i}=a_{j},b_{i}=b_{j} $，可以证明 $ x_{i}=x_{j} $。如果不相等，不妨设 $ i< j $。若 $ x_{i}< x_{j} $，那么我们将 $ x_{j} $ 加到以 $ x_{i} $ 结尾的最长上升子序列之后，就得到了一个长度为 $ a_{i}+1 $ 的上升子序列，所以 $ a_{j}\geq a_{i}+1 $，与 $ a_{i}=a_{j} $ 矛盾；若 $ x_{i}>x_{j} $，同理可以得到 $ b_{j}\geq b_{i}+1 $，与 $ b_{i}=b_{j} $ 矛盾。所以一定有 $ x_{i}=x_{j} $。 ...

Problem 1 在一个 $ m $ 条边的二分图中，存在一个匹配，其大小至少为 $ m / \Delta $，其中 $ \Delta $ 表示图中最大顶点的度数。 证 我们需要证明这个二分图最大匹配的大小大于等于 $ m / \Delta $。根据柯尼希定理，只需要证明最小边覆盖的大小大于等于 $ m / \Delta $。 设最小边覆盖大小为 $ t $。若 $ t< m / \Delta $，对于一个被选中的顶点 $ v $，其至多覆盖 $ \text{deg}(v)\leq\Delta $ 条边，因此最多只能覆盖 $$ t\cdot\Delta < m $$ 显然不能覆盖所有的边，不可能是一个边覆盖，矛盾。 因此至少存在一个匹配的大小至少为 $ m / \Delta $。 Problem 2 证明一名学生有 $ 20 $ 周的时间来准备 ICPC，他决定每周至少完成一次训练比赛，但他只有 $ 30 $ 套训练题。请证明，无论他如何安排训练，都会存在连续的几周，他完成的训练题集数正好是 $ 9 $ 套。 ...

Problem 1 (1) 证明： $$ \chi(G) + \chi(\overline{G}) \leq v(G) + 1 $$ 证 归纳证明。对于大小为 $ 1 $ 的图，结论显然成立，此时 $ \chi(G)=\chi(\overline{G})=1 $。 假设对于大小为 $ n-1 $ 的图这个结论都成立，那么对于一个大小为 $ n $ 的图 $ G $，我们考虑加入一个点 $ v $。此时我们有 $$ \chi(G-v)+\chi(\overline{G}-v) \leq n $$ 我们现在证明 $ \chi(G) $ 和 $ \chi(\overline{G}) $ 中至多只有一个可能会增加 $ 1 $。设 $ G $ 中 $ v $ 的度数为 $ d(v) $，在 $ \overline{G} $ 中为 $ \overline{d}(v)=n-1-d(v) $。 ...

Problem 1 证明存在常数 $ c > 1 $ 和 $ N > 0 $，使得当 $ n > N $ 时， $ [n] $ 上树的同构类数量至少为 $ c^n $ 。 证 我们需要的同构类的数量则可以看成 $ n $ 个点无标号的树的数量。需要证明这个数量增长的足够快。 首先根据 Cayley 公式，$ n $ 个点的有标号的树的数量为 $ n^{n-2} $。显然所有无标号的树的数量大于 $ \dfrac{n^{n-2}}{n!} $，因为这里直接假设所有点都是对称的，但是实际上一棵有标号的树并不会对应 $ n! $ 颗无标号的树。我们直接取 $ c=2 $，于是就只需要证明存在 $ N>0 $ 满足在 $ n>N $ 时有 $$ \dfrac{n^{n-2}}{n!} > 2^{n} $$ 我们使用斯特林公式，在 $ n $ 足够大时有 $$ n! \approx \sqrt{ 2\pi n }\left( \dfrac{n}{e} \right)^{n} $$ 带入下界，得到 $$ \dfrac{n^{n-2}}{n!} \approx \dfrac{e^{n}}{\sqrt{ 2\pi}\cdot n^{5 / 2}} $$ 所以只需要证明在 $ n>N $ 时有 $$ (\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n} < \dfrac{e}{2} $$ 对于左式，显然有 $$ \lim_{ n \to \infty } [(\sqrt{ 2\pi })^{1 / n} \cdot n^{5 / 2n}] = 1 < \dfrac{e}{2} $$ 根据极限的定义，我们总能找到一个 $ N $ 满足条件。因此得证！ ...

Problem 1 证明 $$ \begin{align*} \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } \\ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! \end{align*} $$ 证 1 对于第一个式子，我们考虑组合意义。设有 $ A,B $ 两个集合，分别包含 $ n $ 和 $ m $ 个元素，总共 $ n+m $ 个元素。我们希望从集合 $ B $ 中恰好选择 $ k $ 个元素。我们可以通过容斥原理的补集形式求解，定义事件 $ A_{i} $ 为所选的 $ k $ 个元素中至少包含 $ i $ 个来自 $ A $ 的元素，那么我们需要求解的事件集合为 $ U\setminus\bigcup_{i\leq n}A_{i} $，并且 $$ \left| A_{i} \right| = \binom{ n }{ i } \binom{ n+m-i }{ k-i } $$ 因此根据容斥原理，就可以得到 $$ \left| U\setminus \bigcup_{i\leq n}A_{i} \right| = \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } $$ ...

Principle of Inclusion and Exclusion 对于任意有限集合 $ A_1, A_2, \dots, A_n $，容斥原理如下： $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} \left| A_i \right| - \sum_{1\leq i< j\leq n} \left| A_i \cap A_j \right| + \dots + (-1)^{n} \left| \bigcap_{i=1}^{n} A_i \right| $$ 可更紧凑地表示为 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{S \subseteq [n], |S|=k} \left| \bigcap_{i \in S} A_i \right| $$ 或 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right| $$ ...

Problem 1 用生成函数求解递推式 $$ a_{n} = 4a_{n-1} - 5a_{n-2} + 2a_{n-3} $$ 初始值为 $ a_{0}=0,a_{1}=3,a_{2}=7 $。 解： 设数列 $ \{ a_{n} \} $ 的生成函数为 $ F(x) $，那么根据递推式和初值 $ a_{0}=0,a_{1}=3,a_{2}=7 $ 得到 $$ F(x) = 4xF(x) - 5x^{2}F(x) + 2x^{3}F(x) + 3x - 5x^{2} $$ 得到 $$ F(x) = \dfrac{5x^{2}-3x}{2x^{3}-5x^{2}+4x-1} = \dfrac{3x-5x^{2}}{(1-x)^{2}(1-2x)} $$ 我们希望分解成 $$ \dfrac{A}{1-x} + \dfrac{B}{(1-x)^{2}} + \dfrac{C}{1-2x} $$ 待定系数可以解得 $$ F(x) = \dfrac{-3}{1-x} + \dfrac{2}{(1-x)^{2}} + \dfrac{1}{1-2x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} (-3+2(n+1)+2^{n})x^{n} $$ 因此 $$ a_{n} = -3+2(n+1)+2^{n} = 2^{n} + 2n - 1 $$ ...

考虑上一节引入的二项式定理 $$ (1+x)^{n} = \sum_{k=0}^{n} \binom{ n }{ k } x^{k} $$ 这可以理解成我们把二项系数转换成了一个函数，这使得我们能更有效地操作和分析序列，这个工具被成为生成函数。 Ordinary Generating Functions 给定序列 $ \{ a_{n} \}_{n\geq 0} $，由 $ \{ a_{n} \} $ 定义的普通生成函数 (OGF) 为： $$ G(x) = \sum_{n\geq 0} a_{n}x^{n} $$ 虽然看起来 OGF 并没有被很好的定义，对于和某些数列，这个形式不会收敛，但是实际上生成函数并不能被看成一个真正的函数，它是一个形式幂级数，并且不被要求收敛。 以下是一些生成函数的基础例子： $$ G(x) = 1+x+x^{2}+x^{3} +\dots = \dfrac{1}{1-x} $$ $$ G(x) = 1+ax+a^{2}x^{2} + a^{3}x^{3} + \dots = \dfrac{1}{1-ax} $$ 给定一个序列，写出他的生成函数是很容易的。尽管找到他的闭合形式不容易，但是我们一般不需要这样做。相反，我们需要考虑给定一个闭合形式，需要如何知道其对应的序列。 我们约定 $ [x^{n}]G(x) $ 表示生成函数中 $ x^{n} $ 的系数。 ...

Problem 1 (1) 求 $$ \sum_{k=0}^{n} \binom{ 2n }{ 2k } $$ 解 $$ \begin{align*} & \sum_{k=0}^{n} (-1)^{k}\binom{ n }{ k } = 0 \\ \implies & \sum_{k=0}^{2n} (-1)^{k}\binom{ 2n }{ k } =0 \\ \implies & \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } \end{align*} $$ 同时由于 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } + \sum_{k=1}^{2n} \binom{ 2n }{ 2k - 1 } = \sum_{k=0}^{2n} \binom{ 2n }{ k } = 2^{2n} $$ 得到 $$ \sum_{k=0}^{2n} \binom{ 2n }{ 2k } = 2^{2n-1} $$ ...

Product and Sum Principles 加法原理（分类计数） 若一个任务可分解为若干个互斥的子类，第 $ i $ 类有 $ a_i $ 种方案，则总数为 $ \sum_i a_i $。 解释：互斥保证不重不漏，求和即“或”的计数。 乘法原理（分步计数） 若一个任务分为若干个有序步骤，步骤 $ i $ 有 $ b_i $ 种选择且相互独立，则总数为 $ \prod_i b_i $。 解释：有序步骤逐个做决定，“且”的计数对应乘法。 Constructing Maps 有些组合证明可以依赖于构造映射： 单射：不同原像映到不同像，用于证明下界或“可嵌入性”。 满射：像覆盖全体，用于证明上界可达或构造覆盖。 双射：建立集合 $ A $ 与 $ B $ 的一一对应，从而数 $ |A|=|B| $；这是“数某一个量 ⇒ 构造双射”的核心思想。 Twelvefoldway 将 $ n $ 个球放入 $ m $ 个盒子，球与盒子可“可区分/不可区分”，以及盒子容量约束“任意/至多 1/至少 1”。 $ n $ $ m $ 任意 $ \leq 1 $ $ \geq 1 $ 不同 不同 $ m^{n} $ $ m^{\underline{n}} $ $ m!\left\{ {n \atop m} \right\} $ 同 不同 $ \binom{ n+m-1 }{ m-1 } $ $ \binom{ m }{ n } $ $ \binom{ n-1 }{ m-1 } $ 不同 同 $ \sum_{k=0}^{\min(n,m)} \left\{ {n \atop k} \right\} $ $ [n \leq m] $ $ \left\{ {n \atop m} \right\} $ 同 同 $ p_{\leq m}(n) $ $ [n \leq m] $ $ p(n,m) $ “把 $ n $ 个不同球分成 $ k $ 个非空无序盒”对应第二类斯特林数 $ \left\{ {n \atop k} \right\} $。 ...

Problem 1 (1) 根据泊松分布的定义，我们有 $$ \mathbb{P}[X=\lambda+k] = \dfrac{e^{ -\lambda }\lambda^{\lambda+k}}{(\lambda+k)!},\quad \mathbb{P}[X=\lambda-k-1] = \dfrac{e^{ -\lambda }\lambda^{\lambda-k-1}}{(\lambda-k-1)!} $$ 我们计算两者的比值，有 $$ \dfrac{\mathbb{P}[X=\lambda+k]}{\mathbb{P}[X=\lambda-k-1]} = \dfrac{\lambda^{2k+1}\cdot(\lambda-k-1)!}{(\lambda+k)!} = \dfrac{\lambda^{2k+1}}{(\lambda+k)(\lambda+k-1)\dots(\lambda-k)} $$ 将分母的乘积左右两两配对，得到 $$ (\lambda+k)\dots(\lambda-k) = \lambda \cdot \prod_{i=1}^{k} (\lambda^{2}-k^{2}) > \lambda \cdot \prod_{i=1}^{k} \lambda^{2} = \lambda^{2k+1} $$ 从而就有 $$ \dfrac{\mathbb{P}[X=\lambda+1]}{\mathbb{P}[X=\lambda-k-1]} \geq 1 \implies \mathbb{P}[X=\lambda+1]\geq \mathbb{P}[X=\lambda-k-1] $$ 接着证明 $ \mathbb{P}[X\geq\lambda]\geq \frac{1}{2} $，将事件展开并拆分可以得到 $$ \begin{align*} \mathbb{P}[X\geq \lambda] & =\sum_{k=0}^{\infty} \mathbb{P}[X=\lambda+k] \\ & = \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] + \mathbb{P}[X\geq 2\lambda] \\ & \geq \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] \end{align*} $$ 我们再考虑 $ \mathbb{P}[X< \lambda] $，也就是 $$ \begin{align*} \mathbb{P}[X< \lambda] & = \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda-k-1] \\ & \leq \sum_{k=0}^{\lambda-1} \mathbb{P}[X=\lambda+k] \end{align*} $$ 又因为 $ \mathbb{P}[X\geq\lambda]+\mathbb{P}[X< \lambda]=1 $，这样就得到了 $$ 1-\mathbb{P}[X\geq \lambda] \leq \mathbb{P}[X\geq \lambda] \implies \mathbb{P}[X\geq \lambda] = \dfrac{1}{2} $$ (2) ...

Problem 1 (1) 根据题设条件，我们知道最多抽取 $ m $ 个黑球，最少抽取 $ 0 $ 个黑球。设随机变量 $ X $ 表示抽到黑球的个数，根据组合意义，我们得到 $ X $ 的概率质量函数为 $$ \mathbb{P}(X=x) = \dfrac{\binom{ m }{ x } \binom{ n-m }{ k-x } }{\binom{ n }{ k } },\quad x = 0,1,\dots,m $$ (2) 矩生成函数定义为 $ M_{X}(\theta) = \mathbb{E}[e^{ \theta X }] $。我们带入得到 $$ \begin{align*} M_{X}(\theta) & = \sum_{x}e^{ \theta x }\mathbb{P}(X=x) \\ & = \sum_{x=0}^{m} e^{ \theta x } \dfrac{\binom{ m }{ x } \binom{ n-m }{ k-x } }{\binom{ n }{ k } } \\ & = \dfrac{1}{\binom{ n }{ k } }\sum_{x=0}^{m} e^{ \theta x }\binom{ m }{ x } \binom{ n-m }{ k-x } \end{align*} $$ (3) ...

题目 Problem 1 (1) 不正确。 反例 设离散概率空间 $ (\Omega,\mathcal{F},\mathbb{P}) $，其中 $ \Omega=\mathbb{N}^{+} $，$ \mathcal{F} $ 是 $ \Omega $ 的幂集，概率测度定义为 $ \mathbb{P}(\{ k \})=\dfrac{1}{2^{k}} $。我们定义随机变量 $ X_{n}:\Omega\to \mathbb{R} $ 为 $$ X_{n}(k) = \begin{cases} 2^{n} & k = n \\ -2^{n+1} & k = n+1\\ 0 & \text{o.w.} \end{cases} $$ 此时显然每个 $ X_{n} $ 都可积，并且 $$ \mathbb{E}[X_{n}] = X_{n}(n)\mathbb{P}(\{ n \}) + X_{n}(n+1)\mathbb{P}(\{ n+1 \}) = 0 \implies \sum_{n=1}^{\infty} \mathbb{E}[X_{n}] = 0 $$ 但是 $$ \sum_{n=1}^{\infty} X_{n}(k) = \begin{cases} 2 & k=1 \\ 0 & \text{o.w.} \end{cases} $$ 从而 $$ \mathbb{E}\left[ \sum_{n=1}^{\infty} X_{n} \right] = 2 \times \mathbb{P}(\{ 1 \}) + 0 \times (1 - \mathbb{P}(\{ 1 \})) = 1 $$ 所以此时 $$ \sum_{n=1}^{\infty} \mathbb{E}[X_{n}] \neq \mathbb{E}\left[ \sum_{n=1}^{\infty} X_{n} \right] $$ 不成立的原因在于我们需要级数绝对可积才能交换求和和期望。 ...

题目 Problem 1.1 (1) 证：若 $ \sigma $-代数包含所有 $ (a,b) $，则包含 $ [a,b] $。 $$ [a,b] = \bigcap_{n=1}^{\infty} \left(a-\frac{1}{n}, b+\frac{1}{n}\right) $$ 由 $ \sigma $-代数对可数交封闭，故 $ [a,b] $ 在其中。 证：若 $ \sigma $-代数包含所有 $ [a,b] $，则包含 $ (a,b) $。 $$ （a,b) = \bigcup_{n=1}^{\infty} \left[a+\frac{1}{n}, b-\frac{1}{n}\right] $$ 由 $ \sigma $-代数对可数并封闭，故 $ (a,b) $ 在其中。 (2) 证：若 σ-代数包含所有 $ (a,b) $，则包含 $ [x,\infty) $。 $$ [x,\infty) = \bigcap_{n=1}^{\infty} \left(x-\frac{1}{n}, \infty\right) = \bigcap_{n=1}^{\infty} \bigcup_{m=1}^{\infty} \left(x-\frac{1}{n}, m\right) $$ 由 $ \sigma $-代数对可数并、可数交封闭，故 $ [x,\infty) $ 在其中。 ...

题目 Problem 1 (1) 设每次合成仙丹为一次尝试。 在每次尝试中： 合成成功：概率为 $ p $。 产生 $ 1 $ 份仙丹。 消耗 $ 2 $ 份仙果。 合成失败：概率为 $ 1-p $。 产生 $ 0 $ 份仙丹。 消耗 $ 1 $ 份仙果。 我们关注的是平均每份仙果可以得到多少仙丹。这可以理解为仙丹产出的期望值与仙果消耗的期望值之比。 每次尝试中，获得的仙丹数量的期望值 $ \mathbb{E}[\text{仙丹}] $ 为： $$ \mathbb{E}[\text{仙丹}] = 1 \cdot p + 0 \cdot (1-p) = p $$ 每次尝试中，消耗的仙果数量的期望值 $ \mathbb{E}[\text{仙果}] $ 为： $$ \mathbb{E}[\text{仙果}] = 2 \cdot p + 1 \cdot (1-p) = 2p + 1 - p = p + 1 $$ ...

题目 Problem 1.1 设 $ \mathcal{F} $ 是一个有限的 $ \sigma $-代数。定义其中“最小"的元素为其包含于 $ \mathcal{F} $ 中的子集仅为自身和空集，形式化地描述，若 $ A\in \mathcal{F} $ 为“最小”的元素，那么如果 $ B\in \mathcal{F} $ 并且 $ B\subseteq A $，那么一定有 $ B\in \{ \emptyset,A \} $。 可以证明这样的元素存在并且有限：如果不存在，那么我们每次任取一个 $ \mathcal{F} $ 中的元素，都能找到属于它的一个更小的元素，但 $ \mathcal{F} $ 是有限集，所以这样的过程不可能一直重复下去，因此“最小”元素必然存在并且有限。 我们设所有这些不同的“最小”元素为 $ S=\{ A_{1},A_{2},\dots,A_{n} \} $。我们先证明这构成了全空间的一个分划： 首先这些元素肯定两两不相交，否则不满足“最小”的定义。假设 $ A_{i}\cap A_{j}= C\neq\emptyset $，根据“最小”，非空的 $ C $ 是 $ A_{i} $ 的子集，一定有 $ C=A_{i} $，同样也有 $ C=A_{j} $，这就推出了 $ A_{i}=A_{j} $，从而矛盾。 ...

Introduction 条件概率指一个事件在另一个事件发生的条件下发生的概率，用记号 $ \mathbb{P}(A|B) $ 表示，仅在 $ \mathbb{P}(B)>0 $ 时有定义： $$ \mathbb{P}(A|B) = \dfrac{\mathbb{P}(A \cap B)}{P(B)} $$ 可以写成 $$ \mathbb{P}(A \cap B) = \mathbb{P}(B)\cdot \mathbb{P}(A|B) $$ 对于 $ n $ 个事件，连续使用上式，即可得到 $$ \mathbb{P}\left( \bigcap_{i=1}^{n}A_{i} \right) = \prod_{k=1}^{n} \mathbb{P}\left( A_{k}\bigg|\bigcap_{i=1}^{k-1}A_{i} \right) $$ 这个式子被称为 链式法则。 Independence 对于事件 $ A,B $，如果 $ \mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B) $，或者等价地 $ \mathbb{P}(A|B)=\mathbb{P}(A) $，那么我们称 $ A $ 和 $ B $ 是独立的。这表明 $ A $ 或 $ B $ 自己是否发生对对方是否发生没有影响。 ...

Motivation 例题：在圆上“随机”选一段弧，问弧长大于圆周的 $ \frac{1}{3} $ 的概率？（Bertrand paradox） 至少三种自然的“均匀化”模型会给出不同答案： 对弧长参数均匀（在 $ [0, 2\pi) $ 上均匀取长度，再随机起点）。 对端点在圆上独立均匀（等价于随机两点确定弧，需指定取较短或较长弧）。 对中心角或几何构造的中间量均匀（如均匀选角度后裁剪）。 核心问题：如何定义“随机”？不同“随机化”方案导致不同答案。 讨论概率问题必须先明确概率空间（样本空间、事件族与概率测度），否则“概率”无从谈起。 Probability Space 一个概率空间由三元组 $ (\Omega, \mathcal{F}, \mathbb{P}) $ 构成： $ \Omega $：样本空间（一次随机试验所有可能结果）。 $ \mathcal{F} \subseteq 2^{\Omega} $：事件族（允许讨论与运算的集合）。 $ \mathbb{P} : \mathcal{F} \to [0,1] $：概率测度（赋予事件概率）。 记号说明： $ \Omega $：样本空间。 $ 2^{\Omega} $：$ \Omega $ 的幂集（所有子集的集合）。 为什么 $ \mathbb{P} $ 要定义在 $ \mathcal{F} $ 上而非直接在 $ \Omega $ 上？ 离散可数时，取 $ \mathcal{F} = 2^{\Omega} $ 可行，且对单点赋值即可确定所有事件的概率。 连续时不同：单点的概率通常为 $ 0 $，但不可数并可有正概率；且 $ 2^{\Omega} $ 中存在不可测集合，无法一致赋值（见下文 Vitali set 与 Axiom of Choice）。因此需选择一个足够大又可控的 $ \sigma $- 代数作为事件族。 Sigma-Algebra 要求 $ \mathcal{F} $ 构成一个 $ \sigma $- 代数（域）： ...

课程讲义 在这门课里，我们会专注于所谓的 科尔莫哥洛夫（Kolmogorov）的公理体系，它使得我们能够使用数学分析的工具来研究概率。 St. Petersburg Paradox 圣彼得堡悖论。假设一个基于抛硬币赌博的游戏，庄家会一直扔硬币直到结果是正面，如果扔了 $ k $ 次，那么就会给玩家 $ 2^{k} $ 元的奖金。现在的问题是你愿意花多少钱来购买一次玩这个游戏的机会。 一个很自然的想法是计算游戏的期望，那么我们很容易发现期望收益是 $$ \sum_{k \geq 1} 2^{k}\cdot 2^{-k} = 1 + 1 + \dots = +\infty $$ 这说明平均每一轮我们的收益是无穷大，然而在现实生活中你真的愿意花大价钱去玩这个游戏吗？或者可以写一个简单的程序模拟一下就会发现，在比如门票定为 $ 100 $ 元，玩几百局，还是会轻易地输掉几万块钱。我们生活中一个常见的直觉是如果重复一个随机过程足够多次，平均收益就会逐渐趋近于期望收益，这在概率论中叫做大数定律（Law of large numbers），但是在现实生活中我们并没有能力重复足够多游戏轮数去达到这个期望值。那么现在的问题就是如果定价用 $ a\cdot n $ 元来购买 $ n $ 次游戏机会，$ a $ 定为多少是合理的？ 用这门课中后续会学习到的数学工具，我们可以得到答案为 $ \log n $ （这个结果也符合我们实际的直觉）。 随机游走 对二维随机游走问题的一个简化的建模是在 $ \mathbb{Z}^{2} $ 的网格上随机游走，从原点 $ (0,0) $ 出发，每次以 $ \dfrac{1}{4} $ 的概率往上下左右四个方向移动。我们现在询问，这个随机游走的路径是否会无数次回到原点？用 $ T $ 来表示第一次回到原点的时间，那么可以证明无数次回到原点等价于 $ \mathbb{P}[T < \infty] = 1 $ ，也就是 $ T $ 以 $ 1 $ 的概率是有限的，当然目前只能从直觉上去理解，这个写法需要在后续的课程中去严格定义。 ...

Exercise 1 根据分块对角矩阵的性质，秩等于对角线上各个子块的秩之和，因此 $$ \text{rank}(AB)+n = \text{rank}\left(\begin{bmatrix} AB & 0 \\ 0 & I \end{bmatrix}\right) $$ 接着由于初等列变换不改变矩阵的秩，将第二列右乘 $ B $ 加到第一列得到 $$ \text{rank}\left(\begin{bmatrix} AB & 0 \\ 0 & I \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} AB & 0 \\ B & I \end{bmatrix}\right) $$ 同样由于初等行变换也不改变矩阵的秩，将第二行左乘 $ A $ 再和第一行相减，得到 $$ \text{rank}\left(\begin{bmatrix} AB & 0 \\ B & I \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} 0 & -A \\ B & I \end{bmatrix}\right) $$ 交换上下两行，得到 $$ \text{rank}\left(\begin{bmatrix} 0 & -A \\ B & I \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} B & I \\ 0 & -A \end{bmatrix}\right) $$ 第二行乘以 $ -1 $ 就得到了 $$ \text{rank}\left(\begin{bmatrix} B & I \\ 0 & -A \end{bmatrix}\right) = \text{rank}\left(\begin{bmatrix} B & -I \\ 0 & A \end{bmatrix}\right) $$ 再根据上三角分块矩阵的性质，就有 $$ \text{rank}\left(\begin{bmatrix} B & -I \\ 0 & A \end{bmatrix}\right) \geq \text{rank}(A) + \text{rank}(B) $$ ...

Exercise 1 (1) 对于任意标量 $ c $ 和向量 $ x,y\in U $，都有 $$ \begin{align*} TS(cx+y) & = T(S(cx+y)) \\ & = T(cS(x)+S(y)) \\ & = cT(S(x)) + T(S(y)) \\ & = cTS(x) + TS(y) \end{align*} $$ 从而证明了这是一个线性变换。 (2) 设 $ U,V,W $ 的基为 $$ \bar{u} = \{ u_{1},\dots,u_{p} \},\bar{v}=\{ v_{1},\dots,v_{n} \},\bar{w}=\{ w_{1},\dots,w_{m} \} $$ 根据线性变换矩阵的定义，有 $$ S(u_{i}) = \sum_{k=1}^{n} (A_{S})_{k,i}v_{k},\quad T(v_{i})=\sum_{k=1}^{m} (A_{T})_{k,i}w_{k} $$ 计算 $ TS(u_{i}) $ 并观察系数 $$ \begin{align*} TS(u_{j}) & = T(S(u_{j})) \\ & = T\left( \sum_{k=1}^{n} (A_{S})_{k,j}v_{k} \right) \\ & = \sum_{k=1}^{n} (A_{S})_{k,j}T(v_{k}) \\ & = \sum_{k=1}^{n} (A_{S})_{k,j}\left( \sum_{i=1}^{m} (A_{T})_{i,k}w_{i} \right) \\ & = \sum_{i=1}^{m} \left( \sum_{k=1}^{n} (A_{T})_{i,k}(A_{S})_{k,j} \right)w_{i} \\ & = \sum_{i=1}^{m} (A_{T}A_{S})_{i,j}w_{i} \end{align*} $$ 再结合 $ A_{TS} $ 的定义就证明了 $$ A_{TS}=A_{T}A_{S} $$ ...

Exercise 1 设 $ A $ 的特征多项式为 $ P(\lambda) = \det(A-\lambda I) $。由于特征值 $ \lambda_{1},\lambda_{2},\dots,\lambda_{n} $ 是 $ P(\lambda) $ 的根，因此 $$ P(\lambda) = (-1)^{n}(\lambda-\lambda_{1})(\lambda-\lambda_{2})\dots(\lambda-\lambda_{n}) $$ 我们首先证明 $ \prod_{i=1}^{n}\lambda_{i}=\det(A) $。首先直接带入 $$ P(0)=\det(A-0\cdot I)=\det A $$ 又有 $$ P(0) = (-1)^{n}(0-\lambda_{1})(0-\lambda_{2})\dots(0-\lambda_{n})=\prod_{i=1}^{n} \lambda_{i} $$ 这样就得到了 $ \prod_{i=1}^{n}\lambda_{i}=\det(A) $。 接着证明 $ \sum_{i=1}^{n}\lambda_{i}=\mathrm{trace}(A) $。展开 $ P(\lambda) $ 考察 $ \lambda^{n-1} $ 的系数，为 $$ (-1)^{n}\cdot \sum_{i=1}^{n} (-\lambda_{i}) = (-1)^{n+1}\sum_{i=1}^{n} \lambda_{i} $$ 同时对于矩阵 $ M=A-\lambda I $，利用行列式定义，有 $$ \det(A-\lambda I)=\sum_{\sigma \in S_{n}}\text{sgn}(n)\prod_{i=1}^{n} (A-\lambda I)_{i,\sigma(i)} $$ 其中 $ S_{n} $ 表示 $ [n] $ 中所有置换的集合。 ...

Exercise 1 设 $ A $ 是一个 $ n\times n $ 的矩阵，记 $ A $ 的不同特征值为 $ \lambda_{1},\lambda_{2},\dots,\lambda_{k} $，代数重数分别为 $ a_{i} $，几何重数为 $ g_{i}=\text{dim ker}(A-\lambda_{i}I) $。 (⇒) 若 $ A $ 可对角化，则存在可逆矩阵 $ P $ 使得 $ P^{-1}AP=D $ 为对角阵。由于 $$ \begin{align*} \det(A - \lambda I) & = \det(P^{-1}DP-\lambda I) \\ & = \det(P^{-1}(D-\lambda I)P) \\ & = \det(D-\lambda I) \end{align*} $$ 说 $ A $ 和 $ D $ 的特征多项式相同，从而有一样的特征值和代数重数。 ...

Exercise 2 先证充分性。如果 $ G $ 是一个二分图，设两部分的点集分别为 $ L,R $，所有边均满足两端点分别在 $ L,R $ 中。反证法，加入存在奇环，设环中第一和最后一个点分别为 $ v_{1},v_{k} $，那么 $ k $ 为奇数。不妨设 $ v_{1}\in L $，由于一条边必然在 $ L,R $ 两部分之间 ，所以环中的点在 $ L,R $ 交替出现，即 $ v_{2}\in R,v_{3}\in L,\dots $，由于 $ k $ 是奇数，因此 $ v_{k}\in L $。这说明 $ v_{1},v_{k} $ 两个 $ L $ 中的点存在连边，与二分图矛盾。因此二分图中没有奇环。 再证必要性。如果 $ G $ 没有奇环，我们可以将 $ G $ 分成若干个连通块，每个连通块中任取一个点 $ u_{i} $，我们按照一下顺序将所有点分成 $ L,R $ 两组：首先令 $ u_{i}\in L $，将所有与 $ u_{i} $ 最短距离为偶数的点加入 $ L $，其余的点，也就是到 $ u_{i} $ 最短距离为奇数的点加入 $ R $。 ...

Exercise 1 首先计算 $ A $ 的特征值和特征向量。 $$ \det(A-\lambda I) = (-1-\lambda)(-\lambda)-6 = 0 \implies \lambda^{2}+\lambda-6 = 0 $$ 解得 $ \lambda_{1}=2,\lambda_{2}=-3 $。 对于 $ \lambda_{1}=2 $，我们求解 $ (A-2I)x=0 $，特征向量为 $$ x_{1} = k\begin{pmatrix} 1 \\ 1 \end{pmatrix} $$ 对于 $ \lambda_{2}=-3 $，我们求解 $ (A+3I)x=0 $，可以取特征向量为 $$ x_{2} = k\begin{pmatrix} 3 \\ -2 \end{pmatrix} $$ 对于 $ A^{2} $，我们计算得到 $ \mu_{1}=4,\mu_{2}=9 $。对于每个特征值，带入解出 $$ x_{1} = k\begin{pmatrix} 1 \\ 1 \end{pmatrix},x_{2} = k\begin{pmatrix} 3 \\ -2 \end{pmatrix} $$ ...

Exercise 1 证 我们有 $ \det(A^{T})=\det(-A) $，同时又有 $ \det(A^{T})=\det A $ 以及 $ \det(-A)=(-1)^{n}\det A $。 如果 $ n $ 是奇数，那么 $ (-1)^{n}=-1 $，从而得到 $ \det A=-\det A\implies \det A=0 $。如果 $ n $ 是偶数，则无法说明，这个结论必然成立。 Exercise 2 解 我们直接展开计算，就可以得到 $$ \begin{align*} \det & = \begin{vmatrix} b & b^{2} \\ c & c^{2} \end{vmatrix} - a\begin{vmatrix} 1 & b^{2} \\ 1 & c^{2} \end{vmatrix} + a^{2}\begin{vmatrix} 1 & b \\ 1 & c \end{vmatrix} \\ & = (bc^{2}-b^{2}c) - a(c^{2}-b^{2}) + a^{2}(c-b) \\ & = (b-a)(c-a)(c-b) \end{align*} $$ ...

Exercise 1 解 根据题设，平面法向量为 $ \mathbf{n}=(1,1,2) $。我们观察出一组解 $ v_{1}=(1,-1,0) $，再取 $$ v_{2} = \mathbf{n}\times v_{1} = (2,2,-2) $$ 单位化得到 $$ e_{1} = \dfrac{1}{\sqrt{ 2 }}(1,-1,0),\quad e_{2} = \dfrac{1}{\sqrt{ 3 }}(1,1,-1) $$ Exercise 2 (1) 我们取 $ q_{1}=(1,3,4,5,7) $，利用 G-S 正交化，得到 $$ q_{2} = \mathbf{b} - \dfrac{q_{1}\cdot \mathbf{b}}{\| q_{1} \| ^{2}}q_{1} = (-7,3,4,-5,1) $$ 再单位化得到 $$ \mathbf{e}_{1} = \dfrac{1}{10}(1,3,4,5,7),\quad \mathbf{e}_{2} = \dfrac{1}{10}(-7,3,4,-5,1) $$ (2) 实际上只需要求 $ y $ 到平面的投影。根据 $ (1) $ 我们得到的一组标准正交基，我们就有投影为 $$ p = (y\cdot e_{1})e_{1} + (y\cdot e_{2})e_{2} = \dfrac{1}{10}e_{1} - \dfrac{7}{10}e_{2} = \left( \dfrac{1}{2},-\dfrac{9}{50},-\dfrac{6}{25},\dfrac{2}{5},0 \right) $$ ...

Exercise 1 (1) 如果 $ A=B $，那么 $ Ax=Bx $ 对于所有 $ x \in \mathbb{R}^{n\times 1} $ 是显然的。 如果 $ \forall x \in \mathbb{R}^{n\times 1} $，都有 $ Ax=Bx $，那么我们有 $ (A-B)x=0 $。由于 $ x $ 是 $ \mathbb{R}^{n} $ 中的任意一个向量，说明 $ A-B $ 的零空间是 $ \mathbb{R}^{n} $，因此 $ \text{rank}(A-B)=0 $，也就有 $ A-B=0 $，从而 $ A=B $。 (2) $ A(A^{T}A)^{-1}A^{T} $ 和 $ B(B^{T}B)^{-1}B^{T} $ 分别是 $ A $ 和 $ B $ 的投影矩阵，记为 $ P_{A},P_{B} $。 ...

Exercise 1 (1) $$ u\cdot v = v\cdot u = \sum_{i=1}^{m} v_{i}w_{i} $$ (2) $$ (u+v)\cdot w = u\cdot w + v\cdot w = \sum_{i=1}^{m} (v_{i}+u_{i})w_{i} $$ (3) $$ cu\cdot v = c(u\cdot v) = \sum_{i=1}^{m} (c\cdot u_{i}v_{i}) $$ (4) $$ u\cdot u = \sum_{i=1}^{m} u_{i}^{2} \geq 0 $$ 若 $ u\cdot u = 0 $，可以得到 $ u_{i}=0 $，从而 $ u=\mathbf{0} $。 Exercise 2 $$ u\perp v \implies u\cdot v = \sum_{i=1}^{m} u_{i}v_{i} = 0 $$ 从而 $$ \begin{align*} \| u+v \| ^{2} & = \sum_{i=1}^{m} (u_{i}+v_{i})^{2} \\ & = \sum_{i=1}^{m} u_{i}^{2} + \sum_{i=1}^{m} v_{i}^{2} + 2\sum_{i=1}^{m} u_{i}v_{i} \\ & = \sum_{i=1}^{m} u_{i}^{2} + \sum_{i=1}^{m} v_{i}^{2} \\ & = \| u \| ^{2} + \| v \| ^{2} \end{align*} $$ ...

Exercise 1 (1) 若 $ x \in \mathcal{N}(A) $，说明 $ Ax=0 $，从而一定有 $ BAx=0 $，这就得到了 $ x \in \mathcal{N}(BA) $，因此 $$ \mathcal{N}(A) \subseteq \mathcal{N}(BA) $$ (2) 当 $ \text{rank}(B)=n $，设 $ x \in \mathcal{N}(BA) $，此时有 $ BAx=0 $。由于 $ \text{rank}(B)=n $，因此我们可以得到 $ Ax=0 $，从而 $$ x \in \mathcal{N}(A) $$ 于是必然有 $ \mathcal{N}(A)=\mathcal{N}(BA) $。 如果 $ \mathcal{N}(A)=\mathcal{N}(BA) $，并不能推出 $ \text{rank}(B)=n $。我们可以构造出反例 $$ A = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix},\quad B = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} $$ 显然这时 $ A=BA $，结论成立，但是 $ B $ 不满秩。 ...

Exercise 1 先证明行阶梯矩阵中主元列的唯一性。由于初等行变换保持了列向量之间的线性关系，因此如果矩阵 $ A $ 的第 $ j $ 列是前 $ j-1 $ 列的线性组合，初等行变换之后也仍然成立。并且一个列为主元列，当且仅当它不能被前面的列线性表示，所以 $ A_{1} $ 和 $ A_{2} $ 中的主元列位置完全相同。 接着证明简化行阶梯矩阵的唯一性。对于每个主元列 $ j_{k} $，必须化简成单位向量 $ e_{k} $，满足主元为 $ 1 $，其余元素为 $ 0 $，具有唯一性；对于非主元列，可以表示为前面的列的线性组合，所以为 $ 0 $，也具有唯一性。因此简化行阶梯矩阵具有唯一性。 Exercise 2 (1) 我们通过选择 $ W=\text{span}\{ v_{1},v_{2},\dots,v_{n} \} $ 中的一个子集，可以构造出 $ W $ 的一个基。我们依次考虑 $ i=1,2,\dots,n $，如果 $ i=1 $ 或者 $ v_{i} $ 不是前 $ i-1 $ 个向量的线性组合，就选择 $ v_{i} $，这样最终就得到了 $ B=\{ v_{i_{1}},v_{i_{2}},\dots,v_{i_{r}} \} $。 ...

Exercise 1 首先初等行变换保持了行向量之间的线性关系，因此保证了矩阵的行空间不会改变，从而它的行秩自然也不便。同时对于列秩，这等价于左乘一个一个初等矩阵，此时显然 $ Ax=0 $ 与 $ EAx=0 $ 等价，说明两者有相同的零空间，因此列秩也不边。 对于列变换，和行变换完全同理，也可以证明行秩和列秩都不变。 下面证明矩阵 $ A $ 可以通过初等操作化为 $ \begin{pmatrix}I & 0 \\ 0 & 0\end{pmatrix} $。设 $ \mathrm{rank}(A)=r $，那么我们先通过初等行变换将 $ A $ 化成阶梯矩阵的形式，得到 $ \begin{pmatrix}I_{r} & R \\ 0 & 0\end{pmatrix} $。再对这个结果进行初等列变换，可以直接消除掉 $ R $ 部分中的所有非零元素，并且不影响其他部分。最终就可以化简为 $ \begin{pmatrix}I & 0 \\ 0 & 0\end{pmatrix} $。 Exercise 2 我们需要证明通过任意执行步骤的高斯消元得到的行阶梯矩阵，其主元数量是相同的，从而说明矩阵的秩是一个唯一的值，和消元过程无关。 由于高斯消元本质上就是一系列初等矩阵变换操作，根据第一问我们已经证明了这些操作不会改变矩阵的秩，因此最后得到的阶梯矩阵的秩也不变，最终主元数量就是秩的数量必然相同，等于原来的秩。 Exercise 3 若 $ c=0 $，那么显然有 $$ A\cdot \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \mathbf{0} $$ 说明 $ \text{rank}(A)\neq n $，因此 $ A $ 不可逆，矛盾，所以 $ c\neq 0 $。 ...

Exercise 1 Let $ A $ be an $ n \times n $ matrix. Prove the equivalence between: (i) There is a $ B $ with $ AB = I $. (ii) There is a $ C $ with $ CA = I $. Proof: We show both conditions are equivalent to $ \operatorname{rank}(A) = n $. If there exists $ B $ with $ AB = I $, then $ A $ is surjective, so $ \operatorname{rank}(A) = n $. ...

Exercise 1 Let $ S \subseteq V $ be a subset of vectors in a vector space $ V $. A finite subset $ S' \subseteq S $ is maximally linearly independent in $ S $ if $ S' $ is linearly independent, and for any $ v \in S \setminus S' $ the set $ S' \cup \{v\} $ is not linearly independent. Prove that: (i) $ S' $ is maximally linearly independent in $ S $ if and only if $ S' $ (viewed as a sequence of vectors) is a basis for $ \operatorname{span}(S) $. ...

Exercise 1 Give a basis for the vector space $ M_{m\times n}(\mathbb{R}) $ consisting of all $ m \times n $ matrices. A basis consists of the matrices $ E_{ij} $ for $ 1 \leq i \leq m $ and $ 1 \leq j \leq n $, where $ E_{ij} $ has a 1 in the $ (i,j) $-th position and 0 elsewhere. Exercise 2 Give a basis for $ V = \mathbb{R}^+ = \{x \mid x \in \mathbb{R} \text{ with } x > 0\} $ with $ x \oplus x' = x \times x' $ and $ c \otimes x = x^c $. ...

Exercise 1 (Multiplication of block matrices). Consider two block matrices $$ A = \begin{pmatrix} A_{11} & \cdots & A_{1t} \\ \vdots & \ddots & \vdots \\ A_{p1} & \cdots & A_{pt} \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} B_{11} & \cdots & B_{1q} \\ \vdots & \ddots & \vdots \\ B_{t1} & \cdots & B_{tq} \end{pmatrix} $$ Moreover, for every $ i \in [p] $, $ j \in [t] $, and $ l \in [q] $ the number of columns of $ A_{ij} $ is equal to the number of rows of $ B_{jl} $. In particular, $ A_{ij} \cdot B_{jl} $ is defined. Prove that $$ A \cdot B = \begin{pmatrix} C_{11} & \cdots & C_{1q} \\ \vdots & \ddots & \vdots \\ C_{p1} & \cdots & C_{pq} \end{pmatrix} $$ with $$ C_{il} = \sum_{j \in [t]} A_{ij} B_{jl} $$ for any $ i \in [p] $ and $ l \in [q] $. ...

Exercise 1 What rows or columns or matrices do you multiply to find the second column of $ AB $ ? the first row of $ AB $ ? the entry in row $ 3 $, column $ 5 $ of $ AB $ ? the entry in row $ 1 $, column $ 1 $ of $ CDE $ ? To find the second column of $ AB $, we multiply matrix $ A $ by the second column of matrix $ B $. ...

Exercise 1 Let $ f:\mathbb{R}\to\mathbb{R} $ be a function. Prove that the following are equivalent: (i) There is a constant $ a\in\mathbb{R} $ such that for every$ x\in\mathbb{R} $ we have$ f(x)=ax $. (ii) For all $ x_1,x_2,c,x\in\mathbb{R} $ we have $ f(x_1+x_2)=f(x_1)+f(x_2) $ and $ f(cx)=c\,f(x) $. (i ⇒ ii) Assume there exists $ a\in\mathbb{R} $ such that $ f(x)=a x $ for all $ x\in\mathbb{R} $ . Then for any $ x_1,x_2,c,x\in\mathbb{R} $ , ...

File Allocation Table 要设计并实现一个文件系统，我们首先需要关注并解决存储媒介带来的两大核心挑战： 读写放大 (Read/Write Amplification)：现代存储设备（无论是机械硬盘还是固态硬盘）的物理特性决定了，它们最高效的读写方式是操作连续的大块数据区域，我们称之为一个块 (Block)。如果需要修改一个块中哪怕一个字节的数据，也必须将整个块读入内存、修改、再完整写回。这种“操作少量数据却导致整块数据被读写”的现象就是读写放大，它会严重影响性能。 局部性 (Locality)：程序的内存访问行为通常具有局部性原理 (Principle of Locality)，即在一段时间内，访问的地址会集中在某个区域。文件系统可以通过合理的数据排布，让物理上相邻的数据块在逻辑上也相关联（例如，属于同一个文件），从而在读取一块数据时，可以利用预读机制将后续可能被访问的数据也加载到内存缓存中，提高效率。 在软盘上实现文件系统 我们的需求是为一个存储容量很小的设备（如软盘）设计一个文件系统。在这种场景下，使用复杂的树形数据结构（如 B+ 树）会因为元数据本身占用过多空间而显得浪费。因此，一个简单的链式结构是更合适的选择。 目录的实现 在简单的文件系统中，目录本身可以被实现为一个普通的文件。这个文件的特殊之处在于，它的内容遵循一种固定格式，即一个目录项数组。 1 2 3 4 5 6 // 一个简单的目录项 (dentry) 结构 struct dentry { char filename[256]; // 文件名 unsigned int start_block; // 文件数据起始块的编号 unsigned int size; // 文件大小 (以字节为单位) }; 当我们需要打开一个目录时，文件系统只需读取这个文件的内容，并将其解析为一个 struct dentry 数组即可。 文件数据的存储 用链表来组织一个文件的所有数据块，主要有两种实现思路。 方法一：在每个数据块后放置指针 这种方法非常直观。每个数据块的末尾都留出一小块空间，用于存放下一个数据块的地址或编号。 优点：实现简单，逻辑清晰。 缺点： 极差的随机访问性能：要访问文件的第 N 个数据块，必须从第一个块开始，依次读入前 N-1 个块来找到第 N 块的指针。这需要 N-1 次磁盘 I/O，对于大文件而言是毁灭性的。 空间浪费：每个数据块都不能被 100% 用来存储文件内容，必须牺牲一部分空间给指针。 方法二：将指针集中存放在文件系统的某个区域 为了解决上述问题，我们可以将所有数据块的“链表指针”抽离出来，集中存放在一个被称为文件分配表 (File Allocation Table, FAT) 的核心数据结构中。 FAT 本质上是一个大数组。数组的下标与磁盘上的数据块编号一一对应。数组中存储的值则是该文件链表中的下一个数据块的编号。 ...

目录树 文件的抽象 操作系统将物理存储设备（如磁盘）的复杂性隐藏起来，提供了一个简单、统一的抽象——文件 文件可以看作是一个虚拟的磁盘，即一个命名的、一维的字节序列，支持 read, write, lseek 等操作 这种抽象使得上层应用无需关心数据在物理磁盘上的具体位置和存储方式 目录的引入 当文件数量增多时，需要一种方式来组织和管理它们 操作系统引入了目录 (Directory) 的概念，它是一种特殊的文件，其内容是其他文件或目录的列表 通过将文件和目录组织成一个层次化的树状结构，即目录树，可以方便地对文件进行分类、查找和管理 多数类 Unix 系统遵循 FHS (Filesystem Hierarchy Standard) 的目录结构约定，为软件和用户预测文件位置提供了便利 目录操作 API 操作系统提供了一系列系统调用来操作目录树，核心操作围绕“增删改查” mkdir: 创建一个新的目录 rmdir: 删除一个空的目录 getdents: 读取目录中的条目 (directory entries) link / unlink: 创建或删除文件的链接 链接 链接是文件系统的一个重要特性，它允许一个文件拥有多个名字或存在于目录树的多个位置 链接主要分为两种类型：硬链接和软链接（符号链接） 硬链接 Hard Link 定义：硬链接是让多个目录条目（文件名）直接指向磁盘上同一个文件索引节点 (inode) 每个文件在文件系统中都有一个唯一的 inode，它包含了文件的元数据（如权限、大小、数据块位置等）和数据本身 创建一个硬链接，相当于为同一个 inode 增加了一个新的入口点（文件名） 特性： 所有指向同一个 inode 的硬链接地位平等，没有主次之分 inode 内部维护一个链接计数 (reference count), 只有当这个计数减到 0 时，文件系统才会真正删除该 inode 和对应的数据块，这也是 unlink 系统调用的由来 限制： 不能为目录创建硬链接，以防止在目录树中产生循环 不能跨越不同的文件系统（因为 inode 号只在当前文件系统内唯一） 软链接 Symbolic Link 定义：软链接，也称符号链接 (symlink)，是一个特殊的文件，它的内容是另一个文件或目录的路径 ...

科普性质，简单记录一下 1-Bit 的存储：磁铁 要实现“持久化”存储，核心是要找到一个能反复改写的状态，很容易想到能够利用磁的特性，这就有了磁带的初步想法： 一个长条的带子上面均匀有磁性物质 定位到特定位置之后通过放大感应电流读取 用电磁铁改变磁化方向来写入数据 为了提高存储密度，可以把这样的带子给卷起来，于是就得到了磁带 这样的存储方式主要缺点是几乎不能随机读写（比如磁带收音机需要倒带），一般用于冷数据的存档和备份 为了解决这个缺点，可以想到用旋转的二维平面来替代卷起来的带子，这样读写延迟就不会超过旋转的周期，这就得到了磁鼓： 再在磁鼓的基础上进一步内卷，把用圆盘代替柱面，从而可以堆叠起来，进一步提高了存储密度，这就得到了磁盘： 磁盘作为存储设备的随机读写性能虽然相比磁带有了很大的改善，但是还是需要等待定位到正确的位置，性能仍然不够优秀，为了读写定位到一个扇区通常需要花费几个毫秒的时间，这一点可以通过缓存和调度算法来缓解，让数据尽可能连续存储 当我们在磁盘的基础上把读写头和盘片本体分开，我们就实现了数据的移动，这也就得到了软盘，这是上个数据数据发行的主要方式，虽然性能和可靠性都比较低，但是胜在了便捷、可移动 1-Bit 的存储：挖坑 古人实现持久化存储的方式是在石头上刻字，也就是通过挖坑来存储信息，这种方式可以跨越非常长的时间 而现代工业使我们可以挖出更加精细的坑，从而可以存储更高密度的信息 为了读取这样的信息，我们可以从光学的角度考虑：在反射平面上挖粗糙坑，激光扫过表面，在平面会反射回来，在坑里会发生漫反射，于是我们只要检测是否收到反射光就可以识别是坑还是表面，这也就是光盘 光盘最有趣的特性是容易复制，我们要制造光盘可以先仔细地制造一张反转的盘片，坑的位置对应其表面的突起，之后只需要直接用这个盘片压制加热的塑料再镀上反射膜就可以得到一张光盘，这种方式可以达到极高的写入速度 当然这种挖坑方式的一个重要特性就是不能修改已经写入的内容的，很难填上一个已经挖了的坑（当然通过特殊的制造材料和工艺也是可以做到的），这也就是说里面存储的数据是 append only 的，想要修改之前的内容可以采用可持久化二叉树的结构 光盘作为存储设备，价格低的同时容量和可靠性都比较高，同时顺序读性能一般，随机读性能低并且很难写入，一个重要的应用常见就是数字时代的内容分发 现代这种挖坑的存储方式还有一种应用方式是回归古人石碑的形式，把信息刻在很稳定的材料上来做到永久存储 1-Bit 的存储：电荷 前两种存储介质都存在比较大的缺陷： 磁：依赖机械部件，从而无法避免 ms 级别的延迟 坑（光）：挖坑效率低，同时填坑很困难 而电荷则是一种非常理想的存储介质：电子的密度极高，并且电路的速度极快（还天然并行） 在电路中实现 1-bit 的持久存储，一个想法是我们可以挖一个坑，两种状态分别是： 在坑里填入电子 从坑里放跑电子 而这就得到了闪存 (Flash Memory) ： 其作为存储设备，价格低，容量和可靠性高，而且读写性能极高（由于电路天然并行，所以容量越大，速度越快） 然而，闪存的物理原理也带来了其固有的缺陷，即会磨损 (wear out) 每次放电 (erase) 操作都无法 100% 将电子放干净，这会对存储单元造成微小的、不可逆的损伤 在经历数千或数万次擦写循环后，一些存储单元会因为累积的损伤而失效，无法再可靠地存储数据，这被称为 “死单元 (Dead Cell)” 为了解决闪存的磨损问题，并将其更好地呈现给操作系统，现代固态存储设备（如 SSD、U 盘、SD 卡）内部实际上都集成了一个微型计算机系统 这个系统运行着一层被称为 FTL (Flash Translation Layer) 的固件，它的核心功能之一是 磨损均衡 (Wear Leveling) ...

输入输出设备 Everything is a File 在 Unix-like 系统中，与外部设备交互的核心思想是 Everything is a File 文件描述符 (File Descriptor)：操作系统为上层软件提供了一个统一的抽象，即文件描述符，它是一个指向内核中任何 I/O 对象的“指针”或句柄 统一接口：无论是普通文件、硬件设备（如终端、磁盘）、还是网络连接，都可以通过 open 获得一个文件描述符，然后使用相同的 read/write 等系统调用来进行操作，这极大地简化了应用程序的编写 设备控制器与 MMIO “文件”这个美好的抽象背后，是具体的硬件工作原理 设备控制器 (Device Controller)：每个 I/O 设备都有一个控制器，它是一个包含 CPU、内存和寄存器的微型计算机，作为 CPU 和物理设备之间的桥梁 设备寄存器：控制器通过一组寄存器与 CPU 通信，通常包括： 状态寄存器：用于表示设备当前是否繁忙、是否准备好等 指令寄存器：CPU 写入指令，告诉设备要做什么 数据寄存器：用于在 CPU 和设备之间传输数据 内存映射 I/O (MMIO)：为了让 CPU 能访问这些寄存器，现代系统普遍采用 MMIO (Memory-Mapped I/O)，操作系统会将设备的寄存器映射到物理内存地址空间中的特定区域，这样一来，CPU 就可以像访问普通内存一样，使用标准的 load/store 指令来读写设备寄存器，从而实现对设备的控制 GPIO GPIO (General-Purpose Input/Output) 是理解 I/O 设备原理最直观的例子，GPIO 就是一个物理引脚，可以通过编程设置为输入或输出模式 通过 MMIO，一个 GPIO 引脚的电平状态被映射到一个特定的内存地址，当 CPU 向这个地址写入 1 时，引脚就变为高电平；写入 0 时，则变为低电平，这个过程将一条内存写指令直接转化为了一个物理世界的动作（比如点亮一个 LED） ...

CPU 内的并行编程 CPU 的功耗 $ P=C\cdot V^{2}\cdot f $ 导致纵使有更大的电路，热功耗限制了性能上限，从而有一堵“功耗墙”限制了 CPU 的性能，为此需要考虑如何在降低 $ V $ 和 $ f $ 的同时用面积换性能 有两个思路： 让一条指令能处理更多的数据：SIMD (Single Instruction, Multiple Data) “一条指令” 浪费的能量大致是定数 处理的数据越多，浪费越少 用更多更简单的处理器：多处理器系统、异构多处理器 同等面积，处理器越简单，数量越多 异构计算：最经典的例子是大小核架构（如 Apple M1） SIMD SIMD 的核心思想是在硬件层面实现数据级并行，它通过引入专门的硬件单元来达成这个目标： 宽位寄存器 (Wide Registers)：CPU 内部增加了比通用寄存器宽很多的专用寄存器 Intel 的 SSE 指令集引入了 128 位的 XMM 寄存器，而最新的 AVX-512 拥有 512 位的 ZMM 寄存器 这些宽位寄存器可以一次性装入多个数据元素，比如一个 128 位的寄存器可以同时容纳 4 个 32 位的浮点数，或者 16 个 8 位的整数 这些被打包在一起的数据被称为 Vector 向量处理单元 (Vector ALU)：CPU 内部也配备了能够对整个向量进行并行计算的 ALU ...

并发编程的核心抽象是实现一个计算图，计算发生在节点上，边表示节点之间的依赖关系，同时计算图在运行时可能是动态变化的 使用条件变量、锁、信号量等 api 去实现计算图并不是一个优雅的实现方式，因为这样会在代码中引入众多干扰代码，也可能导致一些问题 为此可以增加一些功能受限的语法，可以在同样描述计算图的功能下减少了许多潜在的问题 高性能计算中的并行编程 在高性能计算中，计算图通常易于静态切分，尤其适用于物理模拟的网格划分，为此 HPC 发展出多种高效的并行编程模型，具体学习可以参考 SJTU HPC 学习手册 MPI: 分布式内存并行 每个 MPI 进程有独立的内存空间，进程间通过显式消息传递（发送/接收）交换数据 OpenMP: 共享内存并行 多个线程在同一地址空间中并行执行，所有线程可以直接访问相同的数据，使用 #pragma omp 指令实现并行化 对非计算机专业来说非常友好，只需要在正常的代码上面加上编译指令即可，能轻松实现高效的并行优化 CUDA: GPU 异构并行 CPU 调度，GPU 执行大规模并行计算 概念： 核函数 (Kernel) ：在 GPU 上并行执行的函数 线程层次：线程 (threadIdx) 组成线程块 (blockIdx)，线程块组成网格 (gridDim) 内存层次：寄存器、共享内存（块内高速）、全局内存（所有线程可访问） 我们身边的并发编程 从 Web 1.0 到 Web 2.0 在 Web 时代用的最广泛的是 Javascript Asynchronous JavaScript and XML (Ajax; ~1999) 允许网页实现“后台刷新” jQuery $ (2006): A DOM Query Language (编程抽象) Web 2.0 时代的并发编程 线程开销大，并且大多数 Web 开发者难以进行并发编程 ...

数据竞争 大多并发 bug 最后都会体现为数据竞争 (Data Race) 对于顺序程序而言，函数 f() 返回之后就已经完成了所有的状态修改，对于其他部分而言这个修改是立即生效的；如果对于并发程序而言模式的切换也在瞬间完成，那就不会导致并发的问题 然而实际上模式的切换需要时间，执行的操作在未来一段时间之后才会就绪，但是我们在实际编程时总是容易有“立即生效”的肌肉记忆，这就导致了并发问题的可能性 不过对于函数式编程而言，操作不存在对外状态的修改，没有副作用（只会操作局部变量），这就不会导致并发问题 Data Race 发生的实质是不同的线程同时访问同一内存，并且至少有一个是写，形象的理解就是不同的内存访问在“赛跑”，跑赢的操作先执行 Not that easy: 虽然我们将数据竞争形象地比喻为“赛跑”，但实际上，哪一个操作能“跑赢”并没有想象中那么简单和确定，其复杂性主要体现在以下几个方面 弱内存模型 (Weak memory model)：在现代处理器架构中，为了提升性能，处理器可能会对内存操作进行重排序。这意味着，不同的线程或“观察者”在不同时间点看到共享内存的状态可能是不一致的。一个线程对内存的写入操作，可能不会立即对所有其他线程可见，导致不同线程观察到不同的结果。这种内存模型的一致性问题使得确定哪个操作“先发生”变得非常困难且不确定。 未定义行为 (Undefined Behavior)：从 C++11 标准开始，数据竞争被明确规定为未定义行为。这意味着，如果你的程序发生了数据竞争，编译器可以自由地产生任何行为，无论是崩溃、产生错误结果，还是看似正常运行但结果不可预测。这使得数据竞争成为非常危险且难以调试的并发错误，因为它的表现可能是不确定、不稳定的。 多线程与多内存的复杂交互：在实际的并发程序中，通常会有多个线程同时访问多个共享内存位置。这些线程和内存之间存在复杂的读（R）写（W）交互。一个线程对一个内存位置的写入可能影响到其他多个线程对该位置的读取，同时，多个内存位置之间也可能存在复杂的依赖关系和缓存一致性问题。这种错综复杂的交互网络进一步加剧了数据竞争的不可预测性。 为了消灭数据竞争，我们需要保证程序的 serializability ，可能竞争的内存访问要么互斥，要么同步 实际编程中遇到的数据竞争 bug 大多属于上错了锁和忘记上锁两种情况的变种 Case 1: 上错了锁 1 2 void T_1() { spin_lock(&A); sum++; spin_unlock(&A); } void T_2() { spin_lock(&B); sum++; spin_unlock(&B); } Case 2: 忘记上锁 1 2 void T_1() { spin_lock(&A); sum++; spin_unlock(&A); } void T_2() { sum++; } 但是实际系统面临的情况比这复杂的多，因为 内存可以是地址空间的任何内存，比如全局变量、堆内存分配的变量、程序的栈…… 访问可以发生在任何代码，比如自己的代码、框架代码、一行没读到的汇编指令、某条 ret 指令 “一行没读到的汇编指令”造成的访问的情况有编译器优化造成的指令重排、硬件层面弱内存模型的内存访问重排、还有一些高层语言操作的隐式内存访问 实际系统中虽然难以避免，但是会尽可能保证底层的结构对上层尽可能封闭来防止这种错误 死锁 死锁 (Deadlock) 是指一个群体中的每个成员都在等待其他成员（包括自身）采取行动的状态 死锁有两种： AA-Deadlock: 自己等待自己 1 2 3 4 5 6 7 lock(&lk); // lk->locked == ✅; proceed ... // Possibly in interrupt handler lock(&lk); // while (lk->locked == ❌) ; 这样的错误虽然看起来很傻，但是在真实程序复杂的控制流中是可能出现的 ...

信号量 互斥锁在某种意义上也可以认为实现了 “happens-before” 的依赖关系—— release 必然发生在 acquire 之前。我们可以试着利用这种依赖关系来实现计算图的调度：为每条边分配一个互斥锁，代表数据或前置任务的完成；一个节点必须获得所有入边对应的互斥锁才能开始计算，计算完成后，就释放所有出边对应的互斥锁，通知下游节点输出就绪（但是这种直接使用互斥锁作为边状态信号的方式是 undefined behavior，因为互斥锁主要用于保护临界区，其释放通常要求由持有它的线程完成，若释放未曾获取的锁，则行为未定义） 我们可以从这种想法中抽象出其本质，也就是用一个“信号”去获取资源的许可，类似餐厅的取号吃饭 这种信号的思想很适合用来管理计数类型的同类资源，比如停车场的空位，为了实现这种 producer-customer 的问题，用 条件变量 可以轻易解决，进入的条件就是存在空位 count < capacity ，那我们从减少变量的角度出发，这实际上也就是剩余空位的数量大于零，我们停车相当于消耗了一个车位，离开相当于创造了一个车位，这也就得到了所谓“信号量”的机制 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void P(sem_t *sem) { // Prolaag - try + decrease/down/wait/acquire mutex_lock(&sem->lk); while (!(sem->count > 0)) { cond_wait(&sem->cv, &sem->lk); } sem->count--; // 消耗一个信号 (车位) mutex_unlock(&sem->lk); } void V(sem_t *sem) { // Verhoog - increase/up/post/signal/release mutex_lock(&sem->lk); sem->count++; // 创建一个信号 (车位) cond_broadcast(&sem->cv); mutex_unlock(&sem->lk); } 根据这个一路推出信号量的思路，或许可以认为这是互斥锁的扩展 ...

同步和条件变量 互斥实现了原子性，但是无法实现确定性，也就是无法正确实现 “happens-before” 的关系 因此需要引入条件变量来实现线程的同步，形成受控制的并发事件的发生顺序（可以用乐团指挥来类比），把一系列不确定的状态在某一个时间点同步到了一个确定的状态，将发散的并发程序状态 “收束” 实现同步 实现 $ A\to B $： 1 2 3 4 5 6 7 A; can_proceed = true; (signal) while(!can_proceed); B // B: wait until the condition is satisfied 这样的思路大致正确，但是自选的循环有很大的性能问题，因此需要一个更加底层的机制来帮助实现这一点 最理想的 API 是 wait_until(cond) ，但是过去为了简化设计，变成了 条件不满足时等待：wait - 直接睡眠等待 条件满足时继续：signal/broadcast - 唤醒所有线程 （小时候的 scratch 编程其实已经有了这样的思想😂） 在 c++ 代码中我们可以把条件放到 $ \lambda $ 表达式中： 1 2 3 4 5 6 7 8 9 10 11 12 std::mutex mtx; std::condition_variable cv; void T_player() { std::unique_lock lk(mtx); cv.wait(lk, []{ return can_proceed; } ); cv.notify_all(); lk.unlock(); } 注意条件变量在等待时需要带着一把锁（需要确保检查和等待是原子操作） ...