Ruiqy~

返回：本科课程：疾风计划 1、课程定位算法设计与分析训练的是“把问题变成可计算方案”的能力。数据结构更偏向组织数据，算法设计更偏向选择策略、证明正确性、估计复杂度，并判断一个问题到底能不能高效求解。 项目 内容 课程 算法设计与分析 教师 王振波 院校 清华大学 资料来源 清华/学堂在线公开课程大纲 + 常见算法设计课程内容 学习定位 408 主干入门后的算法能力补强，衔接刷题、AI、网络安全和系统项目 笔记范围 0401~0411，对应算法设计与分析 11 个主题 这一组笔记先按“算法范式”整理，而不是按题库刷题顺序整理。每章保留问题模型、核心算法、正确性证明思路、复杂度和复盘清单，后面做题时再把错题和代码实验补进对应章节。 2、参考大纲 来源 采用内容 清华大学 / 学堂在线《算法设计与分析》 算法基础、图、贪心、分治、动态规划、网络流、NP、近似算法、局部搜索、随机算法 国家高等教育智慧教育平台课程页 课程简介、教师和 11 章大纲 中国科学院大学《计算机算法设计与分析》大纲 分治、贪心、动态规划、回溯、分支限 ...

返回：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) 最小边覆盖大小 “极小/极大”说的是不能再删或不能再加，是局部性质；“最小/最大”说的是数量最少或最多，是全局最优。极小支配集不一定是最小支配集，极大匹配也不一定是最大匹配。 3、支配、独立、点覆盖 ...

返回：本科课程：疾风计划 1、课程定位数据结构是 408 主干入门的第一门课，也是 C++ 程序设计之后最适合继续补强的一门课。它关心的不是“语法怎么写”，而是数据如何组织、操作如何定义、算法为什么正确、复杂度如何估计。 项目 内容 课程 数据结构 教师 邓俊辉 院校 清华大学 资料来源 本地邓俊辉《数据结构》上、下视频与 PDF 课件 学习定位 408 主干入门，衔接算法设计、计算机系统、网络安全项目和后续刷题 笔记范围 0301~0312，对应 12 章课程内容 这组笔记按邓俊辉老师课程的 12 章整理：先搭总框架，再逐章复盘 ADT、实现、关键算法、复杂度、易错点和练习清单。后面真正跟视频学习时，可以在每章继续补截图、推导和代码实验。 2、学习主线 部分 章节 核心问题 后续连接 算法分析基础 Chap 1 如何度量算法效率，如何理解迭代、递归、动态规划和下界 408 算法复杂度、递归分析 线性结构 Chap 2-4 向量、列表、栈和队列如何支持不同访问模式 顺序表、链表、表达式求值、BFS 树与图 Chap ...

返回：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&g ...

返回：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、章节主线 模块 本章要会什么 后续连接 欧拉图 会用度数判定欧拉图 ...

返回：0100 离散数学课程总目录 · 上一章：0105 等势、基数、序数与集合论公理 · 下一章：0107 欧拉图与哈密顿图 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第六章。Auto_Tutor 中整理到的资料包括： 资料 内容 6.1 图的基本概念 图、无向图、有向图、简单图、度、握手定理、度数列、Havel 定理、图同构、子图、补图 6.2 通路与回路 通路、简单通路、初级通路、回路、圈、周长、围长、扩大路径法 6.3 无向图的连通性 连通关系、连通分支、距离、直径、二部图、强/单向/弱连通 6.4 无向图的连通度 点割集、边割集、割点、桥、点连通度、边连通度、Whitney 不等式、Menger 定理、块 006 习题与答案 习题 1、2、3、5、11、14、16、18、22、25，重点考察握手定理、补图、自补图、极大路径法、连通度和块 本章的核心目标：把图论的对象语言搭起来。先会数点、数边、数度，再会判断“走法”和“连通性”，后面的欧拉图、哈密顿图、树、平面图都会反复调用这些定义。 2、颜色标注 颜色 ...

返回：0100 离散数学课程总目录 · 上一章：0104 自然数的定义与性质 · 下一章：0106 图的基本概念、通路回路与连通性 1、资料来源与学习目标本章对应北大离散数学刘田老师“集合论与图论”第五章。Auto_Tutor 中整理到的资料包括： 资料 内容 5.1 集合的等势、有穷集与无穷集合 等势、典型等势例子、Cantor 定理、有穷集、无穷集 5.2 基数和基数的比较运算 基数定义、优势/劣势、Schröder-Bernstein 定理、可数集、基数运算 5.3 集合论习题课 4-5 章 第四、五章习题复盘 5.3 序数和集合论公理 序数、连续统假设、ZF/ZFC 公理、罗素悖论 005 习题与答案 习题 2、5、11、12、补充题，重点考察等价类、等势、可数性和基数运算 本章的核心目标：分清基数和序数。基数回答“有多少”，靠双射匹配；序数回答“排第几、先后如何”，靠良序结构。 2、颜色标注 颜色 含义 粉色 必背、必会证明、后续章节反复使用 蓝色 核心术语和定义 橙色 易错点、边界条件 绿色 理解提示和后 ...