“2023级--学期安排 (第四学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| 第47行： | 第47行： | ||
! 阅读材料 | ! 阅读材料 | ||
! 引导要点 | ! 引导要点 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第58行： | 第57行： | ||
| | | | ||
* 公理化系统的思想 | * 公理化系统的思想 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第70行： | 第68行： | ||
* 置换群 | * 置换群 | ||
* 拉格朗日定理 | * 拉格朗日定理 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第81行： | 第78行： | ||
| | | | ||
* 群同态、同构基本思想 | * 群同态、同构基本思想 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第94行： | 第90行： | ||
| | | | ||
* 布尔代数 | * 布尔代数 | ||
| − | |||
| − | |||
|- | |- | ||
| | | | ||
| 第117行： | 第111行： | ||
| | | | ||
* 数论算法的问题大小度量方式的特殊性 | * 数论算法的问题大小度量方式的特殊性 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第129行： | 第122行： | ||
| | | | ||
* 数论算法的核心作用 | * 数论算法的核心作用 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第151行： | 第143行： | ||
| | | | ||
* 如何有效地理解形式化描述？ | * 如何有效地理解形式化描述？ | ||
| − | |||
|- | |- | ||
| | | | ||
| 第162行： | 第153行： | ||
| | | | ||
* 归约在NPC理论中的意义 | * 归约在NPC理论中的意义 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第173行： | 第163行： | ||
| | | | ||
* 近似算法分类的基本参考指标以及意义 | * 近似算法分类的基本参考指标以及意义 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第184行： | 第173行： | ||
| | | | ||
* 正确性的概念与期望正确率的概念 | * 正确性的概念与期望正确率的概念 | ||
| − | |||
|- | |- | ||
| | | | ||
| 第195行： | 第183行： | ||
| | | | ||
* 如何从自然界获得灵感，以非常简单的思路改造算法 | * 如何从自然界获得灵感，以非常简单的思路改造算法 | ||
| − | + | } | |
2024年2月18日 (日) 16:55的版本
基本要求
- 掌握复杂性理论的基本内容与问题归约方法
- 掌握解决“难”问题的主要方法，理解相关的重要理论结果
- 程序设计能力
指定教材
- TJ: Thomas Judson: Abstract Algebra - Theory and Applications, 2018.
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- CS: Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
- JH: Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004
推荐课外读物
- Richard Lipton: The P=NP Question and Gödel's Lost Letter. Springer, 2010
考核方法
所有形式的考核,均不准抄袭。
| 考核形式 | 分值 |
|---|---|
| 作业 | 15 |
| OT | 10 |
| 编程 | 20 |
| 机试 | 15 |
| 笔试 | 40 |
学习周历
| 日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | |
|---|---|---|---|---|---|
| 4-1：群论初步 |
|
|
| ||
| 4-2：置换群与拉格朗日定理 |
|
|
| ||
| 4-3：正规子群与群同态基本定理 |
|
|
| ||
|
4-4: 布尔代数 |
|
|
| ||
| 4-5: 数论基础 |
|
|
|
||
| 4-6：数论算法 |
|
TC第31章第1、2、3、4、5、6节 |
| ||
| [4-7：密码算法] |
|
|
| ||
| 4-8：代数编码 |
|
|
|
||
| [4-8：问题的形式化描述] |
为严格的算法分析打下基础 |
|
| ||
| 4-9：NP完全理论初步 |
|
|
| ||
| [4-10：近似算法的基本概念] |
|
|
| ||
| [ 4-11：随机算法的概念] |
|
|
| ||
| [ 4-12：启发式算法] |
|
|
} |
