离散数学2021秋期末回忆版.pdf

回忆版期末卷子，以飨后人。

2023.6.3更新：这学期修算法基础，又讲什么最大流最小割，什么最大支配集，虽然忘完了，但查一下CSDN居然都能记起来，感觉一切都回来了！杀不死我的，将使我更强大。

老师之前在密歇根大学当过教授，上课很有美国范.

上课内容其实不难，个人觉得很有启发性，因为人少，也算是一个讨论型课堂.老师基本不会马上反对某个同学关于某理论提出的质疑，而是会先听他的思路。个人觉得很难得，虽然台下一片蒙圈。

助教和老师都很仙风逸骨，上课就带几张手稿，揣兜里的那种。

有问题一定下课问掉！线上问老师题 老师永远只会叫你线下去找他讨论|･ω･｀)

95谢谢

课程内容前面同学已经说的很清楚了，作为计科学过三门离散数学的人来选这门课主要是为了听一下丁老师在图论算法方面的讲解。

最大的惊喜就是TSP问题，以及近似解，以及各种图论算法的复杂度。

丁老师上课风格类似讨论班，有看法可以随时提出，而且进度适中。

最佩服的是老师的出卷水平，期中题目难度平均，我恰好做到最后10分钟，期末一道题需要思考(至少我这么认为)， 于是其他题目就偏简单，考场我有1个小时去思考这道题，最后想出来成就感爆棚

希望丁老师可以单独开个研究生算法！

附一学期笔记and作业(可能有错)and今年期末考题(在最后一页)

链接：https://rec.ustc.edu.cn/share/e81c7080-8bde-11eb-b2c3-51119829739d密码：cse0

扣一分在课程深度上

终于出分了，老师给10分，助教很棒追加2分，smjwc现在才出分扣2分，所以给10分。

上课&老师：老师用Notability手写上课内容，下课后再由助教上传至QQ群。讲得很清晰详细，节奏的话，一直认真听的话肯定可以跟得上，但是有的时候低头摸一分钟的鱼再抬头可能就是听天书了（本人之前没有任何代数结构、图论的基础）。总体来说节奏适中，适合绝大部分同学（唯一美中不足的可能是老师的PDF一学期下来一直是接着写，从不分节，导致学期末PDF大小直接过100M，并且强迫症患者表示不分类分级难以接受）。课程内容详见其余同学评论。老师人很好。我期末查完卷遇上老师，跟老师一起下楼，老师问了我的分数和掌握情况，然后还仔细的问了我上课的感受，对他上课有什么建议等等，还跟我讲“不用太在意最后的成绩，一定会让每个人都满意，主要还是你自己真正收获了多少，这也是我上课的目的”。还扯了一些别的，“出国的话不少大学是强professor，GPA就显得不那么重要了blabla”，大意就是认真学，其他的交给老天hhh。

考试&助教：期中考试难度较大，平均分较低。期末稍好一些，但好像平均分也没及格。一开始是有些懵的，因为除了物理考试之外（我物理大菜鸡）本人还没遇到过这种让人“痛苦”的考试。但助教后来在群里发了长文，让我印象深刻。“不是为了让你们卷，去做计科那几本书，死命刷题。重要的永远是理解，举一反三。” 仔细想来确实，盲目地为了卷去卷有什么意义吗（doge）。也私聊了另一位助教，“理解老师上课的内容，这里为什么要这么设计，启发点和巧妙点在哪里，在以后的科研工作中这也是很重要的，因为人们大多是在前人的工作上进行改进，重要的是发现inspiration和approach的创新点”。本人语言水平有限，助教们其实说的很多、很好，就只截取记忆的大意片段了。另：一开始助教对我们的期望可能比较高，言语之中让人感觉助教xgg很厉害我们很菜（甚至有点装x）的感觉，有点像ICS的某位助教。但其实后来发现助教xgg人非常好，不会在给分和作业批改上难为大家，也不会像ICS那位助教一样“这也不会吗... 上网查查学学就知道了吧... 这不难吧”等等。不可否认自学能力很重要，但是作为助教，详细地阐述知识 和 对大家能力的要求高 这两者其实并不矛盾吧。。。考虑过我们非大佬普通学生的感受吗。。。离散数学助教给我的感受就是心服口服的厉害，并且也能学到知识。而不是无意义的“炫技”和“装x”。

作业：量不是很小，认真写呗，一次作业4-8h很正常。还记得有一次作业我看只有三道题就拖到ddl才写，结果后来发现参考资料是隔壁计科的图论PPT，200多页，直接emo，就刷夜了。。。

给分：对我来说很棒了。本人考前把讲过的算法都又看了一遍（结合老师的PDF和《离散数学》这本书），有遇到不会的就请教数学专业的舍友（代数方向），图论方向不会的就跟一位大佬同学请教讨论。没有刷题。最后自认为对一些概念和算法的理解还是可以的，也学到了挺多东西的。得到的成绩也比较符合本人一学期的付出吧（虽说考的都只比中位数高一些...，但是私以为付出和收获也不能只用考试成绩衡量）。总体来说老师的调分力度巨大，奶王本王。

2021秋季学期的教学内容和往年基本一致，前半学期是集合、数论、群论的基本知识，后半学期主要是图论，最后简单介绍了数理逻辑的内容。处于本课程的定位和时间的原因，每个部分都涉之不深，但是个人感觉讲到的内容还是很有代表性的。上课形式主要是老师板书，我个人比较喜欢这种教学方式，尤其是对数学类课程，如果只是过个ppt的话估计我就懒得听了（。

其他的东西往年的评课已经比较详细了，稍有不同的是今年的考试，客观说说我的看法：
期中考试的内容是偏引导性的，考试时间是1.5h，整个班上的分绝对数都不太理想，其实吧，我觉得期中这卷子的部分题作为平时作业出会不会更好呢。群内部分同学（包括但不限于匿名暴躁老哥）觉得这门课既然是替代计科离散三部曲，题目的内容应该也会和代数结构等有较高的关联性，所以看到卷子大家还是有点措手不及的，虽然之前习题课助教有强调过关联性，但是个人觉得并不是很够，毕竟很多同学是第一次接触到代数学的内容，理解基础的东西还是要花上不少时间的，在平时作业做更多的引导也许大家会更从容一点。这里倒不是在抱怨助教出的卷子哪里哪里不好，只是一个客观感受和一点不成熟的看法，期中考完后群内都没人敢说话了，应该可以处理的更好。

期末卷子期中前期中后的部分4:6分成，一道数理逻辑，三道图论，一道数论，一道群论，可能是期中大家分数都太惨淡了，想送点分出去，大部分题都很基础，证明题具体内容要么是上课老师提了一嘴的证明的复现，要么是利用上课提到的证明思想来解决，第五题是一道利用某算法A给出解决两个上课讲过的算法的另解，我大概用了一半左右的考试时间对着第五题干瞪眼，尽管老师和助教在不断的提醒，但是思路始终没打开，我觉得课外再多看点其他的算法并做点其他的算法题可能会有帮助，我本来打算看看算法导论的，但在后半学期跑去复习高中组合数学的内容了，可能是期中ptsd了。另外，代码复现一次还是很有意思。

关于给分，评论区都认爹了给分能不好吗。给个具体的参考，期中没问（最后做第一题的战士就不为难自己了），期末85+，最后应该是硬奶到了4.3。

最后感谢助教和老师一学期的付出。

----------------

有同学问better implementation，可以参考BGL, 写了ICS大作业应该会用一些Boost了.

利益相关96，

本来这门课是大数据学院为了代替代数结构，图论，数理逻辑三门课而开的一门课，

时间短本来就决定了这门课讲不了太多东西，

丁虎老师和蔼可亲，仙风道骨，上课确实每次只带几张纸，但是讲课依然非常有条理，逻辑清晰。

助教也是如此，记得几次习题课讲了很多以前没听说过的东西，

包括卡特兰数（这个还稍微好一点，听说过），图论里面的邻接矩阵以外的一些像拉普拉斯矩阵等等，

记忆最清楚的是图论与线性代数（矩阵）的结合那一些知识，简直打开了我对线代的认知大门，回去之后从图书馆借了一本《图与矩阵》打算好好研究然而到现在也没看。。。。。。

作业只布置了四次，每次不到十道题，都很简单

期中期末也很简单，因为丁虎老师说自己认为考试应该是这个样子的，应该出的简单一点，

毕竟在数院待过一年，学过代数学基础且拿了90，高中时期学数学竞赛学过图论的基础知识，像欧拉回路，哈密顿链一类的，所以学起来比较轻松。

离散主要的知识在群论，图论，数理逻辑三部分

期中主要考察群论，期末所有知识都有涉及，22年考试的难度要比21年更适中

总评原则上按照0.3+0.35+0.35计算，但是助教会捞一下，学期会有一次点名，没有来的总评会扣一分

助教们都比较好，我尤其喜欢杨助教的抽象（

心碎破防人在此:-)

主要也是自己的原因，卷子简单的考试都犯大病错一道分值高的大题，导致相应学科全部翻车，这学期也必然成为我绩点最低的一个学期。（好不甘心啊）

离散数学内容对我来说比较难，考试也不平易近人，期中考得相对很好，期末不知道。宝啊，你是我这学期唯一的希望了，呜呜！

我期末还没考完，等离散成绩出了，如果还不错，我就分享一下我的学习体会和笔记总结，如果太差，我还是别误人子弟了。

神爱世人，信民愿龙虎济世，福泽众生，信民必诚心祷祈，铭记恩惠。

（ps：这门课的顾言午助教身上的味道好香，有时上课感觉心旷神怡的，大家有机会可以去试试X

出分后补充：

这门课是只要你认真对待、好好学了，助教和老师就一定不会让你失望！！！

除了老师的课堂内容，我也看了一些参考书，还是很有收获的。

数论和群论参考书：《整数与多项式》、《代数群论》  其实都是在电子资料群的找的

图论：图书馆借的《图论及其应用》卢开澄 卢华明

整体：科大出版的《离散数学》 是一本我开学在网上买的书，可以看看

占坑，卷面分出了，按35 35 30算的话是89，不知道虎哥能不能捞一手到90。

更新：助教在bb发了预计的总评，然而并没有被捞，还是89。不过我期末考的确实不好，这样也知足了。

出分后更新：被捞到了90，感激之情无以言表，虎哥请受我一拜🙇

期中考寄了，在卷子难度比去年友好很多的情况下，因为考试失误错了第一题，又复习不充分寄了第四题（悲）在这插个眼，效仿一下去年写离散往事的老哥。

要是总评能有3.3我也过年回来给天使助教和🐯爷拜早年。

更新一下，期中出分了，没有完全寄，感谢天使助教海底捞，期末再回来看看要不要写离散往事。（α 这是阿尔法， β 这是贝塔， γ 这是伽玛，δ 这是德尔， ε 这是我亲助教gg的嘴​巴）

这门课主要分为代数结构、图论、数理逻辑三部分。老师是研究算法的，讲到一些以名字命名的图算法的时候，会说见过这个人，总之很强就是了。上课全程板书，可能对不记笔记的同学不太友好。

代数结构：和计科的代数结构前几章一样，作业题也都是孙淑玲的代数结构的课后作业（我可从来没说电子资料群里有答案），这一部分我感觉比图论简单，考试也是上课的简单拓展（比如多个数的最大公约数之类的），和作业的难度相当，但是一定要注意严谨性，有一些证明还挺巧妙的。

图论：大部分内容都能在王树禾的图论里找到对应，主要就是最小生成树、赫夫曼树、匹配问题、强连通分量、最大流、TSP问题等等。老师上课讲得很细（老师常说xx很显然，关键是怎么严谨证明呢，然而我感觉一点也不显然），建议参考算法导论，有一些图更能辅助理解，也适合课后的进一步消化，并且一些拓展的知识点也都能在算法导论里找到相应的。这一部分考试出了几道不简单的题，（比如最大流解最大匹配，并考虑分数解，还有最小生成树的kruskal算法的拓展），并且我没找到合适的习题集，（王树禾图论和算法导论的课后题与最终的考试题风格不太一样），大概只能多复习笔记了。

数理逻辑：讲得很浅，考试也很简单。

作业很少，占比不低。

给分不错。

楼上两位4.3的大佬说的差不多了，我来补充几句。

这门课内容：

代数结构，包含集合论，数论，映射与二元关系（带过），群论（重点），讲的内容与计科的代数结构课差不多，主要是多讲了一个RSA

图论，包含图的基本概念，树，匹配，Hamilton图及旅行商问题（TSP），网络流，图论部分老师讲的特别慢，而且偏算法（这一点与计算机学院的图论课有区别），基本上是一节课只讲一个算法，老师特别强调证明算法的正确性，而且考试的图论题都与算法相关，因此严谨性很重要！严谨性很重要！严谨性很重要！

数理逻辑，由于图论部分进度较慢，老师只讲了开头的一点点内容，只讲了两周，或许算是一点点遗憾吧，不过我已准备个性化计科cxp老师的数理逻辑

上课氛围：这一点wyx大佬已经说了，我就不补充了

作业及考试：四次作业，大多数题目选自计科离散数学的三本教材，也有一些难题，考试题里有些题直接考课上讲过的定理的证明或将其稍作变化，期中期末考试改的都很严，所以再次强调，严谨性很重要！严谨性很重要！严谨性很重要！（代数结构4.0，图论3.7，离散数学3.3的流下了不学无术的泪水.jpg）

最后的最后，丁老师讲的非常好，人也很好！