2013级--学期安排 (第四学期)

学习周历

</tr> </tr>

tbd	4-1x：数论基础	掌握数论的基础知识，理解典型的数论问题及其解决思路	TJ第2章 CS第2章第2节	模算术的概念与处理方法在数论中的应用	TJ第2章练习13、14、15、16、19、22、28、29、30、31 TJ第2章编程练习1、3 CS第2.2节问题2、4、6、8、15、16、17、19	WS第13章项目3 WS第13章项目8
tbd	4-1x：数论算法	掌握数论中一些基本问题的算法	TC第31章第1、2、3、4、5、8节	数论算法的问题大小度量方式的特殊性	TC第31.1节练习12、13 TC第31.2节练习4、5、6、9 TC第31.3节练习5 TC第31.4节练习2、3 TC第31.5节练习2、3 TC第31.6节练习2、3	实现解模线性方程组的程序 实现两个任意长度整数精确相乘的程序
tbd	4-1x：密码算法	掌握公钥密码系统的基本原理 理解其中核心的数论算法	TJ第7章 TC第31章第7、9节	数论算法的核心作用	TJ第7章练习3、7、9、12 TC第31.7节练习1、2 TC第31章问题2、3	实现Miller-Rabin算法 如果有兴趣，尝试了解与实现ASK算法
tbd	3-1x：代数编码	理解如何能建立利于查错，纠错的编码系统 理解抽象代数的应用意义	TJ第8章	群的性质如何保证编码系统的性质	TJ第8章练习6、7、8、9、11、13、18、19、21、22、23	WS第16章项目6
tbd	4-1x：串匹配	掌握最常用的字符串匹配算法	TC第32章	匹配算法的原理及其适用性	TC第32.1节练习2、3、4 TC第32.2节练习1、2、3、4 TC第32.3节练习2、3、5	KMP算法，比较普通文本与由5个符号组成的很长的串上效率的差异
日期	论题	学习目的	阅读材料	引导要点	书面作业	编程任务
2.17--2.21	4-1：问题的形式化描述	熟悉以基于集合的形式化方式描述问题以及相关的对象，为严格的算法分析打下基础	JH第2章第3节	如何有效地理解形式化描述？	JH第2章练习2.3.1.7、2.3.1.8、2.3.3.8	附录A.01
2.24--2.28	4-2：NP完全理论初步	理解如何按照问题难度对问题进行分类 理解NPC的证明方法	TC第34章	规约在NPC理论中的意义	TC第34.1节练习2、3、5 TC第34.2节练习3、4、6、11 TC第34.3节练习2 TC第34.4节练习3、5、7 TC第34.5节练习6	附录A.02
3.3--3.7	4-3：伪多项式算法	理解为什么若输入满足一定条件，则此条件有可能被利用来降低算法的复杂性	JH第3章第2、3节	如何识别一个可利用的输入子集条件	JH第3章练习3.3.2.7、3.3.2.8、3.3.2.9	附录A.03
3.10--3.14	4-4：分支-界限算法	理解如何加快解空间搜索的速度，以至于算法复杂度得以降低	JH第3章第4、5节	如何判断可以剪枝的条件	JH第3章练习3.4.2.1、3.4.2.2、3.5.2.3 采用branch-and-bound方法解背包问题，并分别给出对你的方法有利与不利的输入	附录A.04
3.17--3.21	4-5：局部搜索算法	掌握通过局部搜索试图获得最优解的方法	JH第3章第6节	如何合理定义邻集	JH第3章练习3.6.1.3 如果一个局部搜索算法给出的解一定是全局最优解，则这个算法称为“精确局部搜索算法”：(1)证明解TSP的2-exchange不是精确的。(2)证明解TSP的(n-1)-exchange是精确的。 带权图的最大边割集问题……（参见课件）	附录A.05
3.24--3.28	4-6：松弛算法	掌握将整数规划问题转换为一般线性规划问题的解题途径	JH第3章第7节	如何从可能是非可行解得到需要的结果	JH第3章练习3.4.2.1、3.7.2.4、3.7.2.5、3.7.4.4、3.7.4.12、3.7.4.16	附录A.06
3.31--4.4	4-7：近似算法的基本概念	理解近似算法相关的基本概念 理解近似算法的基本评价方法	JH第4章第1、2节	近似算法分类的基本参考指标以及意义	JH第4章练习4.2.1.4、4.2.1.5、4.2.3.3、4.2.3.4、4.2.3.5	附录A.07
4.7--4.11	4-8：覆盖问题与最大割集问题	通过覆盖问题与最大割集的例子理解将贪心算法与松弛算法结合进行问题求解的方法	JH第4章第3节第1、2、3小节	基于“直觉”的思路可以产生明显的效果	JH第4章练习4.3.2.3、4.3.2.6、4.3.2.9、4.3.3.5、4.3.3.6	附录A.08
4.14--4.18	4-9：背包问题	以背包问题为例理解如何针对一个相对容易的“难”问题找到好的算法（PTAS）	JH第4章第3节第4小节	如何有效地利用多种概念与算法设计策略以达到效率的提高	完整地写出MOD-SKP是解KP_delta的PTAS的证明 JH第4章练习4.3.4.9、4.3.4.13	附录A.09
4.21--4.25	4-10：旅行推销商问题	以旅行推销商问题为例理解最难的一类优化问题的处理方法	JH第4章第3节第5小节	如何对算法进行不断改进 理解近似算法的问题性以及其在问题求解中的意义	JH第4章练习4.3.5.6、4.3.5.7、4.3.5.11、4.3.5.13	附录A.10
4.28--5.2	4-11：Bin-Packing问题	以Bin-Packing问题为例，理解对偶近似方法	JH第4章第3节第6小节	理解对偶在算法设计中的意义与效果	JH第4章练习4.3.6.6	附录A.11
5.5--5.9	4-12：随机算法的概念	理解与随机算法相关的基本概念 理解随机算法的基本评价方法	JH第5章第1、2节	正确性的概念与期望正确率的概念	JH第5章练习5.2.2.7、5.2.2.8	附录A.12
5.12--5.16	4-13：Random Sampling和Abundance of Witnesses	理解Random Sampling和Abundance of Witnesses在随机算法设计中的应用	JH第5章第3节第1、2、3小节	为什么“乱猜”也是一种算法设计方法 如何利用数学知识减少false witness	JH第5章练习5.3.2.5、5.3.3.3、5.3.3.9、5.3.3.10、5.3.3.17	附录A.13
5.19--5.23	4-14：等价测试问题	以多项式等价测试为例理解随机算法设计中的指纹方法	JH第5章第3节第4小节	问题的转移	JH第2章练习2.2.3.21、2.2.3.22 JH第5章练习5.3.4.12	附录A.14
5.26--5.30	4-15：最小割集问题	以最小割集为例理解如何用随机算法解优化问题	JH第5章第3节第5小节	随机算法用于优化问题与用于判定问题的差别	JH第5章练习5.3.5.9、5.3.5.10	附录A.15
6.2--6.6	4-16：不同方法结合使用	通过Max-Sat问题理解如何将随机算法和优化算法很好地结合起来，以达到效率与解质量的权衡	JH第5章第3节第6、7小节	多种方法的结合使用	推导409页的第一个公式。 分别用k=3和k=10，各随机生成10个不同的input instances，比较RSMS和RRRMS两个算法的执行效果。	附录A.16
6.9--6.13	4-17：去随机方法	理解并掌握去随机的基本方法，结合应用场景，可能可以在输入空间的一个子集上将随机算法改为确定算法	JH第5章第4节	如何找合适的输入子集合	JH第5章练习5.4.2.3、5.4.2.4、5.4.3.2、5.4.3.3	附录A.17
6.16--6.20	4-18：启发式算法	通过典型的模拟淬火算法，理解启发式算法的基本概念、其价值以及局限性 理解遗传算法的基本思想及其适用性	JH第6章	如何从自然界获得灵感，以非常简单的思路改造算法	列出这学期讨论的典型“难题”，在每个题目下列出可能采用的解法，并比较解的质量与代价。	附录A.18