“2023级--学期安排 (第三学期)”的版本间的差异
来自问题求解
(→学习周历) |
|||
(未显示同一用户的19个中间版本) | |||
第1行: | 第1行: | ||
==指定教材== | ==指定教材== | ||
<ul> | <ul> | ||
− | <li>'''CH''': 程龚: 图论与算法, | + | <li>'''CH''': 程龚: [http://ws.nju.edu.cn/gtabook 图论与算法], 2024</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>'''TJ''': Thomas Judson: Abstract Algebra - Theory and Applications, | + | <li>'''TJ''': Thomas Judson: Abstract Algebra - Theory and Applications, August 12, 2015.</li> |
<li>'''WS''': Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008</li> | <li>'''WS''': Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008</li> | ||
</ul> | </ul> | ||
第40行: | 第40行: | ||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td> | + | <td>【学号后3位 % 3 = 0的同学完成】<br/>图在计算机和人工智能研究中有很多应用,例如程序分析中的[https://en.m.wikipedia.org/wiki/Control-flow_graph 控制流图]、信息检索中的[https://en.wikipedia.org/wiki/Webgraph 网页链接图]、知识表示中的[https://en.wikipedia.org/wiki/Knowledge_graph 知识图谱]等,请调研至少3种应用(其中至多1种来自上述例子),描述应用场景,讨论用图建模的方式,形式化描述问题并概述现有解决方案。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第83行: | 第83行: | ||
</td> | </td> | ||
<td>中秋调休,本次课安排在9月14日</td> | <td>中秋调休,本次课安排在9月14日</td> | ||
− | <td> | + | <td>中秋放假</td> |
− | |||
− | |||
− | |||
− | |||
− | |||
<td>【学号后3位 % 3 = 2的同学完成】<br/>请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件,讨论条件的适用场景,并阐述证明过程。</td> | <td>【学号后3位 % 3 = 2的同学完成】<br/>请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件,讨论条件的适用场景,并阐述证明过程。</td> | ||
</tr> | </tr> | ||
第108行: | 第103行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习3.14</li> |
+ | <li>CH练习3.22</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = 0的同学完成】<br/> | + | <td>【学号后3位 % 3 = 0的同学完成】<br/>请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法;门格尔定理在图论中有很多应用,请调研至少2种应用,描述应用场景。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第152行: | 第148行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习4.2</li> |
</ul> | </ul> | ||
</td> | </td> | ||
第176行: | 第172行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习5.2、5.3</li> |
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = | + | <td>【学号后3位 % 3 = 1的同学完成】<br/>花算法有很多优化改进,例如[https://doi.org/10.1145/321941.321942 Gabow'76]、[https://doi.org/10.1109/SFCS.1980.12 Micali'80]等,请调研至少2种优化改进(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与花算法比较异同并分析优劣。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第198行: | 第194行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习6.1、6.2</li> |
− | |||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = | + | <td>【学号后3位 % 3 = 2的同学完成】单源最短路问题有很多并行算法,例如[https://doi.org/10.1016/S0196-6774(03)00076-2 Δ-stepping算法]、[https://doi.org/10.1145/2935764.2935765 Radius Stepping算法]等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,比较异同并分析优劣。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第221行: | 第216行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>请编程实现Floyd-Warshall算法。</li> |
+ | <li>请编程实现Johnson算法。</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = 0的同学完成】<br/> | + | <td>【学号后3位 % 3 = 0的同学完成】<br/>[https://doi.org/10.1145/2530531 距离索引](Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第242行: | 第238行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习6.4</li> |
− | |||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = 1的同学完成】<br/> | + | <td>【学号后3位 % 3 = 1的同学完成】<br/>最小生成树问题有很多[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> | ||
第265行: | 第260行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li>CH练习7. | + | <li>CH练习7.3</li> |
+ | <li>CH练习7.11</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td> | + | <td>作业讲解 + OJ讲解</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第287行: | 第283行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习7.23</li> |
</ul> | </ul> | ||
</td> | </td> | ||
− | <td> | + | <td>【学号后3位 % 3 = 2的同学完成】<br/>除福特-法尔克森算法外,最大流问题还有很多其它算法,例如[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> | ||
第308行: | 第304行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习8.3、8.4</li> |
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = 0的同学完成】<br/> | + | <td>【学号后3位 % 3 = 0的同学完成】<br/>在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、[https://en.wikipedia.org/wiki/Connected_dominating_set 最小连通支配集问题]等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第323行: | 第319行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>TJ第3章练习3、6、7、17、29、37、39、42、49</li> |
<li>TJ第4章练习1、12、21、24、32</li> | <li>TJ第4章练习1、12、21、24、32</li> | ||
</ul> | </ul> | ||
第330行: | 第326行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>CH练习9.3、9.4</li> |
</ul> | </ul> | ||
</td> | </td> | ||
− | <td>【学号后3位 % 3 = 1的同学完成】<br/> | + | <td>【学号后3位 % 3 = 1的同学完成】<br/>除米什拉-格赖斯算法和贪心算法外,边染色和点染色问题还有很多其它算法,请为每种问题调研至少1种精确算法(暴力算法不在调研范围内),结合例子介绍算法的设计与分析。</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第346行: | 第342行: | ||
<ul> | <ul> | ||
<li>TJ第5章练习3、5、16、27、29</li> | <li>TJ第5章练习3、5、16、27、29</li> | ||
− | <li> | + | <li>TJ第6章练习11、12、16</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td>正常上课</td> | <td>正常上课</td> | ||
− | <td> | + | <td> |
− | <td>【学号后3位 % 3 = 2的同学完成】<br/> | + | <ul> |
+ | <li>CH练习10.5</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td>【学号后3位 % 3 = 2的同学完成】<br/>除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
第373行: | 第373行: | ||
</ul> | </ul> | ||
</td> | </td> | ||
− | <td> | + | <td>作业讲解 + OJ讲解</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>12.23-12.27</td> | <td>12.23-12.27</td> | ||
− | <td> | + | <td>复习</td> |
+ | <td>无</td> | ||
+ | <td>无</td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>部分同学讲解TJ第9、10章</li> |
+ | <li>部分同学讲解TJ第12.1、12.2节</li> | ||
+ | <li>部分同学讲解TJ第16.1、16.2节</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
+ | <td>OJ期末考试</td> | ||
+ | <td>答疑</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td>寒假自学</td> | ||
+ | <td>群同构、正规子群和因子群、群同态</td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>TJ第9、10、11章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
− | <td> | + | <td></td> |
− | <td> | + | <td></td> |
− | <td> | + | <td></td> |
+ | <td></td> | ||
</tr> | </tr> | ||
</table> | </table> |
2024年12月16日 (一) 16:46的最新版本
指定教材
- CH: 程龚: 图论与算法, 2024
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- TJ: Thomas Judson: Abstract Algebra - Theory and Applications, August 12, 2015.
- WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008
学习周历
日期 | 论题 | 阅读材料 | 书面作业 | 周一小班(讲课) | 周二大班(OJ) | 周四大班(OT) |
---|---|---|---|---|---|---|
9.2-9.6 | 3-1:图的基本概念 |
|
|
正常上课 |
|
【学号后3位 % 3 = 0的同学完成】 图在计算机和人工智能研究中有很多应用,例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等,请调研至少3种应用(其中至多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种证明方法;门格尔定理在图论中有很多应用,请调研至少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的同学完成】 花算法有很多优化改进,例如Gabow'76、Micali'80等,请调研至少2种优化改进(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与花算法比较异同并分析优劣。 |
10.21-10.25 | 3-8:最小生成树和赋权欧拉图 |
|
|
正常上课 |
|
【学号后3位 % 3 = 2的同学完成】单源最短路问题有很多并行算法,例如Δ-stepping算法、Radius Stepping算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,比较异同并分析优劣。 |
10.28-11.1 | 3-9:有向图 |
|
|
正常上课 |
|
【学号后3位 % 3 = 0的同学完成】 距离索引(Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。 |
11.4-11.8 | 3-10:流网络和最大流 |
|
|
正常上课 |
|
【学号后3位 % 3 = 1的同学完成】 最小生成树问题有很多相关问题,例如Steiner tree、k-MST、MBST等,请调研至少2种问题(其中至多1种来自上述例子,欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题并概述现有解决方案。 |
11.11-11.15 | 3-11:独立、覆盖和支配 |
|
|
正常上课 |
|
作业讲解 + OJ讲解 |
11.18-11.22 | 3-12:染色 |
|
|
正常上课 |
|
【学号后3位 % 3 = 2的同学完成】 除福特-法尔克森算法外,最大流问题还有很多其它算法,例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与福特-法尔克森算法比较异同并分析优劣。 |
11.25-11.29 | 3-13:平面 |
|
|
正常上课 |
|
【学号后3位 % 3 = 0的同学完成】 在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、最小连通支配集问题等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。 |
12.2-12.6 | 3-14:群和循环群 |
|
|
正常上课 |
|
【学号后3位 % 3 = 1的同学完成】 除米什拉-格赖斯算法和贪心算法外,边染色和点染色问题还有很多其它算法,请为每种问题调研至少1种精确算法(暴力算法不在调研范围内),结合例子介绍算法的设计与分析。 |
12.9-12.13 | 3-15:置换群、陪集和拉格朗日定理 |
|
|
正常上课 |
|
【学号后3位 % 3 = 2的同学完成】 除DMP算法外,可平面图的判定问题还有很多其它算法,请调研至少2种算法,结合例子介绍算法的设计与分析,与DMP算法比较异同并分析优劣。 |
12.16-12.20 | 3-16:代数编码 |
|
|
正常上课 |
|
作业讲解 + OJ讲解 |
12.23-12.27 | 复习 | 无 | 无 |
|
OJ期末考试 | 答疑 |
寒假自学 | 群同构、正规子群和因子群、群同态 |
|