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

来自问题求解
跳转至: 导航搜索
学习周历
 
(未显示同一用户的11个中间版本)
第98行: 第98行:
 
   <tr>
 
   <tr>
 
     <td>10.2-10.6</td>
 
     <td>10.2-10.6</td>
     <td>3-5:匹配</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第5次课.pdf|3-5:匹配]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第115行: 第115行:
 
   <tr>
 
   <tr>
 
     <td>10.9-10.13</td>
 
     <td>10.9-10.13</td>
     <td>3-6:单源最短路</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第6次课.pdf|3-6:单源最短路]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第136行: 第136行:
 
   <tr>
 
   <tr>
 
     <td>10.16-10.20</td>
 
     <td>10.16-10.20</td>
     <td>3-7:多源最短路</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第7次课.pdf|3-7:多源最短路]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第150行: 第150行:
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
     <td>OT:[https://doi.org/10.1145/2530531 距离索引](Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍距离索引构造和距离查询算法的设计与分析。</td>
+
     <td>OT:[https://doi.org/10.1145/2530531 距离索引](Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。</td>
 
     <td>第5次OJ</td>
 
     <td>第5次OJ</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
 
     <td>10.23-10.27</td>
 
     <td>10.23-10.27</td>
     <td>3-8:最小生成树</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第8次课.pdf|3-8:最小生成树]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第171行: 第171行:
 
   <tr>
 
   <tr>
 
     <td>10.30-11.3</td>
 
     <td>10.30-11.3</td>
     <td>3-9:问题的形式化描述</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第9次课.pdf|3-9:问题的形式化描述]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第187行: 第187行:
 
   <tr>
 
   <tr>
 
     <td>11.6-11.10</td>
 
     <td>11.6-11.10</td>
     <td>3-10:NP完全理论初步</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第10次课.pdf|3-10:NP完全理论初步]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第205行: 第205行:
 
   <tr>
 
   <tr>
 
     <td>11.13-11.17</td>
 
     <td>11.13-11.17</td>
     <td>3-11:有向图和伪多项式时间算法</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第11次课.pdf|3-11:有向图和伪多项式时间算法]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第224行: 第224行:
 
   <tr>
 
   <tr>
 
     <td>11.20-11.24</td>
 
     <td>11.20-11.24</td>
     <td>3-12:分支定界和局部搜索算法</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第12次课.pdf|3-12:分支定界和局部搜索算法]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>JH第3.4、3.6节</li>
+
         <li>JH第3.4、3.6.1、3.6.2节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第241行: 第241行:
 
   <tr>
 
   <tr>
 
     <td>11.27-12.1</td>
 
     <td>11.27-12.1</td>
     <td>3-13:松弛算法</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第13次课.pdf|3-13:松弛算法]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>JH第3.7节</li>
+
         <li>JH第3.7.1、3.7.2、3.7.4节(不含练习3.7.4.12之后的内容)</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第250行: 第250行:
 
       <ul>
 
       <ul>
 
         <li>JH练习3.7.2.1、3.7.2.4、3.7.2.5</li>
 
         <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>
+
         <li>JH练习3.7.4.4、3.7.4.12</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第258行: 第258行:
 
   <tr>
 
   <tr>
 
     <td>12.4-12.8</td>
 
     <td>12.4-12.8</td>
     <td>3-14:近似算法的基本概念</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第14次课.pdf|3-14:近似算法的基本概念]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>JH第4.2.1、4.2.2、4.3.3节</li>
+
         <li>JH第4.2.1、4.2.2、4.2.3、4.3.3节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
         <li>JH练习4.2.1.4、4.2.1.5</li>
+
         <li>JH练习4.2.1.4、4.2.1.5、4.2.3.3</li>
 
         <li>JH练习4.3.3.5、4.3.3.6</li>
 
         <li>JH练习4.3.3.5、4.3.3.6</li>
 
       </ul>
 
       </ul>
第275行: 第275行:
 
   <tr>
 
   <tr>
 
     <td>12.11-12.15</td>
 
     <td>12.11-12.15</td>
     <td>3-15:独立、覆盖和支配</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第15次课.pdf|3-15:独立、覆盖和支配]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第292行: 第292行:
 
   <tr>
 
   <tr>
 
     <td>12.18-12.22</td>
 
     <td>12.18-12.22</td>
     <td>3-16:染色</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第16次课.pdf|3-16:染色]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第309行: 第309行:
 
   <tr>
 
   <tr>
 
     <td>12.25-12.29</td>
 
     <td>12.25-12.29</td>
     <td>3-17:平面</td>
+
     <td>[[媒体文件:大班课件-22级-第3学期-第17次课.pdf|3-17:平面]]</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第321行: 第321行:
 
     </td>
 
     </td>
 
     <td>OT:除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。</td>
 
     <td>OT:除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。</td>
     <td>作业讲解+OJ讲解+答疑</td>
+
     <td>作业讲解+OJ讲解</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>

2024年2月1日 (四) 09:52的最新版本

基本要求

  • 掌握典型应用中抽象出来的重要算法问题的求解方法。
  • 掌握复杂性理论的基本内容与问题规约方法。
  • 理解解决“难”问题的主要方法、技术以及相关的重要理论。

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

指定教材

  • CH: 程龚: 图论与算法, 2023
  • TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
  • JH: Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004
  • WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008

学习周历

日期 论题 阅读材料 书面作业 周三小班 周四大班
9.4-9.8 3-1:图的基本概念
  • CH第1章
  • CH练习1.1、1.2、1.3、1.4
  • CH练习1.7、1.8
OT:图在计算机和人工智能研究中有很多应用,例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等,请调研至少2种应用(其中至多1种来自上述例子),描述应用场景,讨论用图建模的方式,形式化描述问题并概述现有解决方案。 第1次OJ
9.11-9.15 3-2:连通和遍历
  • CH第2章
  • CH练习2.1、2.2、2.3
  • CH练习2.8
  • CH练习2.11、2.12、2.13
OT:在DFS和BFS的基础上,形成了很多扩展的搜索算法,例如词典序BFS双向搜索最佳优先搜索等,请调研至少2种扩展搜索算法(其中至多1种来自上述例子),讨论适用场景,结合例子介绍算法的设计与分析,与DFS或BFS比较异同并分析优劣。 第2次OJ
9.18-9.22 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
OT:请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件,讨论条件的适用场景,并阐述证明过程。 第3次OJ
9.25-9.29 3-4:连通度
  • CH第4章
  • CH练习4.1
  • CH练习4.4、4.5、4.6、4.7
OT:请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法(其中至少1种来自论文原文);门格尔定理在图论中有很多应用,请调研至少2种应用,描述应用场景。 第4次OJ
10.2-10.6 3-5:匹配
  • CH第5章
  • CH练习5.1
  • CH练习5.5、5.6
国庆放假 补周一
10.9-10.13 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
OT:单源最短路问题有很多并行算法,例如Δ-stepping算法Radius Stepping算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,比较异同并分析优劣。 作业讲解+OJ讲解
10.16-10.20 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
OT:距离索引(Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。 第5次OJ
10.23-10.27 3-8:最小生成树
  • CH第6.2节
  • CH练习6.3
OT:最小生成树问题有很多相关问题,例如Steiner treek-MSTMBST等,请调研至少2种问题(其中至多1种来自上述例子,欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题并概述现有解决方案。 第6次OJ
10.30-11.3 3-9:问题的形式化描述
  • JH第2.3.1、2.3.2节
  • JH练习2.3.1.7、2.3.1.8
OT:请调研教材中未介绍过的至少2种判定问题和2种优化问题(不能是相互对应版本,也不能是教材中介绍过的问题的对应版本),讨论适用场景,用教材中的方法形式化描述问题。 第7次OJ
11.6-11.10 3-10:NP完全理论初步
  • TC第34章
  • TC练习34.2-3、4、6、11
  • TC练习34.3-2
  • TC练习34.5-6
OT:请调研并介绍图灵机及其至少2种等价模型,讨论图灵机、P、NP之间的关系。 第8次OJ
11.13-11.17 3-11:有向图和伪多项式时间算法
  • CH第7章
  • JH第3.2.1、3.2.3节
  • CH练习7.1、7.2
  • CH练习7.4、7.5
  • CH练习7.17、7.18、7.19、7.20、7.21、7.22
OT:除福特-法尔克森算法外,最大流问题还有很多其它算法,例如Edmonds-Karp算法Dinitz算法Push-Relabel算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与福特-法尔克森算法比较异同并分析优劣。 第9次OJ
11.20-11.24 3-12:分支定界和局部搜索算法
  • JH第3.4、3.6.1、3.6.2节
  • JH练习3.4.2.1、3.4.2.2
  • JH练习3.6.1.3
OT:除MAX-SAT和TSP外,分支定界和局部搜索算法还可用于解决其它问题,请为每种算法调研至少1种可以解决的问题,结合例子介绍算法的设计与分析。 作业讲解+OJ讲解
11.27-12.1 3-13:松弛算法
  • JH第3.7.1、3.7.2、3.7.4节(不含练习3.7.4.12之后的内容)
  • JH练习3.7.2.1、3.7.2.4、3.7.2.5
  • JH练习3.7.4.4、3.7.4.12
OT:除IP外,广义的“松弛-修正”思想还可用于解决其它问题,例如TSP的松弛修正算法最短超串问题的松弛修正算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,重点阐述其中的“松弛-修正”思想。 第10次OJ
12.4-12.8 3-14:近似算法的基本概念
  • JH第4.2.1、4.2.2、4.2.3、4.3.3节
  • JH练习4.2.1.4、4.2.1.5、4.2.3.3
  • JH练习4.3.3.5、4.3.3.6
OT:除MS和MAX-CUT外,近似算法还可用于解决其它问题,例如SCP(JH算法4.3.2.11)、SKP(JH算法4.3.4.1和4.3.4.2)等,请调研至少2种近似算法(其中至多1种来自上述例子,图上的优化问题不在调研范围内),结合例子介绍算法的设计与分析,重点阐述近似比的证明过程。 第11次OJ
12.11-12.15 3-15:独立、覆盖和支配
  • CH第8章
  • CH练习8.1、8.2
  • CH练习8.5
OT:在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、最小连通支配集问题等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。 第12次OJ
12.18-12.22 3-16:染色
  • CH第9章
  • CH练习9.1、9.2
  • CH练习9.5、9.6
OT:除米什拉-格赖斯算法和贪心算法外,边染色和点染色问题还有很多其它算法,请为每种问题调研至少1种精确算法(暴力算法不在调研范围内),结合例子介绍算法的设计与分析。 第13次OJ
12.25-12.29 3-17:平面
  • CH第10章
  • CH练习10.1、10.2、10.3、10.4
OT:除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。 作业讲解+OJ讲解
寒假自学 3-18:背包问题
  • JH第4.3.4节
-- -- --