“2019级--学期安排 (第四学期)”的版本间的差异
(→学习周历) |
(→学习周历) |
||
第25行: | 第25行: | ||
! 引导要点 | ! 引导要点 | ||
! 书面作业 | ! 书面作业 | ||
− | |||
|- | |- | ||
| 2019-03-06 | | 2019-03-06 | ||
第49行: | 第48行: | ||
关于模p乘法构成 p-1 阶循环群。 | 关于模p乘法构成 p-1 阶循环群。 | ||
(此处的 1, 2, ..., p-1 是模p等价类代表元) | (此处的 1, 2, ..., p-1 是模p等价类代表元) | ||
+ | |- | ||
| | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
| [[Media:计算机问题求解-2017-群与拉格郎日定理.pptx | 4-3:置换群与拉格朗日定理 (OLD)]] | | [[Media:计算机问题求解-2017-群与拉格郎日定理.pptx | 4-3:置换群与拉格朗日定理 (OLD)]] | ||
| | | | ||
第77行: | 第69行: | ||
* TJ 第5章练习 5 (注: 只需列出S4的所有子群, 无需解(a)、(b)、(c))、16、29 | * TJ 第5章练习 5 (注: 只需列出S4的所有子群, 无需解(a)、(b)、(c))、16、29 | ||
* (''选做'') 证明: A_n 中的每个置换皆可表成形如 (k k+1 k+2) 的 3-cycle 的乘积。 | * (''选做'') 证明: A_n 中的每个置换皆可表成形如 (k k+1 k+2) 的 3-cycle 的乘积。 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-03-20 | | 2019-03-20 | ||
第109行: | 第94行: | ||
* (''选做'') 在同构意义下, 给出所有的六阶群。 | * (''选做'') 在同构意义下, 给出所有的六阶群。 | ||
(你可以再尝试给出所有的八阶群。) | (你可以再尝试给出所有的八阶群。) | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-03-27 | | 2019-03-27 | ||
第136行: | 第114行: | ||
* TC第32.3节练习 5 | * TC第32.3节练习 5 | ||
* (''选做'') TC第32.3节练习 4 | * (''选做'') TC第32.3节练习 4 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-04-09 | | 2019-04-09 | ||
第162行: | 第133行: | ||
* TJ第2章练习 29、30 | * TJ第2章练习 29、30 | ||
* CS第2.2节问题 19 | * CS第2.2节问题 19 | ||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-04-10 | | 2019-04-10 | ||
第192行: | 第159行: | ||
x = 11 (mod 20), | x = 11 (mod 20), | ||
x = 1 (mod 15) | x = 1 (mod 15) | ||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-04-17 | | 2019-04-17 | ||
第216行: | 第179行: | ||
* TC第31.7节练习 2 | * TC第31.7节练习 2 | ||
* (''选做'') TC第31章问题 4 | * (''选做'') TC第31章问题 4 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-04-24 | | 2019-04-24 | ||
第238行: | 第194行: | ||
'''课后作业(截止日期: 2019-04-27 22:00)''' | '''课后作业(截止日期: 2019-04-27 22:00)''' | ||
* TJ第8章练习 19、21、22、23 | * TJ第8章练习 19、21、22、23 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-05-08 | | 2019-05-08 | ||
第260行: | 第209行: | ||
'''课后作业(截止日期: 2019-05-04 22:00)''' | '''课后作业(截止日期: 2019-05-04 22:00)''' | ||
* 无 | * 无 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-05-15 | | 2019-05-15 | ||
第288行: | 第230行: | ||
* TC第34.5节练习 6 | * TC第34.5节练习 6 | ||
* (''选做'') TC第34.5节练习 2 | * (''选做'') TC第34.5节练习 2 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-05-22 | | 2019-05-22 | ||
第310行: | 第245行: | ||
'''课后作业(截止日期: 2019-05-25 22:00)''' | '''课后作业(截止日期: 2019-05-25 22:00)''' | ||
* JH第4章练习 4.2.3.3、4.2.3.4 | * JH第4章练习 4.2.3.3、4.2.3.4 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-06-05 | | 2019-06-05 | ||
第332行: | 第260行: | ||
'''课后作业(截止日期: 2019-06-01 22:00)''' | '''课后作业(截止日期: 2019-06-01 22:00)''' | ||
* JH第5章练习 5.2.2.8 | * JH第5章练习 5.2.2.8 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
| 2019-06-12 | | 2019-06-12 | ||
第356行: | 第271行: | ||
* 如何从自然界获得灵感,以非常简单的思路改造算法 | * 如何从自然界获得灵感,以非常简单的思路改造算法 | ||
| | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
| | | | ||
2021年2月24日 (三) 13:25的版本
基本要求
- 掌握复杂性理论的基本内容与问题归约方法
- 掌握解决“难”问题的主要方法,理解相关的重要理论结果
- 程序设计能力
指定教材
- 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
学习周历
日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | 书面作业 | |
---|---|---|---|---|---|---|
2019-03-06 | 4-2:群论初步 |
|
|
|
课前作业(截止日期: 2019-03-05 22:00)
TJ 第四章 4.6节、4.7节 关于 SageMath 的内容
课后作业(截止日期: 2019-03-09 22:00)
关于模p乘法构成 p-1 阶循环群。 (此处的 1, 2, ..., p-1 是模p等价类代表元) | |
4-3:置换群与拉格朗日定理 (OLD) |
|
|
|
课前作业(截止日期: 2019-03-12 22:00)
课后作业(截止日期: 2019-03-16 22:00)
| ||
2019-03-20 | 4-4:群同态基本定理与正规子群 |
|
|
|
课前作业(截止日期: 2019-03-19 22:00)
课后作业(截止日期: 2019-03-23 22:00)
(你可以再尝试给出所有的八阶群。) | |
2019-03-27 | 4-5:串匹配 |
|
|
|
课前作业(截止日期: 2019-03-26 22:00)
课后作业(截止日期: 2019-03-30 22:00)
| |
2019-04-09 | 4-6: 数论基础 |
|
|
|
课前作业(截止日期: 2019-04-02 22:00)
课后作业(截止日期: 2019-04-06 22:00)
| |
2019-04-10 | 4-7:数论算法 (OLD) |
|
TC第31章第1、2、3、4、5、6节 |
|
课前作业(截止日期: 2019-04-10 10:00)
课后作业(截止日期: 2019-04-13 22:00)
x = 3 (mod 8), x = 11 (mod 20), x = 1 (mod 15) | |
2019-04-17 | 4-8:密码算法 |
|
|
|
课前作业(截止日期: 2019-04-17 10:00)
课后作业(截止日期: 2019-04-20 22:00)
| |
2019-04-24 | 4-9:代数编码 |
|
|
|
课前作业(截止日期: 2019-04-25 22:00)
课后作业(截止日期: 2019-04-27 22:00)
| |
2019-05-08 | 4-10:问题的形式化描述 |
为严格的算法分析打下基础 |
|
|
课前作业(截止日期: 2019-05-01 22:00)
课后作业(截止日期: 2019-05-04 22:00)
| |
2019-05-15 | 4-11:NP完全理论初步 |
|
|
|
课前作业(截止日期: 2019-05-14 22:00)
课后作业(截止日期: 2019-05-18 22:00)
| |
2019-05-22 | 4-12:近似算法的基本概念 |
|
|
|
课前作业(截止日期: 2019-05-21 22:00)
课后作业(截止日期: 2019-05-25 22:00)
| |
2019-06-05 | 4-13:随机算法的概念 (OLD) |
|
|
|
课前作业(截止日期: 2019-05-28 22:00)
课后作业(截止日期: 2019-06-01 22:00)
| |
2019-06-12 | 4-14:启发式算法 |
|
|
|
||
2019-06-19 | 4-15:问题求解课程总复习 |
|
|
|
|
|