背景：程序员的数学基础课——素数判定、对数反运算、集合论、图论、代数结构、组合数学、数理逻辑。本文用 7 大离散数学分支 + 5 大数论核心 + 4 大图论应用，把"程序员必备数学"做一次系统梳理。

Why 2016 年：2015-2016 是国内"程序员数学基础"觉醒期——LeetCode 中文站上线、《算法导论》第 3 版翻译、《数学之美》《程序员的数学》系列书热销。本文写给"想补数学基础的工程师"。

一、素数（质数）：自然数的"原子"

1.1 定义

素数（Prime）：在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数；否则称为合数（Composite）。

1

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...

1.2 素数的 5 个性质

1.3 程序员最常用的素数判定

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import math

def is_prime(n: int) -> bool:
    """素数判定：试除法 O(√n)"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 只需检查到 √n
    for i in range(3, int(math.isqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

# 测试
for n in [2, 3, 4, 17, 25, 97, 100, 997]:
    print(f"{n}: {is_prime(n)}")

1
2
3
4
5
6
7
8
9

# 输出
2: True
3: True
4: False
17: True
25: False
97: True
100: False
997: True

性能优化：

• 6k±1 优化：所有 >3 的素数都形如 6k+1 或 6k-1（因为 6k+0/2/3/4 必被 2/3 整除）
• Miller-Rabin：O(k log³n) 概率算法，大数判定（>10^18）首选
• AKS：O(log^6 n) 确定算法，2002 年发现，理论突破但实际慢

1.4 素数在程序员世界的应用

二、对数：指数的"反函数"

2.1 定义

对数（Logarithm）：是对求幂的逆运算，正如除法是乘法的逆运算。 如果 a^x = N（a > 0，且 a ≠ 1），那么数 x 叫做以 a 为底 N 的对数，记作 x = log_a(N)。

2.2 程序员最常用的 3 个对数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import math

# 自然对数（ln）：e 为底
print(math.log(7.389))      # 2.0

# 常用对数（lg）：10 为底
print(math.log10(100))       # 2.0

# 二进制对数（lb）：2 为底（算法复杂度分析最常用！）
print(math.log2(1024))       # 10.0（二分 10 次找到 1024 内的数）

2.3 对数在算法分析中的 5 大应用

2.4 4 条核心对数运算法则

1
2
3
4

换底公式：log_a(b) = log_c(b) / log_c(a)
对数幂：log(a^n) = n · log(a)
对数乘积：log(a·b) = log(a) + log(b)
对数商：log(a/b) = log(a) - log(b)

三、离散数学 7 大分支

离散数学（Discrete mathematics）是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素，主要是研究基于离散量的结构和相互间的关系。

它的对象一般是有限个或可数个元素（连续数学研究的是实数区间这样的连续量）。

3.1 离散数学在 CS 课程中的位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

程序设计语言
数据结构
操作系统
编译技术
人工智能
数据库
算法设计与分析
理论计算机科学基础
↑
都依赖 离散数学

3.2 7 大分支速览

四、集合论（Set Theory）

4.1 5 大核心概念

4.2 程序员对应实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Java
Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5));

// 并集
Set<Integer> union = new HashSet<>(a);
union.addAll(b);  // [1, 2, 3, 4, 5]

// 交集
Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);  // [3]

// 差集
Set<Integer> difference = new HashSet<>(a);
difference.removeAll(b);  // [1, 2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

-- SQL：集合的并集（UNION）、交集（INTERSECT）、差集（EXCEPT）
SELECT id FROM table_a
UNION
SELECT id FROM table_b;

SELECT id FROM table_a
INTERSECT
SELECT id FROM table_b;

SELECT id FROM table_a
EXCEPT
SELECT id FROM table_b;

4.3 集合论 3 大基础

五、图论（Graph Theory）

5.1 6 大基本概念

5.2 5 类图着色问题

1
2
3
4
5

支配集：选出最少的顶点"监视"所有顶点
覆盖集：选出最少的边"覆盖"所有顶点
独立集：选出最多的顶点两两不相邻
匹配：选出最多的边两两不共享顶点
带权图：边上加权（最短路径、最小生成树）

5.3 程序员最常用的 5 个图算法

5.4 图在程序员世界的 7 大应用

六、代数结构

6.1 5 大基本结构

6.2 4 个衍生结构

6.3 程序员最常用：有限域 GF(2⁸)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# AES 加密用 GF(2^8) 域
def gf_mult(a, b):
    """GF(2^8) 上的多项式乘法（不可约多项式 x^8 + x^4 + x^3 + x + 1 = 0x11B）"""
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        hi_bit = a & 0x80
        a = (a << 1) & 0xFF
        if hi_bit:
            a ^= 0x1B  # 不可约多项式
        b >>= 1
    return p

# 测试
print(hex(gf_mult(0x57, 0x83)))  # AES 中的核心运算

七、组合数学

7.1 4 大计数公式

7.2 5 大计数定理

7.3 程序员应用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# 二项式系数：Pascal 三角形
def binomial_coefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)

# 错排：5 个人各写 1 张贺卡，都不寄给自己
def derangement(n):
    if n == 0: return 1
    if n == 1: return 0
    return (n - 1) * (derangement(n-1) + derangement(n-2))

print(derangement(5))  # 44

八、数理逻辑

8.1 3 大核心

8.2 5 大经典推理规则

8.3 程序员应用：SQL 谓词逻辑

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

-- 谓词演算 → SQL WHERE
-- ∀x (学生(x) → 选课(x))
SELECT s.id
FROM student s
WHERE EXISTS (SELECT 1 FROM course_selection c WHERE c.student_id = s.id);

-- ∃x (学生(x) ∧ 成绩(x) >= 90)
SELECT s.id, s.name
FROM student s
JOIN score sc ON sc.student_id = s.id
WHERE sc.score >= 90;

九、5 个数学基础速查表

9.1 自然数对数表

9.2 常用数学符号

9.3 初等代数恒等式

1
2
3
4

完全平方：(a±b)² = a² ± 2ab + b²
立方和：a³ + b³ = (a+b)(a² - ab + b²)
立方差：a³ - b³ = (a-b)(a² + ab + b²)
二次方程求根：x = (-b ± √(b² - 4ac)) / 2a

9.4 几何基础

9.5 概率统计速查

十、4 大推荐教材

十一、参考与延伸

• Prime Pages（素数数据库）：https://primes.utm.edu/
• Wolfram MathWorld：https://mathworld.wolfram.com/
• 图论算法可视化：https://visualgo.net/zh
• MIT 6.042J 离散数学（OCW）：https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/
• 陶哲轩《实分析》：https://terrytao.wordpress.com/books/

下一步：先把《程序员的数学》通读一遍（2-3 周），再选《算法导论》部分章节深入；接下来在 LeetCode 上有意识地用数学思维（如用对数法分析时间复杂度、用素数优化哈希）。

十二、2024+ 视角：8 年后，程序员的数学基础变了吗？

本文写于 2016 年 1 月。8 年后（2024-2026）回望，7 大离散数学分支 + 5 大数论核心 + 4 大图论应用——这套"老菜单"依然有效，但每道菜都多了一层"AI 时代"的浇头。下面逐条对照。

12.1 素数：8 年后的新角色

2016 年我写"素数 = RSA + 哈希表"。2024-2026 素数的新角色：

1. 后量子密码学（Post-Quantum Cryptography, PQC）——2024-08 NIST 正式发布 PQC 标准
   • ML-KEM（原 Kyber，格密码 / Lattice-based）——核心仍依赖有限域运算 + 素数
   • ML-DSA（原 Dilithium）——签名算法，基于模运算 + 拒绝采样
   • SLH-DSA（原 SPHINCS+）——哈希签名，只依赖哈希函数（无素数）
2. 国密算法 SM2/SM3/SM4——等保 2.0 三级强制要求，SM2 基于 256 位素数域椭圆曲线
3. 零知识证明（ZKP）——zk-SNARK、zk-STARK 在区块链 + 隐私计算中爆发，核心数学是素数域 + 多项式承诺
4. RSA 仍在用——2024-2026 仍是 80% HTTPS 站点的主流算法，2048 位 / 4096 位 RSA 是事实标准

关键变化：素数从"经典密码学"扩展到"后量子密码 + 零知识证明 + 国产化合规"——8 年后素数仍是程序员必须懂的"硬数学"。

12.2 对数：LLM 时代的新复杂度

2016 年我写"对数 = O(log n) 时间复杂度"。2024-2026 对数有了新战场：

1. Transformer 复杂度：
   • 标准 Attention：O(n²)（n 是序列长度）——128K 上下文就是 163 亿次运算
   • FlashAttention：O(n log n) 显存、实际计算仍是 O(n²)——2022-2024 主流优化
   • Linear Attention（Performer / Mamba）：O(n)——2024-2026 正在突破的方向
2. Token 经济学：
   • LLM 推理时 KV Cache 占显存 O(n²)——各种压缩方案都在用对数技巧
   • 上下文长度 1M（Llama 4 2025 目标）需要 Sub-quadratic 算法——对数是关键
3. 时间复杂度面试新题：
   • 2024 面试题：“为什么 Attention 是 O(n²)？”
   • 2024 面试题：“如何把 Attention 优化到 O(n log n)？”
   • 2024 面试题：“KV Cache 怎么压缩？”

关键变化：对数从"二分查找"扩展到"LLM 复杂度分析"——8 年后对数仍是计算机科学的"复杂度语言"。

12.3 集合论 / 图论：RAG 与知识图谱的基础

2016 年我写"集合论 = SQL 基础"。2024-2026 集合论 / 图论的新角色：

1. RAG（检索增强生成）——本质是集合论 + 向量空间：
   • 文档 → Embedding → 集合 Top-K 查询
   • 关系代数（UNION / INTERSECT / JOIN）在 RAG pipeline 里反复出现
2. 知识图谱——图论 + Embedding：
   • Microsoft GraphRAG（2024 发布）——基于 LLM 抽取实体关系，建图
   • Neo4j 5.x + LangChain——2024-2026 知识图谱 + LLM 主流方案
   • 实体关系（Entity-Relation） = 图论里的"边"+“顶点”
3. 图神经网络（GNN）——图论 + 深度学习：
   • 药物发现（分子结构 = 图）——2024-2026 大爆发
   • 推荐系统（用户-商品二分图）——几乎所有大厂都在用
   • 社交网络分析——Facebook / 微信的"朋友推荐"
4. 数据库 JOIN 优化——图论 + 关系代数的回旋镖：
   • 2024-2026 图数据库（Neo4j / TigerGraph / NebulaGraph）爆发
   • SQL + Graph Hybrid 成为新趋势

关键变化：集合论 / 图论从"数据库基础"扩展到"RAG + 知识图谱 + GNN"——8 年后图论成为 AI 时代"数据建模"的核心语言。

12.4 代数结构 / 数理逻辑：形式化验证与 AI 推理

2016 年我写"代数结构 = 密码学"。2024-2026 新角色：

1. 形式化验证（Formal Verification）：
   • Lean 4 + Mathlib（2024-2026 爆发）——用数理逻辑证明数学定理
   • Coq / Isabelle / TLA+——形式化验证工业软件
   • AWS 用 TLA+ 验证 S3 正确性——经典案例
2. AI 自动定理证明：
   • DeepMind AlphaProof（2024-07，IMO 银牌）——AI 解数学题
   • OpenAI o1/o3 系列——Chain-of-Thought 推理的工业化
   • Lean Copilot（2024）——AI + Lean 4 证明助手
3. 约束求解（SMT Solver）：
   • Z3——程序分析、编译器优化、形式化验证的核心
   • SMT-LIB——形式化逻辑标准语言
4. 格密码（Lattice-based Cryptography）：
   • LWE / RLWE 问题——后量子密码学基础
   • 格理论（Lattice Theory） = 离散数学的"现代分支"

关键变化：代数结构 / 数理逻辑从"教科书理论"走向"AI 推理 + 形式化验证"——8 年后数理逻辑成为 AI 推理的"形式化底层"。

12.5 组合数学：算法竞赛 → AI 推理

2016 年组合数学主要用于"算法竞赛 + 概率分析"。2024-2026 新场景：

1. AI 推理的组合优化：
   • Chain-of-Thought 路径搜索 = 图搜索 + 组合
   • Tree-of-Thoughts / Graph-of-Thoughts（2023-2024）= 显式的组合搜索
2. 密码学协议：
   • 安全多方计算（MPC）——基于秘密分享 + 组合数学
   • 同态加密——基于格 + 模运算 + 组合优化
3. 生成式 AI：
   • 采样算法（MCMC / 拒绝采样 / 重要性采样）= 组合数学 + 概率

关键变化：组合数学从"竞赛技巧"扩展到"AI 推理路径搜索"——8 年后组合数学成为 AI 系统设计的"组合优化"工具。

12.6 计算模型：图灵机 → 神经网络的"可计算性"

2016 年我说"图灵机 = 理论 CS 的基础"。2024-2026 新思考：

• 大语言模型能"计算"吗？——这是个 2023-2026 仍在争论的哲学问题
• Transformer 是图灵完备的（已被严格证明）——但它的"计算范式"和图灵机完全不同
• 神经图灵机 / 神经 RAM（2024-2026 探索中）——结合神经网络 + 外部记忆
• 可解释性 / 形式化推理——2024-2026 在"AI 可解释"领域，数理逻辑 + 计算模型仍是基础

关键变化：计算模型从"理论 CS 课程"扩展到"AI 系统的可计算性 / 可解释性"——8 年后计算模型成为 AI 系统的"理论根基"。

12.7 8 年对照表

12.8 8 年升级版书单

2016 年我推荐 4 本书。2024 年我会加 3 本：

外加 3 个免费在线资源：

• 3Blue1Brown（YouTube / B 站）——线性代数 / 微积分 / 信息论可视化
• MIT 18.065 Matrix Methods in Data Analysis（OCW）——线性代数应用
• Distill.pub（归档前存档）——深度学习可视化讲解

12.9 8 年前 vs 8 年后：写给"想补数学基础"的工程师

2016 年的建议：

“想补数学基础 → 读 Rosen 离散数学 → 读 CLRS 算法导论 → 在 LeetCode 上用数学思维”

2024 年的升级版建议：

“想补数学基础 → 读 Rosen 离散数学（仍是基础）→ 读 MML Book 入门 ML 数学 → 读《Lean 4 定理证明导论》入门形式化 → 在 LLM 应用上用数学思维（RAG / Embedding / 知识图谱）”

核心变化：8 年后离散数学没变，ML 数学 + 形式化验证是新基础。RAG 时代补数学，MML Book + 信息论 + 一点 Lean 4 比单纯啃 CLRS 更实用。

12.10 写在最后

2016 年我写"想补数学基础的工程师从 LeetCode 开始"。8 年后我想说：

LeetCode 仍然是好起点，但终点已经变了——
2016 年终点是"写出高效的算法"
2024 年终点是"用数学理解 LLM 的能力边界"

离散数学、线性代数、概率论、数理逻辑——这 4 门课是 8 年不变的"硬基础"；信息论、计算复杂性、形式化验证——这 3 门是 2024-2026 的"新基础"。

8 年前我担心"被数学卡住 5 分钟"，
8 年后我担心"被 AI 系统的数学基础卡住 5 小时"。

数学不会变老，只是换了个地方等我们回来。

参考资料（2024+ 补充）

• NIST PQC 标准（FIPS 203/204/205）
• Microsoft GraphRAG
• Lean 4 形式化证明
• Mathematical Structures in Deep Learning（综述）
• Mamba: Linear-Time Sequence Modeling with Selective State Spaces
• MML Book: Mathematics for Machine Learning
• DeepMind AlphaProof（IMO 2024）
• Lean Copilot: AI for Theorem Proving
• FlashAttention 2 论文