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

==指定教材==
<ul>
  <li>'''CH''': 程龚: 图论与算法, 2023</li>
  <li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</li>
  <li>'''TJ''': Thomas Judson: Abstract Algebra - Theory and Applications, http://abstract.ups.edu/</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>周二大班（OJ）</th>
    <th>周四大班（OT）</th>
  </tr>
  <tr>
    <td>9.2-9.6</td>
    <td>3-1：图的基本概念</td>
    <td>
      <ul>
        <li>CH第1章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习1.1、1.2、1.3、1.4</li>
        <li>CH练习1.7、1.8</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习1.5、1.6</li>
        <li>CH练习1.9、1.10</li>
      </ul>
    </td>
    <td>【全体同学完成】<br/>图在计算机和人工智能研究中有很多应用，例如程序分析中的[https://en.m.wikipedia.org/wiki/Control-flow_graph 控制流图]、信息检索中的[https://en.wikipedia.org/wiki/Webgraph 网页链接图]、知识表示中的[https://en.wikipedia.org/wiki/Knowledge_graph 知识图谱]等，请调研至少2种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。</td>
  </tr>
  <tr>
    <td>9.9-9.13</td>
    <td>3-2：连通和遍历</td>
    <td>
      <ul>
        <li>CH第2章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习2.1、2.2、2.3</li>
        <li>CH练习2.8</li>
        <li>CH练习2.11、2.12、2.13</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习2.7</li>
        <li>CH练习2.9</li>
        <li>CH练习2.15</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 1的同学完成】<br/>在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如[https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search 词典序BFS]、[https://en.wikipedia.org/wiki/Bidirectional_search 双向搜索]、[https://en.wikipedia.org/wiki/Best-first_search 最佳优先搜索]等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。</td>
  </tr>
  <tr>
    <td>9.16-9.20</td>
    <td>3-3：圈和遍历</td>
    <td>
      <ul>
        <li>CH第3章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习3.1、3.2、3.3、3.4、3.5、3.6、3.7</li>
        <li>CH练习3.10、3.11、3.12、3.13</li>
        <li>CH练习3.16、3.17、3.18、3.19</li>
        <li>CH练习3.23、3.24</li>
      </ul>
    </td>
    <td>中秋调休，本次课安排在9月14日</td>
    <td>
      <ul>
        <li>CH练习3.9</li>
        <li>CH练习3.14</li>
        <li>CH练习3.22</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 2的同学完成】<br/>请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件，讨论条件的适用场景，并阐述证明过程。</td>
  </tr>
  <tr>
    <td>9.23-9.27</td>
    <td>3-4：连通度</td>
    <td>
      <ul>
        <li>CH第4章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习4.1</li>
        <li>CH练习4.4、4.5、4.6、4.7</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习4.2、4.3</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 0的同学完成】<br/>请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法（其中至少1种来自论文原文）；门格尔定理在图论中有很多应用，请调研至少2种应用，描述应用场景。</td>
  </tr>
  <tr>
    <td>9.30-10.4</td>
    <td>3-5：匹配</td>
    <td>
      <ul>
        <li>CH第5章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习5.1</li>
        <li>CH练习5.5、5.6</li>
      </ul>
    </td>
    <td></td>
    <td>国庆放假</td>
    <td>国庆放假</td>
  </tr>
  <tr>
    <td>10.7-10.11</td>
    <td>3-6：单源最短路</td>
    <td>
      <ul>
        <li>CH第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>国庆调休，本次课安排在10月12日</td>
    <td>
      <ul>
        <li>CH练习5.2、5.3</li>
      </ul>
    </td>
    <td>作业讲解 + OJ讲解</td>
  </tr>
  <tr>
    <td>10.14-10.18</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>
      <ul>
        <li>CH练习6.1、6.2</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 1的同学完成】单源最短路问题有很多并行算法，例如[https://doi.org/10.1016/S0196-6774(03)00076-2 Δ-stepping算法]、[https://doi.org/10.1145/2935764.2935765 Radius Stepping算法]等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，比较异同并分析优劣。</td>
  </tr>
  <tr>
    <td>10.21-10.25</td>
    <td>3-8：最小生成树</td>
    <td>
      <ul>
        <li>CH第6.2节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习6.3</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>请编程实现Floyd-Warshall算法。</li>
        <li>请编程实现Johnson算法。</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 2的同学完成】<br/>[https://doi.org/10.1145/2530531 距离索引]（Distance Oracle）是一种用于查询精确或近似距离的数据结构，请调研至少1种精确距离索引和1种近似距离索引，讨论适用场景，结合例子介绍索引构造算法和距离查询算法的设计与分析。</td>
  </tr>
  <tr>
    <td>10.28-11.1</td>
    <td>3-9：有向图</td>
    <td>
      <ul>
        <li>CH第7.1、7.2、7.3、7.4节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习7.1、7.2</li>
        <li>CH练习7.4、7.5</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习6.4</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 0的同学完成】<br/>最小生成树问题有很多[https://en.wikipedia.org/wiki/Minimum_spanning_tree#Related_problems 相关问题]，例如[https://en.wikipedia.org/wiki/Steiner_tree Steiner tree]、[https://en.wikipedia.org/wiki/K-minimum_spanning_tree k-MST]、[https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree MBST]等，请调研至少2种问题（其中至多1种来自上述例子，[https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree 欧氏最小生成树问题]等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。</td>
  </tr>
  <tr>
    <td>11.4-11.8</td>
    <td>3-10：流网络和最大流</td>
    <td>
      <ul>
        <li>CH第7.5节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习7.17、7.18、7.19、7.20、7.21、7.22</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习7.3</li>
        <li>CH练习7.6、7.11</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 1的同学完成】<br/></td>
  </tr>
  <tr>
    <td>11.11-11.15</td>
    <td>3-11：独立、覆盖和支配</td>
    <td>
      <ul>
        <li>CH第8章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习8.1、8.2</li>
        <li>CH练习8.5</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习7.23</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 2的同学完成】<br/>除福特-法尔克森算法外，最大流问题还有很多其它算法，例如[https://doi.org/10.1145/321694.321699 Edmonds-Karp算法]、[https://doi.org/10.1007/11685654_10 Dinitz算法]、[https://doi.org/10.1145/48014.61051 Push-Relabel算法]等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。</td>
  </tr>
  <tr>
    <td>11.18-11.22</td>
    <td>3-12：染色</td>
    <td>
      <ul>
        <li>CH第9章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习9.1、9.2</li>
        <li>CH练习9.5、9.6</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习8.3、8.4</li>
      </ul>
    </td>
    <td>作业讲解 + OJ讲解</td>
  </tr>
  <tr>
    <td>11.25-11.29</td>
    <td>3-13：平面</td>
    <td>
      <ul>
        <li>CH第10章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CH练习10.1、10.2、10.3、10.4</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习9.3、9.4</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 0的同学完成】<br/>在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、[https://en.wikipedia.org/wiki/Connected_dominating_set 最小连通支配集问题]等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。</td>
  </tr>
  <tr>
    <td>12.2-12.6</td>
    <td>3-14：群和循环群</td>
    <td>
      <ul>
        <li>TJ第3、4章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TJ第3章练习3、6、7、17、28、36、38、41、48、52</li>
        <li>TJ第4章练习1、12、21、24、32</li>
      </ul>
    </td>
    <td></td>
    <td>
      <ul>
        <li>CH练习10.5</li>
      </ul>
    </td>
    <td>【学号后3位 % 3 = 1的同学完成】<br/>除米什拉-格赖斯算法和贪心算法外，边染色和点染色问题还有很多其它算法，请为每种问题调研至少1种精确算法（暴力算法不在调研范围内），结合例子介绍算法的设计与分析。</td>
  </tr>
  <tr>
    <td>12.9-12.13</td>
    <td>3-15：置换群、陪集和拉格朗日定理</td>
    <td>
      <ul>
        <li>TJ第5、6章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TJ第5章练习3、5、16、27、29</li>
        <li>TJ第6章练习11、12、16、21</li>
      </ul>
    </td>
    <td></td>
    <td></td>
    <td>【学号后3位 % 3 = 2的同学完成】<br/>除DMP算法外，可平面图的判定问题还有很多其它算法，请调研至少2种算法，结合例子介绍算法的设计与分析，与DMP算法比较异同并分析优劣。</td>
  </tr>
  <tr>
    <td>12.16-12.20</td>
    <td>3-16：代数编码</td>
    <td>
      <ul>
        <li>TJ第8章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TJ第8章练习6、7、8、9、11、13、18、19、21、22、23</li>
      </ul>
    </td>
    <td></td>
    <td></td>
    <td>【学号后3位 % 3 = 0的同学完成】<br/></td>
  </tr>
  <tr>
    <td>12.23-12.27</td>
    <td>3-17：群同构、正规子群和因子群</td>
    <td>
      <ul>
        <li>TJ第9、10章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td></td>
    <td></td>
    <td>作业讲解 + OJ讲解</td>
  </tr>
</table>