课程概述

离散数学是对可数或不同且可分离的数学结构的研究。离散结构的例子有组合、图形和逻辑语句。离散结构可以是有限的或无限的。

Discrete mathematics is the study of mathematical structures that are countable or otherwise distinct and separable. Examples of structures that are discrete are combinations, graphs, and logical statements. Discrete structures can be finite or infinite.
(--Brilliant)

课程内容

引入:抽屉原理

抽屉原理/鸽巢原理作为整个课程的引入

在处理问题时,尝试从优化的角度和反问题的角度来构造抽屉

介绍抽屉原理的其他形式

请多留意其思想在整个课程中的作用

第一部分:数论 / Introduction to Number Theory

数论部分内容涵盖整除与唯一分解(裴蜀公式、算术基本定理等)、同余与欧拉定理、中国剩余定理等数论知识

介绍RSA加密算法

第二部分:代数结构 / Algebraic Structures

介绍群、环、域等代数结构的基本概念

在群论的课程中,会讲解到交换群、循环群、群同构、置换群、群作用与轨道公式

之后从群出发介绍“环”与“域”,以及环的理想等知识

第三部分:组合数学 / Combinatorics

学期中将讲解组合计数的部分内容,包括基础的排列组合(排列包括线排列、圆排列和项链数等),组合恒等式等内容

随之而来的则是容斥原理与Mobius反演(集合上的、数论中的),请注意容斥原理各种不同场景的应用(如错排问题)以及容斥原理与Mobius反演的等价关系

此部分的最后,再一窥群作用,并基于此引出Polya计数原理

第四部分:图论 / Graph Theory

图论开局七桥问题、基础的边与顶点染色问题

然后讲解图相关的基本概念,着手研究图的连通性(无向图的连通,有向图的弱连通、单向连通和强连通等)并介绍Eulerian Circuit(针对边)和Hamilton Cycle(针对点)

介绍二部图、图同构及图的矩阵表示:邻接矩阵(同数据结构)、关联矩阵,还会介绍图的Laplace矩阵

图讲得差不多开始讲树(Tree)和图的生成树(Spanning Tree),其中还会涉及最小生成树及相关算法

收尾时涉及图的割(Cut)

数理逻辑基础 / Basic Mathematical Logic

讲解逻辑命题、推理规则等数理逻辑基础内容

(后补)

课程进展

Topic Date Lecture Topic Lecture Notes Supplement
抽屉原理 Sep 2 课程介绍&抽屉原理 查看笔记 课上习题讲解(助教版)
Sep 7 构造抽屉的两个角度 查看笔记 课上部分习题讲解(助教版)
Sep 13 抽屉原理的其他形式 查看笔记 课上习题讲解(助教版)
数论 Sep 14 中国剩余定理与裴蜀定理(逆序食用口感更佳) 查看笔记
Sep 20 从整除和裴蜀公式出发 查看笔记
Sep 23 素数与算术基本定理 查看笔记
Sep 23 初识环-不可约元和素元 查看笔记
Sep 27 同余&再窥中国剩余定理 查看笔记
Sep 30 & Oct11 欧拉定理&欧拉函数计算 查看笔记
Oct 11 RSA加密 查看笔记
代数结构 Oct 14 群的定义与性质 查看笔记
Oct 18 有限群的定义与陪集分解(有限和无限群) 查看笔记
Oct 21 & Oct 28 循环群与群同构 查看笔记
Oct 28 置换群(手动添加轨道公式) 查看笔记
Nov 8 环和整环-域 查看笔记
Nov 22&23&25 理想-主理想-素理想-极大理想 查看笔记
NAN 子环-理想-商环 查看笔记
组合计数 Nov 29 各种排列 查看笔记
~~ 组合恒等式 查看笔记
~~ 容斥原理 查看笔记
~~ Mobius反演 [查看笔记][查看笔记]
图论 ~~~ 图论部分笔记参考 查看笔记

作业(已移除)

# Assignment Topic Download Link Deadline Sample Answer
1 抽屉原理
2 初等数论
3 代数结构(群论)
4 代数结构(环论)
5 组合计数
6 组合计数
7 图论
参考资料
重要通知
上课时间、地点

3A311:1(1, 2), 5(8, 9)

1~18周

课程回放

回放链接:111

课程主讲

邵帅

个人主页:http://staff.ustc.edu.cn/~wwwucuc/

邮箱:shao10@ustc.edu.cn

办公室:西区科技楼西楼613

助教

申长硕: shenc217@163.com

王元叙: konjacwyx@mail.ustc.edu.cn

考试信息

期中重点考察数论和抽象代数部分内容

期末重点考察组合及图论相关内容

...