“2018级--学期安排 (第四学期)”的版本间的差异

来自问题求解
跳转至： 导航、 搜索
（→‎学习周历）
（→‎学习周历）
第78行： 第78行：
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
 +
        <li>TC第34.2节练习3、4、6、11</li>
 +
        <li>TC第34.3节练习2</li>
 +
        <li>TC第34.5节练习6</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>

2020年2月24日 (一) 12:03的版本

基本要求

  • 掌握复杂性理论的基本内容与问题规约方法。
  • 理解解决“难”问题的主要方法、技术以及相关的重要理论。

注意：程序设计能力要求贯穿于整个课程，不再单列。

指定教材

  • JH: Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004
  • TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009

推荐课外读物

  • Richard Lipton: The P=NP Question and Gödel's Lost Letter. Springer, 2010

学习周历

日期 论题 学习目的 阅读材料 引导要点 书面作业 编程任务
2.17--2.21 4-1：问题的形式化描述
  • 熟悉以基于集合的形式化方式描述问题以及相关的对象，为严格的算法分析打下基础
  • JH第2章第3节第2小节定义2.3.2.1和2.3.2.2及相应的示例
  • 如何有效地理解形式化描述？
  • 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章第2节、第3节前3页、第5.1节
  • 规约在NPC理论中的意义
  • TC第34.2节练习3、4、6、11
  • TC第34.3节练习2
  • TC第34.5节练习6
  • 附录A.02
3.2--3.6 4-3：伪多项式算法
  • 理解为什么若输入满足一定条件，则此条件有可能被利用来降低算法的复杂性
  • JH第3章第2节第1、2小节
  • 如何识别一个可利用的输入子集条件
  • 附录A.03
3.9--3.13 4-4：分支-界限算法
  • 理解如何加快解空间搜索的速度，以至于算法复杂度得以降低
  • JH第3章第4节第1、2小节
  • 如何判断可以剪枝的条件
  • 附录A.04
3.16--3.20 4-5：局部搜索算法
  • 掌握通过局部搜索试图获得最优解的方法
  • JH第3章第6节第1、2小节
  • 如何合理定义邻集
  • 附录A.05
3.23--3.27 4-6：松弛算法
  • 掌握将整数规划问题转换为一般线性规划问题的解题途径
  • JH第3章第7节第1小节、第2小节的集合覆盖问题、第4小节的开头部分
  • 如何从可能是非可行解得到需要的结果
  • 附录A.06
3.30--4.3 4-7：近似算法的基本概念
  • 理解近似算法相关的基本概念
  • 理解近似算法的基本评价方法
  • JH第4章第1节、第2节第1、2小节
  • 如何评价近似算法的质量
  • 附录A.07
4.6--4.10 4-8：覆盖问题与最大割集问题
  • 通过点覆盖问题和集合覆盖问题理解贪心算法这类很“直观”的思想可能引导我们设计有效的近似算法解相对较难的问题
  • JH第4章第3节第1、2小节
  • 基于“直觉”的思路可以产生明显的效果
  • 附录A.08
4.13--4.17 4-9：背包问题
  • 理解PTAS的算法意义，并以背包问题为例理解如何针对一个相对容易的“难”问题找到好的算法(PTAS)
  • JH第4章第3节第4小节
  • 如何有效地利用多种概念与算法设计策略以达到效率的提高
  • 附录A.09
4.20--4.24 4-10：旅行推销商问题
  • 以旅行推销商问题为例讨论对于“非常难”的问题如何针对某个有代表性的子问题找到有效解法
  • JH第4章第3节第5小节前半部分
  • 算法的持续改进以及近似算法的稳定性概念在问题求解中的意义
  • 附录A.10
4.27--5.1 4-11：Bin-Packing问题
  • 以Bin-Packing问题为例，理解对偶近似方法
  • JH第4章第3节第6小节
  • 理解对偶在算法设计中的意义与效果
  • 附录A.11
5.4--5.8 4-12：随机算法的概念
  • 理解与随机算法相关的基本概念
  • 理解随机算法的基本评价方法
  • JH第5章第2节第1、2小节
  • 正确性的概念与期望正确率的概念
  • 附录A.12
5.11--5.15 4-13：素性判定和Abundance of Witnesses
  • 理解Abundance of Witnesses在随机算法设计中的应用
  • JH第5章第3节第3小节
  • 为什么“乱猜”也是一种算法设计方法
  • 如何利用数学知识减少false witness
  • 附录A.13
5.18--5.22 4-14：等价测试问题
  • 以多项式等价测试为例理解随机算法设计中的指纹方法
  • JH第5章第3节第4小节
  • 问题的转移
  • 附录A.14
5.25--5.29 4-15：最小割集问题
  • 以最小割集为例理解如何用随机算法解优化问题
  • JH第5章第3节第5小节
  • 随机算法用于优化问题与用于判定问题的差别
  • 附录A.15
6.1--6.5 4-16：不同方法结合使用
  • 通过Max-Sat问题理解如何将随机算法和优化算法很好地结合起来，以达到效率与解质量的权衡
  • JH第5章第3节第6小节
  • 多种方法的结合使用
  • 附录A.16
6.8--6.12 4-17：去随机方法
  • 理解并掌握去随机的基本方法，结合应用场景，可能可以在输入空间的一个子集上将随机算法改为确定算法
  • JH第5章第4节第2、3小节
  • 如何找合适的输入子集合
  • 附录A.17
暑假自学 4-18：启发式算法
  • 通过典型的模拟淬火算法，理解启发式算法的基本概念、其价值以及局限性
  • 理解遗传算法的基本思想及其适用性
  • JH第6章第2节第1、2小节
  • 如何从自然界获得灵感，以非常简单的思路改造算法
  • 附录A.18

附录A

取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2018级--学期安排_(第四学期)&oldid=3673”