“2021级--学期安排(第四学期)”的版本间的差异
来自问题求解
(→学习周历) |
(→学习周历) |
||
(未显示同一用户的34个中间版本) | |||
第15行: | 第15行: | ||
* Richard Lipton: The P=NP Question and Gödel's Lost Letter. Springer, 2010 | * Richard Lipton: The P=NP Question and Gödel's Lost Letter. Springer, 2010 | ||
+ | |||
+ | == 考核方法 == | ||
+ | |||
+ | 所有形式的考核,均不准抄袭。 | ||
+ | |||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! 考核形式 !! 分值 | ||
+ | |- | ||
+ | | 作业 || 15 | ||
+ | |- | ||
+ | | OT || 10 | ||
+ | |- | ||
+ | | 编程 || 20 | ||
+ | |- | ||
+ | | 机试 || 15 | ||
+ | |- | ||
+ | | 笔试 || 40 | ||
+ | |} | ||
==学习周历== | ==学习周历== | ||
第45行: | 第64行: | ||
2-15 | 2-15 | ||
| | | | ||
− | 3-16:线性规划 | + | [https://box.nju.edu.cn/f/0109a8e491104a698681/?dl=1 3-16:线性规划] |
| | | | ||
* 掌握线性规划的基本概念、问题描述方式以及基本算法 | * 掌握线性规划的基本概念、问题描述方式以及基本算法 | ||
第57行: | 第76行: | ||
|- | |- | ||
| | | | ||
− | | 4-1:群论初步 | + | 3-1 |
+ | | [https://box.nju.edu.cn/f/145b1cdd802e43a09f24/?dl=1 4-1:群论初步] | ||
| | | | ||
* 理解抽象代数结构的基本概念 | * 理解抽象代数结构的基本概念 | ||
第65行: | 第85行: | ||
| | | | ||
* 公理化系统的思想 | * 公理化系统的思想 | ||
− | | 4-1-group.zip | + | | [[media:2021-4-1-group.zip|4-1-group.zip]] |
| | | | ||
|- | |- | ||
| | | | ||
− | | 4-2:置换群与拉格朗日定理 | + | 3-8 |
+ | | [https://box.nju.edu.cn/f/17c28317759c4789ad95/?dl=1 4-2:置换群与拉格朗日定理] | ||
| | | | ||
* 理解抽象代数结构的基本概念 | * 理解抽象代数结构的基本概念 | ||
第78行: | 第99行: | ||
* 置换群 | * 置换群 | ||
* 拉格朗日定理 | * 拉格朗日定理 | ||
− | | 4-2-permutation-group-and-lagrange-theorem.zip | + | | [https://box.nju.edu.cn/f/c341a89c3fac4f92af37/?dl=1 4-2-permutation-group-and-lagrange-theorem.zip] |
|- | |- | ||
| | | | ||
− | | 4-3:群同态基本定理与正规子群 | + | 3-15 |
+ | | [https://box.nju.edu.cn/f/04d41a925ee24183bf1e/?dl=1 4-3:群同态基本定理与正规子群] | ||
| | | | ||
* 理解抽象代数结构的基本概念 | * 理解抽象代数结构的基本概念 | ||
第89行: | 第111行: | ||
| | | | ||
* 群同态、同构基本思想 | * 群同态、同构基本思想 | ||
− | |4-3-group-isomorphism-and-normal-subgroups.zip | + | |[https://box.nju.edu.cn/f/19a3466ea7c14be49f47/?dl=1 4-3-group-isomorphism-and-normal-subgroups.zip ] |
| | | | ||
|- | |- | ||
| | | | ||
− | | 4-4: 数论基础 | + | 3-22 |
+ | | [https://box.nju.edu.cn/f/356498e62bc54e208efd/?dl=1 4-4: 数论基础] | ||
| | | | ||
* 掌握数论的基础知识 | * 掌握数论的基础知识 | ||
第102行: | 第125行: | ||
| | | | ||
* 模算术的概念与处理方法在数论中的应用 | * 模算术的概念与处理方法在数论中的应用 | ||
− | |4-4-number-theory.zip | + | | [https://box.nju.edu.cn/f/01051905efc4443189ef/?dl=1 4-4-number-theory.zip] |
|- | |- | ||
− | | | + | | 3-29 |
− | | 4-5:数论算法 | + | | [https://box.nju.edu.cn/f/b57ffb5796b8484d8004/?dl=1 4-5:数论算法] |
| | | | ||
* 掌握数论中一些基本问题的算法 | * 掌握数论中一些基本问题的算法 | ||
第112行: | 第135行: | ||
| | | | ||
* 数论算法的问题大小度量方式的特殊性 | * 数论算法的问题大小度量方式的特殊性 | ||
− | |4-5-algorithms-of-number-theory.zip | + | |[https://box.nju.edu.cn/f/7b96d40445204068a9c9/?dl=1 4-5-algorithms-of-number-theory.zip] |
|- | |- | ||
− | | | + | | 4-03 |
− | | | + | | [https://box.nju.edu.cn/f/daacfc5798544c579daf/?dl=1 4-6:密码算法] |
| | | | ||
* 掌握公钥密码系统的基本原理 | * 掌握公钥密码系统的基本原理 | ||
第124行: | 第147行: | ||
| | | | ||
* 数论算法的核心作用 | * 数论算法的核心作用 | ||
− | |4-6-encription.zip | + | |[https://box.nju.edu.cn/f/fa0e3052b4334681a77f/?dl=1 4-6-encription.zip] |
|- | |- | ||
− | | | + | | 4-19 |
− | | 4-7:代数编码 | + | | [https://box.nju.edu.cn/f/214c19d6dbb54c63ae41/?dl=1 4-7:代数编码] |
| | | | ||
* 理解如何能建立利于查错,纠错的编码系统 | * 理解如何能建立利于查错,纠错的编码系统 | ||
第135行: | 第158行: | ||
| | | | ||
* 群的性质如何保证编码系统的性质 | * 群的性质如何保证编码系统的性质 | ||
− | |4-7- | + | |[https://box.nju.edu.cn/f/768b2f426f4746b3952e/?dl=1 4-7-encoding.zip] |
|- | |- | ||
− | | | + | | 5-10 |
− | | 4-8:问题的形式化描述 | + | | [https://box.nju.edu.cn/f/b6150eade1584af59ce4/?dl=1 4-8:问题的形式化描述] |
| | | | ||
* 掌握问题的形式化描述方法, | * 掌握问题的形式化描述方法, | ||
第146行: | 第169行: | ||
| | | | ||
* 如何有效地理解形式化描述? | * 如何有效地理解形式化描述? | ||
− | |[ | + | |[https://box.nju.edu.cn/f/fce7937cd62b4a2f9b2a/?dl=1 4-8-Formalization.zip] |
|- | |- | ||
− | | | + | | 5-17 |
− | | 4-9:NP完全理论初步 | + | | [[media:计算机问题求解-2021-5-7-NP完全性.pptx | 4-9:NP完全理论初步]] |
| | | | ||
* 理解如何按照问题难度对问题进行分类 | * 理解如何按照问题难度对问题进行分类 | ||
第157行: | 第180行: | ||
| | | | ||
* 归约在NPC理论中的意义 | * 归约在NPC理论中的意义 | ||
− | |4-9-NP-completeness.zip | + | |[https://box.nju.edu.cn/f/55932cfe8e934fdb9a17/?dl=1 4-9-NP-completeness.zip] |
|- | |- | ||
− | | | + | | 5-24 |
− | | 4-10:近似算法的基本概念 | + | | [https://box.nju.edu.cn/f/cd4b44ac2c524ab08f72/?dl=1 4-10:近似算法的基本概念] |
| | | | ||
* 理解近似算法相关的基本概念 | * 理解近似算法相关的基本概念 | ||
第169行: | 第192行: | ||
* 近似算法分类的基本参考指标以及意义 | * 近似算法分类的基本参考指标以及意义 | ||
| | | | ||
− | 4-10-approximation-algorithm.zip | + | [https://box.nju.edu.cn/f/3f88e5ac0f284534a84d/?dl=1 4-10-approximation-algorithm.zip] |
|- | |- | ||
− | | | + | | 5-31 |
− | | 4-11:随机算法的概念 | + | | [https://box.nju.edu.cn/f/796624f941054352849e/?dl=1 4-11:随机算法的概念] |
| | | | ||
* 理解与随机算法相关的基本概念 | * 理解与随机算法相关的基本概念 | ||
第181行: | 第204行: | ||
* 正确性的概念与期望正确率的概念 | * 正确性的概念与期望正确率的概念 | ||
| | | | ||
− | 4-11-randomized-algorithm.zip | + | [https://box.nju.edu.cn/f/583cbd4d265948bea8d2/?dl=1 4-11-randomized-algorithm.zip] |
|- | |- | ||
− | | | + | | 6-7 |
− | | 4-12:启发式算法 | + | | [https://box.nju.edu.cn/f/6eb5ed6c52e6456a9cd5/?dl=1 4-12:启发式算法] |
| | | | ||
* 通过模拟退火算法理解启发式算法的基本概念、价值以及局限性 | * 通过模拟退火算法理解启发式算法的基本概念、价值以及局限性 | ||
第193行: | 第216行: | ||
* 如何从自然界获得灵感,以非常简单的思路改造算法 | * 如何从自然界获得灵感,以非常简单的思路改造算法 | ||
| | | | ||
− | 4-12-heuristic-algorithms.zip | + | [https://box.nju.edu.cn/f/19aa9d4701c041d0bafc/?dl=1 4-12-heuristic-algorithms.zip] |
|- | |- | ||
| | | |
2023年6月17日 (六) 15:01的最新版本
基本要求
- 掌握复杂性理论的基本内容与问题归约方法
- 掌握解决“难”问题的主要方法,理解相关的重要理论结果
- 程序设计能力
指定教材
- 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 |
|
|
|
|
|