离散数学学习笔记

这是一个比较草率的离散数学笔记，后面应该会不定期完善，然后会找个时间把数论笔记整理一下

1. 集合论

1.1 集合的基本概念

集合是由一些不同元素组成的集体。元素可以是数字、字母、符号等，且每个元素在集合中只有一次出现。集合的表示方法有：

• 列举法：通过列出所有元素来表示集合，例如 $A = \{1, 2, 3\}$。
• 描述法：通过满足某种条件来定义集合，例如 $B = \{x \mid x \text{ 是偶数}\}$。

1.2 集合的基本运算

集合运算常见的有：

• 并集：$A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}$
• 交集：$A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}$
• 差集：$A - B = \{x \mid x \in A \text{ 且 } x \notin B\}$
• 补集：$A^c = \{x \mid x \notin A\}$
• 对称差：$A \triangle B = (A - B) \cup (B - A)$

1.3 子集与超集

• 子集：如果集合 $A$ 的所有元素都属于集合 $B$，则称 $A$ 是 $B$ 的子集，记作 $A \subseteq B$。
• 超集：如果集合 $B$ 包含了集合 $A$，则称 $B$ 是 $A$ 的超集，记作 $B \supseteq A$。

1.4 集合的运算性质

• 交换律：$A \cup B = B \cup A$，$A \cap B = B \cap A$
• 结合律：$(A \cup B) \cup C = A \cup (B \cup C)$，$(A \cap B) \cap C = A \cap (B \cap C)$
• 分配律：$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$，$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

1.5 集合的势

集合的势（或称为集合的基数）是指集合中元素的个数。集合的势常常用 $|A|$ 来表示，表示集合 $A$ 中元素的个数。

1.5.1 有限集合的势

如果集合是有限的，即其中元素的数量是有限的，那么集合的势就是集合中元素的个数。
例如：

• 对于集合 $A = \{1, 2, 3\}$，则 $|A| = 3$。
• 对于集合 $B = \{a, b, c, d, e\}$，则 $|B| = 5$。

1.5.2 无限集合的势

无限集合的势是一个更为抽象的概念，通常用来表示元素的“数量级”。

• 可数无限集合：如果集合的元素可以与自然数集合一一对应，则该集合是可数的，势记作 $\aleph_0$（阿列夫零）。例如，自然数集合 $\mathbb{N} = \{1, 2, 3, 4, \dots\}$ 的势是 $\aleph_0$。
• 不可数无限集合：如果集合的元素不能与自然数集合一一对应，则该集合是不可数的。实数集合 $\mathbb{R}$ 就是一个不可数的集合。

1.5.3 集合的势与并集

如果两个集合 $A$ 和 $B$ 的并集是有限的，则：

• 如果 $A$ 和 $B$ 没有交集，则 $|A \cup B| = |A| + |B|$
• 如果 $A$ 和 $B$ 有交集，则 $|A \cup B| = |A| + |B| - |A \cap B|$

1.6 幂集

集合 $A$ 的幂集（power set）是所有 $A$ 的子集构成的集合，记作 $P(A)$。例如：

• 对于集合 $A = \{1, 2\}$, 它的幂集是 $P(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$。

幂集的元素个数为 $2^n$，其中 $n$ 是集合 $A$ 的元素个数。因此，如果集合 $A$ 有 $n$ 个元素，则 $|P(A)| = 2^n$。

---

2. 逻辑与命题

逻辑是数学和计算机科学中的一门基础学科，主要研究推理和判断的规律。命题逻辑是逻辑学的一个分支，它研究由命题构成的逻辑系统。命题逻辑的核心在于命题的真值和运算。

2.1 命题与逻辑运算

• 命题：一个可以判断真假的陈述，命题只有真或假的两种状态。例如：“今天是星期五”就是一个命题，因为我们可以判断它是对还是错。
• 逻辑运算：命题可以通过逻辑运算进行组合，常见的逻辑运算包括：
  • 否定（Negation）：$\neg P$，表示命题 $P$ 的否定。如果 $P$ 为真，则 $\neg P$ 为假；如果 $P$ 为假，则 $\neg P$ 为真。
  • 合取（与）（Conjunction）：$P \land Q$，表示命题 $P$ 和命题 $Q$ 都为真时，$P \land Q$ 为真，否则为假。
  • 析取（或）（Disjunction）：$P \lor Q$，表示命题 $P$ 或命题 $Q$ 为真时，$P \lor Q$ 为真。如果 $P$ 和 $Q$ 都为假，则 $P \lor Q$ 为假。
  • 条件（Implication）：$P \rightarrow Q$，表示如果命题 $P$ 为真，则命题 $Q$ 也为真。$P \rightarrow Q$ 仅在 $P$ 为真且 $Q$ 为假时为假，其他情况都为真。
  • 双条件（Biconditional）：$P \leftrightarrow Q$，表示命题 $P$ 和命题 $Q$ 的真假一致，即 $P$ 和 $Q$ 都为真或都为假时，$P \leftrightarrow Q$ 为真。

2.1.1 真值表

真值表是列出逻辑运算在不同输入下的结果的表格。通过真值表，可以验证命题公式的真假值。举例如下：

• 与的真值表：

$P$	$Q$	$P \land Q$
T	T	T
T	F	F
F	T	F
F	F	F

• 或的真值表：

$P$	$Q$	$P \lor Q$
T	T	T
T	F	T
F	T	T
F	F	F

• 条件的真值表：

$P$	$Q$	$P \rightarrow Q$
T	T	T
T	F	F
F	T	T
F	F	T

2.1.2 德摩根定律

德摩根定律为命题逻辑中的两个重要规则，描述了逻辑运算的分配关系：

• $\neg (P \land Q) \equiv \neg P \lor \neg Q$
• $\neg (P \lor Q) \equiv \neg P \land \neg Q$

2.2 命题的等价

命题等价是指两个命题在所有情况下有相同的真值。命题等价可以通过推导或真值表来证明。常见的等价公式有：

• 双重否定律：$\neg (\neg P) \equiv P$
• 条件与析取的等价：$P \rightarrow Q \equiv \neg P \lor Q$
• 对称律：$P \leftrightarrow Q \equiv Q \leftrightarrow P$
• 交换律、结合律、分配律：命题逻辑中的运算遵循类似代数中的运算规律：
  • 交换律：$P \land Q \equiv Q \land P$，$P \lor Q \equiv Q \lor P$
  • 结合律：$(P \land Q) \land R \equiv P \land (Q \land R)$，$(P \lor Q) \lor R \equiv P \lor (Q \lor R)$
  • 分配律：$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$，$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

2.3 量化逻辑

量化逻辑涉及量词的使用，它扩展了命题逻辑，可以处理关于对象集合的陈述。

• 存在量词（Existential Quantifier）：$\exists x \, P(x)$ 表示存在一个 $x$，使得命题 $P(x)$ 为真。
• 全称量词（Universal Quantifier）：$\forall x \, P(x)$ 表示对于所有的 $x$，命题 $P(x)$ 为真。

2.3.1 量化逻辑的规则

• 量化的交换：$\forall x \, \neg P(x) \equiv \neg \exists x \, P(x)$
• 存在量词与全称量词的结合：$\exists x \, (\forall y \, P(x, y)) \equiv \forall y \, (\exists x \, P(x, y))$
• 量化与命题逻辑的结合：量化逻辑中的命题与命题逻辑的命题运算一样，也有合取、析取、条件等运算。

2.4 推理与证明

推理是从已知的前提出发，得出结论的过程。常见的推理规则包括：

• 合取引入（Conjunction Introduction）：如果已知 $P$ 和 $Q$，则可以推导出 $P \land Q$。
• 合取消解（Conjunction Elimination）：如果已知 $P \land Q$，则可以推导出 $P$ 或 $Q$。
• 析取引入（Disjunction Introduction）：如果已知 $P$，则可以推导出 $P \lor Q$。
• 析取消解（Disjunction Elimination）：如果已知 $P \lor Q$ 并且已知 $P \rightarrow R$ 和 $Q \rightarrow R$，则可以推导出 $R$。
• 假言推理（Modus Ponens）：如果已知 $P \rightarrow Q$ 和 $P$，则可以推导出 $Q$。
• 否定前件（Modus Tollens）：如果已知 $P \rightarrow Q$ 和 $\neg Q$，则可以推导出 $\neg P$。

2.4.1 演绎推理

演绎推理是基于已知的前提，通过逻辑推导得出结论。它遵循严格的规则，保证结论的正确性。经典的演绎推理规则包括：

• 直觉主义推理：推理过程通过假设、构造和证明来得出结论。
• 归纳推理：通过从具体的实例中总结出一般规律，归纳推理的结论不一定是绝对正确的，但有较高的概率。

2.5 证明方法

证明方法是数学逻辑中的基本技术，常见的证明方法包括：

• 直接证明：通过逻辑推理直接从假设推导出结论。
• 间接证明（反证法）：假设结论为假，推导出矛盾，从而证明结论为真。
• 归纳法：通过验证基本情况并假设对任意情况成立，然后推导出结论。

2.5.1 数学归纳法

数学归纳法是一种常用的证明方法，适用于证明自然数上的命题。它分为两个步骤：

1. 基础步骤：证明命题对初始值（通常是 0 或 1）成立。
2. 归纳步骤：假设命

3. 图论

图论是离散数学的重要分支之一，研究图的性质和结构。图（Graph）是一种由一组顶点和顶点之间的边组成的数学结构。

3.1 图的基本概念

图由顶点（Vertices）和边（Edges）组成。图通常表示为 $G = (V, E)$，其中：

• $V$ 是顶点的集合，$V = \{v_1, v_2, v_3, \dots\}$；
• $E$ 是边的集合，$E = \{e_1, e_2, e_3, \dots\}$，每条边是顶点对 $(v_i, v_j)$，表示从 $v_i$ 到 $v_j$ 的连接。

3.1.1 图的类型

图的类型决定了图的结构和图中的边如何连接顶点，常见的图类型包括：

• 无向图：图中的边没有方向，即边 $(v_i, v_j)$ 与 $(v_j, v_i)$ 等价。无向图中的边表示顶点之间的双向关系。
• 有向图：图中的边有方向，表示从一个顶点到另一个顶点的单向关系。每条边记作 $(v_i, v_j)$，表示从 $v_i$ 到 $v_j$ 的有向边。
• 带权图：每条边上都有一个权值，表示连接两个顶点的代价、距离或其他度量。通常表示为 $G = (V, E, w)$，其中 $w$ 是边权值的映射 $w: E \to \mathbb{R}$。

3.1.2 图的表示方法

• 邻接矩阵：对于一个图 $G$，使用一个 $n \times n$ 的矩阵 $A$ 来表示，其中 $A[i][j]$ 表示顶点 $v_i$ 和 $v_j$ 是否有边连接。如果有边连接，则 $A[i][j] = 1$，否则为 0。对于带权图，$A[i][j]$ 表示边的权值。
• 邻接表：使用一个列表来表示每个顶点与之相连的其他顶点。每个顶点对应一个列表，列表中包含与该顶点相连的其他顶点。

3.1.3 图的度

• 度（Degree）是指一个顶点连接的边的数量：
  • 入度（Indegree）：有向图中，某个顶点的入度是指有多少条边指向该顶点。
  • 出度（Outdegree）：有向图中，某个顶点的出度是指有多少条边从该顶点出发。

3.2 图的运算

图论中的常见运算包括：

• 图的并：将两个图 $G_1 = (V_1, E_1)$ 和 $G_2 = (V_2, E_2)$ 合并为一个图，其中 $V = V_1 \cup V_2$，$E = E_1 \cup E_2$。
• 图的交：两个图 $G_1$ 和 $G_2$ 的交集是一个图，其中包含 $V_1 \cap V_2$ 和 $E_1 \cap E_2$ 中的顶点和边。
• 图的补图：图 $G$ 的补图是一个包含相同顶点集合的图，其中边集合是原图 $G$ 的边集合的补集，即 $E' = \{ (v_i, v_j) \mid (v_i, v_j) \notin E \}$。

3.3 路径与连通性

• 路径：图中的一个路径是从一个顶点到另一个顶点的边的序列。对于无向图，路径是顶点的一个序列，满足序列中的每一对相邻顶点都有一条边连接。对于有向图，路径的边有方向。
  • 简单路径：路径中没有重复顶点。
  • 回路：起点和终点相同的路径。
• 连通性：图的连通性描述了图中顶点之间的连接关系。
  • 连通图：无向图中，若任意两顶点之间都有路径连接，则称图为连通图。
  • 强连通图：有向图中，若任意两顶点之间都有路径连接（即从一个顶点到另一个顶点有路径，反之亦然），则称图为强连通图。
  • 弱连通图：如果图中的无向版本是连通的（忽略边的方向），则该有向图称为弱连通图。

3.4 图的遍历

图的遍历指的是从某个顶点出发，访问图中所有顶点的过程。常见的遍历算法有：

• 深度优先搜索（DFS）：从起始顶点出发，沿着边尽可能深地访问每个未访问过的顶点，直到没有未访问的邻接顶点为止，然后回溯。
• 广度优先搜索（BFS）：从起始顶点出发，先访问所有相邻的顶点，再逐层访问其他顶点，直到访问完所有顶点。

3.5 最短路径问题

最短路径问题是图论中的一个经典问题，旨在找到从一个顶点到另一个顶点的最短路径。常见的算法有：

• Dijkstra 算法：用于带权图中从一个源点到所有其他点的最短路径，要求边的权值为非负数。
• Bellman-Ford 算法：用于带负权边的图，能够检测负权环。
• Floyd-Warshall 算法：用于求解图中任意两点之间的最短路径，可以处理带有负权边的图，但无法处理负权环。

3.6 图的树和生成树

• 树：是一个没有回路的连通无向图。树是特殊的图，其中的任意两顶点之间都有且仅有一条路径。
• 生成树：是一个包含图中所有顶点的子图，并且是一个树。生成树有 $n-1$ 条边，其中 $n$ 是图中顶点的数量。
  • 最小生成树：带权无向图的生成树，边权和最小的生成树。常见的算法有 Kruskal 算法和 Prim 算法。

3.7 图的应用

图论在计算机科学中有广泛的应用，包括：

• 网络设计：如互联网、局域网的路由问题。
• 社会网络分析：社交网络中的用户之间的关系分析。
• 优化问题：如最短路径、最大流、最小生成树等问题。
• 任务调度：在任务调度和资源分配中，图可以用来建模任务间的依赖关系。

---

4. 组合数学

4.1 排列与组合

• 排列：从 $n$ 个不同元素中选取 $r$ 个元素的排列数为：

  $$P(n, r) = \frac{n!}{(n - r)!}$$

• 组合：从 $n$ 个不同元素中选取 $r$ 个元素的组合数为：

  $$C(n, r) = \frac{n!}{r!(n - r)!}$$

4.2 二项式定理

二项式定理给出了 $(x + y)^n$ 的展开式：

$$(x + y)^n = \sum_{k=0}^{n} \left( C(n, k) \cdot x^{n-k} \cdot y^k \right)$$

4.3 生成函数

生成函数是组合数学中的一个重要工具，尤其在解决递推关系和计数问题时非常有用。生成函数是一种将数列表示为一个幂级数的方式，它可以帮助我们通过操作生成函数来解决与数列相关的问题。

4.3.1 生成函数的定义

给定一个数列 $a_0, a_1, a_2, \dots$，其生成函数 $G(x)$ 定义为

$$G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots = \sum_{n=0}^{\infty} a_n x^n$$

这个幂级数的系数 $a_n$ 就是数列的元素。

4.3.2 生成函数的类型

• 普通生成函数（Ordinary Generating Function）：如上所述，表示数列的普通生成函数。
• 指数生成函数（Exponential Generating Function）：用于处理一些特定类型的数列，通常形式为：

$$G(x) = a_0 + a_1 \frac{x}{1!} + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \dots$$

4.3.3 生成函数的运算

生成函数可以通过一些基本的运算来操作，例如：

• 加法：如果 $G_A(x)$ 和 $G_B(x)$ 分别是两个数列的生成函数，那么 $G_A(x) + G_B(x)$ 是这两个数列和的生成函数。
• 乘法：生成函数的乘积对应数列的卷积。如果$G_A(x) = \sum a_n x^n$和 $G_B(x) = \sum b_n x^n $，则

$$G_A(x) \cdot G_B(x) = \sum_{n=0}^{\infty} \left( \sum_{k=0}^{n} a_k b_{n-k} \right) x^n$$

4.3.4 使用例子

例子1：斐波那契数列的生成函数
斐波那契数列的定义是：

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}, \quad n \geq 2$$

其生成函数 ( F(x) ) 可以通过递推关系得出：

$$F(x) = \sum_{n=0}^{\infty} F_n x^n$$

通过代入递推公式并简化，可以得到：

$$F(x) = \frac{x}{1 - x - x^2}$$

这个生成函数的分母给出了斐波那契数列的递推关系。

例子2：组合数的生成函数
如果我们要计算从 n 个元素中选择 r 个元素的组合数 ( C(n, r) )，则其生成函数为：

$$(1 + x)^n = \sum_{r=0}^{n} C(n, r) x^r$$

这是一个常见的组合问题，可以通过生成函数轻松得到组合数的各项。

5. 关系与函数

5.1 关系

在数学中，关系描述了集合之间的联系。集合 $A$ 和 $B$ 之间的关系 $R$ 是 $A$ 中的元素与 $B$ 中的元素之间的一种映射，通常表示为一组有序对。关系的定义和性质对于理解数学对象之间的结构至关重要。

5.1.1 关系的定义

如果 $A$ 和 $B$ 是两个集合，那么 $A$ 和 $B$ 之间的关系 $R$ 是 $A \times B$ 的子集，即 $R \subseteq A \times B$。这意味着每个关系 $R$ 是由 $A$ 中的元素和 $B$ 中的元素组成的一组有序对。记作：

• $(a, b) \in R$ 表示 $a$ 与 $b$ 之间有关系。

例如，考虑集合 $A = \{1, 2, 3\}$ 和集合 $B = \{a, b, c\}$，一个可能的关系是：

• $R = \{(1, a), (2, b), (3, c)\}$，表示集合 $A$ 和 $B$ 之间的关系。

5.1.2 关系的种类

关系可以根据不同的性质和特征进行分类，主要包括以下几种类型：

• 反射性（Reflexive）：对于集合 $A$ 中的每个元素 $a$，有 $(a, a) \in R$，即每个元素与自身都有关系。

  • 例如：关系 $R = \{(1, 1), (2, 2), (3, 3)\}$ 是反射性的。

• 对称性（Symmetric）：如果 $(a, b) \in R$，那么 $(b, a) \in R$，即如果 $a$ 与 $b$ 有关系，那么 $b$ 与 $a$ 也有关系。

  • 例如：关系 $R = \{(1, 2), (2, 1)\}$ 是对称的。

• 传递性（Transitive）：如果 $(a, b) \in R$ 且 $(b, c) \in R$，那么 $(a, c) \in R$，即如果 $a$ 与 $b$ 有关系，$b$ 与 $c$ 有关系，则 $a$ 与 $c$ 也有关系。

  • 例如：关系 $R = \{(1, 2), (2, 3), (1, 3)\}$ 是传递的。

• 反对称性（Antisymmetric）：如果 $(a, b) \in R$ 且 $(b, a) \in R$，那么 $a = b$，即如果 $a$ 与 $b$ 有关系，并且 $b$ 与 $a$ 也有关系，则 $a$ 必须等于 $b$。

  • 例如：关系 $R = \{(1, 2), (2, 1)\}$ 不是反对称的，但关系 $R = \{(1, 2), (2, 3)\}$ 是反对称的。

• 全序关系（Total Order）：如果关系 $R$ 满足反射性、对称性、传递性和反对称性，并且对于集合中的任意两个元素 $a$ 和 $b$，总有 $(a, b) \in R$ 或 $(b, a) \in R$，那么称该关系是全序关系。

  • 例如：集合 $\mathbb{N}$ 上的“小于等于”关系 $\leq$ 是全序关系。

5.1.3 关系的运算

关系也可以进行运算，常见的运算包括：

• 关系的并（Union）：如果 $R_1 \subseteq A \times B$ 和 $R_2 \subseteq A \times B$，则它们的并是 $R_1 \cup R_2$，即包含 $R_1$ 和 $R_2$ 中所有有序对的关系。

• 关系的交（Intersection）：如果 $R_1 \subseteq A \times B$ 和 $R_2 \subseteq A \times B$，则它们的交是 $R_1 \cap R_2$，即包含同时属于 $R_1$ 和 $R_2$ 的有序对的关系。

• 关系的差（Difference）：如果 $R_1 \subseteq A \times B$ 和 $R_2 \subseteq A \times B$，则 $R_1 - R_2$ 表示属于 $R_1$ 但不属于 $R_2$ 的有序对。

• 关系的逆（Inverse）：关系 $R$ 的逆 $R^{-1}$ 是 $A \times B$ 中所有满足 $(b, a) \in R$ 的有序对的集合，即 $R^{-1} = \{(b, a) \mid (a, b) \in R\}$。

5.1.4 关系的闭包

在某些情况下，我们需要将一个关系扩展或增加到满足某些性质。这些扩展操作称为关系的闭包。常见的关系闭包包括：

• 反射闭包：给定关系 $R$，其反射闭包是最小的包含 $R$ 的反射关系。
• 对称闭包：给定关系 $R$，其对称闭包是最小的包含 $R$ 的对称关系。
• 传递闭包：给定关系 $R$，其传递闭包是最小的包含 $R$ 的传递关系。
• 等价闭包：给定关系 $R$，其等价闭包是最小的包含 $R$ 的等价关系。

5.1.5 等价关系

等价关系是一个特殊的关系，具有以下三个性质：

1. 反射性：每个元素与自身有关系，即 $(a, a) \in R$。
2. 对称性：如果 $(a, b) \in R$，则 $(b, a) \in R$。
3. 传递性：如果 $(a, b) \in R$ 且 $(b, c) \in R$，则 $(a, c) \in R$。

如果一个关系满足这三个性质，我们称这个关系为等价关系。等价关系将集合划分成若干个等价类，每个等价类是集合中的一个子集，包含了所有彼此之间有等价关系的元素。

例如，考虑集合 $\{1, 2, 3, 4\}$，关系 $R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1)\}$ 是一个等价关系，其等价类为：

• $\{1, 2\}$ 和 $\{3\}$ 和 $\{4\}$。

5.2 函数

在集合论中，函数是一种特殊的关系，它将集合 $A$ 中的每个元素映射到集合 $B$ 中的唯一元素。函数的定义为：如果 $A$ 和 $B$ 是两个集合，$f$ 是从集合 $A$ 到集合 $B$ 的函数，表示为 $f: A \rightarrow B$，其中每个 $a \in A$ 都有唯一的 $b \in B$，记作 $f(a) = b$。

5.2.1 函数的种类

• 单射（Injective Function）：如果函数 $f$ 满足对于所有的 $a_1, a_2 \in A$，如果 $f(a_1) = f(a_2)$，则 $a_1 = a_2$，即不同的元素在映射后对应不同的元素。
• 满射（Surjective Function）：如果函数 $f$ 满足对于 $B$ 中的每个元素 $b$，都存在 $A$ 中的元素 $a$，使得 $f(a) = b$，即每个元素都被映射到。
• 双射（Bijective Function）：如果函数同时是单射和满射，即满足 $f$ 是单射且 $f$ 是满射。

5.2.2 函数的运算

函数也可以进行运算，常见的函数运算包括：

• 函数的合成：给定函数 $f: A \rightarrow B$ 和 $g: B \rightarrow C$，则它们的合成函数 $g \circ f: A \rightarrow C$ 定义为 $g(f(a))$，即先应用函数 $f$，再应用函数 $g$。
• 函数的逆：如果函数 $f: A \rightarrow B$ 是双射的，则存在一个逆函数 $f^{-1}: B \rightarrow A$，它满足对于任意 $a \in A$ 和 $b \in B$，如果 $f(a) = b$，则 $f^{-1}(b) = a$。

5.2.3 函数的性质

• 保持运算性：一些特殊的函数，比如线性函数、同构函数，保持代数结构不变。
• 可逆性：只有双射函数才能是可逆的。

6. 算法

6.1 算法的定义

算法是一个明确的、有限的步骤序列，用于解决特定问题。每一步都是具体的、可执行的操作，算法从输入数据开始，经过一系列步骤后输出结果。

6.1.1 算法的特点

• 输入：算法有一个或多个输入，代表着需要处理的数据。
• 输出：算法有一个或多个输出，代表算法的结果。
• 确定性：算法的每一步都应当是确定的，即在相同的输入下，算法每次执行的结果相同。
• 有限性：算法必须在有限的时间内终止，且每个步骤数目有限。
• 可行性：每个步骤都可以通过有限的时间和资源执行。

6.2 算法设计方法

6.2.1 分治法（Divide and Conquer）

分治法是一种将问题分解为多个子问题，解决这些子问题后再将它们合并成一个解的方法。这个方法通常适用于可以递归分解的结构化问题。

• 基本步骤：

  1. 将问题分解为多个较小的子问题。
  2. 递归地解决子问题。
  3. 合并子问题的解。

• 经典例子：

  • 归并排序（Merge Sort）：将待排序数组递归地分成两半，分别排序后合并。
  • 快速排序（Quick Sort）：通过选择一个基准元素，将数组分割成两部分，然后递归地排序每部分。

6.2.2 动态规划（Dynamic Programming）

动态规划用于解决具有重叠子问题和最优子结构的问题，常见于求解优化问题。它通过将子问题的解缓存下来避免重复计算。

• 基本步骤：

  1. 定义子问题的状态和状态转移方程。
  2. 通过迭代或递归的方式从小到大求解问题。
  3. 记录每个子问题的解，并利用已解决的子问题来构建最终解。

• 经典例子：

  • 斐波那契数列：通过缓存先前的计算结果来避免重复计算。
  • 背包问题：在背包容量限制下，选择物品以最大化总价值。

6.2.3 贪心算法（Greedy Algorithm）

贪心算法通过每一步选择当前最优解来构建整体解。贪心算法的核心在于在每一步做出局部最优选择，并希望最终能得到全局最优解。

• 基本步骤：

  1. 从问题的初始状态开始。
  2. 在每一步中选择当前最优的解。
  3. 最终得到一个解。

• 经典例子：

  • 最短路径问题：如 Dijkstra 算法，选择当前最短的路径，逐步扩展。
  • 活动选择问题：选择最大数量的不重叠活动。

6.2.4 回溯法（Backtracking）

回溯法是一种通过逐步构建解空间树来解决问题的方法。在搜索过程中，当发现当前的路径不可能得到解时，算法会返回并尝试其他的路径。

• 基本步骤：

  1. 从解空间树的根节点开始。
  2. 在每个节点上选择一个可行的解。
  3. 当选择的解无法继续扩展时，回溯并选择另一个解。
  4. 直到找到一个合适的解或遍历所有可能的解。

• 经典例子：

  • 八皇后问题：在一个 $8 \times 8$ 的棋盘上，摆放 8 个皇后，使得它们互不攻击。
  • 图的着色问题：为图的每个节点着色，确保相邻节点的颜色不同。

6.3 算法复杂度分析

6.3.1 时间复杂度（Time Complexity）

时间复杂度表示算法执行所需的时间随输入规模的变化情况。常见的时间复杂度包括：

• 常数时间复杂度：$O(1)$，算法执行时间与输入大小无关。
• 对数时间复杂度：$O(\log n)$，如二分查找。
• 线性时间复杂度：$O(n)$，如遍历一个数组。
• 线性对数时间复杂度：$O(n \log n)$，如归并排序、快速排序。
• 平方时间复杂度：$O(n^2)$，如冒泡排序、选择排序。
• 指数时间复杂度：$O(2^n)$，如解决某些递归问题。

6.3.2 空间复杂度（Space Complexity）

空间复杂度描述算法所需要的额外存储空间随输入规模的变化情况。常见的空间复杂度包括：

• 常数空间复杂度：$O(1)$，算法所需的空间不随输入规模的变化而变化。
• 线性空间复杂度：$O(n)$，如存储输入数组。
• 递归空间复杂度：递归调用栈的空间，通常是递归深度。

6.3.3 大O表示法（Big O Notation）

大O表示法用于描述算法在最坏情况下的时间复杂度或空间复杂度，忽略常数项和低阶项。

例如：

• $O(n^2)$：表示算法的时间复杂度随着输入规模的平方增长。
• $O(n \log n)$：表示算法的时间复杂度随着输入规模与其对数的乘积增长。

6.4 排序算法

排序是计算机科学中常见的基本操作之一。排序算法根据不同的策略和复杂度可以分为不同的类别。

6.4.1 交换排序

• 冒泡排序（Bubble Sort）：通过重复比较相邻的元素并交换它们的位置，直到所有元素都按照正确顺序排列。
• 选择排序（Selection Sort）：每次从未排序的部分选择最小（或最大）的元素放到已排序的部分。

6.4.2 分治排序

• 归并排序（Merge Sort）：将数组分成两半，递归排序后合并两部分。
• 快速排序（Quick Sort）：通过选择基准元素，将数组划分为小于基准的部分和大于基准的部分，递归排序。

6.4.3 插入排序

• 插入排序（Insertion Sort）：从数组的第二个元素开始，依次与前面的元素进行比较，插入到合适的位置，直到整个数组排序完成。

6.4.4 计数排序

• 计数排序（Counting Sort）：通过计算每个元素出现的次数，来决定元素的最终位置。

6.5 图算法

图算法是计算机科学和离散数学中的重要内容。常见的图算法包括：

6.5.1 最短路径算法

• Dijkstra 算法：用于计算从一个源点到图中所有其他节点的最短路径，前提是图的边权非负。
• Bellman-Ford 算法：适用于带负权边的图，能够检测负权环。

6.5.2 图遍历算法

• 深度优先搜索（DFS）：通过深入每个节点的子节点来遍历图，适用于寻找图中的路径或连通性。
• 广度优先搜索（BFS）：通过层次逐层遍历图，适用于计算最短路径和图的连通性。

6.5.3 最小生成树

• Prim 算法：用于从一个图的节点开始，找到一棵最小生成树，所有的边权和最小。
• Kruskal 算法：通过将图中的边按权重排序，然后逐步选择不形成环的最小边来生成最小生成树。

---

7. 密码学

7.1 密码学的基本概念

密码学的基本目标是通过算法将明文转化为密文，并保证数据在传输和存储过程中的安全性。密码学的核心概念包括：

• 加密：将明文数据通过一定的算法和密钥转换为密文，目的是保护数据的机密性。
• 解密：通过密钥将密文恢复为明文。
• 密钥：用于加密和解密过程的秘密数据。密钥的保密性决定了加密系统的安全性。
• 算法：执行加密和解密过程的数学步骤或规则。

7.2 对称加密与非对称加密

7.2.1 对称加密

对称加密（Symmetric Encryption）是加密和解密使用相同密钥的加密方式。发送方和接收方使用相同的密钥进行加解密操作，因此密钥的安全性至关重要。

• 优点：

  • 算法速度较快，适用于大量数据加密。
  • 计算资源消耗较少。

• 缺点：

  • 密钥分发问题：如何安全地传输密钥是一个挑战。
  • 如果密钥泄露，所有的通信内容都会受到威胁。

• 常见算法：

  • AES（高级加密标准）：当前广泛使用的对称加密算法，支持128位、192位和256位密钥长度。
  • DES（数据加密标准）：一种较旧的加密算法，已经被AES替代。

7.2.2 非对称加密

非对称加密（Asymmetric Encryption）使用一对密钥：公钥和私钥。公钥用于加密，私钥用于解密。公钥可以公开，而私钥必须保密。

• 优点：

  • 无需提前共享密钥，公钥可以公开分发，私钥保持秘密。
  • 可以用于数字签名，确保数据的完整性和真实性。

• 缺点：

  • 相比对称加密，算法的运算速度较慢，计算开销大。
  • 主要用于小规模数据的加密，如密钥交换、数字签名等。

• 常见算法：

  • RSA（Rivest–Shamir–Adleman）：最广泛使用的非对称加密算法，基于大数分解的数学问题。
  • ECC（椭圆曲线密码学）：比RSA更高效的非对称加密方法，使用椭圆曲线数学。
  • DSA（数字签名算法）：用于数字签名，确保数据的完整性和认证。

7.3 哈希函数

哈希函数（Hash Function）是一种将任意大小的输入（通常是文本或文件）映射到固定长度的输出值的函数。哈希函数通常用于数据完整性校验、密码存储和数字签名等领域。

• 性质：

  • 单向性：难以从哈希值反推出原始输入。
  • 碰撞抵抗性：不同的输入不能产生相同的哈希值。
  • 一致性：相同的输入总是产生相同的输出。
  • 不可预测性：微小的输入变化应该导致完全不同的输出。

• 常见哈希算法：

  • MD5（消息摘要算法5）：虽然已被证明不再安全，但依然广泛用于文件校验。
  • SHA-1（安全哈希算法1）：曾广泛应用，但已被认为不再安全。
  • SHA-256：SHA-2家族中的一员，广泛应用于现代加密协议（如比特币区块链）。

7.4 数字签名与认证

7.4.1 数字签名

数字签名是非对称加密的应用，旨在验证信息的来源和完整性。它使用发送者的私钥对消息进行签名，接收者使用发送者的公钥来验证签名的有效性。

• 过程：

  1. 发送者对消息的哈希值进行加密，得到数字签名。
  2. 接收者使用发送者的公钥对数字签名进行解密，并比对解密后的哈希值与消息的哈希值，验证消息是否被篡改。

• 应用：

  • 电子邮件加密：确保邮件内容和发送者的真实性。
  • 区块链：数字签名用于确保交易的合法性和不可篡改性。

7.4.2 认证

认证是验证一个主体的身份，通常通过证书链或身份验证协议来实现。常见的认证协议包括：

• SSL/TLS：用于互联网通信的加密协议，提供数据加密和身份验证。
• OAuth：用于第三方应用访问用户资源的开放标准协议，广泛应用于社交媒体登录等场景。

7.5 密码学中的经典问题

7.5.1 公钥分发

公钥分发问题是指如何在不安全的通信信道上安全地传输公钥。通常通过以下方式解决：

• 证书：由可信的证书颁发机构（CA）签发公钥证书，以确保公钥的真实性。
• Diffie-Hellman密钥交换：一种安全的密钥交换协议，允许双方在不直接交换密钥的情况下共享一个密钥。

---

8. 计算模型

计算模型是数学中用于描述和理解计算过程的抽象框架。通过计算模型，研究人员能够定义什么是“可计算的”并提出算法设计的标准。计算模型为计算机科学中的自动机理论、复杂性理论等奠定了基础。

8.1 图灵机

图灵机（Turing Machine）是由英国数学家艾伦·图灵在1936年提出的抽象计算模型，它是理论计算机科学中的核心模型之一，用于定义什么是可计算的。

8.1.1 图灵机的结构

图灵机由以下部分组成：

• 带子（Tape）：图灵机的输入数据存储在一个无限长的带子上。带子分为多个单元格，每个单元格可以存储一个符号。
• 读写头（Head）：读写头可以在带子上进行读写操作，并能在带子上左右移动。
• 状态控制器（State Controller）：图灵机的操作由一个有限的状态集合控制，控制器根据当前状态和带子上符号的内容来决定接下来的操作。

8.1.2 图灵机的工作过程

图灵机的计算过程遵循以下规则：

1. 图灵机在当前状态下读取带子上的符号。
2. 根据当前状态和读取的符号，图灵机决定：
   • 写入新的符号到带子上。
   • 移动读写头：向左或向右。
   • 转换到下一个状态。
3. 图灵机重复上述步骤，直到进入“停机状态”，即不再继续计算。

图灵机是计算模型中的最强模型，因为它能够模拟任何有效的计算过程。

8.1.3 图灵机的应用

图灵机不仅是理论计算机科学中的核心概念，还在计算复杂性理论中发挥了重要作用。通过图灵机的可计算性定义，可以判断某个问题是否是可解的。图灵机还被用来证明计算不可解问题的存在，如停机问题。

8.2 有限自动机

有限自动机（Finite Automaton, FA）是一种简化的计算模型，用于描述具有有限状态的计算过程。与图灵机相比，有限自动机的计算能力较弱，但在许多实际应用中，如编译器和正则表达式的实现中，有限自动机有广泛应用。

8.2.1 有限自动机的结构

有限自动机由以下部分组成：

• 有限的状态集合：自动机有一个有限数量的状态。
• 输入符号集合（字母表）：自动机接受输入符号的集合，通常是一个有限集合。
• 转换函数：规定自动机如何从一个状态转移到另一个状态。每次读入一个符号，自动机会根据当前状态和符号来选择下一个状态。
• 初始状态：自动机开始时的状态。
• 接受状态：如果自动机在计算结束时处于某个接受状态，则认为输入是接受的。

8.2.2 有限自动机的类型

有限自动机有两种常见类型：

• 确定性有限自动机（DFA）：在每个状态和每个输入符号下，自动机只能转移到一个确定的状态。DFA没有任何不确定性。
• 非确定性有限自动机（NFA）：在某些状态下，自动机可以有多个可能的转移，或者在某些情况下可以不进行任何状态转移。

8.2.3 有限自动机的应用

有限自动机广泛应用于：

• 正则表达式匹配：正则表达式引擎内部使用有限自动机来匹配字符串。
• 词法分析：编译器使用有限自动机来分析输入的源代码，识别出关键字、标识符等词法单元。

8.3 随机过程模型

随机过程模型（Stochastic Process Model）是一种描述在随机环境中随时间变化的系统的数学模型。在离散数学中，随机过程广泛应用于概率论、统计学、随机算法和机器学习等领域。

8.3.1 马尔可夫链

马尔可夫链（Markov Chain）是一种特殊的随机过程，其特点是系统的状态转移仅依赖于当前状态，而与之前的状态无关。换句话说，马尔可夫链满足无记忆性，即系统的未来状态只与当前状态有关，与过去的状态无关。

• 状态空间：马尔可夫链可以在一个有限或无限的状态空间中进行转移。
• 转移矩阵：马尔可夫链的转移矩阵描述了从一个状态到另一个状态的概率。

8.3.2 马尔可夫链的应用

• 随机算法：在很多基于概率的算法中，马尔可夫链被用来模拟随机过程，如蒙特卡罗方法。
• 语音识别与自然语言处理：马尔可夫链常用于建模语言的统计特性，如在隐马尔可夫模型（HMM）中应用。

8.4 λ-演算

λ-演算（Lambda Calculus）是一种基于函数的计算模型，是理论计算机科学中的基础之一。它通过函数应用和变量替换来定义计算过程，是描述计算机程序的基础模型之一。

8.4.1 λ-演算的基本元素

• λ表达式：λ-演算中的基本构建块。一个λ表达式的形式为 λx.E，表示一个接受输入 x 的函数，其中 E 是表达式。
• 函数应用：将一个λ表达式应用于一个参数。例如，(λx.E)(a) 表示将表达式 E 中的 x 替换为 a。

8.4.2 λ-演算的应用

λ-演算为函数式编程语言（如Lisp、Haskell等）提供了理论基础。它也用于研究计算的可计算性，描述计算机程序的逻辑。

8.5 可计算性与复杂性理论

计算模型的另一个重要应用是可计算性与复杂性理论，旨在定义哪些问题可以被计算机解决，以及这些问题的计算难度。

8.5.1 可计算性

• 可计算问题：一个问题是可计算的，如果存在一个算法（如图灵机）可以在有限时间内解决这个问题。
• 不可计算问题：一个问题是不可计算的，如果没有任何算法能够解决该问题。著名的不可计算问题包括停机问题。

8.5.2 复杂性理论

复杂性理论研究问题的计算难度。常见的复杂度类包括：

• P类问题：可以在多项式时间内解决的问题。
• NP类问题：可以在多项式时间内验证一个解的问题。NP完全问题是NP类中最难的问题。
• NP完全性：一个问题是NP完全的，如果它是NP类中最难的问题，并且所有NP类问题都可以在多项式时间内归约到它。

---

TO BE CONTINUED . . . . . .