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

来自问题求解
跳转至： 导航、 搜索
（→‎学习周历）
（→‎学习周历）
第209行： 第209行：
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>JH第3章第1、2节</li>
+
         <li>JH第4章第1、2节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第215行： 第215行：
 
       <ul>
 
       <ul>
 
         <li>近似算法分类的基本参考指标以及意义</li>
 
         <li>近似算法分类的基本参考指标以及意义</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li></li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li></li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>4.7--4.11</td>
 +
    <td>4-8：覆盖问题与最大割集问题</td>
 +
    <td>
 +
      <ul>
 +
        <li>通过覆盖问题与最大割集的例子理解将贪心算法与松弛算法结合进行问题求解的方法</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第4章第3节第1、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>4.14--4.18</td>
 +
    <td>4-9：背包问题</td>
 +
    <td>
 +
      <ul>
 +
        <li>以背包问题为例理解如何针对一个相对容易的“难”问题找到好的算法（PTAS）</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第4章第3节第4小节</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>如何有效地利用多种概念与算法设计策略以达到效率的提高</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li></li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li></li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>4.21--4.25</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>
 +
        <li>理解近似算法的问题性以及其在问题求解中的意义</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>

2014年2月16日 (日) 11:27的版本

基本要求

  • 掌握复杂性理论的基本内容与问题规约方法。
  • 掌握解决“难”问题的主要方法，理解相关的重要理论结果。

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

指定教材

  • 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

学习周历

日期 论题 学习目的 阅读材料 引导要点 书面作业 编程任务
2.17--2.21 4-1：问题的形式化描述
  • 熟悉以基于集合的形式化方式描述问题以及相关的对象，为严格的算法分析打下基础
  • JH第2章第3节
  • 如何有效地理解形式化描述？
2.24--2.28 4-2：NP完全理论初步
  • 理解如何按照问题难度对问题进行分类
  • 理解NPC的证明方法
  • TC第34章
  • 规约在NPC理论中的意义
3.3--3.7 4-3：伪多项式算法
  • 理解为什么若输入满足一定条件，则此条件有可能被利用来降低算法的复杂性
  • JH第3章第2、3节
  • 如何识别一个可利用的输入子集条件
3.10--3.14 4-4：分支-界限算法
  • 理解如何加快解空间搜索的速度，以至于算法复杂度得以降低
  • JH第3章第4、5节
  • 如何判断可以剪枝的条件
3.17--3.21 4-5：局部搜索算法
  • 掌握通过局部搜索试图获得最优解的方法
  • JH第3章第6节
  • 如何合理定义邻集
3.24--3.28 4-6：松弛算法
  • 掌握将整数规划问题转换为一般线性规划问题的解题途径
  • JH第3章第7节
  • 如何从可能是非可行解得到需要的结果
3.31--4.4 4-7：近似算法的基本概念
  • 理解与近似算法相关的基本概念
  • 理解近似算法的基本评价方法
  • JH第4章第1、2节
  • 近似算法分类的基本参考指标以及意义
4.7--4.11 4-8：覆盖问题与最大割集问题
  • 通过覆盖问题与最大割集的例子理解将贪心算法与松弛算法结合进行问题求解的方法
  • JH第4章第3节第1、2、3小节
  • 基于“直觉”的思路可以产生明显的效果
4.14--4.18 4-9：背包问题
  • 以背包问题为例理解如何针对一个相对容易的“难”问题找到好的算法（PTAS）
  • JH第4章第3节第4小节
  • 如何有效地利用多种概念与算法设计策略以达到效率的提高
4.21--4.25 4-10：旅行推销商问题
  • 以旅行推销商问题为例理解最难的一类优化问题的处理方法
  • JH第4章第3节第5小节
  • 如何对算法进行不断改进
  • 理解近似算法的问题性以及其在问题求解中的意义
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--学期安排_(第四学期)&oldid=714”