Ruiqy~

返回：0300 数据结构总目录 · 下一章：0302 Chap2 向量 1、学习目标本章先回答一个问题：为什么同样能得到结果的程序，仍然要比较“好坏”。数据结构后面每一章都会反复讨论时间、空间、最坏情况、平均情况和分摊意义，所以绪论不是开场白，而是整门课的计量工具。 模块 要掌握的内容 计算 算法是有限、确定、可执行的步骤序列 模型 RAM 模型、基本操作、输入规模 复杂度 大 O、Omega、Theta、常见增长阶 分析 级数估计、循环分析、递归分析 方法 迭代、递归、减而治之、分而治之、动态规划 下界 排序下界、比较决策树、问题本身的限制 2、资料范围 PDF 课件 内容 01.Introduction.A.Computation.pdf 计算、算法、正确性 01.Introduction.B.Computational_Models.pdf 计算模型、RAM、基本操作 01.Introduction.C.Big_o.pdf 大 O 记号和增长阶 01.Introduction.D.Algorithm_anal ...

返回：0100 离散数学课程总目录 · 上一章：0119 组合数学引言、鸽巢原理与 Ramsey 定理 · 下一章：0121 递推方程与生成函数 1、学习目标本章是组合计数的基础工具箱。核心不是背一堆公式，而是先分清：分类还是分步、有序还是无序、重复还是不重复、盒子是否有区别、限制是否有上界。 主线： 1234567加法法则：互斥分类。乘法法则：连续分步。排列组合：有序/无序，不重复选取。多重集：对象允许重复。二项式定理：处理组合数、展开式系数和求和。多项式定理：处理多类对象分配与多项式系数。非降路径：用格路模型证明组合恒等式。 本站页面编号是 0120，但课件与习题内部称为“第二十一章/习题二十一”。下面答案按教材题号写成 21.1-21.47。 2、两个计数原则加法法则若完成一件事可以分成互不重叠的 k 类，第 i 类有 n_i 种方法，则总数为： 1n1+n2+...+nk 适用关键词： 1或者、分类、按情况讨论、互斥。 乘法法则若完成一件事要依次做 k 步，第 i 步有 n_i 种方法，则总数为： 1n1*n2*...*nk 适用关键词： 1先...再...、分步、每一步独 ...

返回：0100 离散数学课程总目录 · 上一章：0118 格与布尔代数 · 下一章：0120 计数原则、排列组合与组合恒等式 1、学习目标本章进入组合存在性。它不急着数“有多少种”，而是先问：在对象足够多、模式足够少的情况下，某种结构是否必然出现。 主线： 1234组合数学引言：一一对应、数学归纳法、上下界逼近。鸽巢原理：对象数超过模式数时，某个模式必然重复或拥挤。Ramsey 定理：任意染色足够大的结构，必然出现单色有序子结构。相异代表系：每个集合选一个互不相同的代表元素。 本章要能熟练处理： 123451. 找出题目里的“鸽子”和“巢”。2. 用余数类、前缀和、星期模式、奇偶模式建模。3. 掌握 R(3,3)=6、R(3,4)=9 以及 Ramsey 递推上界。4. 会把图问题翻译成红蓝染色问题。5. 会用 Hall 条件判断相异代表系，并理解置换矩阵分解。 本站页面编号是 0119，但课件与习题内部称为“第二十章/习题二十”。下面的习题答案按教材题号写成 20.1-20.20。 2、组合数学的基本技巧组合数学常见内容包括： 1234组合存在：鸽巢原理、Ramsey 定理、Ha ...

返回：0100 离散数学课程总目录 · 上一章：0117 环与域 · 下一章：0119 组合数学引言、鸽巢原理与 Ramsey 定理 1、学习目标本章把偏序集中的“最大下界”和“最小上界”代数化，得到格。随后沿着“格 → 模格 → 分配格 → 有补格 → 布尔代数”的路线，学习如何从哈斯图和代数等式判断结构。 主线： 12345格：任意两个元素都有 meet 和 join模格：满足模律，等价于不含五角格 N5 子格分配格：满足分配律，等价于不含 N5 与钻石格 M3 子格有补格：有界格中每个元素都有补元布尔代数：有补分配格 本章要熟练掌握： 123451. 从哈斯图判断是否为格。2. 求 meet、join、补元、子格、理想。3. 用 N5、M3 判断模格和分配格。4. 证明格同态、格同构、理想格与直积格。5. 使用布尔代数的德摩根律、补元唯一性和有限表示定理。 判断题不要只看图像“像不像”。核心是检查任意两个元素是否都有唯一的最大下界和最小上界；判断模格、分配格时，再找禁用子格 N5 和 M3。 2、格的定义偏序集 <L, <= > 是格，当且仅当任意 a,b ...

返回：0100 离散数学课程总目录 · 上一章：0116 群论基础 · 下一章：0118 格与布尔代数 1、学习目标本章把“加法结构”和“乘法结构”放在同一个集合上：加法要求是 Abel 群，乘法要求是半群，再用分配律把两者粘起来，得到环。继续加入乘法交换、乘法单位、无零因子、非零元素可逆，就得到整环和域。 主线： 123456环：加法 Abel 群 + 乘法半群 + 分配律交换环：环 + 乘法交换含幺环：环 + 乘法单位元 1无零因子环：ab=0 => a=0 或 b=0整环：交换 + 含幺 + 无零因子 + |R|>1域：非零元素关于乘法构成 Abel 群 本章要能熟练处理： 123451. 判断一个代数系统是否为环、整环或域。2. 计算 Z_n 中的零因子、可逆元和理想。3. 证明子环、理想、商环和环同态。4. 使用有限整环必为域、有限域阶为 p^n。5. 处理多项式商环 F[x]/(f(x)) 的有限域构造。 环里有两个运算。证明时要一直区分：加法部分用群语言，乘法部分用半群语言，理想/商环/同态则同时照顾两个运算。 2、环的定义代数系统： 1<R,+,* ...

返回：0100 离散数学课程总目录 · 上一章：0115 半群与独异点 · 下一章：0117 环与域 1、学习目标本章是在独异点的基础上继续加入“每个元素都有逆元”，得到群。从这里开始，代数结构进入真正高频的证明题区域。 主线： 1234半群：封闭 + 结合律独异点：半群 + 单位元群：独异点 + 每个元素有逆元Abel 群：群 + 交换律 本章要能熟练处理： 123451. 群的定义、等价定义和基本消去性质。2. 子群判定、循环群、生成元与子群结构。3. 置换群、轮换分解、对换分解和置换阶。4. 陪集分解、Lagrange 定理、正规子群与商群。5. 群同态、核、像、同构和同态基本定理。 群题最常见的失误不是“不会算”，而是忘记非 Abel 群里一般不能交换顺序。凡是移动 a、b 的位置，都要问一句：题目是否已给出 ab=ba，或是否在 Abel 群、循环群、商群等可交换环境中？ 2、群的定义与等价定义群代数系统： 1<G,*> 若满足： 12341. 封闭性：任意 a,b in G，有 a*b in G；2. 结合律：(a*b)*c = a*(b*c)；3. 存在单 ...

返回：0100 离散数学课程总目录 · 上一章：0114 代数结构基础 · 下一章：0116 群论基础 1、学习目标本章是代数结构的第一层：从“一种封闭二元运算”出发，加入结合律得到半群，再加入单位元得到独异点。后续的群就是“每个元素都有逆元的独异点”。 主线： 1234广群：封闭二元运算半群：封闭 + 结合律独异点：半群 + 单位元群：独异点 + 每个元素可逆 半群和独异点看似简单，但证明题高度依赖结合律。看到 abc、a^n、左零元、生成子半群、商半群时，第一反应都应该是：先用结合律合法改括号。 2、半群与独异点定义半群代数系统 1V=<S,*> 若满足： 121. * 在 S 上封闭；2. * 满足结合律：(a*b)*c = a*(b*c)； 则称 V 为半群。 半群判定模板： 12第一步：任取 a,b in S，验证 a*b in S。第二步：任取 a,b,c in S，验证 (a*b)*c = a*(b*c)。 独异点若半群 <S,*> 中存在单位元 e： 1e*a = a*e = a, 对任意 a in S 则称 1<S,*,e> ...

返回：0100 离散数学课程总目录 · 上一章：0113 图论应用 · 下一章：0115 半群与独异点 1、学习目标本章进入代数结构。核心目标是把“集合 + 运算 + 公理”作为一个整体来研究：运算是否封闭、满足哪些算律、有没有单位元/零元/逆元，以及不同结构之间能否通过同态、同构、商代数联系起来。 课程主线： 123集合 A + 运算 Ω + 常数 K + 公理=> 代数系统=> 子代数 / 积代数 / 同态同构 / 同余关系 / 商代数 本章最容易混的是“性质是否保持”：积代数、商代数、满同态像能保持交换、结合、幂等、分配、吸收、单位元、零元、逆元，但消去律一般不保持。 2、代数结构总图 模块 问什么 关键词 二元运算 运算结果还在集合里吗，满足哪些算律 封闭、交换、结合、幂等、消去 特异元素 有没有特殊元素 单位元、零元、幂等元、逆元 代数系统 集合和运算构成什么结构 载体、运算集、常数集、公理 子代数 子集是否继承结构 非空、封闭、含 0 元运算 积代数 两个同类型系统如何组合 笛卡儿积、按分量运算 同态同构 结构之间如何映射 ...

返回：本科课程：疾风计划 1、课程定位计算机组成原理解释程序在硬件层面如何运行。它连接 C/C++、汇编语言、操作系统和计算机体系结构，是理解“代码为什么这样执行、性能为什么这样变化、硬件如何支撑软件”的核心课程。 项目 内容 课程 计算机组成原理 教师 纪禄平 院校 电子科技大学 资料来源 国家高等教育智慧教育平台课程大纲 + 纪禄平《计算机组成原理》课程体系 学习定位 408 主干入门，衔接 C/C++、汇编、操作系统、体系结构和网络安全底层分析 笔记范围 0501~0506，对应课程 6 章主体内容 这组笔记按“总体框架 -> 处理对象 -> 硬件子系统”的顺序整理。先建立整机视角，再理解数据如何表示和运算，最后拆 CPU、存储、总线、I/O。复习时不要只背部件名，要尽量把“指令如何取、数据如何来、结果如何写回、外设如何交互”串成一条执行链。 2、参考大纲 来源 采用内容 国家高等教育智慧教育平台《计算机组成原理》课程页 课程简介、教师、教材、6 章课程大纲 电子科技大学纪禄平老师课程体系 系统概述、数 ...

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