2023级--学期安排 (第四学期)
来自问题求解
基本要求
- 掌握复杂性理论的基本内容与问题归约方法
- 掌握解决“难”问题的主要方法,理解相关的重要理论结果
- 程序设计能力
指定教材
- 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 |
学习周历
* open-topic 报名链接 * open-topic 报名结果查询 * open-topic 分班查询 * open-topic 报告分配查询
* open-topic (ppt)上传链接 * open-topic (录像)上传链接 * open-topic (报告)上传链接 注意事项: * 文件命名规则:学号_姓名_论题序号_OT序号。例如,“99149102_张三_3_OT1” 表示学号为99149102的张三做论题4-3的OT1。
日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 |
---|---|---|---|---|
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:启发式算法 |
|
|
|