CS1601 离散数学（A类）

Edit me

课程信息

对于把“离散数学”这样一个重大话题打包在大一上学期的培养计划而言，这门课的内容相对宽泛而并不深入（不过曹钦翔老师补充了很多较为深入的内容），涵盖数理逻辑、集合论、图论三大部分。

教师

这门课由曹钦翔和付鸿飞两位老师讲授，AI班限定曹老师。（2020秋）

曹钦翔老师是一位各方面能力卓越，授课风格具有浓厚个人色彩的老师。即使是在离散数学这样一门相对不容易掺杂个人讲授风格的课程中，曹老师还是能够以各种方式展现他的特点，下文会详述。

分数构成

5%签到 15%课堂发言，可以用大作业替代（详见后文） 30%作业 50%期末

关于签到，曹老师只点了一次名，这一次就占了全部的5分。曹老师本人是一位在课堂气氛、授课质量、课堂进度等方面对自己要求都很高的老师，对同学们的要求也很严谨。所以这门课相对不推荐翘课，点名不到后果还是比较严重的。

关于课堂发言。一般情况下曹老师一次计一分，课后在QQ群里的非匿名有效发言也会被助教统计，曹老师会以月为单位把发言进度公布在canvas上。通常情况下，课堂发言这种评价体系会在一定程度上拖慢课堂进度，但是曹老师以强大的授课能力避免了这一负面影响。具体表现在，对于同学们当堂提出的问题，曹老师能够很快地给出答案，而且是定义非常严谨的答案。所以不必担心课程上没有足够的时间进行提问或交流。另外由于这门课的学习气氛很浓郁，曹老师在课间也会和大家详尽地讨论，这时候如果提出了intriguing的观点，老师也会直接加分。

对于不喜欢讨论环节的同学而言，曹老师提供了两个项目。只要完成其中任何一个并在学期末展示，就可以拿到这部分的15分，后文会详述项目的内容。2020秋季学期约有10位同学以这种方式拿到这部分分数。

另外，经调查，即使一次没有参与讨论，曹老师也会给到一部分分数。所以不必过于担心。

作业分为预习和课后两部分，预习部分是简单的单选或多选，（未经调查）应该没有参与到分数构成。课后作业一共20次，平均每次5道题目，几乎所有题目都是证明，需要结合课堂内容在lecture notes里寻找思路和灵感，大致每次会有一到两道需要下功夫的题目。此外曹老师偶尔会留一些附加题，如果做出来也可以加分。附加题的难度和普通作业完全不在一个量级，本人只成功尝试了这些题目中很少的几道。其中有涉及到Finite Matroid, 连续函数和数集的等势问题这类需要很大思考量的题目。附加题不会加到30分以上，把其他作业题目正确完成也能拿到这部分30分。

期末考试一共8道题（2020秋），所有题目都是综合题。两个班会共用一张卷子，但是如果两个班有关某个问题的定义不同，会在卷子上标明，根据自己班级的授课情况作答即可。题目难度与作业的中等难度题目大致相当，不会达到曹老师的附加题难度，实际上甚至也没有达到作业中较难题目的难度。

课程体验

课堂氛围

得益于曹钦翔老师的强大能力和认真负责的态度，本门课程有着绝对能满足所有同学探求知识欲望的课程氛围。

先夹带一点关于曹钦翔老师本人的私货：曹老师在上海中学就读期间，就已经收获了NOI第一名和CMO满分的成绩，然而大牛的成长路径是非常富有个性化色彩的，曹老师接下来在北京大学哲学系获得本科学位，随后又在普林斯顿大学获得理论计算机方向的博士学位。这样一位对着自己人生有着独特定义的老师，其课堂自然有着独具特色的个人魅力。曹老师不但能够在课上高效解答同学们的疑问，而且每堂课后都会留下来和同学们探讨。探讨的时间甚至可以长达若干小时（直到最晚一班的校车发车），而且曹老师在QQ群也有问必答。

Projects

上文所述的两个项目分别是1.CDCL SAT Solver 2.Planar Graph Solver 曹老师限定使用C语言，项目开展中有任何问题都可以随时和老师探讨。两个项目都是课程话题的延展，老师会在课上和所有同学讲授算法。

CDCL全称Conflict Driven Clause Learning，是一种判断一组给定的命题逻辑是否有使其全为真的解（Satisfiable）的算法，是本门课程数理逻辑的范畴；Planar Graph则要求实现一个判定一个图能否平面化的算法，并将其实际平面化绘出。可能出于第二个项目公布较晚，亦或是难度相对较大的原因，该学期所有在最后一周成功展示的同学均实现的是CDCL项目。

我的感受

Sylvan:

虽然由于曹老师扩展了很多内容，导致这门课的容量被极度加大了，但是本人还是希望交通大学能够多一些像曹老师离散数学这样的优秀课程。一门好的课程可以很难，可以在考核上比较严格，只要教师认真负责，能够给所有想要探求知识的同学以自由的讨论空间、充足的学习资料、必要和及时的指导。毋庸多言，曹老师在这三个方面都能拿到100分。整个学期修读这门课程的体验称不上是轻松，但是绝对是很愉快的。

GihhArwtw:

大一上学期最喜欢的课程之一，真正让我感受到“啊，真正的大学的课原来长这样”的课程之一。某种意义上给我留下了“John Hopcroft Center的老师们的上课方式都很不错”的良好第一印象。（当然这一印象后续被各位JHC的优秀老师们反复验证。） 我大概属于“喜欢思考、不喜欢刷题”的类型，因此这门课的授课方式是我最喜欢的类型之一。

笔记资源

GihhArwtw:

没错又是我来贡献笔记了，具体内容详见GihhArwtw/SJTU_AI。

说明	pdf
离散数学	下载

Misc.

关于曹老师唯一一次课程点名。当天（2020.12.25）有同学请曹老师给大家发红包，曹老师便顺势说，“老师给大家发分数，我们点一次名，所有来了的同学都可以拿到5分”。曹老师的行为是比较难预测的（想翘课的同学要小心了——）

数理逻辑部分有一次作业很多同学proof的形式都不正确，于是曹老师说，“如果一项作业有超过半数同学的方法不对，那么是老师的问题”。于是又给大家讲解了一遍，让大家再做一次。