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

来自问题求解
跳转至： 导航、 搜索
第10行： 第10行：
 
<ul>
 
<ul>
 
   <li>'''CHENG''': 程龚: 图论与算法</li>
 
   <li>'''CHENG''': 程龚: 图论与算法</li>
−
  <li>'''GC''': Gary Chartrand et al.: Introduction to Graph Theory, 1st ed. McGraw-Hill, 2004</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>'''JH''': Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004</li>
 
   <li>'''JH''': Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004</li>
第116行： 第115行：
 
   <tr>
 
   <tr>
 
     <td>10.30-11.3</td>
 
     <td>10.30-11.3</td>
−
     <td>3-9：有向图</td>
+
     <td>3-9：有向图和伪多项式时间算法</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
第127行： 第126行：
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>4.24-4.28</td>
+
     <td>11.6-11.10</td>
−
     <td>[[媒体文件:计算机问题求解-2022-10-堆与堆排序.pdf|2-10：堆与堆排序]]</td>
+
     <td>3-10：问题的形式化描述</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第6章</li>
+
         <li>JH第2.3.1、2.3.2节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第138行： 第137行：
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>5.1-5.5</td>
+
     <td>11.13-11.17</td>
−
     <td>[[媒体文件:计算机问题求解-2022-11-hashing方法.pdf|2-11：Hashing方法]]</td>
+
     <td>3-11：NP完全理论初步</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第11章</li>
+
         <li>TC第34章</li>
−
        <li>CS第5章第5节</li>
 
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 
     <td></td>
 
     <td></td>
−
     <td>习题课</td>
+
     <td></td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>5.8-5.12</td>
+
     <td>11.20-11.24</td>
−
     <td>[[媒体文件:计算机问题求解-2022-12-搜索树.pdf|2-12：搜索树]]</td>
+
     <td>3-12：分支定界和局部搜索算法</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第12、13章</li>
+
         <li>JH第3.4、3.6节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第161行： 第159行：
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>5.15-5.19</td>
+
     <td>11.27-12.1</td>
−
     <td>[[媒体文件:计算机问题求解-2022-13-动态规划.pdf|2-13：动态规划]]</td>
+
     <td>3-13：松弛算法</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第15章</li>
+
         <li>JH第3.7节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 
     <td></td>
 
     <td></td>
−
     <td>OT</td>
+
     <td></td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>5.22-5.26</td>
+
     <td>12.4-12.8</td>
−
     <td>[[媒体文件:计算机问题求解-2022-14-贪心算法.pdf|2-14：贪心算法]]</td>
+
     <td>3-14：近似算法的基本概念</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第16章</li>
+
         <li>JH第4.2.1、4.2.2、4.3.3节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第183行： 第181行：
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>5.29-6.2</td>
+
     <td>12.11-12.15</td>
−
     <td>[[媒体文件:计算机问题求解-2022-15-用于动态等价关系的数据结构.pdf|2-15：用于动态等价关系的数据结构与均摊分析]]</td>
+
     <td>3-15：独立、覆盖和支配</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第17章</li>
+
         <li>CHENG第8章</li>
−
        <li>TC第21章</li>
 
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 
     <td></td>
 
     <td></td>
−
     <td>OT</td>
+
     <td></td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>6.5-6.9</td>
+
     <td>12.18-12.22</td>
−
     <td>[[媒体文件:计算机问题求解-2022-16-线性规划.pdf|2-16：线性规划]]</td>
+
     <td>3-16：染色</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第29章</li>
+
         <li>CHENG第9章</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
 
     <td></td>
 
     <td></td>
−
     <td>习题课</td>
+
     <td></td>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>暑假自学</td>
+
     <td>12.25-12.29</td>
−
     <td>2-17：矩阵计算</td>
+
     <td>3-17：平面</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第28章</li>
+
         <li>CHENG第10章</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>
第217行： 第214行：
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td>暑假自学</td>
+
     <td>寒假自学</td>
−
     <td>2-18：串匹配</td>
+
     <td>3-18：背包问题</td>
 
     <td>
 
     <td>
 
       <ul>
 
       <ul>
−
         <li>TC第32章</li>
+
         <li>JH第4.3.4节</li>
 
       </ul>
 
       </ul>
 
     </td>
 
     </td>

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

基本要求

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

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

指定教材

  • 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：有向图和伪多项式时间算法
  • CHENG第7章
  • JH第3.2.1、3.2.3节
11.6-11.10 3-10：问题的形式化描述
  • JH第2.3.1、2.3.2节
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节
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2022级--学期安排_(第三学期)&oldid=5072”