“人有两件宝，双手和大脑，双手能计算，大脑能思考。”我相信对于科大的学生来讲，学习一门课程，尤其是数学课，不单单只是为了记下一些定理公式和解题套路，更多的还是要学会思考。这也是我希望大家能够通过这门课程的学习，通过自己亲自动手计算，动脑思考，能尝试了解并且掌握这些数学知识发现的过程，并且建立起这些知识之间的内在联系。

最后，我希望大家在科大这几年的学习过程中，能够真正收获学习的快乐（因为真的很快乐），变得聪明，而不是只有被成绩所支配的恐惧。

邵老师在有限时间内，从数学的角度，把这门压缩版课程（代数结构 + 图论，略去了较为形式化的数理逻辑）讲的非常精彩，同时能够充分调动学生自己动手计算、动脑思考，无疑是十分优秀的。但是客观评价这门课，其实与我的预期还有些差距。

数论和代数结构对将来学习密码学 / 形式化方法的同学较为重要；图论几乎覆盖所有主流技术领域，应用广泛，在算法设计中尤为重要。本学期大部分时间都在学习前者，对于图论最后只是浅尝辄止，重心略有失衡。同时，这门课作为 DS 和 AI 的必修课，希望能在课程中加入更多实际算法的应用 /  编程练习，比如RSA 算法、稳定匹配算法、网络拓扑设计、纠错码设计等，这或许会对我们更有帮助。如此看来，丁虎 老师的离散数学课堂似乎更符合我的口味。感兴趣的同学也可以参考 Berkeley 的离散数学入门课程：Discrete Mathematics and Probability Theory。

可能用到的替代关系如下图，计科的代数结构开在秋季，数院的代数学基础开在秋季，想深入了解数理逻辑的可以考虑选择计科的数理逻辑基础。（离散数学在秋季开设给 DS，春季开设给 AI，两位老师的课堂风格迥异，大家可以根据自己的喜好自行选择，然后提前一学期修读）

不点名，不小测，老师明确支持我们选择更适合自己的学习方式。一共 7 次作业，每次满分 120 分，总评计算是 作业 : 期末 = 3 : 8（作业超过 100 按 100 计算），期末总分 180，满分按照 \(\mathrm{min}\{卷面最高, 150\}\) 计算，最后继续上调给满优秀率，所以给分相当不错。

2024 秋作业+答案：

• 2024 秋离散数学作业；
• 2024 秋离散数学作业答案。

作业答案（可能从这些地方找到）：

• 代数结构和图论的评课社区；
• 组合数学引论 和 组合数学引论部分习题答案；
• 计科三部曲教材 例题；
• 知乎；
• Ramsey 数下界；
• StackExchange；
• ……

老师的手写讲义（文件太大只能分开上传了）：1~5；6~8；9~10。

助教的随堂笔记（文件太大只能分开上传了）：1~10；11~18；19~22。

期末试卷（为了方便使用，我敲成了 PDF，顺便敲了一下别的评课里提供的试卷）： 

• 2024 秋离散数学期末试卷；
• 2023 秋离散数学期中试卷 [来源]；
• 2023 秋离散数学期末试卷 [来源]（缺失的题目用一道类似的作业题补上了）；

本课程和邵老师的研究生课 组合数学 风格较为类似，所以

• 2022 秋组合数学期中试卷
• 2024 春组合数学期末试卷 

等也可以作为参考。最后想小声问问邵老师，您说的计算理论和复杂度理论什么时候端给我们本科生作为选修课品尝。猜你想看：少十七（邵老师的知乎）。

2025.1.6

2024 秋  离散数学  期末考试  考试时间：3 小时  总分：180 分

1. (15 分) 对任意整数 \(n\), 求 \(\mathrm{gcd}(24n+4,\ 18n+6)\) 的值并证明. (对 \(n\) 从 \(1\) 到 \(6\) 分别求解可得 5 分)

2. (20 分) 考虑同余方程组  \(x\equiv b_1\ \mathrm{mod}\ m_1\)   \(x\equiv b_2\ \mathrm{mod}\ m_2\)   \(x\equiv b_3\ \mathrm{mod}\ m_3\)  其中, 对任意 \(i \in \{1,\ 2,\ 3\}\), \(b_i\), \(m_i\in N^*\). 给出该同余方程组有解的充分必要条件并证明. (注意 \(m_1\), \(m_2\), \(m_3\) 两两互素只是有解的充分条件)

3. (20 分) (a) 若群 \(G\) 的阶 \(|G|\) 为素数, 证明 \(G\) 是循环群;
(b) 若群 \(G\) 的阶 \(|G|\) 为 \(pq\), 其中 \(p\) 和 \(q\) 均为素数且 \(p < q\), 证明 \(G\) 至多包含一个 \(q\) 阶子群.

4. (20 分) 设 \(S\) 为 \([m]=\{1,\ 2,\ ...\ ,m\}\) 上的一个置换群, \(F=\{f:[m]\rightarrow \{0,\ 1\}\}\) 为所有 \([m]\) 到 \(\{0,\ 1\}\) 的函数. 对于函数 \(f\), \(g\in F\), 如果存在 \(\sigma \in S\), 使得 \(g=f\circ \sigma\), 则称 \(f\) 与 \(g\) 在 \(S\) 下等价, 记为 \(f\simeq _S g\). 对于 \(f\in F\), 令 \(Z_f =\{\sigma\in S|f=f\circ \sigma\}\).
(a) (6 分) 假设 \(S\) 为 \([m]\) 上的对称群 (即 \(S\) 包含 \([m]\) 上的所有置换), \(f\) 将 \([m]\) 中 \(m_1\) 个元素映为 \(0\), 求此时的 \(|Z_f|\); (对特殊情况 \(m=10\), \(m_1=4\) 求解最多可得 3 分)
(b) (6 分) 令 \(F_o=\{f\in F|f\) 将 \([m]\) 中偶数个元素映为 \(0\}\), \(O_f=\{g\in F_o|g\simeq_Sf\}\). 对于 \(f\in F_o\), 证明 \(|O_f|\cdot |Z_f|=|S|\);
(c) (8 分) 令 \(F_1\) 为 \(F\) 任一非空子集, \(O_f^,=\{g\in F_1|g\simeq_S f\}\). 对于 \(f\in F_1\), \(|O_f^,|\cdot |Z_f|=|S|\) 是否成立? 请证明或给出反例.

5. (15 分) 从 \(3\), \(5\), … , \(299\), \(301\) 共 \(150\) 个奇数中任选 \(n\) 个数, 使得其中一定存在两个数互素, 问 \(n\) 最小可以是多少并证明. (找出最小的 \(n\) 并证明可获得满分, 若你能证明某个更大 \(n<150\) 使得题目要求成立, 可视情况获得部分分数)

6. (15 分) 已知: 对完全图 \(K_{14}\) 的所有边进行红蓝染色, 则一定存在一个红色 \(K_5\) 或者蓝色 \(K_3\).
证明: 对完全图 \(K_{19}\) 的所有边进行红蓝染色, 则一定存在一个红色 \(K_6\) 或者蓝色 \(K_3\).

7. (20 分) 考虑方程 \(x_1+x_2+\ ...\ +x_n=m\), 其中 \(m\), \(n\) 均为偶数且 \(m>n\).
(a) (6 分) 求该方程非负整数解的个数;
(b) (6 分) 求该方程满足 \(x_1=x_2\), \(x_3=x_4\), \(...\) , \(x_{n-1}=x_n\) 的非负整数解的个数;
(c) (8 分) 求该方程满足 \(x_1\), \(x_3\), \(...\) , \(x_{n-1}\) 为非负奇数, \(x_2\), \(x_4\), \(...\) , \(x_n\) 为非负偶数的解的个数.
(b, c 小问对特殊情况 \(n=6\), \(m=16\) 求解每问最多可得一半分)

8. (20 分) \(f\) 和 \(g\) 为定义在非负整数上的函数, 已知对任意 \(n\geq0\) 有 \(\displaystyle{f(n)=\sum_{i=0}^n\tbinom{n}{i}g(i) }\), 证明对任意 \(n\geq0\), \(g(n)\) 可唯一表示为 \(\displaystyle{g(n)=\sum_{i=0}^n(-1)^{n-i}\tbinom{n}{i}f(i) }\).

9. (20 分) 考虑连通有向图 \(D=(V,\ E)\).
(a) 证明若对于任意 \(x\in V\), 都有 \(|\mathrm{deg}_D^+(x)-\mathrm{deg}_D^-(x)|\leq1\), 且任何边 \(a\in E\) 均包含在奇数个有向 \(\mathrm{cycle}\) 中, 则 \(D\) 是 \(\mathrm{Euler}\) 图;
(b) 说明上述命题的逆命题不成立.

10. (15 分) 设图 \(G=(V,\ E)\) 是简单平面图且 \(|V|>2\), 证明 \(|E|\leq3|V|-6\).

2024.12.15

我们需要教材
We need textbooks
教材が必要です
우리는 교재가 필요하다
Nous avons besoin de matériel pédagogique
نحن بحاجة إلى التدريس
Wir brauchen material
Нам нужны учебные материалы
Kita memerlukan bahan pengajaran
Precisamos de materiais didáticos
เราต้องการหนังสือ
Öğretim materyallerine ihtiyacımız var
Necesitamos material didáctico
אנחנו צריכים חומרי לימוד
Χρειαζόμαστε διδακτικό υλικό
Abbiamo bisogno di materiale didattico
हमें पाठ्य-पुस्तकों की ज़रुरत है।
Kita butuh bahan ajar
Avem nevoie de materiale didactice
Имаме нужда от учебни материали
ما به مواد آموزشی نیاز داریم
Potrebni su nam nastavni materijali
Vi behöver läromedel
Tarvitsemme opetusmateriaalia

这门课没有像样的教材也没有ppt和老师的讲稿，自学起来似乎有一点点困难…

内容方面：主要讲了数论与群论的基础内容（大概与代数学基础相当，但是代基讲的更多一些），组合计数（个人觉得课程很精彩的一部分是组合计数和前面的群论联动的部分），以及图论（美中不足的是这学期老师事情比较多，这部分的内容讲的就比较少了）。

老师的板书有点杂乱，开个小差回来就不知道讲到哪了（悲。不过老师讲课思路非常有意思，当你全部听懂的时候会感觉讲的很好，但是如果没听懂就是另一个故事了。本学期的助教建了一个网站，可以在网站上查看助教的笔记自学，还是非常不错的

作业有点小困难，不过由于作业总分溢出所以混混平时分还是很轻松的。

希望老师下次能做个ppt或者给出latex讲义/ll

容错率很高的考试！按3：8比例计算总评的情况下4.3率可能能达到接近20%（而且似乎还要继续调），神！

本身计算总评只有2.0一打开成绩单3.0不多说了邵老师再生父母

从今以后我不允许任何人忤逆邵老师

感谢的话说完了，现在来认真的评价一下这门课吧。

• 感觉比较难受的是没有一本系统性的教材或者讲义，导致每次上课都有一种开盲盒的感觉。虽然课程主页有大纲但还是上的比较茫然和吃力。
• 老师讲课的水平毋庸置疑，非常善于启发学生的思考，逻辑清晰，有深度有广度，讲的内容都非常有水平，一节课的高度集中注意力结束后会有很通畅通透舒适的感觉，总之就课堂体验来说绝对是可以称之为艺术品的课堂。
• 奈何本人对于抽象数学的天赋实在有限，150分的卷子只写了70分。以及作为aids的班，班上真的很卷，出来一些少院大佬，希望后来的学弟学妹们不要相信一些佬们所说的期末考试内容不算难，认真听课写作业就能得高分诸如此类的话！
• 作业是有难度的，至少我没有几道题是能够靠自己的思考完全写出来的，期末考更是破防加破防，在临近考试时复习真的非常崩溃。没有办法把握住系统性的重点，也没有熟悉到能够举一反三解决同类问题。总会给人一种见一题不会一题的感觉🤣，所以那些觉得不难或者认真学就能学好的别轻易相信。至少我知道我是付出了150%的努力了（或许确实没什么天分）但这门课就是很有难度不是能让人通过认真学习认真上课就能得到优秀的（没有打击后来者的意思，纯纯个人看法）老师非常有胸怀和视野，在课程结束后甚至给每位同学都发了邮件写下了老师对于这门课的想法和对于学生的祝福，非常的温暖，在科大为数不多的感受到老师对于学生的人文关怀。
• 同时我的想法是不需要因为自己缺乏这一方面的天分就觉得压力山大，因为每个人的天赋点不同，东边不亮西边亮。（这是本人这学期结束后的深刻体验）
• 来了大数据后就不要有什么心怀侥幸了，身边的同学大概是除了少院最卷的一批了，所以或许有时候真的得学会和自己比，因为和别人比永远有比不过的时候。在科大无论再难的题都有人觉得简单。离散数学这门课能认识邵老师让我觉得很幸运，只是过于离散数学和我并不投缘，但希望后来者可以窥探到学习之美，正如邵老师所说！

课程定位似乎有些问题，计科有离散三部曲，而aids居然用一门课就涵盖了这三门课。

老师水平确实很高，没有照着课本的思路，而是先从抽屉原理引入，显然是对如何上好这门课有着自己的思考。但是只上了一节课，所以暂时不多评价。

除了上课内容本身之外，这门课的其他地方也让我眼前一亮。

1.老师不要求到课，说“只要同学们觉得自学比上课好，那就可以不来上课。”

2.有课程主页，给出了作业/参考书/教学安排等重要信息

3.给分标准改革。作业/考试会有120分，只需要得到100分就会拿满该项；平时：期中：期末=3：4：4，留出了一定的冗余。

“经常有同学说总评100分难拿，你上我的课，肯定很容易拿100”

第一节课老师上课迟到，扣1分。但由于总分11，留出了1分冗余，所以总评为10分。

（吐槽一下，那个教室真的热

这个离散越复习越发现啥也不会啊，我怎么去考试啊，

怎么办怎么办，电磁甚至一点没学，后面的考试都没学，能活吗

what can i say man

现在是深夜一点，距离离散考试还有七个小时

会活吗

邵老师，邵老师，我明年还会来的！

要期末了感觉啥也不会，最近还有较频繁的作业，好焦虑啊˃ʍ˂

演都不演了😭出题要有挑战性是吧，我不活了😭

邵老师开的离散数学课程与科大别的离散数学课程在内容上会有很大的不同，也因此没有一本教材可以囊括本课程所有的内容，需要大家上课认真听/多找一些资料参考。

由于邵老师同时教研究生课程《组合数学》，所以这门课和组合数学有相当一部分是重叠的。首先提醒大家，邵老师所讲的所有与组合、计数相关的内容均可以在《组合数学引论》中找到相关的例题和习题。

课程开篇讲述抽屉原理，然后用抽屉原理推出中国剩余定理解的存在性，进而过渡到数论模块。

数论模块介绍了裴蜀定理、同余、欧拉函数等内容，在讲到唯一分解定理的时候引入了环的概念，介绍了素元和不可约元，为后续讲代数结构做铺垫。数论的最后介绍了 RSA 加密算法（似乎邵老师在 23 春的算法基础课程里也讲了这个）。

代数结构部分的重心是群和环，域基本没怎么讲。群的部分的重点是陪集分解的一套理论以及群同构，还介绍了循环群、置换群的部分内容；环的部分的重点是素理想、极大理想、素元、不可约元之间的互相推导及依赖条件，这是课程的一个小高潮部分。

随后开始的内容是组合计数，这在大多离散数学的课程里是不会花大篇幅去介绍的。这一部分以给项链染色的问题引出了莫比乌斯反演和 Polya 定理两种思路，然后从组合计数最基础的定理、不定方程解的个数等问题出发讲了若干组合恒等式的内容。在不定方程解问题的最后引出了容斥原理（请重点关注错排问题和 ménage 问题），进而介绍了子集反演（邵老师直接称之为莫比乌斯反演）、数论的莫比乌斯反演等内容。这中间又完整介绍了群论里没细讲的群作用与轨道公式，用莫比乌斯反演和 Polya 定理两种方式解决了最初的项链染色问题。

最后一部分是图论。本学期由于时间关系，图论的内容讲的很少。开篇是欧拉回路问题，进而介绍了图的基本概念以及连通性相关问题。然后单独讲了一个 Ramsey 问题（这个是必考的内容，请后来者注意），这是抽屉原理与图论的结合。最后又讲了树的概念和平面图的概念，证明了平面图的欧拉定理。

如果时间充足的话，应该还会讲解图论中与矩阵相关的知识、割问题这些非常经典的内容。

而完整的离散数学还应当包括数理逻辑的内容，只是邵老师将其略去了。数理逻辑的内容非常深刻，比大家在中学时代所接触的命题等内容要深刻得多。计科以前用了 3 学分才能讲完完整的包括 Gödel 不完备定理在内的数理逻辑知识，所以这门课讲不了那么多也可以理解（真要讲的话可能大家连语法和语义的区别都还没弄清楚就结课了）。

本学期因为种种因素没有期中考试，期末考试的题目别的评课已经回忆了。今年的期末卷子难度不大，把基础分都拿到基本就稳稳 4.3 了，因为算分公式比较暴力（平时：期末=3：8，期末按 100 * 总分 / min(150,最高分) 算）甚至总评 100 分也不算难。

总的来说，这是一门很硬的课程，即使是在如此暴力的算分公式下，如果不调分优秀率也才 30%。希望后来者能在这门课上多花一些心思。这门课的助教都很厉害，提供了很丰富的学习资料，给了大家很大的帮助。希望后来者能喜欢这门课。

出分了，跟预料中一样的三位数总评，感恩😊

老师简直是大学以来听过思路逻辑包括讲课技巧什么的最顶的老师了！唯一一门能从头听到尾的课（虽然真的是对我太难太难太难了，应该是我太辣鸡了）虽然没学明白，作业考试都不太会，但老师讲的确实很好啊。

课程对没基础的我来说真的顶天难了😭😭😭

等待捞分，其他待出分再说

啥也不说了上图

显然，注意到，结论平凡

易得，答案略，留作习题

同理，不妨设，由上可知

证毕，QED，自证不难

ss老师谁不爱呢？

十分

wt can I say？

（注:这是我到科大之后第一次认真听课  没办法，老师讲的实在是太好了，让我恍惚间找回了曾经热爱数学的自己……）

老师真的太好了😭😭😭

180分卷子  还有3比8的算分方式  躺下等捞就好了😍

老师讲课很好，但是感觉现在期末无从下手，知识点太多了……

周围同学都认为很简单，而我觉得要爆炸了，希望助教改卷大放水

本人是听课党，学之前几乎零基础，除了听邵老师讲课外没看其他资料/网课，也没做作业以外的其他题目，出分后按照给分公式算出来总评甚至超过了100（？

建议没有修过相关课程或者没有数竞基础的同学认真听课（强烈建议不要翘课，因为本课程知识的连贯性挺强的，少一次课可能会导致后面的课听不懂），上课的时候尽量跟上老师思路（跟不上也没关系，我听课的时候也经常慢半拍，但一定要动脑子思考），老师提出来的一些问题可以积极回答（不过我回答了几次都是错的hhhh），边想边把老师上课写下的板书记下来（因为本课程没有教材，没有讲义（虽然助教会写一份以及课程最后老师会把之前的讲义发出来，但自己写下来能加深印象），记下来的笔记可以方便复习（做作业的时候不会可以翻一翻，作业很多题老师上课都有提及，有些提示啥的））。考试挺轻松的，至少比作业题简单，基本都是基础题，有几道题甚至考前的习题课刚讲过类似的。

考试实在不会做可以试试枚举，反证，数归……把能推出来的结论都写上去，会给不少分的。

总结：老师上课有意思，认真听课收获很大，给分很好，强烈推荐！

教课水平超神，学不会是我的问题。但是没有教材真的太伤了，加上期中因为老师有事没考，期末真的无从下手o(╥﹏╥)o 靠老师和助教发力了