情理 CS 考点重难点大纲

1. 数值分析

1.1 误差分析

1.2 矩阵分解

Matrix Decompositions

• LU 分解 1. LU Decomposition LU 分解
• SVD 分解 3. Singular Value Decomposition (SVD) 奇异值分解 (SVD)

1.3 函数逼近

• 最佳一致逼近
• 最佳平方逼近

1.4 插值法

• 样条插值
• 拉格朗日插值 Lagrange Multiplier
• 牛顿插值法

1.5 常微分方程数值解法

• 龙格库塔方法

2. 计算机组成原理

2.1 CPU 流水线

流水线

• 设计原理
• 冒险（数据冒险、控制冒险、结构冒险）及其解决方法 流水线冒险 Pipeline Hazards

2.2 缓存（Cache）

• 结构和工作原理
• 缓存一致性

2.3 虚拟内存

2.4 性能评估

• CPI (Cycles Per Instruction) 计算

2.5 MIPS 汇编语言基础

2.6 数据表示

数据表示

• 整数的表示和运算方式
• 浮点数的表示和运算方式

2.7 分支预测

3. 操作系统

3.1 进程与线程

• 基本概念
• 进程调度算法 进程调度算法
• 进程同步（互斥、信号量、管程）
• 进程通信（共享内存、消息传递）

3.2 死锁

死锁

• 死锁的必要条件
• 死锁预防、避免、检测和恢复

3.3 内存管理

内存管理基础

• 分页
• 分段
• 虚拟内存
• 页面置换算法

3.4 文件系统

• 文件分配方法
• FAT 和索引方法

3.5 I/O 系统

• 磁盘调度算法
• RAID 技术

4. 数字电路

4.1 布尔代数与逻辑门

布尔代数

逻辑门

4.2 逻辑化简

• 卡诺图 Karnaugh图

4.3 组合逻辑电路设计

• 加法器（半加器、全加器）
• 乘法器

4.4 时序逻辑电路

• 触发器（SR、D、JK、T 型） Flip-Flop
• 有限状态机（FSM） 有限状态机

4.5 CMOS 电路基础

CMOS

5. 形式语言与自动机

5.1 有限自动机

• DFA、NFA、ε-NFA 及其转换 有限自动机

5.2 正则表达式

• 正则表达式与 NFA 的转换

5.3 正则语言的性质

正则语言

• 封闭性
• 泵引理及其应用

5.4 上下文无关语言 (CFG)

上下文无关语言

• 语法推导
• 分析树
• 二义性

5.5 下推自动机 (PDA)

5.6 上下文无关语言的性质

• 泵引理及其应用 RL的泵引理

6. 数据结构与算法

6.1 基本数据结构

• 链表、栈、队列、树、图 树 图理论基础

6.2 排序算法

• 快速排序、归并排序、堆排序 排序 排序算法分析

6.3 图算法

• BFS、DFS BFS&DFS
• 最短路径算法（Dijkstra、Bellman-Ford） 寻路算法
• 最小生成树算法（Prim、Kruskal） 最小生成树
• 拓扑排序 拓扑排序 Topological Sorting

6.4 动态规划

6.5 贪心算法

6.6 分治算法

6.7 字符串算法

• KMP 算法 KMP算法

6.8 高级数据结构

• 并查集 并查集

6.9 复杂度分析

时间复杂度

• 时间复杂度、空间复杂度
• 主定理 主定理

6.10 NP 完全性基础概念

7. 机器学习

7.1 回归

• 线性回归
• 多元线性回归
• 岭回归

7.2 分类

• 逻辑回归
• 朴素贝叶斯

7.3 优化方法

• 梯度下降法

7.4 概率与统计

• 极大似然估计
• 贝叶斯统计
• 中心极限定理

7.5 降维与特征选择

• 主成分分析 (PCA)

7.6 聚类

• K-means 算法 K-means 算法

7.7 模型评估与选择

• 交叉验证
• 过拟合与欠拟合

7.8 EM 算法

EM算法

7.9 高斯判别分析

8. 编程语言

8.1 编程范式

• 命令式、面向对象、函数式、逻辑、并发编程 常见编程语言类型

8.2 语言特性

• 类型系统
• 内存管理
• 异常处理
• 并发机制

参数传递机制

9. 离散数学

9.1 图论

• 平面图

9.2 组合数学

9.3 生成函数