课程概述
离散数学是对可数或不同且可分离的数学结构的研究。离散结构的例子有组合、图形和逻辑语句。离散结构可以是有限的或无限的。
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)
课程内容
抽屉原理/鸽巢原理作为整个课程的引入
在处理问题时,尝试从优化的角度和反问题的角度来构造抽屉
介绍抽屉原理的其他形式
请多留意其思想在整个课程中的作用
数论部分内容涵盖整除与唯一分解(裴蜀公式、算术基本定理等)、同余与欧拉定理、中国剩余定理等数论知识
介绍RSA加密算法
介绍群、环、域等代数结构的基本概念
在群论的课程中,会讲解到交换群、循环群、群同构、置换群、群作用与轨道公式
之后从群出发介绍“环”与“域”,以及环的理想等知识
学期中将讲解组合计数的部分内容,包括基础的排列组合(排列包括线排列、圆排列和项链数等),组合恒等式等内容
随之而来的则是容斥原理与Mobius反演(集合上的、数论中的),请注意容斥原理各种不同场景的应用(如错排问题)以及容斥原理与Mobius反演的等价关系
此部分的最后,再一窥群作用,并基于此引出Polya计数原理
图论开局七桥问题、基础的边与顶点染色问题
然后讲解图相关的基本概念,着手研究图的连通性(无向图的连通,有向图的弱连通、单向连通和强连通等)并介绍Eulerian Circuit(针对边)和Hamilton Cycle(针对点)
介绍二部图、图同构及图的矩阵表示:邻接矩阵(同数据结构)、关联矩阵,还会介绍图的Laplace矩阵
图讲得差不多开始讲树(Tree)和图的生成树(Spanning Tree),其中还会涉及最小生成树及相关算法
收尾时涉及图的割(Cut)
讲解逻辑命题、推理规则等数理逻辑基础内容
(后补)
课程进展
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 | 图论 |