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

==基本要求==
<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>

==学习周历==
<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节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何有效地理解形式化描述？</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></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章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>规约在NPC理论中的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.3--3.7</td>
    <td>4-3：伪多项式算法</td>
    <td>
      <ul>
        <li>理解为什么若输入满足一定条件，则此条件有可能被利用来降低算法的复杂性</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第2、3节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何识别一个可利用的输入子集条件</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.10--3.14</td>
    <td>4-4：分支-界限算法</td>
    <td>
      <ul>
        <li>理解如何加快解空间搜索的速度，以至于算法复杂度得以降低</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第4、5节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何判断可以剪枝的条件</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.17--3.21</td>
    <td>4-5：局部搜索算法</td>
    <td>
      <ul>
        <li>掌握通过局部搜索试图获得最优解的方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第6节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何合理定义邻集</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.24--3.28</td>
    <td>4-6：松弛算法</td>
    <td>
      <ul>
        <li>掌握将整数规划问题转换为一般线性规划问题的解题途径</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第7节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何从可能是非可行解得到需要的结果</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.31--4.4</td>
    <td>4-7：近似算法的基本概念</td>
    <td>
      <ul>
        <li>理解与近似算法相关的基本概念</li>
        <li>理解近似算法的基本评价方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH第3章第1、2节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>近似算法分类的基本参考指标以及意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
  </tr>
</table>