Introduction

什么是离散数学？

离散数学是数学的一个分支，主要研究离散对象 (discrete objects)，离散(discrete) 这个词，是相对与连续(continuous)而言的。所以，微积分(Calculus)这样处理连续对象的 数学就不属于离散数学的范畴了。

下面举一些离散数学研究的对象的例子（包括但不局限于这些）：

• 整数(integers), 整数是最基本的离散对象之一；
• 计算机程序执行的步骤，每一步都可以作为一个离散对象；
• 从地图上的 A 点移动到地图上的 B 点的路径，每一条路径都是离散数学中的一个离散 对象；
• 彩票中的数字组合，排列组合是离散数学研究的内容之一

离散数学可以解决的问题，例如

• 当我们忘记密码时，按照一定的规则，有多少种可能的密码？
• 有多少合法的网络地址？
• 买了一注彩票，中奖的概率是多少？
• 在一个网络中，两台电脑之间是否有连接？
• 怎样来识别电子邮箱中的垃圾邮件？
• 怎样加密信息以防止没有授权的人都无法读取这些信息？
• 我们怎样来设计一个电路做两个整数的加法运算？
• 在一个交通系统中（比如我们的航空系统，体露系统），求取两个城市之间的最短路径？ 这个最短路径可以使用“花费”来衡量。
• 从一个城市出发，游览一遍计划中的城市，每个城市只经过一次，最后返回出发的城市， 路线应该怎么安排？
• 如何来对中文语句进行“描述” (represent)，使得计算机可以理解这些语句？
• 怎样证明有无穷多个质数 (prime numbers)？
• 怎样对一串序列进行排序，使得排完序后的序列按照从小到大或者从大到小的顺序排列？
• 等等……

离散数学涉及的问题非常多，很多都非常有趣，和我们的生活息息相关。学好离散数学，说 不定我们可以在生活中成为更智慧的人。

课程目标

学习数学课程，不仅仅是知识的积淀，更重要的是，在学习这些课程中，我们能够学习、训 练新的思维方法。学习离散数学课程对大家的数学逻辑思维的训练是非常有帮助的。

通过学习这门课程中，希望同学们能够初步掌握下面五个方面的主体：

1. 数学推理 (Mathematical Reasoning)：数学推理是离散数学的基础。我们首先要学习数 理逻辑 (mathematical logic)，掌握构造证明 (constructing proofs) 的方法和技巧。 数学归纳法是离散数学中一种重要的方法。

2. 组合分析 (Combinatorial Analysis)：离散数学中，计数 (counting) 或 枚举 (enumeration) 是重要的解题技巧。我们需要用组合分析方法来求解计数问题，并且分 析算法。

3. 离散结构 (Discrete Structures)：离散结构是表示离散对象及这些对象间关系的抽象 数学机构，包括集合 (sets)、置换 (permutations)、关系 (relationships)、图 (graphs)、树 (trees)和有限状态机 (finite-state machines)等。

4. 算法思维 (Algorithmic Thinking)：最终，我们希望通过程序来实现算法，最后解决问 题。这个过程中涉及的数学问题包括：算法的详细说明、正确性验证以及执行算法所需 要的计算机内存和运行时间的分析等。这里，我们需要掌握为代码来描述算法。

5. 应用与建模 (Applications and Modeling)：事实上，离散数学可以应用在现有的所有 研究领域，并不仅仅局限于信息科学和计算机科学，所以，使用离散数学方法对不同问 题进行数学建模，也是本课程需要训练的能力。