“2018级--学期安排 (第二学期)”的版本间的差异
来自问题求解
（创建页面，内容为“==暂时沿用2016级的学期安排== ==基本要求== <ul> <li>理解数据抽象，理解并能够应用常用的数据结构。</li> <li>掌握重要算法...”） |
（→学习周历） |
||
| （未显示同一用户的7个中间版本） | |||
| 第1行： | 第1行： | ||
| − | |||
| − | |||
==基本要求== | ==基本要求== | ||
<ul> | <ul> | ||
| 第12行： | 第10行： | ||
<ul> | <ul> | ||
<li>'''CS''': Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010</li> | <li>'''CS''': Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010</li> | ||
| − | <li>'''GC''': Gary Chartrand et al.: | + | <li>'''GC''': Gary Chartrand et al.: A First Course in Graph Theory, 1st ed. Dover, 2012</li> |
<li>'''SB''': Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)</li> | <li>'''SB''': Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)</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> | ||
| 第31行： | 第29行： | ||
<th>阅读材料</th> | <th>阅读材料</th> | ||
<th>引导要点</th> | <th>引导要点</th> | ||
| − | |||
| − | |||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>2. | + | <td>2.25-3.1</td> |
| − | <td>2-1：算法问题与解题的算法</td> | + | <td>[[媒体文件:计算机问题求解-2019-02-25-算法问题与解题的算法.pdf|2-1：算法问题与解题的算法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第51行： | 第47行： | ||
<ul> | <ul> | ||
<li>算法设计与算法分析是计算机问题求解不可互却的两个方面</li> | <li>算法设计与算法分析是计算机问题求解不可互却的两个方面</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td> | + | <td>3.4-3.8</td> |
| − | <td>2-2：组合与计数</td> | + | <td>[[媒体文件:计算机问题求解-2019-03-04-组合与计数.pdf|2-2：组合与计数]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第82行： | 第66行： | ||
<ul> | <ul> | ||
<li>为什么算法分析中需要计数</li> | <li>为什么算法分析中需要计数</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>3. | + | <td>3.11-3.15</td> |
| − | <td>2-3：分治法与递归</td> | + | <td>[[媒体文件:计算机问题求解-2019-03-11-分治法与递归.pdf|2-3：分治法与递归]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第115行： | 第86行： | ||
<ul> | <ul> | ||
<li>策略在计算机算法设计中的意义</li> | <li>策略在计算机算法设计中的意义</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>3. | + | <td>3.18-3.22</td> |
| − | <td>2-4：递归及其数学基础</td> | + | <td>[[媒体文件:计算机问题求解-2019-03-18-递归及其数学基础.pdf|2-4：递归及其数学基础]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第142行： | 第100行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CS第4章第1、2、3、4节</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第148行： | 第106行： | ||
<ul> | <ul> | ||
<li>如何解递归式</li> | <li>如何解递归式</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>3. | + | <td>3.25-3.29</td> |
| − | <td>2-5：离散概率基础</td> | + | <td>[[媒体文件:计算机问题求解-2019-03-25-离散概率基础.pdf|2-5：离散概率基础]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第183行： | 第126行： | ||
<ul> | <ul> | ||
<li>正确理解期望值，由此建立算法分析中期望效率理解的基础</li> | <li>正确理解期望值，由此建立算法分析中期望效率理解的基础</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td> | + | <td>4.1-4.5</td> |
| − | <td>2-6：概率分析与随机算法</td> | + | <td>[[媒体文件:计算机问题求解-2019-04-01-概率分析与随机算法.pdf|2-6：概率分析与随机算法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第217行： | 第147行： | ||
<ul> | <ul> | ||
<li>随机变量在算法分析中的意义</li> | <li>随机变量在算法分析中的意义</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>4. | + | <td>4.8-4.12</td> |
| − | <td>2-7：排序与选择</td> | + | <td>[[媒体文件:计算机问题求解-2019-04-08-排序与选择.pdf|2-7：排序与选择]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第252行： | 第168行： | ||
<ul> | <ul> | ||
<li>如何证明问题复杂度的下限</li> | <li>如何证明问题复杂度的下限</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>4. | + | <td>4.15-4.19</td> |
<td>2-8：基本数据结构</td> | <td>2-8：基本数据结构</td> | ||
<td> | <td> | ||
| 第292行： | 第187行： | ||
<ul> | <ul> | ||
<li>数据结构的算法支撑与实现效率的平衡</li> | <li>数据结构的算法支撑与实现效率的平衡</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>4. | + | <td>4.22-4.26</td> |
| − | <td>2-9：堆与堆排序</td> | + | <td>[[媒体文件:计算机问题求解-2019-04-22-堆与堆排序.pdf|2-9：堆与堆排序]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第327行： | 第208行： | ||
<ul> | <ul> | ||
<li>从数据结构到抽象数据类型的思想发展</li> | <li>从数据结构到抽象数据类型的思想发展</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>4. | + | <td>4.29-5.3</td> |
| − | <td>2-10：Hashing方法</td> | + | <td>[[媒体文件:计算机问题求解-2019-04-29-hashing方法.pdf|2-10：Hashing方法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第361行： | 第228行： | ||
<ul> | <ul> | ||
<li>Hashing方法中的冲突处理</li> | <li>Hashing方法中的冲突处理</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>5. | + | <td>5.6-5.10</td> |
| − | <td>2-11：搜索树</td> | + | <td>[[媒体文件:计算机问题求解-2019-05-6-搜索树.pdf|2-11：搜索树]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第394行： | 第247行： | ||
<ul> | <ul> | ||
<li>树的平衡与搜索效率的关系</li> | <li>树的平衡与搜索效率的关系</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>5. | + | <td>5.13-5.17</td> |
| − | <td>2-12：动态规划</td> | + | <td>[[媒体文件:计算机问题求解-2019-05-13-动态规划.pdf|2-12：动态规划]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第431行： | 第267行： | ||
<li>以空间换时间的关键是存储效率</li> | <li>以空间换时间的关键是存储效率</li> | ||
<li>动态规划与指数时间的有效降低</li> | <li>动态规划与指数时间的有效降低</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>5. | + | <td>5.20-5.24</td> |
| − | <td>2-13：贪心算法</td> | + | <td>[[媒体文件:计算机问题求解-2019-05-20-贪心算法.pdf|2-13：贪心算法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第467行： | 第288行： | ||
<ul> | <ul> | ||
<li>贪心算法的正确性证明</li> | <li>贪心算法的正确性证明</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>5. | + | <td>5.27-5.31</td> |
| − | <td>2-14：用于动态等价关系的数据结构</td> | + | <td>[[媒体文件:计算机问题求解-2019-05-27-用于动态等价关系的数据结构.pdf|2-14：用于动态等价关系的数据结构]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第502行： | 第310行： | ||
<ul> | <ul> | ||
<li>算法分析的困难性</li> | <li>算法分析的困难性</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td> | + | <td>6.3-6.7</td> |
| − | <td>2-15：图的基本概念</td> | + | <td>[[媒体文件:计算机问题求解-2019-06-03-图的基本概念.pdf|2-15：图的基本概念]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第537行： | 第332行： | ||
<li>图论应用的广泛性以及图论证明方法的独特性</li> | <li>图论应用的广泛性以及图论证明方法的独特性</li> | ||
<li>理解图与关系的联系</li> | <li>理解图与关系的联系</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td>6. | + | <td>6.10-6.14</td> |
<td>2-16：图的计算机表示以及遍历</td> | <td>2-16：图的计算机表示以及遍历</td> | ||
<td> | <td> | ||
| 第575行： | 第353行： | ||
<li>图表示中形式与效率的关系</li> | <li>图表示中形式与效率的关系</li> | ||
<li>不同遍历方法的算法意义</li> | <li>不同遍历方法的算法意义</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td> | + | <td>暑假自学</td> |
<td>2-17：树</td> | <td>2-17：树</td> | ||
<td> | <td> | ||
| 第609行： | 第373行： | ||
<ul> | <ul> | ||
<li>树的数学性质在计算机问题求解中的意义</li> | <li>树的数学性质在计算机问题求解中的意义</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| − | <td> | + | <td>暑假自学</td> |
<td>2-18：最小生成树算法</td> | <td>2-18：最小生成树算法</td> | ||
<td> | <td> | ||
| 第640行： | 第392行： | ||
<ul> | <ul> | ||
<li>如何评价同一问题的不同算法</li> | <li>如何评价同一问题的不同算法</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
</table> | </table> | ||
2019年6月5日 (三) 21:15的最新版本
基本要求
- 理解数据抽象，理解并能够应用常用的数据结构。
- 掌握重要算法设计策略以及算法设计与分析的基本方法。
- 理解并能够应用支持上述内容的离散数学工具与方法。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- CS: Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
- GC: Gary Chartrand et al.: A First Course in Graph Theory, 1st ed. Dover, 2012
- SB: Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008
推荐课外读物
- Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th ed. McGraw-Hill, 2011
学习周历
| 日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 |
|---|---|---|---|---|
| 2.25-3.1 | 2-1：算法问题与解题的算法 |
|
|
|
| 3.4-3.8 | 2-2：组合与计数 |
|
|
|
| 3.11-3.15 | 2-3：分治法与递归 |
|
|
|
| 3.18-3.22 | 2-4：递归及其数学基础 |
|
|
|
| 3.25-3.29 | 2-5：离散概率基础 |
|
|
|
| 4.1-4.5 | 2-6：概率分析与随机算法 |
|
|
|
| 4.8-4.12 | 2-7：排序与选择 |
|
|
|
| 4.15-4.19 | 2-8：基本数据结构 |
|
|
|
| 4.22-4.26 | 2-9：堆与堆排序 |
|
|
|
| 4.29-5.3 | 2-10：Hashing方法 |
|
|
|
| 5.6-5.10 | 2-11：搜索树 |
|
|
|
| 5.13-5.17 | 2-12：动态规划 |
|
|
|
| 5.20-5.24 | 2-13：贪心算法 |
|
|
|
| 5.27-5.31 | 2-14：用于动态等价关系的数据结构 |
|
|
|
| 6.3-6.7 | 2-15：图的基本概念 |
|
|
|
| 6.10-6.14 | 2-16：图的计算机表示以及遍历 |
|
|
|
| 暑假自学 | 2-17：树 |
|
|
|
| 暑假自学 | 2-18：最小生成树算法 |
|
|
|
