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

来自问题求解
跳转至： 导航、 搜索
第162行： 第162行：
 
     </td>
 
     </td>
 
   </tr>
 
   </tr>
 +
<tr>
 +
    <th>日期</th>
 +
    <th>论题</th>
 +
    <th>学习目的</th>
 +
    <th>阅读材料</th>
 +
    <th>引导要点</th>
 +
    <th>书面作业</th>
 +
    <th>编程任务</th>
 +
  </tr>
 +
  <tr>
 +
    <td>2.17--2.21</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/4/45/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-02-18-%E9%97%AE%E9%A2%98%E7%9A%84%E5%BD%A2%E5%BC%8F%E5%8C%96%E6%8F%8F%E8%BF%B0.pdf 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>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>[http://cslab.nju.edu.cn/problem_solving/images/f/f8/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-02-25-NP%E5%AE%8C%E5%85%A8%E7%90%86%E8%AE%BA%E5%88%9D%E6%AD%A5.pdf 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>TC第34.1节练习2、3、5</li>
 +
        <li>TC第34.2节练习3、4、6、11</li>
 +
        <li>TC第34.3节练习2</li>
 +
        <li>TC第34.4节练习3、5、7</li>
 +
        <li>TC第34.5节练习6</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.02</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>3.3--3.7</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/f/fb/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-03-04-%E4%BC%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E7%AE%97%E6%B3%95.pdf 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>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.10--3.14</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/b/b4/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-03-11-%E5%88%86%E6%94%AF%E7%95%8C%E9%99%90%E7%AE%97%E6%B3%95.pdf 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>JH第3章练习3.4.2.1、3.4.2.2、3.5.2.3</li>
 +
        <li>采用branch-and-bound方法解背包问题，并分别给出对你的方法有利与不利的输入</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.04</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>3.17--3.21</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/1/10/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-03-18-%E5%B1%80%E9%83%A8%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95.pdf 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>JH第3章练习3.6.1.3</li>
 +
        <li>如果一个局部搜索算法给出的解一定是全局最优解，则这个算法称为“精确局部搜索算法”：(1)证明解TSP的2-exchange不是精确的。(2)证明解TSP的(n-1)-exchange是精确的。</li>
 +
        <li>带权图的最大边割集问题……（参见课件）</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.05</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>3.24--3.28</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/3/3e/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-03-25-%E6%9D%BE%E5%BC%9B%E7%AE%97%E6%B3%95.pdf 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>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</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.06</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>3.31--4.4</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/3/3a/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-01-%E8%BF%91%E4%BC%BC%E7%AE%97%E6%B3%95%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5.pdf 4-7：近似算法的基本概念]</td>
 +
    <td>
 +
      <ul>
 +
        <li>理解近似算法相关的基本概念</li>
 +
        <li>理解近似算法的基本评价方法</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第4章第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.7--4.11</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/a/a0/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-08-%E8%A6%86%E7%9B%96%E9%97%AE%E9%A2%98%E5%92%8C%E6%9C%80%E5%A4%A7%E8%BE%B9%E5%89%B2%E9%9B%86%E9%97%AE%E9%A2%98.pdf 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>JH第4章练习4.3.2.3、4.3.2.6、4.3.2.9、4.3.3.5、4.3.3.6</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.08</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>4.14--4.18</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/7/7e/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-15-%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98.pdf 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>完整地写出MOD-SKP是解KP_delta的PTAS的证明</li>
 +
        <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.21--4.25</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/c/c5/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-22-%E6%97%85%E8%A1%8C%E6%8E%A8%E9%94%80%E5%95%86%E9%97%AE%E9%A2%98.pdf 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>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第4章练习4.3.5.6、4.3.5.7、4.3.5.11、4.3.5.13</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.10</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>4.28--5.2</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/9/99/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-29-Bin-Packing%E9%97%AE%E9%A2%98.pdf 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.5--5.9</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/5/5f/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-06-%E9%9A%8F%E6%9C%BA%E7%AE%97%E6%B3%95%E7%9A%84%E6%A6%82%E5%BF%B5.pdf 4-12：随机算法的概念]</td>
 +
    <td>
 +
      <ul>
 +
        <li>理解与随机算法相关的基本概念</li>
 +
        <li>理解随机算法的基本评价方法</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章第1、2节</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>正确性的概念与期望正确率的概念</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章练习5.2.2.7、5.2.2.8</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.12</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>5.12--5.16</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/b/bc/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-13-Random_Sampling%E5%92%8Cabundance_of_witnesses.pdf 4-13：Random Sampling和Abundance of Witnesses]</td>
 +
    <td>
 +
      <ul>
 +
        <li>理解Random Sampling和Abundance of Witnesses在随机算法设计中的应用</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章第3节第1、2、3小节</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>为什么“乱猜”也是一种算法设计方法</li>
 +
        <li>如何利用数学知识减少false witness</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章练习5.3.2.5、5.3.3.3、5.3.3.9、5.3.3.10、5.3.3.17</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.13</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>5.19--5.23</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/b/b3/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-20-%E7%AD%89%E4%BB%B7%E6%B5%8B%E8%AF%95%E9%97%AE%E9%A2%98.pdf 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>
 +
        <li>JH第2章练习2.2.3.21、2.2.3.22</li>
 +
        <li>JH第5章练习5.3.4.12</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.14</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>5.26--5.30</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/1/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-27-%E6%9C%80%E5%B0%8F%E5%89%B2%E9%9B%86%E9%97%AE%E9%A2%98.pdf 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>
 +
        <li>JH第5章练习5.3.5.9、5.3.5.10</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.15</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>6.2--6.6</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/8/8f/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-06-03-%E4%B8%8D%E5%90%8C%E6%96%B9%E6%B3%95%E7%9A%84%E7%BB%93%E5%90%88%E4%BD%BF%E7%94%A8.pdf 4-16：不同方法结合使用]</td>
 +
    <td>
 +
      <ul>
 +
        <li>通过Max-Sat问题理解如何将随机算法和优化算法很好地结合起来，以达到效率与解质量的权衡</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章第3节第6、7小节</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>多种方法的结合使用</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>推导409页的第一个公式。</li>
 +
        <li>分别用k=3和k=10，各随机生成10个不同的input instances，比较RSMS和RRRMS两个算法的执行效果。</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.16</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>6.9--6.13</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/d/de/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-06-10-%E5%8E%BB%E9%9A%8F%E6%9C%BA%E6%96%B9%E6%B3%95.pdf 4-17：去随机方法]</td>
 +
    <td>
 +
      <ul>
 +
        <li>理解并掌握去随机的基本方法，结合应用场景，可能可以在输入空间的一个子集上将随机算法改为确定算法</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章第4节</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>如何找合适的输入子集合</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第5章练习5.4.2.3、5.4.2.4、5.4.3.2、5.4.3.3</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.17</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
  <tr>
 +
    <td>6.16--6.20</td>
 +
    <td>[http://cslab.nju.edu.cn/problem_solving/images/1/1d/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-06-17-%E5%90%AF%E5%8F%91%E5%BC%8F%E7%AE%97%E6%B3%95.pdf 4-18：启发式算法]</td>
 +
    <td>
 +
      <ul>
 +
        <li>通过典型的模拟淬火算法，理解启发式算法的基本概念、其价值以及局限性</li>
 +
        <li>理解遗传算法的基本思想及其适用性</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>JH第6章</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>如何从自然界获得灵感，以非常简单的思路改造算法</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>列出这学期讨论的典型“难题”，在每个题目下列出可能采用的解法，并比较解的质量与代价。</li>
 +
      </ul>
 +
    </td>
 +
    <td>
 +
      <ul>
 +
        <li>附录A.18</li>
 +
      </ul>
 +
    </td>
 +
  </tr>
 +
 +
</table>

2015年3月1日 (日) 17:45的版本

学习周历

</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
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2013级--学期安排_(第四学期)&oldid=1130”