2025.9.10 更新

今天吕老师和徐老师班一起进行了 2025 春代数结构的查卷. 查卷结束临走的时候, 徐老师和在场包括我在内的两位助教吐槽了几件事, 非常有趣, 在这里稍微记一下: 

一是吐槽这几年来代数结构和图论的试卷已经出得越来越简单, 但学生做出来的答卷却没有相应的起色, 言下似乎有点 “学生一届比一届差” 的意味. 按徐老师的原话, “尤其是上学期的这个代数结构, 学得好的人半个多小时就能写完, 不知道出出来干嘛" . 我不知道徐老师有没有看吕老师班的卷面情况, 如果看了就该知道吕老师班卷面分几乎已经突破了优秀率限制……有点难绷.

二是代数结构和图论的卷子, 只要稍微出难一点, 学生做得就一塌糊涂: 多半是写了大半面纸, 没有一句有用的话, 最后只能给一两分, 一来二去卷面总分低到可怕, 教务处那边过不了关; 出简单吧, 学生又大半能做全对, 拉不开区分度, 特别是优秀率下面一点儿竞争激烈的学生, 一看自己总评 84 , 难免查卷的时候要来吵吵, 不胜其烦, 干脆全给他们 83 (所以学生查卷的时候采取最激进的策略长期来看未必是有好处的). 

我总觉得这两条吐槽有点儿 “左脑战胜右脑” 的意味: 如果真怕卷面分高, 稍微出难一点, 出卷面分之后再向上调分, 这样又能拉开区分度, 又能让学生开心, 岂不两全其美? 我给徐老师分析了去年图论卷面分冲破天际的原因: 计算题和算法手操题太多, 证明题太少, 而且全是书上有的原题, 自然压不下去分. 这时徐老师回答了我他图论教学的一条方针: “我一向觉得学图论, 特别是计算机系的同学学图论, 会很多证明不是重要的.” 至于什么重要, 他没说. 这话单拿出来到很合适, 但是放在科大计科离散数学已经一分为三的前提下, 又刚吐槽过卷面分压不下来, 总让人感觉有点儿自相矛盾. 去年有学生表达了现在的图论课与算法基础课重合度过高的意见, 我把这条意见转达给了徐老师 (实际上这个问题不成为问题: 图论考试和算法基础考试虽然都有算法题, 但前者是 “算法手操题” , 后者是 “算法设计题” , 并不是重合关系, 而是图论课被算法基础课完爆的关系) , 他没说话. 临走的时候徐老师说了句, “今年的图论出卷怎么搞, 我还要想想.” 我感觉做久了领导位子的老师, 说话做事, 果然都带着这样一种雷打不动的沉稳.

当年立志要把离散三部曲的助教全部带一遍的我, 是带着点 “改善教学质量” 的雄心壮志的; 两年后的我大概验证了, 在助教的位子上, 做不了什么对这个目的有帮助的事情. 从水论文的角度讲, 我这种 “证明走不通” , 倒也算一个成果. 说做不了什么, 倒不是说这几位老师不好, 而是现在这几门课 (当然可能不局限于这几门课) 的教学已经陷入了一种死而不僵的状态: 所有局部虽然一起构成一个整体, 但是这个整体并不呈现出什么意志, 能够努力用功达到一个理想的目标; 只有每个局部干自己的事, 干的时候遵照一种 “方向上不出错, 过程上最轻便” 的方针, 保证自己这个环节不出原则问题, 事后没人追责追到到自己头上. 至于工作的成效, 在纸面的, 可见的方面 (例如学生成绩) , 那自然是完全说得过去; 但在潜在的, 长远的方面 (例如学生到底学会了什么图论) , 没人愿意担这个责任, 触这个霉头. 具体地说, 教师考虑的是怎么让学生不起意见, 怎么让卷面分好看, 怎么在教务处那边过得去; 助教考虑的是怎么应付完工作不亏工资, 怎么让学生少来找自己, 怎样弄完老师指派的任务. 

为了实现改善教学质量的目标, 我原准备了几条意见, 其中首要的一条就是增设习题课, 确保学生能够即使发现自己的不解和误解, 得到反馈. 如果理解了这台课程机器的上述运行原理, 就容易推出这种意见为什么通不过: 从老师的角度讲, 此事没有先例, 不做不会有人说什么; 做了, 助教这边时间精力成本增加, 埋怨的是自己, 此外明面上给学生增加上课负担, 如果最后没有纸面上的成效 (当然也不可能有: 课程绩点是个零和游戏, 给所有的学生上同一堂习题课, 没法让每个人总评都高 10 分) , 免不了被学生喷. 从助教的角度讲, 原本安安心心批作业, 准备一下习题课讲作业 ppt 就能领工资; 现在还要自己上习题课讲课, 还要研究学生的理解疑难, 工资并不多拿一块钱, 是万本无利的买卖. 从我自己的角度讲, 现在这两门课助教生态越来越差, 如果徐老师真奇迹般地因为听了我的意见, 而实行了这种改革, 将来混工资的助教自己脑子里没有多少理解, 心态上又厌于应付, 胡乱准备一通就讲, 落实到学生身上估计也没多大益处. 所以直到最后走的时候, 我也没提什么意见.

我觉得通过做助教的方式改善教学质量或许终将是无效的. 这里的 “终将” 是在这样一种意义下: “单个学期的助教工作, 对学生带来的益处, 随着时间推移而趋近于 0 ” . 这是因为助教工作是一时的: 讲一次习题课, 说话声能在学生脑子里的留存, 终归是越来越少. 如果没有配套的精心设计的习题, 没有学习习惯上的指引, 这种衰减还要快得多, 恐怕半衰期还不到一个月. 将来我也许会尝试做一些 “做一次而生效无数次” 的工作, 继续写那两本笔记自然是一方面, 但现在看来效果有限. 未来也许会试试录课发到b站上这种形式.

不过, 徐宏力老师是真给满优秀率啊, 大善人.

推荐和代数结构的评课搭配食用: https://www.icourse.club/course/14363/

·

内容简介

在读者没有了解关于图的一些定义的前提下, 几乎不可能根据课本的章节名字有意义地介绍每个部分讲什么. 因此建议读者至少粗看一遍课本的第一章, 然后再看目录中每一章的标题. 这里只讲一点抽象的结构:

图论的知识和代数结构有相似也有不同. 相似之处在于二者都有抽象的特点, 学习的过程中很需要学习者 "凭空想象" 的能力--即使图论有时可以寻求可视化的理解, 也要注意画出来的 "图" 与图论中的图是不同的, 并且没有很强的关联性. 有时拿画的图来理解图论反而会有误导效果, 比如你可能默认了一些看上去很显然, 但证明并不平凡甚至错误的结论.

不同之处主要在于图论的知识体系比较零散. 如果说代数结构每一章的知识结构是链式的 (不学群就没有办法学环和域) , 那么图论的知识结构就是树状的: 学了第1章图的基本概念, 几乎就可以开始接触2~10章中的任何地方; 即使第3章连通性学得云里雾里, 也不妨碍你看第4章可平面图 (这么说其实不太精确, 比如学可平面图的染色显然需要先学了可平面图) . 对学习者来说, 这种松散型一方面作了个保底: 不用担心一个地方没学好影响大局; 另一方面也使得要记的东西更多, 所谓 "融会贯通" 的作用更小.

(11, 12章是偏科普性的内容. 我们这届考试不做要求, 徐老师也意料之中地不讲. )

此外, 图论有很多学习内容是理解解决某个特定问题的算法, 考试也有相当一部分题是让你对一个具体图跑一个算法. 这使得至少决定要应付这门课的同学在这方面可以放心大胆地 "不理解证明, 只知道成立" .

·

讲课

徐老师的讲课风格在代数结构中的点评已有介绍. 这学期据我的舍友说情况更上一层: 不但绝对不跳出课本一句话, 甚至连课本上的内容也不能复述完全. 讲课速度很慢 (发生过一星期没讲完一个知识点因而没有布置作业的情况) , 有时看时间不够或者自己搞不明白就说 "这里我们不细讲" --不过这个事情是我间接听说的, 仅供参考, 真实性自行取舍.

·

作业&考勤

和代数结构也基本一样, 甚至作业量更少了.

考勤方面, 有一天因为到的人太少而愤怒第地点名 (我的一位舍友只迟到了30s好像都没记到课) . 建议的应对方式上一篇也讲了, 此不赘.

(结课后补充: 这次点名好像对总评没有影响)

·

考试

2022秋期末 (开学) 考回忆版:

1. 给定一个图:
(1) 回答是否是二分图并给出理由;
(2) 回答是否是可平面图, 若是则给出面数, 否则说明理由;
(3) 回答是否是Hamilton图并给出理由;
(4) 对一对点执行Dijkstra算法求最短路径.
2. 给定一个二分图及其一个匹配, 用匈牙利算法将其优化为最大匹配.
3. 给定一个情境 (教师用教室上课) 并问一些特定的最优问题, 利用图论的染色知识可求解.
4. 证明: 如果一个图G有Hamilton路径, 则任取V(G)一个非空真子集S, ω(G-S)≤|S|+1.
5. 证明: 一棵树T的所有点度数均为奇数, 当且仅当任取T的一条边e, T-e得到的两个连通片均为奇子树.
6. 证明: 对于一个k色临界图, 其任一割集S不是团, 即S的生成子图G(S)不是完全图.
7. 在考虑同构与不考虑同构的情况下, 分别求出将K5定向成竞赛图的方法数. 对于考虑同构的情况, 写出所有竞赛图.
(有传言说助教会按 “写出所有度数序列” 批改. ~~如果是真的, 鉴定为自己都没学懂.~~ )
8. 利用最大流最小截定理证明König-Egerváry定理.
(不知道直接证明给不给分. )
9. 给定一个基本关联矩阵 (ν=4, ε=5) , 在不画出图的前提下判断:
(1) 其是否是连通图;
(2) 其是否是Eular图;
(3) 其是否是可平面图.

·

学习

课本据同班同学说有一些错误, 但没有代数结构那么高频. 启发性方面比代数结构那肯定是好了不少, 但也仅限于到了及格线.

我对图论没有对抽代那么感兴趣, 也没有自己去找教材完善知识体系, 只是把书上给出的定理都证过了一遍 (除了最难的第3章) . 针对图论的抽象性, 上篇提到的学习建议依然成立.

需要提的一点不同的是: 代数结构的证明格外需要的是思路, 而图论的证明格外需求的除此之外还包括严谨性. 如果不死扣定义出发写证明, 很多定理可能看似平凡得像废话, 但实则你的证明过程是有漏洞的.

推荐的参考书方面, 助教推荐的是清华的教材和习题解答.

·

总评

(23.6.7最终更新)

据ics的群友说, 今年由于许徐两个班的期末考试平均分差距过大 (许班>>徐班) , 赵功名老师决定将两个班合并起来给分, 优秀率也合起来算. 换言之, 许班的优秀率会超40%而徐班则会偏低. 从最后出来的总评结果来看, 合并算分的情况的确是存在的, 但两个班的优秀率依然是各自给的, 这也就使得徐班3.7非常好拿, 从周围同学的情况来看只要作业按时交, 考试把基础分拿到, 基本就比较有可能拿优秀了.

作者期末是班上最高分, 查卷的时候偷瞄了一眼助教的电脑, 看到自己卷面90, 平时分好像是62.5 (因为一半作业是迟交的) . 总评则是89/3.7, 按照老师明面上给出的 "严格三七开" 来算怎么都到不了这个数, 可见老师还是捞了的. 在此也提醒读者千万要按时写作业, 哪怕不会至少也把自己能想到的东西写上去按时交了 (何况你看我都编了份习题解答了) . 不要像我一样平时弃分如土, 总评出了的时候又来懊悔. 除非你对这门课的掌握到了驾轻就熟的地步, 不然关键时候作业分对总评的影响还是相当可观的.

总得来说这门课给分挺好. 但又据流传的内部消息称, 徐老师以后不会带图论班了. 这份评课总结出的修课方法将来不一定还适用, 也请读者仅作参考.

·

其它补充

①

隔壁班的许胤龙老师据说讲课水平很高. 我去听过第一节: 至少讲课风格上与照本宣科大不相同, 而是 在自己认为有必要的地方着重解析地讲, 平凡的地方则少花时间; 实际效果方面, 由于第一节的内容没什么难度, 不具有参考性, 据隔壁班同学说和徐宏力老师是天壤之别. 但许班的作业量远超徐 (好像会把所有大部分课后题都布置下去) , 想学真东西的同学可以考虑采用 "选一门赚绩点, 旁听另一门学知识" 的模式.

这学期许徐两个班的所有助教活跃性都很低. 发通知改作业自然是合格地完成了, 但没有在群里提供额外的帮助. 许班的课群发生过因为助教不回答提问在群里开喷的事. 我不了解助教义务有哪些范围, 对此事没有什么说的.

②

~~23年秋的时候我会尽可能申请这门课的助教.~~ 可惜了, 没申到.

·

资源

图论导引 习题解答.pdf

自己编写的一份教材习题解答 (外加一些对书上知识的讲解) , 希望能够帮助到有需要的同学. 把之前用word写的那个弱智版本撤了下来, 工具换成了latex, 视觉效果应该会好不少. 由于时间有限, 只改编完了1, 2, 4, 5, 6这五章, 以及附录中关于归纳原理的一部分. 之后我会尽量抽时间完成剩下的内容. 如果发现解答中有严重的知识错误, 或者对这份解答有其它意见或建议, 欢迎联系 [email protected]

注意: 分享此解答的目的在于帮助想要深入学习的同学获得更好的反馈, 避免 "做了题但没有答案" 的处境 ~~(也避免某些申必助教在作业答案里写伪证误导学生)~~ . 请不要抄这里面的题解以应付你的课堂作业!

我是22秋图论班的学生。上课徐的水平实在不敢评价，当然如果上课就是把课本在黑板抄一遍再念一遍也叫教书那确实，和许老师云泥之别。先把图论的道理弄懂，许老师带的蛮好的，你再加一个念书的干什么(巧了两人都姓xu）

不过好在作业不多，而且大部分人之后感觉用不到这玩意

课去的不多，主要内容是图的基本性质、树、环路，二分图匹配，连通图和最大流最小割，感觉作为思想体操还是挺有意思的。