2021级--学期安排（第四学期）
来自问题求解
基本要求
- 掌握复杂性理论的基本内容与问题归约方法
- 掌握解决“难”问题的主要方法，理解相关的重要理论结果
- 程序设计能力
指定教材
- 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 |
学习周历
| 日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | 作业 | 编程训练 |
|---|---|---|---|---|---|---|
|
2-13 |
|
|
|
| ||
|
2-15 |
|
|
|
|||
|
3-1 |
4-1：群论初步 |
|
|
|
4-1-group.zip | |
|
3-8 |
4-2：置换群与拉格朗日定理 |
|
|
|
4-2-permutation-group-and-lagrange-theorem.zip | |
|
3-15 |
4-3：群同态基本定理与正规子群 |
|
|
|
4-3-group-isomorphism-and-normal-subgroups.zip | |
|
3-22 |
4-4: 数论基础 |
|
|
|
4-4-number-theory.zip | |
| 3-29 | 4-5：数论算法 |
|
TC第31章第1、2、3、4、5、6节 |
|
4-5-algorithms-of-number-theory.zip | |
| 4-03 | 4-6：密码算法 |
|
|
|
4-6-encription.zip | |
| 4-19 | 4-7：代数编码 |
|
|
|
4-7-encoding.zip | |
| 5-10 | 4-8：问题的形式化描述 |
为严格的算法分析打下基础 |
|
|
4-8-Formalization.zip | |
| 5-17 | 4-9：NP完全理论初步 |
|
|
|
4-9-NP-completeness.zip | |
| 5-24 | 4-10：近似算法的基本概念 |
|
|
|
||
| 5-31 | 4-11：随机算法的概念 |
|
|
|
||
| 6-7 | 4-12：启发式算法 |
|
|
|
||
| 4-13：总复习之形式化和建模 |
|
|
|
|
| |
| 4-14：总复习之数据结构与算法.pptx |
|
|
|
|
|
