离散数学学习指北
离散数学学习指北
[TOC]
应老师之约，特写此文，顺便纪念下三个学期的离散数学满绩。
没有笔记，只是经验。
水平有限，仅供参考。
什么是离散数学
抄一段维基百科:smile:
离散数学（英语：discrete mathematics）是数学的几个分支的总称，研究基于离散空间而不是连续的数学结构。与连续变化的实数不同，离散数学的研究对象——例如整数、图和数学逻辑中的命题——不是连续变化的，而是拥有不等、分立的值。因此离散数学不包含微积分和分析等“连续数学”的内容。离散对象经常可以用整数来枚举。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括实数集）的数学分支。但是，“离散数学”不存在准确且普遍认可的定义。实际上，离散数学经常被定义为不包含连续变化量及相关概念的数学，甚少被定义为包含什么内容的数学。由于运算对象是离散的，所以计算机科学的数学基础基本上也是离散的。我们可以说计算机科学的数学语言就是离散数学。人们会使用离散数学里面的槪念和表示方法，来研究和描述计算机科学下所有分支的对象和问题，如计算机运算、编程语言、密码学、自动定理证明和软件开发等。相反地，计算机的应用使离散数学的概念得以应用于日常生活当中（如运筹学）。
换句不恰当的话说，因为计算机只能处理「离散」对象，所以出现了「离散数学」。是作为计算机专业的学生，必须学好的一门课。
至于离散数学在计算机外的应用，可以参考一下 有哪些离散数学/图论应用在数学/CS以外学科的例子？。
集合论与数理逻辑
强烈建议上课认真听讲。
从这里开始，就需要锻炼抽象思维了。它把现实世界的各种实体、关系，转化为了公式、逻辑，与小学时期的应用题有异曲同工之妙啊:sunglasses:。自然语言的好处是提供直觉上的理解，坏处是不精确。形式语言的好处是精确，坏处是无法提供直觉上的理解。二者相辅相成吧。
这里给出我个人、不准确的一些理解：
- 给出一个对象的集合，一般满足有限、可数的性质；
- 给出这个集合元素之间的关系，对这些关系的表述既可以使用集合意义上的「有序元组」(ordered tuple) 也可以使用逻辑意义上的「谓词」(predicate)；
- 给出在这个集合上的运算以及参加运算的元素的个数，即函数；
- 给出描述上述公理、定义、定理的语言，这就是一阶语言。
对于这些的理解，可能会影响后面面向对象编程语言里的对类的理解。
对于函数的理解，可能会影响后面函数式编程的理解。
对于关系的理解，可能会影响后面数据库的理解。
但是，集合论与数理逻辑这一块切忌钻牛角尖，如果有些术语、例子实在是太过拗口，不妨先跳过，等学得差不多了，再回过头看看，相信还是能顺利理解的。如果还不行，再去问问同学、老师吧，这里最好不要一个人死憋着不问（如果最后是例子错了你会嘿嘿嘿的）。
最后推荐一本黑皮书，《离散数学及其应用》，Rosen 著，图书馆就有。个人建议看中文版，因为这样可以自己找翻译错误，并以此验证自己的知识水平:joy:。同时，可以借这本书体验一下中英文、国内外对计算机教学方式的差异，为接下来的几年学习做好准备。
除此之外，左孝凌和屈婉玲老师写的教材对我帮助也很大。不过，左孝凌老师写的那本书，我在图书馆找了好久好久才找到。
学完这部分后，可以像卓里奇一样高贵冷艳地调戏出卷人了。证明中不出现文字，而应该仅有以逻辑语句完成。后果自负哟。举一个数学归纳法的例子：
$$ (E \subset \{N}) \wedge(1 \in E) \wedge(\forall x \in E(x \in E \Rightarrow(x+1) \in E)) \Rightarrow E=\{N} $$
图论与组合数学
强烈建议上课认真听讲。
我平时会打打三人团体竞技游戏 XCPC，所以对这方面比较熟悉。
先说组合数学。
相信能考上大学的，高中一定学过数学吧:yum:。在这里没加什么特别难的东西，譬如卡特兰数、斯特林数、康托展开、卢卡斯定理、二项式反演等等都没有涉及。
好好听课，多多练习，不要吃老本。
再说图论。与数据结构相辅相成。
这里可能是一些同学的瓶颈了。
首先要学会更进一步的抽象，把具体事物用图来描述。换句话说，如何进行数学建模？多看书，可以去知乎上搜搜，多悟。理解通彻后，再之后就好多了吧，都是在图上的一些定义、应用，没什么特别 trick 的地方。只要看一遍书和例题，相信就懂得差不多了。
在这个学期的学习里，为了寻找单源最短路径，有了迪杰斯特拉算法；为了找到最小生成树，有了Kruskal、Prim 算法；为了有向无环图上不相交路径的计数，有了 LGV 引理（而这需要线性代数的知识）。。。
在之后的学习里，可能会疑惑垃圾回收是怎么一回事，循环优化为什么这么牛逼，正则表达式引擎该怎么写，寄存器分配，这些都与图论有关。譬如我在考试月写的一款编程语言wen，理论设计部分就用到了大量图论知识，快来 star。
代数结构与初等数论
这是我在离散数学里考得最差的一门，但同时是印象里考试最简单的一门（可能请假次数过多了吧）。
我平时会打打三人团体竞技游戏 XCPC，所以对这方面挺熟悉的。
先说初等数论。
相信能考上大学的，高中一定学过数学吧:yum:。在这里没加什么特别难的东西，譬如扩展中国孙子剩余定理、二次剩余、拉格朗日定理等等都没有涉及。
剩下的内容也很少，编程语言学了俩学期了，模运算应该也滚瓜烂熟了，其它应该没什么难度了吧。
再说代数结构。
老师考察得比较简单，像原根、Burnside 引理、Pólya 定理等一些近世代数的东西没有涉及。
不过可能也是一些同学的最后瓶颈了。这里应该是要求最高的抽象了。
群环域相当于理论归纳，用它们对一些离散的数学结构进行分析。多看书，多理解，多悟。悟不出来去知乎上大佬们的一些回答，这里我没找到合适的课外读物推荐。
举几个好玩的例子，
- 1×0＝0 是因为 0 乘以任何数字都等于 0，还是因为 1 乘任何数字都等于那个数？
- 能不能定义一个数 x，与 0 的乘积等于 1？
- 如何保证数据存储安全、数据处理安全？
请读者自证，证不出来可以上网搜题解。
考试
过一遍书本，过一遍 PPT，相信老师是不会为难大家的（要是为难就好了）。
多刷题，多刷题，多刷题。
多检查，多检查，多检查。
千万不要让考试结果、复习过程影响你对计算机的热爱之情！