Ruiqy~

返回：本科课程：疾风计划 1、课程定位计算机组成原理解释程序在硬件层面如何运行。它连接 C/C++、汇编、操作系统和体系结构，也是考研 408 中非常核心的一部分。 2、学习目录 模块 内容 复盘重点 数据表示 二进制、补码、浮点数 理解机器如何表示数据 运算器 算术逻辑运算、溢出、ALU 理解运算过程 指令系统 指令格式、寻址方式、汇编基础 程序到机器指令的过渡 存储系统 Cache、主存、虚拟存储基础 理解性能和层次结构 CPU 与 I/O 控制器、流水线、中断、总线 建立整机运行视角 3、后续补充后面补 408 题型、计算题、结构图和它与操作系统、CSAPP 的对应关系。

返回：0100 离散数学课程总目录 · 上一章：0112 支配、覆盖、独立与匹配 · 下一章：0114 代数结构基础 1、学习目标本章是图论部分的收束：把欧拉图、哈密顿图、最短路、最小生成树和匹配组合起来解决带权图问题。 重点只抓两类模型： 12中国邮递员问题：边必须都走到，目标是最短闭迹。货郎担问题 / TSP：点必须都走到，目标是最短哈密顿回路。 记忆口令：邮递员走边，货郎走点。邮递员问题可以转成最短路 + 最小权完美匹配 + 欧拉回路；货郎担问题一般是难解问题，常用近似算法或动态规划。 2、带权图与应用问题建模带权图记为： 1G=<V,E,W>, W:E -> R 其中 W(e) 是边 e 的权，可以表示距离、时间、费用、容量损耗等。 常见题目翻译： 真实问题 图论模型 关键对象 邮递员走完所有街道 连通带权图中最短闭迹，覆盖全部边 欧拉回路、奇度顶点、匹配 旅行商访问所有城市 带权完全图中最短哈密顿回路 哈密顿回路、近似算法 路线补边 / 重复边 让所有顶点变成偶度 最短路、最小权完美匹配 小规模求精确最优 枚举 ...

返回：本科课程：疾风计划 1、课程定位算法设计与分析用来训练从问题到解法的能力。重点是复杂度、算法范式和证明思路，而不是把题解背下来。后续算法复盘、AI 自动化和安全分析都会用到这种思维。 2、学习目录 模块 内容 复盘重点 复杂度分析 时间复杂度、空间复杂度、递推 判断解法是否可行 递归与分治 分治策略、归并、快速排序 把大问题拆成子问题 动态规划 状态、转移、初始化、优化 建立状态表达能力 贪心算法 局部最优、证明、反例 明确适用条件 图算法 最短路、生成树、拓扑排序 连接数据结构与实际问题 3、后续补充后面按算法范式补模板、典型题、复杂度证明和自己的错题记录。

返回：0100 离散数学课程总目录 · 上一章：0111 图着色 · 下一章：0113 图论应用、习题课与课程总结 1、学习目标本章把图论中的“选点/选边”问题系统化：支配、覆盖、独立、匹配和边覆盖。核心目标是会在这些参数之间互相转化，尤其是Gallai 恒等式、Berge 定理、Hall 定理。 2、核心概念 概念 记号 定义 支配集 D 每个不在 D 中的顶点都与 D 中某点相邻 支配数 gamma0(G) 最小支配集大小 点覆盖 K 每条边至少有一个端点在 K 中 点覆盖数 alpha0(G) 最小点覆盖大小 点独立集 S 任意两点不相邻 点独立数 beta0(G) 最大点独立集大小 匹配 M 任意两条边不相邻 匹配数 beta1(G) 最大匹配大小 边覆盖 L 每个顶点都与 L 中某条边关联 边覆盖数 alpha1(G) 最小边覆盖大小 “极小/极大”说的是不能再删或不能再加，是局部性质；“最小/最大”说的是数量最少或最多，是全局最优。极小支配集不一定是最小支配集，极大匹配也不一定是最大匹配。 ...

返回：本科课程：疾风计划 1、课程定位数据结构是算法和系统课程之间的桥。它关注数据的逻辑结构、存储结构、基本操作和复杂度，是考研 408、算法题和项目代码复盘都绕不开的一门课。 2、学习目录 模块 内容 复盘重点 线性结构 顺序表、链表、栈、队列 操作定义、边界条件、代码实现 树结构 二叉树、遍历、堆、平衡树基础 递归思想和结构性质 图结构 存储、遍历、最短路、生成树 把抽象关系转成可计算模型 查找与排序 哈希、二分、各类排序 复杂度、稳定性和适用场景 3、后续补充后面补每类结构的定义、图示、典型题、C/C++ 实现和 408 常考点。

返回：0100 离散数学课程总目录 · 上一章：0110 平面图 · 下一章：0112 支配、覆盖、独立与匹配 1、学习目标本章对应刘田老师图着色部分，资料包括点着色、色多项式、平面图着色、面着色和边着色。核心目标是掌握色数、色多项式、四色问题、边色数这条线。 2、颜色标注 颜色 含义 粉色 必背结论 蓝色 概念名称 橙色 易错点 绿色 证明提示 3、点着色与色数点着色： 1给顶点染色，使相邻顶点颜色不同。 k-可着色表示可用不超过 k 种颜色完成点着色。色数： 1chi(G)=使 G 可着色的最小颜色数。 典型结果： 123456chi(K_n)=nchi(C_{2r})=2chi(C_{2r+1})=3树 T_n 的色数为 2（n>=2）chi(W_n)=4, n 偶数chi(W_n)=3, n 奇数 二部图判定： 1G 是 2-可着色图 <=> G 是二部图 <=> G 不含奇圈。 色数上界： 1chi(G) <= Delta(G)+1 Brooks 定理： 12n ...

返回：0100 离散数学课程总目录 · 上一章：0109 图的矩阵表示 · 下一章：0111 图着色 1、资料来源与学习目标本章对应刘田老师平面图部分，Auto_Tutor 中包含 10.1 到 10.5 的课件、习题课、习题十一和答案。核心目标是把“能否无交叉画图”转化为欧拉公式、面次数、禁用子图和对偶图的判断。 本章主线：平面嵌入 -> 面 -> 欧拉公式 -> 边数上界 -> 非平面判定。 2、颜色标注 颜色 含义 粉色 必背公式和判定定理 蓝色 核心概念 橙色 易错边界 绿色 证明线索 3、核心概念 概念 定义 平面图 已画在平面上，边只允许在公共端点相交的图 可平面图 存在某种平面嵌入的图 平面嵌入 把图画到平面上且没有非端点交叉 面 平面图中不含顶点和边的极大连通区域及其边界 外部面 面积无界的面 面次数 面边界长度，桥要在同一面边界上计两次 极大平面图 已是平面图，任意两个不相邻点之间加边都会破坏平面性 极小非平面图 非平面图，删任意一条边后变成平面图 4、欧拉公式与边数上 ...

返回：0100 离散数学课程总目录 · 上一章：0108 树 · 下一章：0110 平面图 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第九章，课件实际标题是“第十章 图的矩阵表示”。Auto_Tutor 中整理到的资料包括： 资料 内容 9.1 图的矩阵表示 有向图关联矩阵、无向图关联矩阵、基本关联矩阵、生成树判定、邻接矩阵、矩阵幂、可达矩阵、相邻矩阵、连通矩阵 009 习题与答案 习题 10.2、10.4，重点考察基本关联矩阵求生成树、邻接矩阵幂求通路与回路数量 本章的核心目标：把“图的结构问题”翻译成矩阵计算问题。关联矩阵服务于连通性和生成树，邻接矩阵服务于通路计数，可达矩阵和连通矩阵服务于可达性判断。 2、颜色标注 颜色 含义 粉色 必背定理、矩阵算法、习题直接使用的结论 蓝色 核心术语、矩阵名、图论对象 橙色 易错点、适用条件、下标方向 绿色 理解提示和操作步骤 3、章节主线 模块 本章要会什么 典型题型 关联矩阵 会按边和顶点写 M(D)、M(G) 判断度数、平行边、连通分支 基本关联 ...

返回：0100 离散数学课程总目录 · 上一章：0107 欧拉图与哈密顿图 · 下一章：0109 图的矩阵表示 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第八章。Auto_Tutor 中整理到的资料包括： 资料 内容 8.1 树 树、森林、树叶、分支点、树的六个等价定义、生成树、基本回路、基本割集、生成树计数、Cayley 公式 008 习题与答案 习题 9.2、9.6、9.11，重点考察握手定理、树的边数、森林边数上界、最大度与树叶数量 本章的核心目标：掌握树 = 连通 + 无圈这条主线，并能在“连通、无圈、边数 n-1、唯一路径、极小连通、极大无圈”之间自由切换。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后续连接 3、章节主线 模块 本章要会什么 后续连接 树与森林 会用连通性和圈判定树/森林 图论基础 等价定义 会在六种树定义之间转换 证明题 树叶 会用握手定理证明非平凡树至少两 ...

返回：0100 离散数学课程总目录 · 上一章：0106 图的基本概念、通路回路与连通性 · 下一章：0108 树 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第七章。Auto_Tutor 中整理到的资料包括： 资料 内容 7.1 欧拉图 欧拉通路、欧拉回路、欧拉图、半欧拉图、有向欧拉图、Fleury 算法、逐步插入回路算法 7.2 哈密顿图 哈密顿通路、哈密顿回路、哈密顿图、必要条件、Ore 条件、Dirac 条件、竞赛图 007 习题与答案 习题 8.4、8.7、8.13，重点考察任意行遍点、哈密顿必要条件和半哈密顿充分条件 本章的核心目标：区分欧拉与哈密顿。欧拉关注“每条边恰好走一次”，判定容易；哈密顿关注“每个顶点恰好经过一次”，判定困难，更多依赖必要条件和充分条件。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后续连接 3、章节主线 模块 本章要会什么 后续连接 欧拉图 会用度数判定欧拉图、半欧拉图 一笔 ...