“2017级--小班讨论 (第三学期)”的版本间的差异
来自问题求解
(→学习周历) |
(→学习周历) |
||
(未显示同一用户的15个中间版本) | |||
第46行: | 第46行: | ||
# [[Media:3-2-Huffman-张灵毓.pptx | 张灵毓]] | # [[Media:3-2-Huffman-张灵毓.pptx | 张灵毓]] | ||
* Tiling Path | * Tiling Path | ||
− | # 鄢振宇 | + | # |
+ | # 鄢振宇 | ||
| | | | ||
* 无 | * 无 | ||
第142行: | 第143行: | ||
| | | | ||
* Floyd-Warshall 算法输出最短路径 | * Floyd-Warshall 算法输出最短路径 | ||
− | # 周海波 | + | # [[Media:3-8-FloydWarshall-周海波.pptx | 周海波]] |
# [[Media:3-8-FloydWarshall-李凯旭.pptx | 李凯旭]] | # [[Media:3-8-FloydWarshall-李凯旭.pptx | 李凯旭]] | ||
* 炼钢厂选址 | * 炼钢厂选址 | ||
第167行: | 第168行: | ||
| 2018-11-26 | | 2018-11-26 | ||
| | | | ||
− | * [[Media:3-9-connectivity.pdf | 3-9-connectivity]] | + | * [[Media:3-9-connectivity-part-I.pdf | 3-9-connectivity-part-I]] |
− | * [[Media:3-9-connectivity-handout.pdf | 3-9-connectivity-handout]] | + | * [[Media:3-9-connectivity-part-I-handout.pdf | 3-9-connectivity-part-I-handout]] |
| | | | ||
* 竞赛图 | * 竞赛图 | ||
第182行: | 第183行: | ||
| 2018-12-03 | | 2018-12-03 | ||
| | | | ||
− | * [[Media:3-9- | + | * [[Media:3-9-connectivity-part-II.pdf | 3-9-connectivity-part-II: Menger Theorem]] |
− | * [[Media:3-9- | + | * [[Media:3-9-connectivity-part-II-handout.pdf | 3-9-connectivity-part-II-handout: Menger Theorem]] |
− | * [[Media:3-10-traversability.pdf | 3-10-traversability]] | + | * [[Media:3-10-traversability-part-I.pdf | 3-10-traversability-part-I: Eulerian Graphs]] |
− | * [[Media:3-10-traversability-handout.pdf | 3-10-traversability-handout]] | + | * [[Media:3-10-traversability-part-I-handout.pdf | 3-10-traversability-part-I-handout: Eulerian Graphs]] |
| | | | ||
* 点独立与点覆盖 | * 点独立与点覆盖 | ||
第192行: | 第193行: | ||
# [[Media:3-11-Cover-韩博.pptx | 韩博]] | # [[Media:3-11-Cover-韩博.pptx | 韩博]] | ||
* 点独立与点覆盖 | * 点独立与点覆盖 | ||
− | # [[Media: 3-11- | + | # [[Media: 3-11-Konig-杨欣然.pptx | 杨欣然]] |
| | | | ||
− | * | + | * 无 |
|- | |- | ||
+ | | 2018-12-10 | ||
+ | | | ||
+ | * [[Media:3-10-traversability-part-II.pdf | 3-10-traversability-part-II: Hamiltonian Graphs]] | ||
+ | * [[Media:3-10-traversability-part-II-handout.pdf | 3-10-traversability-part-II-handout: Hamiltonian Graphs]] | ||
+ | * [[Media:3-11-matchings-factors-part-I.pdf | 3-11-matchings-factors-part-I: Matchings and Covers]] | ||
+ | * [[Media:3-11-matchings-factors-part-I-handout.pdf | 3-11-matchings-factors-part-I-handout: Matchings and Covers]] | ||
+ | | | ||
+ | * Ford-Fulkerson's Labeling Algorithm | ||
+ | # [[Media:3-12-FordFulkerson-张梓悦.pptx | 张梓悦]] | ||
+ | # [[Media:3-12-FordFulkerson-周涛.pdf | 周涛]] | ||
+ | * 利用最大流算法证明 Hall 定理 | ||
+ | # [[Media:3-12-NetworkFlowHall-裴一凡.pdf | 裴一凡]] | ||
+ | # [[Media:3-12-NetworkFlowHall-董杨静.pdf | 董杨静]] | ||
+ | | | ||
+ | * [https://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem (wiki)] | ||
+ | * [https://www.youtube.com/watch?v=Qcv1IqHWAzg Stable Marriage Problem@Numberphile@YouTube] | ||
+ | 有意思的 Stable Matching Problem | ||
+ | |- | ||
+ | | 2018-12-17 | ||
+ | | | ||
+ | * [[Media:3-12-network-flow.pptx | 3-12-network-flow.pptx]] | ||
+ | | | ||
+ | * Brooks 定理 | ||
+ | # [[Media:3-13-Brooks-张廷昊.pptx | 张廷昊]]、[[Media:3-13-Brooks-裴明亮.pdf | 裴明亮]] | ||
+ | # [[Media: 3-13-Brooks-高天朗-邱凯.pptx | 高天朗、邱凯]] | ||
+ | * Martin Gardner | ||
+ | # [[Media:3-13-MartinGardner-赵新榆.pptx | 赵新榆]] | ||
+ | # [[Media:3-13-MartinGardner-兰兆炜.pdf | 兰兆炜]] | ||
+ | | | ||
+ | * 无 | ||
+ | |- | ||
+ | | 2018-12-24 | ||
+ | | | ||
+ | * [[Media:3-11-matchings-factors-part-II.pdf | 3-11-matchings-factors-part-II: Perfect Matchings]] | ||
+ | * [[Media:3-11-matchings-factors-part-II-handout.pdf | 3-11-matchings-factors-part-II-handout: Perfect Matchings]] | ||
+ | | | ||
+ | * LUP 分解算法的正确性 | ||
+ | # [[Media:3-14-LUP-Correctness-廖玺然.pptx | 廖玺然]] | ||
+ | # [[Media:3-14-LUP-Correctness-陶绍诚.pptx | 陶绍诚]] | ||
+ | * LUP 分解求矩阵的行列式 | ||
+ | # [[Media:3-14-LUP-Det-张扬播.pdf | 张扬播]] | ||
+ | # [[Media:3-14-LUP-Det-顾宬.zip | 顾宬]] | ||
+ | | | ||
+ | * [[Media:Matching_Euler_Tours_and_the_Chinese_Postman_(Jack_Edmonds-Johnson,_1973).pdf | Matching Euler Tours and the Chinese Postman (Jack Edmonds-Johnson, 1973).pdf]] | ||
+ | Page 92、Page 93: 利用 Perfect Matching 解决 Chinese Postman Problem。 | ||
+ | * [[Media:Shortest_Path_Algorithms_(math.sfu.ca,_Math_408,_Luis_Goddyn).pdf | Shortest Path Algorithms (math.sfu.ca, Math 408, Luis Goddyn).pdf]] | ||
+ | 利用 Perfect Matching 求无向图(允许有负权边,但不允许有负圈)中的最短简单路径。 | ||
+ | WARNING: 内有少量笔误,把它们找出来吧; 里面还有大量未加证明的论述,把它们证明了吧。然后,你就算真得懂了。 | ||
+ | |- | ||
+ | | 2018-12-29 | ||
+ | | | ||
+ | * 平面图与点着色 | ||
+ | | | ||
+ | * CZ 9.8、CZ 10.5 | ||
+ | # [[Media:3-15-HW-戴若石.pdf | 戴若石]] | ||
+ | * CZ Theorem 10.10 | ||
+ | # [[Media:3-15-Coloring-陈昱名.zip | 陈昱名]] | ||
+ | * Dilworth Theorem | ||
+ | # [[Media:3-15-DilworthTheorem-殷兆恒.zip | 殷兆恒]] | ||
+ | # 张博乔 (取消) | ||
+ | | | ||
+ | * [[Media:Equivalence_of_Seven_Major_Theorems_in_Combinatorics_(Robert_Borgersen,_2004).pdf | Equivalence of Seven Major Theorems in Combinatorics (Robert Borgersen, 2004).pdf]] | ||
|} | |} |
2019年1月2日 (三) 10:31的最新版本
学习周历
日期 | 论题 | Open Topics
(分班表) |
扩展材料 (供感兴趣的同学自学使用) |
---|---|---|---|
2018-09-03 |
|
| |
2018-09-17 |
|
学习如何深入浅出地讲解算法。 | |
2018-09-27 |
|
| |
2018-09-29 |
|
更多有些难度的贪心算法。学习如何分析并证明贪心算法的正确性。 | |
2018-10-08 |
|
进一步熟悉平摊分析的概念与应用。 Robert Tarjan 关于 Amortized Analysis 的论文。 | |
2018-10-15 |
|
Robert Tarjan、Daniel Sleator 关于 Splay Tree 的论文。学习 Splay Tree 数据结构。学习平摊分析技术。 强烈推荐。 | |
2018-10-22 |
|
体会不同的讲法。学习MST相关定理的证明技巧。 | |
2018-10-29 |
|
Robert Tarjan 关于 DFS 在图算法中的应用的经典论文 | |
2018-11-05 |
|
Robert Tarjan's Bicomponent Algorithm | |
2018-11-12 |
|
||
2018-11-19 |
|
所有点对之间的最短路径问题的下界 | |
2018-11-26 |
|
关于连通度的算法。 | |
2018-12-03 |
|
| |
2018-12-10 |
|
有意思的 Stable Matching Problem | |
2018-12-17 |
|
| |
2018-12-24 |
|
Page 92、Page 93: 利用 Perfect Matching 解决 Chinese Postman Problem。 利用 Perfect Matching 求无向图(允许有负权边,但不允许有负圈)中的最短简单路径。 WARNING: 内有少量笔误,把它们找出来吧; 里面还有大量未加证明的论述,把它们证明了吧。然后,你就算真得懂了。 | |
2018-12-29 |
|
|