查看“2018级--学期安排 (第四学期)”的源代码

==基本要求==
<ul>
  <li>掌握复杂性理论的基本内容与问题规约方法。</li>
  <li>理解解决“难”问题的主要方法、技术以及相关的重要理论。</li>
</ul>
注意：程序设计能力要求贯穿于整个课程，不再单列。

==指定教材==
<ul>
  <li>'''JH''': Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004</li>
  <li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</li>
</ul>

==推荐课外读物==
<ul>
  <li>Richard Lipton: The P=NP Question and Gödel's Lost Letter. Springer, 2010</li>
</ul>

==学习周历==
<table border="1px">
  <tr>
    <th>日期</th>
    <th>论题</th>
    <th>学习目的</th>
    <th>阅读材料</th>
    <th>引导要点</th>
    <th>书面作业</th>
    <th>编程任务</th>
  </tr>
  <tr>
    <td>2.17--2.21</td>
    <td>4-1：问题的形式化描述</td>
    <td>
      <ul>
        <li>熟悉以基于集合的形式化方式描述问题以及相关的对象，为严格的算法分析打下基础</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第2章第3节第2小节定义2.3.2.1和2.3.2.2及相应的示例</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何有效地理解形式化描述？</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第2章练习2.3.1.7、2.3.1.8、2.3.3.8</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.01</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>2.24--2.28</td>
    <td>4-2：NP完全理论初步</td>
    <td>
      <ul>
        <li>理解如何按照问题难度对问题进行分类</li>
        <li>理解NPC的证明方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第34章第2节、第3节前3页、第5.1节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>规约在NPC理论中的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第34.2节练习3、4、6、11</li>
        <li>TC第34.3节练习2</li>
        <li>TC第34.5节练习6</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.02</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.2--3.6</td>
    <td>4-3：伪多项式算法</td>
    <td>
      <ul>
        <li>理解为什么若输入满足一定条件，则此条件有可能被利用来降低算法的复杂性</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第2节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何识别一个可利用的输入子集条件</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章练习3.3.2.7、3.3.2.8、3.3.2.9</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.03</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.9--3.13</td>
    <td>4-4：分支-界限算法</td>
    <td>
      <ul>
        <li>理解如何加快解空间搜索的速度，以至于算法复杂度得以降低</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第4节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何判断可以剪枝的条件</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章练习3.4.2.1、3.4.2.2</li>
        <li>采用branch-and-bound方法解背包问题，并分别给出对你的方法有利与不利的输入</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.04</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.16--3.20</td>
    <td>4-5：局部搜索算法</td>
    <td>
      <ul>
        <li>掌握通过局部搜索试图获得最优解的方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第6节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何合理定义邻集</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章练习3.6.1.3</li>
        <li>两道补充题（参见课件）</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.05</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.23--3.27</td>
    <td>4-6：松弛算法</td>
    <td>
      <ul>
        <li>掌握将整数规划问题转换为一般线性规划问题的解题途径</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第7节第1小节、第2小节的集合覆盖问题、第4小节的开头部分</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何从可能是非可行解得到需要的结果</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章练习3.7.2.1、3.7.2.4、3.7.2.5、3.7.4.4、3.7.4.12、3.7.4.16</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.06</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.30--4.3</td>
    <td>4-7：近似算法的基本概念</td>
    <td>
      <ul>
        <li>理解近似算法相关的基本概念</li>
        <li>理解近似算法的基本评价方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章第1节、第2节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何评价近似算法的质量</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章练习4.2.1.4、4.2.1.5、4.2.3.3、4.2.3.4、4.2.3.5</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.07</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.6--4.10</td>
    <td>4-8：覆盖问题与最大割集问题</td>
    <td>
      <ul>
        <li>通过点覆盖问题和集合覆盖问题理解贪心算法这类很“直观”的思想可能引导我们设计有效的近似算法解相对较难的问题</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章第3节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>基于“直觉”的思路可以产生明显的效果</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章练习4.3.2.3、4.3.2.6、4.3.2.9</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.08</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.13--4.17</td>
    <td>4-9：背包问题</td>
    <td>
      <ul>
        <li>理解PTAS的算法意义，并以背包问题为例理解如何针对一个相对容易的“难”问题找到好的算法(PTAS)</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章第3节第4小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何有效地利用多种概念与算法设计策略以达到效率的提高</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章练习4.3.4.9、4.3.4.13</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.09</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.20--4.24</td>
    <td>4-10：旅行推销商问题</td>
    <td>
      <ul>
        <li>以旅行推销商问题为例讨论对于“非常难”的问题如何针对某个有代表性的子问题找到有效解法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章第3节第5小节前半部分</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>算法的持续改进以及近似算法的稳定性概念在问题求解中的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>设计一个找最小完美匹配的算法</li>
        <li>JH第4章练习4.3.5.6、4.3.5.11、4.3.5.13</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.10</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.27--5.1</td>
    <td>4-11：Bin-Packing问题</td>
    <td>
      <ul>
        <li>以Bin-Packing问题为例，理解对偶近似方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章第3节第6小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>理解对偶在算法设计中的意义与效果</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第4章练习4.3.6.6</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.11</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.4--5.8</td>
    <td>4-12：随机算法的概念</td>
    <td>
      <ul>
        <li>理解与随机算法相关的基本概念</li>
        <li>理解随机算法的基本评价方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第5章第2节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>正确性的概念与期望正确率的概念</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.12</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.11--5.15</td>
    <td>4-13：素性判定和Abundance of Witnesses</td>
    <td>
      <ul>
        <li>理解Abundance of Witnesses在随机算法设计中的应用</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第5章第3节第3小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>为什么“乱猜”也是一种算法设计方法</li>
        <li>如何利用数学知识减少false witness</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.13</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.18--5.22</td>
    <td>4-14：等价测试问题</td>
    <td>
      <ul>
        <li>以多项式等价测试为例理解随机算法设计中的指纹方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第5章第3节第4小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>问题的转移</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.14</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.25--5.29</td>
    <td>4-15：最小割集问题</td>
    <td>
      <ul>
        <li>以最小割集为例理解如何用随机算法解优化问题</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第5章第3节第5小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>随机算法用于优化问题与用于判定问题的差别</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.15</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>6.1--6.5</td>
    <td>4-16：不同方法结合使用</td>
    <td>
      <ul>
        <li>通过Max-Sat问题理解如何将随机算法和优化算法很好地结合起来，以达到效率与解质量的权衡</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第5章第3节第6小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>多种方法的结合使用</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.16</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>6.8--6.12</td>
    <td>4-17：去随机方法</td>
    <td>
      <ul>
        <li>理解并掌握去随机的基本方法，结合应用场景，可能可以在输入空间的一个子集上将随机算法改为确定算法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第5章第4节第2、3小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何找合适的输入子集合</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.17</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>暑假自学</td>
    <td>4-18：启发式算法</td>
    <td>
      <ul>
        <li>通过典型的模拟淬火算法，理解启发式算法的基本概念、其价值以及局限性</li>
        <li>理解遗传算法的基本思想及其适用性</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第6章第2节第1、2小节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何从自然界获得灵感，以非常简单的思路改造算法</li>
      </ul>
    </td>
    <td>
      <ul>
      </ul>
    </td>
    <td>
      <ul>
        <li>附录A.18</li>
      </ul>
    </td>
  </tr>
</table>
[http://cslabcms.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:2012%E7%BA%A7--%E5%AD%A6%E6%9C%9F%E5%AE%89%E6%8E%92_(%E7%AC%AC%E5%9B%9B%E5%AD%A6%E6%9C%9F)--%E9%99%84%E5%BD%95A.pdf 附录A]