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

来自问题求解
跳转至: 导航搜索
学习周历
 
(未显示同一用户的26个中间版本)
第1行: 第1行:
 
==指定教材==
 
==指定教材==
 
<ul>
 
<ul>
   <li>'''CH''': 程龚: 图论与算法, 2023</li>
+
   <li>'''CH''': 程龚: [http://ws.nju.edu.cn/gtabook 图论与算法], 2024</li>
 
   <li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</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>'''TJ''': Thomas Judson: Abstract Algebra - Theory and Applications, August 12, 2015.</li>
 
   <li>'''WS''': Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008</li>
 
   <li>'''WS''': Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008</li>
 
</ul>
 
</ul>
第32行: 第32行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第40行: 第40行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </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>
+
     <td>【学号后3位 % 3 = 0的同学完成】<br/>图在计算机和人工智能研究中有很多应用,例如程序分析中的[https://en.m.wikipedia.org/wiki/Control-flow_graph 控制流图]、信息检索中的[https://en.wikipedia.org/wiki/Webgraph 网页链接图]、知识表示中的[https://en.wikipedia.org/wiki/Knowledge_graph 知识图谱]等,请调研至少3种应用(其中至多1种来自上述例子),描述应用场景,讨论用图建模的方式,形式化描述问题并概述现有解决方案。</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
第57行: 第57行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
        <li>CH练习2.7</li>
 
 
         <li>CH练习2.9</li>
 
         <li>CH练习2.9</li>
 
         <li>CH练习2.15</li>
 
         <li>CH练习2.15</li>
第84行: 第83行:
 
     </td>
 
     </td>
 
     <td>中秋调休,本次课安排在9月14日</td>
 
     <td>中秋调休,本次课安排在9月14日</td>
     <td>
+
     <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>
 
     <td>【学号后3位 % 3 = 2的同学完成】<br/>请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件,讨论条件的适用场景,并阐述证明过程。</td>
 
   </tr>
 
   </tr>
第107行: 第100行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习4.2</li>
+
         <li>CH练习3.14</li>
 +
        <li>CH练习3.22</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td>【学号后3位 % 3 = 0的同学完成】<br/>请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法(其中至少1种来自论文原文);门格尔定理在图论中有很多应用,请调研至少2种应用,描述应用场景。</td>
+
     <td>【学号后3位 % 3 = 0的同学完成】<br/>请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法;门格尔定理在图论中有很多应用,请调研至少2种应用,描述应用场景。</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
第129行: 第123行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>国庆放假</td>
 
     <td>国庆放假</td>
 
     <td>国庆放假</td>
 
     <td>国庆放假</td>
第154行: 第148行:
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习5.2、5.3</li>
+
         <li>CH练习4.2</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第175行: 第169行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习6.1、6.2</li>
+
         <li>CH练习5.2、5.3</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </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>
+
     <td>【学号后3位 % 3 = 1的同学完成】<br/>花算法有很多优化改进,例如[https://doi.org/10.1145/321941.321942 Gabow'76]、[https://doi.org/10.1109/SFCS.1980.12 Micali'80]等,请调研至少2种优化改进(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与花算法比较异同并分析优劣。</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
 
     <td>10.21-10.25</td>
 
     <td>10.21-10.25</td>
     <td>3-8:最小生成树</td>
+
     <td>3-8:最小生成树和赋权欧拉图</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH第6.2节</li>
+
         <li>CH第6.2、6.3节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第194行: 第188行:
 
       <ul>
 
       <ul>
 
         <li>CH练习6.3</li>
 
         <li>CH练习6.3</li>
 +
        <li>CH练习6.5</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>请编程实现Floyd-Warshall算法。</li>
+
         <li>CH练习6.1、6.2</li>
        <li>请编程实现Johnson算法。</li>
 
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td>【学号后3位 % 3 = 2的同学完成】<br/>[https://doi.org/10.1145/2530531 距离索引](Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。</td>
+
     <td>【学号后3位 % 3 = 2的同学完成】单源最短路问题有很多并行算法,例如[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>
 
   <tr>
 
   <tr>
第219行: 第213行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习6.4</li>
+
         <li>请编程实现Floyd-Warshall算法。</li>
 +
        <li>请编程实现Johnson算法。</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </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>
+
     <td>【学号后3位 % 3 = 0的同学完成】<br/>[https://doi.org/10.1145/2530531 距离索引](Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
第240行: 第235行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习7.3</li>
+
         <li>CH练习6.4</li>
        <li>CH练习7.6、7.11</li>
 
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td>【学号后3位 % 3 = 1的同学完成】<br/></td>
+
     <td>【学号后3位 % 3 = 1的同学完成】<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>
 
   <tr>
 
   <tr>
第263行: 第257行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习7.23</li>
+
         <li>CH练习7.3</li>
 +
        <li>CH练习7.11</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </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>
+
     <td>作业讲解 + OJ讲解</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
第285行: 第280行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习8.3、8.4</li>
+
         <li>CH练习7.23</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td>作业讲解 + OJ讲解</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>
 
   <tr>
 
   <tr>
第306行: 第301行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习9.3、9.4</li>
+
         <li>CH练习8.3、8.4</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第324行: 第319行:
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>TJ第3章练习3、6、7、17、28、36、38、41、48、52</li>
+
         <li>TJ第3章练习3、6、7、17、29、37、39、42、49</li>
 
         <li>TJ第4章练习1、12、21、24、32</li>
 
         <li>TJ第4章练习1、12、21、24、32</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>CH练习10.5</li>
+
         <li>CH练习9.3、9.4</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第347行: 第342行:
 
       <ul>
 
       <ul>
 
         <li>TJ第5章练习3、5、16、27、29</li>
 
         <li>TJ第5章练习3、5、16、27、29</li>
         <li>TJ第6章练习11、12、16、21</li>
+
         <li>TJ第6章练习11、12、16</li>
 +
      </ul>
 +
    </td>
 +
    <td>正常上课</td>
 +
    <td>
 +
      <ul>
 +
        <li>CH练习10.5</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
    <td></td>
 
    <td></td>
 
 
     <td>【学号后3位 % 3 = 2的同学完成】<br/>除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。</td>
 
     <td>【学号后3位 % 3 = 2的同学完成】<br/>除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。</td>
 
   </tr>
 
   </tr>
第367行: 第366行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td></td>
+
     <td>正常上课</td>
     <td></td>
+
     <td>
     <td>【学号后3位 % 3 = 0的同学完成】<br/></td>
+
      <ul>
 +
        <li>Write a computer program to calculate a^x (mod n) by the method of repeated squares.</li>
 +
        <li>Write a program to implement a (16, 12)-linear code. Your program should be able to encode and decode messages using coset decoding.</li>
 +
      </ul>
 +
     </td>
 +
    <td>作业讲解 + OJ讲解</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
 
     <td>12.23-12.27</td>
 
     <td>12.23-12.27</td>
     <td>3-17:群同构、正规子群和因子群</td>
+
     <td>复习</td>
 +
    <td>无</td>
 +
    <td>无</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>TJ第9、10章</li>
+
         <li>部分同学讲解TJ第9、10章</li>
 +
        <li>部分同学讲解TJ第12.1、12.2节</li>
 +
        <li>部分同学讲解TJ第16.1、16.2节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 +
    <td>OJ期末考试</td>
 +
    <td>答疑</td>
 +
  </tr>
 +
  <tr>
 +
    <td>寒假自学</td>
 +
    <td>群同构、正规子群和因子群、群同态</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li></li>
+
         <li>TJ第9、10、11章</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 
     <td></td>
 
     <td></td>
 
     <td></td>
 
     <td></td>
     <td>作业讲解 + OJ讲解</td>
+
     <td></td>
 +
    <td></td>
 
   </tr>
 
   </tr>
 
</table>
 
</table>

2024年12月16日 (一) 16:46的最新版本

指定教材

  • CH: 程龚: 图论与算法, 2024
  • TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
  • TJ: Thomas Judson: Abstract Algebra - Theory and Applications, August 12, 2015.
  • WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008

学习周历

日期 论题 阅读材料 书面作业 周一小班(讲课) 周二大班(OJ) 周四大班(OT)
9.2-9.6 3-1:图的基本概念
  • CH第1章
  • CH练习1.1、1.2、1.3、1.4
  • CH练习1.7、1.8
正常上课
  • CH练习1.5、1.6
  • CH练习1.9
  • CH练习1.10
【学号后3位 % 3 = 0的同学完成】
图在计算机和人工智能研究中有很多应用,例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等,请调研至少3种应用(其中至多1种来自上述例子),描述应用场景,讨论用图建模的方式,形式化描述问题并概述现有解决方案。
9.9-9.13 3-2:连通和遍历
  • CH第2章
  • CH练习2.1、2.2、2.3
  • CH练习2.8
  • CH练习2.11、2.12、2.13
正常上课
  • CH练习2.9
  • CH练习2.15
【学号后3位 % 3 = 1的同学完成】
在DFS和BFS的基础上,形成了很多扩展的搜索算法,例如词典序BFS双向搜索最佳优先搜索等,请调研至少2种扩展搜索算法(其中至多1种来自上述例子),讨论适用场景,结合例子介绍算法的设计与分析,与DFS或BFS比较异同并分析优劣。
9.16-9.20 3-3:圈和遍历
  • CH第3章
  • CH练习3.1、3.2、3.3、3.4、3.5、3.6、3.7
  • CH练习3.10、3.11、3.12、3.13
  • CH练习3.16、3.17、3.18、3.19
  • CH练习3.23、3.24
中秋调休,本次课安排在9月14日 中秋放假 【学号后3位 % 3 = 2的同学完成】
请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件,讨论条件的适用场景,并阐述证明过程。
9.23-9.27 3-4:连通度
  • CH第4章
  • CH练习4.1
  • CH练习4.4、4.5、4.6、4.7
正常上课
  • CH练习3.14
  • CH练习3.22
【学号后3位 % 3 = 0的同学完成】
请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法;门格尔定理在图论中有很多应用,请调研至少2种应用,描述应用场景。
9.30-10.4 3-5:匹配
  • CH第5章
  • CH练习5.1
  • CH练习5.5、5.6
正常上课 国庆放假 国庆放假
10.7-10.11 3-6:单源最短路
  • CH第6.1节
  • TC第24章
  • TC练习24.1-2、3、4
  • TC练习24.2-2
  • TC练习24.3-2、4、7
  • TC练习24.5-2、5
  • TC问题24-2、3
国庆调休,本次课安排在10月12日
  • CH练习4.2
作业讲解 + OJ讲解
10.14-10.18 3-7:多源最短路
  • TC第25章
  • TC练习25.1-4、5、6、9、10
  • TC练习25.2-2、4、6、8
  • TC练习25.3-2、3
  • TC问题25-2
正常上课
  • CH练习5.2、5.3
【学号后3位 % 3 = 1的同学完成】
花算法有很多优化改进,例如Gabow'76Micali'80等,请调研至少2种优化改进(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与花算法比较异同并分析优劣。
10.21-10.25 3-8:最小生成树和赋权欧拉图
  • CH第6.2、6.3节
  • CH练习6.3
  • CH练习6.5
正常上课
  • CH练习6.1、6.2
【学号后3位 % 3 = 2的同学完成】单源最短路问题有很多并行算法,例如Δ-stepping算法Radius Stepping算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,比较异同并分析优劣。
10.28-11.1 3-9:有向图
  • CH第7.1、7.2、7.3、7.4节
  • CH练习7.1、7.2
  • CH练习7.4、7.5
正常上课
  • 请编程实现Floyd-Warshall算法。
  • 请编程实现Johnson算法。
【学号后3位 % 3 = 0的同学完成】
距离索引(Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。
11.4-11.8 3-10:流网络和最大流
  • CH第7.5节
  • CH练习7.17、7.18、7.19、7.20、7.21、7.22
正常上课
  • CH练习6.4
【学号后3位 % 3 = 1的同学完成】
最小生成树问题有很多相关问题,例如Steiner treek-MSTMBST等,请调研至少2种问题(其中至多1种来自上述例子,欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题并概述现有解决方案。
11.11-11.15 3-11:独立、覆盖和支配
  • CH第8章
  • CH练习8.1、8.2
  • CH练习8.5
正常上课
  • CH练习7.3
  • CH练习7.11
作业讲解 + OJ讲解
11.18-11.22 3-12:染色
  • CH第9章
  • CH练习9.1、9.2
  • CH练习9.5、9.6
正常上课
  • CH练习7.23
【学号后3位 % 3 = 2的同学完成】
除福特-法尔克森算法外,最大流问题还有很多其它算法,例如Edmonds-Karp算法Dinitz算法Push-Relabel算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与福特-法尔克森算法比较异同并分析优劣。
11.25-11.29 3-13:平面
  • CH第10章
  • CH练习10.1、10.2、10.3、10.4
正常上课
  • CH练习8.3、8.4
【学号后3位 % 3 = 0的同学完成】
在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、最小连通支配集问题等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。
12.2-12.6 3-14:群和循环群
  • TJ第3、4章
  • TJ第3章练习3、6、7、17、29、37、39、42、49
  • TJ第4章练习1、12、21、24、32
正常上课
  • CH练习9.3、9.4
【学号后3位 % 3 = 1的同学完成】
除米什拉-格赖斯算法和贪心算法外,边染色和点染色问题还有很多其它算法,请为每种问题调研至少1种精确算法(暴力算法不在调研范围内),结合例子介绍算法的设计与分析。
12.9-12.13 3-15:置换群、陪集和拉格朗日定理
  • TJ第5、6章
  • TJ第5章练习3、5、16、27、29
  • TJ第6章练习11、12、16
正常上课
  • CH练习10.5
【学号后3位 % 3 = 2的同学完成】
除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。
12.16-12.20 3-16:代数编码
  • TJ第8章
  • TJ第8章练习6、7、8、9、11、13、18、19、21、22、23
正常上课
  • Write a computer program to calculate a^x (mod n) by the method of repeated squares.
  • Write a program to implement a (16, 12)-linear code. Your program should be able to encode and decode messages using coset decoding.
作业讲解 + OJ讲解
12.23-12.27 复习
  • 部分同学讲解TJ第9、10章
  • 部分同学讲解TJ第12.1、12.2节
  • 部分同学讲解TJ第16.1、16.2节
OJ期末考试 答疑
寒假自学 群同构、正规子群和因子群、群同态
  • TJ第9、10、11章