“2023级--学期安排 (第三学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| 第33行： | 第33行： | ||
</td> | </td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td> |
| − | <td></td> | + | <ul> |
| + | <li>CH练习1.5、1.6</li> | ||
| + | <li>CH练习1.9、1.10</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td>【学号后3位 % 3 = 0的同学完成】图在计算机和人工智能研究中有很多应用，例如程序分析中的[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> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第53行： | 第58行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 1的同学完成】在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如[https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search 词典序BFS]、[https://en.wikipedia.org/wiki/Bidirectional_search 双向搜索]、[https://en.wikipedia.org/wiki/Best-first_search 最佳优先搜索]等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第73行： | 第78行： | ||
<td>中秋调休，本次课安排在9月14日</td> | <td>中秋调休，本次课安排在9月14日</td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 2的同学完成】请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件，讨论条件的适用场景，并阐述证明过程。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第91行： | 第96行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 0的同学完成】请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法（其中至少1种来自论文原文）；门格尔定理在图论中有很多应用，请调研至少2种应用，描述应用场景。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第131行： | 第136行： | ||
<td>国庆调休，本次课安排在10月12日</td> | <td>国庆调休，本次课安排在10月12日</td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>作业讲解 + OJ讲解</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第151行： | 第156行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 1的同学完成】[https://doi.org/10.1145/2530531 距离索引]（Distance Oracle）是一种用于查询精确或近似距离的数据结构，请调研至少1种精确距离索引和1种近似距离索引，讨论适用场景，结合例子介绍索引构造算法和距离查询算法的设计与分析。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第168行： | 第173行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 2的同学完成】最小生成树问题有很多[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> | ||
| 第186行： | 第191行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 0的同学完成】待定</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
| 第203行： | 第208行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 1的同学完成】除福特-法尔克森算法外，最大流问题还有很多其它算法，例如[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> | ||
| 第221行： | 第226行： | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| − | <td></td> | + | <td>【学号后3位 % 3 = 2的同学完成】在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、[https://en.wikipedia.org/wiki/Connected_dominating_set 最小连通支配集问题]等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
2024年8月18日 (日) 14:22的版本
指定教材
- CH: 程龚: 图论与算法, 2023
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- TJ: Thomas Judson: Abstract Algebra - Theory and Applications, http://abstract.ups.edu/
- WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008
学习周历
| 日期 | 论题 | 阅读材料 | 书面作业 | 周一小班（讲课） | 周二大班（OJ） | 周四大班（OT） |
|---|---|---|---|---|---|---|
| 9.2-9.6 | 3-1：图的基本概念 |
|
|
|
【学号后3位 % 3 = 0的同学完成】图在计算机和人工智能研究中有很多应用，例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等，请调研至少2种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。 | |
| 9.9-9.13 | 3-2：连通和遍历 |
|
|
【学号后3位 % 3 = 1的同学完成】在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如词典序BFS、双向搜索、最佳优先搜索等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。 | ||
| 9.16-9.20 | 3-3：圈和遍历 |
|
|
中秋调休，本次课安排在9月14日 | 【学号后3位 % 3 = 2的同学完成】请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件，讨论条件的适用场景，并阐述证明过程。 | |
| 9.23-9.27 | 3-4：连通度 |
|
|
【学号后3位 % 3 = 0的同学完成】请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法（其中至少1种来自论文原文）；门格尔定理在图论中有很多应用，请调研至少2种应用，描述应用场景。 | ||
| 9.30-10.4 | 3-5：匹配 |
|
|
国庆放假 | 国庆放假 | |
| 10.7-10.11 | 3-6：单源最短路 |
|
|
国庆调休，本次课安排在10月12日 | 作业讲解 + OJ讲解 | |
| 10.14-10.18 | 3-7：多源最短路 |
|
|
【学号后3位 % 3 = 1的同学完成】距离索引（Distance Oracle）是一种用于查询精确或近似距离的数据结构，请调研至少1种精确距离索引和1种近似距离索引，讨论适用场景，结合例子介绍索引构造算法和距离查询算法的设计与分析。 | ||
| 10.21-10.25 | 3-8：最小生成树 |
|
|
【学号后3位 % 3 = 2的同学完成】最小生成树问题有很多相关问题，例如Steiner tree、k-MST、MBST等，请调研至少2种问题（其中至多1种来自上述例子，欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。 | ||
| 10.28-11.1 | 3-9：有向图 |
|
|
【学号后3位 % 3 = 0的同学完成】待定 | ||
| 11.4-11.8 | 3-10：流网络和最大流 |
|
|
【学号后3位 % 3 = 1的同学完成】除福特-法尔克森算法外，最大流问题还有很多其它算法，例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。 | ||
| 11.11-11.15 | 3-11：独立、覆盖和支配 |
|
|
【学号后3位 % 3 = 2的同学完成】在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、最小连通支配集问题等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。 | ||
| 11.18-11.22 | 3-12：染色 |
|
|
|||
| 11.25-11.29 | 3-13：平面 |
|
|
|||
| 12.2-12.6 | 3-14：群和循环群 |
|
|
|||
| 12.9-12.13 | 3-15：置换群、陪集和拉格朗日定理 |
|
|
|||
| 12.16-12.20 | 3-16：代数编码 |
|
|
|||
| 12.23-12.27 | 3-17：群同构、正规子群和因子群 |
|
|
