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

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

==指定教材==
<ul>
  <li>'''CHENG''': 程龚: 图论与算法, 2023</li>
  <li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</li>
  <li>'''JH''': Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004</li>
  <li>'''WS''': Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008</li>
</ul>

==学习周历==
<table border="1px">
  <tr>
    <th>日期</th>
    <th>论题</th>
    <th>阅读材料</th>
    <th>书面作业</th>
    <th>周三小班</th>
    <th>周四大班</th>
  </tr>
  <tr>
    <td>9.4-9.8</td>
    <td>3-1：图的基本概念</td>
    <td>
      <ul>
        <li>CHENG第1章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习1.1-1.4</li>
        <li>CHENG练习1.7-1.8</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>9.11-9.15</td>
    <td>3-2：连通和遍历</td>
    <td>
      <ul>
        <li>CHENG第2章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习2.1-2.3</li>
        <li>CHENG练习2.8</li>
        <li>CHENG练习2.11-2.13</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>9.18-9.22</td>
    <td>3-3：圈和遍历</td>
    <td>
      <ul>
        <li>CHENG第3章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习3.1-3.7</li>
        <li>CHENG练习3.10-3.13</li>
        <li>CHENG练习3.16-3.19</li>
        <li>CHENG练习3.23-3.24</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>9.25-9.29</td>
    <td>3-4：连通度</td>
    <td>
      <ul>
        <li>CHENG第4章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习4.1</li>
        <li>CHENG练习4.4-4.7</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>10.2-10.6</td>
    <td>3-5：匹配</td>
    <td>
      <ul>
        <li>CHENG第5章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习5.1</li>
        <li>CHENG练习5.5-5.6</li>
      </ul>
    </td>
    <td>--</td>
    <td>--</td>
  </tr>
  <tr>
    <td>10.9-10.13</td>
    <td>3-6：单源最短路</td>
    <td>
      <ul>
        <li>CHENG第6.1节</li>
        <li>TC第24章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC练习24.1-2、3、4</li>
        <li>TC练习24.2-2</li>
        <li>TC练习24.3-2、4、7</li>
        <li>TC练习24.5-2、5</li>
        <li>TC问题24-2、3</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>10.16-10.20</td>
    <td>3-7：多源最短路</td>
    <td>
      <ul>
        <li>TC第25章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC练习25.1-4、5、6、9、10</li>
        <li>TC练习25.2-2、4、6、8</li>
        <li>TC练习25.3-2、3</li>
        <li>TC问题25-2</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>10.23-10.27</td>
    <td>3-8：最小生成树</td>
    <td>
      <ul>
        <li>CHENG第6.2节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习6.3</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>10.30-11.3</td>
    <td>3-9：问题的形式化描述</td>
    <td>
      <ul>
        <li>JH第2.3.1、2.3.2节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH练习2.3.1.7、2.3.1.8</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>11.6-11.10</td>
    <td>3-10：NP完全理论初步</td>
    <td>
      <ul>
        <li>TC第34章</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></td>
    <td></td>
  </tr>
  <tr>
    <td>11.13-11.17</td>
    <td>3-11：有向图和伪多项式时间算法</td>
    <td>
      <ul>
        <li>CHENG第7章</li>
        <li>JH第3.2.1、3.2.3节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CHENG练习7.1-7.2</li>
        <li>CHENG练习7.4-7.5</li>
        <li>CHENG练习7.17-7.22</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>11.20-11.24</td>
    <td>3-12：分支定界和局部搜索算法</td>
    <td>
      <ul>
        <li>JH第3.4、3.6节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH练习3.4.2.1、3.4.2.2</li>
        <li>JH练习3.6.1.3</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>11.27-12.1</td>
    <td>3-13：松弛算法</td>
    <td>
      <ul>
        <li>JH第3.7节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>JH练习3.7.2.1、3.7.2.4、3.7.2.5</li>
        <li>JH练习3.7.4.4、3.7.4.12、3.7.4.16</li>
      </ul>
    </td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>12.4-12.8</td>
    <td>3-14：近似算法的基本概念</td>
    <td>
      <ul>
        <li>JH第4.2.1、4.2.2、4.3.3节</li>
      </ul>
    </td>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>12.11-12.15</td>
    <td>3-15：独立、覆盖和支配</td>
    <td>
      <ul>
        <li>CHENG第8章</li>
      </ul>
    </td>
    <td>CHENG练习8.1-8.2、8.5</td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>12.18-12.22</td>
    <td>3-16：染色</td>
    <td>
      <ul>
        <li>CHENG第9章</li>
      </ul>
    </td>
    <td>CHENG练习9.1-9.2、9.5-9.6</td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>12.25-12.29</td>
    <td>3-17：平面</td>
    <td>
      <ul>
        <li>CHENG第10章</li>
      </ul>
    </td>
    <td>CHENG练习10.1-10.4</td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>寒假自学</td>
    <td>3-18：背包问题</td>
    <td>
      <ul>
        <li>JH第4.3.4节</li>
      </ul>
    </td>
    <td>--</td>
    <td>--</td>
    <td>--</td>
  </tr>
</table>