选课类别:计划内与自由选修 | 教学类型:理论课 |
课程类别:本科计划内课程 | 开课单位:人工智能与数据科学学院 |
课程层次:专业基础 | 学分:4.0 |
本课程讲述离散数学的基本概念和理论,主要内容包括:(1) 集合、关系、函数等基本概念和理论;(2) 图论的基本概念和方法; (3) 代数系统的基本概念、几个重要的代数系统:半群、群、环、域、格与布尔代数;(4) 组合数学,其中包括组合存在性、组合计数、组合设计与编码以及组合最优化。(5) 数理逻辑,其中包括命题逻辑、一阶谓词逻辑、Her-brand定理和直觉逻辑。
最大的感受是学的东西多而不精。 拿群论来说,有好多东西作业题里涉及到了但是貌似没讲。比如说有限子群的积还有直积、商群的一些深层次内容。 课程难度很大,而且对于我们这些专业的学生不知道有没有用。(就算有用学了很长时间不用也会忘掉) 这门课是存在问题的,希望教务处或者老师能优化一下这门课。
看完网上的莫比乌斯反演,再看老师讲的,感觉老师讲的比较随意。其实需要挺多前置知识才能学懂、学好、学以致用。 算了不说了,吐槽有什么用呢?
现在我觉得这门课最大的问题是:缺少合适完备的教材,建议搞一本合理的、配套的教材,要不然还是别为难下一届的学弟学妹们了。
话说评课社区就是学生发癫的地方吧…
期中考试题:
1.对任意整数n,求gcd(21n+4,14n+3)的值并证明
2.若n为正整数,p为素数,证明p不整除n等价于Φ(np)=(p-1)Φ(n) Φ(n)为欧拉函数
3.设G为一个n阶群,证明:
(a)若对于任意d整除n,G中至多只有一个d阶子群,则G为循环群
(b)若G为循环群,则对于任意d整除n,G中恰有Φ(d)个元素的阶为d
4.证明:含幺交换有限环的素理想必为极大理想
5.从1-299的150个奇数中任选n个数,使得其中一定存在两个数满足其中一个整除另一个,求n的最小值并证明
6.考虑方程x1+x2+...+xn=m,其中m,n均为偶数并且m>n:
(a)求该方程非负整数解的个数
(b)满足x1=x2,x3=x4...xn-1=xn的非负整数解的个数
(c)满足x1,x3...xn-1为非负奇数,x2,x4...xn为非负偶数的解的个数
7.二项式系数的题,不好敲字,总之是Cni这种
8.蚂蚁爬,每次向上,向下,向右走1,经过m步走到点(k,k)
(a)证明m是偶数
(b)求一共有多少种走法
(c)上述走法中不跨越直线y=x的走法有多少种
仅供以后选此课程的同学参考
期末反正我应该是不会整理了,考完就结束了😋😋😋
btw,如果你是大一搜索离散数学看到了这个评论,那么说明你大概率在研究DS培养方案考虑转专业问题,鄙人在专业选择上有一段波折的经历,由此写了一些关于妮可新工科专业的信息分享,感兴趣可以在 https://github.com/yueyue0407/some-ideas-about-switching-majors-in-USTC 查看,希望能帮助到你QAQ
5.25 update 大二下都要结束了才来评论而且人已经不在DS了QAQ
回首在DS学习的一个学期,邵邵的课无疑是最令人愉快的课程之一。
先来说课程本身,Discrete Math 这课是完全的 discrete ,内容包括但不限于 集合逻辑、数论、组合计数、群论、图论… 任何一个部分都能单拎出来作为一个大课来上。然鹅DS天才地将所有的这些压缩到一门4学分的课程里面(隔壁CS好歹也是 代数结构加 图论 两门课好吧),导致这门课实际上造成了老师和同学的双重折磨,既考验老师的功底和讲课水平,又挑战学生的理解能力… 因此,这门课就像婺源的量子力学一样,不同的老师有迥异的风味。
邵邵也是意识到了这个问题,教学时略去了中学学过的集合逻辑部分,期中考试前讲授数论组合和部分群论内容,下半学期着重于图论并把群论补全。邵邵作为妮可首届华罗庚班班长加海归,功底非常深,上课跟着他的节奏学习会让你感觉如沐春风,然后回去自己做就一脸懵壁了😭。建议上课时一定要自己记笔记,邵邵虽然会发他的笔记,但是那个字迹实在是…而且还是上课的原版,有些随堂的灵感内容如果不结合课堂实况是很难找到逻辑的(因为他们往往会出现在笔记的犄角旮旯…)。作业的难度较大,需要长时间的思考和查询资料,而考试大多数题目则是例子和作业的变体,较为友好。给分很大方。助教也很负责,每次习题课都能把作业讲清楚,感觉他们在这个课上花的时间比我这个学生多得多 ε=ε=ε=┏(゜ロ゜;)┛
邵邵作为过来人,也会分享一些他的感悟和经历,他疫情下出国的故事实在是给了我很大的触动。
最后,感谢邵邵,也祝愿邵邵的家人早日康复!
想复习无从下手,红了😭😭
明天期中考试,先来占个坑
邵老师上课还是很nice的,比较循循善诱,对于一些定理会讲动机,让大家一起算。上课比较有参与感。离散数学的内容比较离散,所以邵老师说他力图用一些问题将内容串起来。比如计算欧拉函数,期中之前讲了数论的方法,期中之后又讲了组合的方法(容斥原理)。对于一些深刻的定理或思想,邵老师会避免陈述定理最一般的形式,而仅仅给出基本的例子。比如莫比乌斯反演,只讲了集合和数论的版本,又比如Polya计数原理,只讲了对n边形用m种颜色染色的例子,还用莫比乌斯反演给出了另一种解法。我认为这是好的,保证了课程深度的同时又不要求大家有很多数学基础,还在大家心中埋下了一颗科学的种子?邵老师的意思是离散数学是一门导论课,可以把大家导到近世代数,组合学和图论上去。总之这学期上课还是比较有收获的,但我建议邵老师把字练一下,把板书写好看一点,或者以后有时间可以整理一个latex讲义。
期末考完了。。。邵老师说期末会比期中简单,大概40%的同学会考85分以上。奈何本人水平太差,愧对老师教诲,只会做80分不到的题。下面是期末考试回忆版:
1.已知对K18染色或者存在红色K5,或者同时存在红色K4和蓝色K3.证明对K35染色一定存在红色K5或蓝色K4.
2.(a)图同构等价于关联矩阵置换相抵(b)关联矩阵置换相抵于分块对角等价于图不连通(c)证明关联矩阵的秩小于等于顶点数减去连通分支的个数
3.(a)简单连通图有一个圈等价于|V|=|E|.(b)若|V|-|E|=k,图中存在两个顶点之间有k+1条路径
4.证明连通简单平面图有一个顶点度数小于等于5.
5.(a)n对夫妻排成一行,求每对夫妻不相邻的排法(b)n对夫妻排成一行,求每对夫妻不相邻,且同性不相邻的排法。
6.对正方形用n中颜色染色。(a)用了至多三种颜色的染色数(b)排除旋转、对称下重复的染色方案求方案数(c)排除中心对称和绕对角线翻转下重复的方案,求方案数(d)在(c)的基础上求至多用了三种颜色的染色数。
7.S为n元集合,f,g是定义在S的子集上的整值函数。已知对于S的偶数元子集,有f(X)=\sum\limits_{Y\subseteqX, |Y| is even}g(Y), 对S的奇数元子集,有f(X)=\sum\limits_{Y\subseteqX, |Y| is even}-g(Y).问题:对于S的奇数元子集X,计算\sum\limits_{Y\subseteq X}f(Y).
几乎没有送分题,建议后来者把老师的讲义全部看懂,这样考试应该能做出大多数题。本人觉得menage问题太难应该不会考,结果就考了还有24分,o( ̄ヘ ̄o#)(主要是邵老师说期末会比较简单)。
PS:期末卷子里最有意思的一道题应该就是第二题的(c)问了。考场上有了思路没做出来,刚刚吃完饭想出来了。首先,前两问的铺垫告诉我们只要对连通图证明rank小于等于顶点数减1(此题的关联矩阵是对于有向图而言的,这里连通的意思是有向图生成的无向图是连通的)。如果图中包含cycle,将cycle上的边在关联矩阵中对应的列进行线性组合会得到0(规定一个定向,正向边加上该列,反向边减去该列),此时关联矩阵不满秩,rank小于等于行数减1等于顶点数减1.所以我们只要对连通的无圈图(也即树)证明结论即可。这是显然的,因为rank小于等于列数等于边数等于顶点数减1.
这题比较的代数,也比较图论。下学期数院开代数图论,感兴趣的同学也许可以选一下?
考完期末了来评价一下,本次4道图论3道组合,在考试之前知道自己不太会证明所以花了挺多的时间去复习组合的,但是怎么说呢,做是都做了,但考场上太慌感觉计算和menage问题的思路上有点问题,图论有两道小题没证出来,只能说希望改卷松一点吧
啥时候出分😬😬
离散要把我g爆了 给分未知 等一手吧 2.3出分 不多说了。感谢ss
2.3
终于出分了,给分大概还是参考3:4:4,算出来也和预期的差不多,这学期唯一的4.3,我认为还是很不错的
1.17
预估分应该不会这么快出了,先来评价一下,这门课平时,期中,期末占比是3 4 4,加起来是11,同时期中期末最高是120分,考到多少分按多少分算,所以你算总评最高可以达到126分
整门课程的内容大概分为
抽屉原理->数论->群论->组合->图论
组合大抵可以分为组合计数,容斥原理和Mobinus反演
图论内容可以参考徐俊明的《图论及其应用》第四版
再贴一个我自己写的期中之前的内容(有些内容不一定完全正确,可以当提纲参考)
不过我感觉这门课确实存在问题,很多的内容塞在这个四学分里面,导致正常上的话是上不完的,所以这学期的课程都比较具有跳跃性,再分一门课出去应该会比较好
再谈一下选课,ds人必修逃不掉,不过从计科转来ds的可以尝试修图论来替代掉这门课,别的院的建议就不要选了,这门课真心不轻松
先占个坑,不知道期中考试会有多难
11.26
诶,复习的有点破防,虽然是离散数学,但为免有点过于“离散”了
11.29
期中考完,客观评价一下,本张试卷容错率还是蛮大的,120的满分,再加上一半的计算具体值的分数,比我预想的要好很多,试卷上的题目大多也是平常作业或者上课讲的题的变式,除了第四道(?)和最后一道,其他的难度都不算大。
后天期末考试,今天来写点评价。
这门课难度很大。包含了很多内容但是受限于一门课的体量没有办法深入介绍,这一点其它评论也有提到。
授课方面相当出色。邵帅老师会把证明过程以非常有逻辑且合理的方式一环扣一环地呈现给同学,手把手教同学如何处理问题。在听完之后不会有任何形如“为什么要这么做”的问题,而是会觉得“这个问题从直觉上来说就应该这么做”。之后再去看参考书上的证明就会觉得与课上的证明有明显差距,只是把某件事情证明出来而并不告诉你其中的道理(这种感觉很像读一些国内教材与国外教材的差距)。
接近学期末的时候邵老师跟我们说到成绩的问题,他觉得成绩并没有那么重要(也是老生常谈了),并且说了一些个人经历作为佐证。这一点我非常认同。所以18周周末的加课,虽然处于考试周并且上课内容不在考试范围内,我还是去听了。
最后一节课(也就是那节加课)结束的时候,邵老师对在场的大约10位同学说“希望今天来了的同学都能拿4.3”。考虑到不太好看的期中成绩(上半学期由于诸多事务,课程没太跟上)和并不出色的作业成绩,这句话对我来说绝无可能。但是我确实认同老师所说的,学到一些数学思想,并且在今后的人生中能够产生一点影响,比成绩重要的多。所以就算最后只拿到2.0甚至更低的绩点也无所谓了。
1.11更新
上午考完了期末,可以说尽力了。组合部分考了Menage问题,有些难度,第一问大概率没算对,第二问只写了n=3的情况。图论部分的证明有些也没做出来。
2.4更新
出分了,确实很差(笑)
这门课在期中前主要学习数论 群论 抽屉 组合 容斥,知识点很离散。不过考试题基本是作业原题,稍微有点变化,难度并不大。作业也比较少,还是可以快乐的水完这门课的 马上要期末了 考完试来评价一下0
期末好难 下一届学弟学妹一定要学好组合学 出分了 4.3 也算在意料之中吧 总评应该是按344给的
邵帅老师超级可爱!而且现在两周一次作业平摊下来作业量也不大,主要是邵老师上课会讲非常多的思路,上课比较轻松,很有意思!
成绩上344给分,期中期末满分都是120,总评满分126,有不小的冗余空间,对于冲100的同学很有优势。
核院老狗并没有学过相关的数学知识,但是只看老师的讲义也做出了大部分的考试题,私以为考试难度其实并不是很大。
虽然这学期的体验不错,但是课程内容上的设计不是很赞成。邵老师似乎是想把离散数学按照导论的形式讲,通过浅或者娱乐的形式介绍其中的各种内容,但是这样对于大二或者大三的学生而言是很少有机会去深入学习其延申知识的。同时由于时间安排问题,相当重要的数理逻辑部分被一笔带过,这是非常可惜的一点。私以为可以像丁虎老师一样加入一些计算机数学的内容,同时舍弃部分过于数学的内容和一些深度,让课程更加贴近计算机和大数据,在开在大二的现在当作导论讲解并不是很合理的。