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\} $。 ...
课程讲义 在这门课里，我们会专注于所谓的 科尔莫哥洛夫（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） ...
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 == ❌) ; 这样的错误虽然看起来很傻，但是在真实程序复杂的控制流中是可能出现的 ...