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

来自问题求解
跳转至: 导航搜索
学习周历
学习周历
第82行: 第82行:
 
     </td>
 
     </td>
 
     <td></td>
 
     <td></td>
     <td></td>
+
     <td>国庆放假</td>
     <td></td>
+
     <td>上大班</td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>

2023年7月10日 (一) 23:37的版本

基本要求

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

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

指定教材

  • CHENG: 程龚: 图论与算法
  • 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:图的基本概念
  • CHENG第1章
9.11-9.15 3-2:连通和遍历
  • CHENG第2章
9.18-9.22 3-3:圈和遍历
  • CHENG第3章
9.25-9.29 3-4:连通度
  • CHENG第4章
10.2-10.6 3-5:匹配
  • CHENG第5章
国庆放假 上大班
10.9-10.13 3-6:单源最短路
  • CHENG第6.1节
  • TC第24章
10.16-10.20 3-7:多源最短路
  • TC第25章
10.23-10.27 3-8:最小生成树
  • CHENG第6.2节
10.30-11.3 3-9:问题的形式化描述
  • JH第2.3.1、2.3.2节
11.6-11.10 3-10:有向图和伪多项式时间算法
  • CHENG第7章
  • JH第3.2.1、3.2.3节
11.13-11.17 3-11:NP完全理论初步
  • TC第34章
11.20-11.24 3-12:分支定界和局部搜索算法
  • JH第3.4、3.6节
11.27-12.1 3-13:松弛算法
  • JH第3.7节
12.4-12.8 3-14:近似算法的基本概念
  • JH第4.2.1、4.2.2、4.3.3节
12.11-12.15 3-15:独立、覆盖和支配
  • CHENG第8章
12.18-12.22 3-16:染色
  • CHENG第9章
12.25-12.29 3-17:平面
  • CHENG第10章
寒假自学 3-18:背包问题
  • JH第4.3.4节