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} $ , ...
考虑上一节引入的二项式定理 $$ (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} $ 的系数。 ...
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 $- 代数（域）： ...
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\} $。 ...
课程讲义 在这门课里，我们会专注于所谓的 科尔莫哥洛夫（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 $ 的概率是有限的，当然目前只能从直觉上去理解，这个写法需要在后续的课程中去严格定义。 ...
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） ...